数值分析 -lec5--病态线性方程组的解法.ppt

1、朱立永,北京航空航天大学 数学与系统科学学院,数值分析,Email: numerical_ Password:beihang 答疑时间：星期四下午2:305:30 答疑地点：主216,第四讲病态线性方程组求解,第二章 线性方程组的解法,In Scientific Computing Large Linear Systems Ax=b as sub-problems/ as intermediate steps,Conjugate Gradient method for symmetric systems,perturbation,perturbation,Its funny that such

2、 small perturbations in the coefficients lead to so big change in the solution!,数值算例,提问：求解Axb时，A和b的误差对x有何影响？,由实际问题建立起来的线性方程组Ax=b本身存在模型误差和观测误差，或者是由计算得到的，存在舍入误差等。总之，A,b都会有一定扰动A, b, 因此实际处理的是A+ A或b+ b ，我们需要分析A或b的扰动对解的影响。,矩阵的条件数与病态线性方程组,提问：求解Axb时，A和b的误差对x有何影响？,1：A非奇异，设精确，b有误差b，导致解x有多大误差？,2：设b精确，A有误差A，导致解

3、x有多大误差？设A非奇异，|A| |A-1|1,3：设b，A分别有误差b和A，导致解x有多大误差？设A非奇异，|A| |A-1|1,解的相对误差,A的相对误差,b的相对误差,矩阵的条件数（Condition number ）,定义：对非奇异矩阵A，称乘积|A| |A-1|为矩阵A的条件数，记为 cond（A） |A| |A-1|,|A| |A-1|是我们遇到的第二个放大因子； cond（A）的具体大小与|有关，但相对大小一致； cond（A）的大小本质取决于A，与解题的方法无关； cond（A），如果A是奇异的。,常用的矩阵条件数,例：Hilbert 阵,注：现在用Matlab数学软件可以很方

4、便求矩阵的条件数!,矩阵条件数的一些性质,cond（A）1； A非奇异，k0，则cond（kA）cond（A）； A非奇异对称矩阵，则cond（A）2|1/n|； A是正交矩阵，则cond（A）21； A可逆，R正交，则cond(RA)2cond(AR)2cond(A)2,病态、良态线性方程组,定义：对线性方程组Axb，若cond(A)相对很大，则称Axb是病态的线性方程组；若cond(A)相对很小，则称Axb是良态的线性方程组。,一个病态线性方程组的例子（见书上P31例5）,对于严重的病态线性方程组，即使原始数据A和b都没有误差，但如果在求解过程中有舍入误差，所得到的解也会有很大的相对误差。

5、,什么样的线性方程组可能是病态的？,注：一般判断矩阵是否病态，并不计算A1，而由经验得出。 行列式很大或很小（如某些行、列近似相关）； 元素间相差大数量级，且无规则； 主元消去过程中出现小主元； 特征值相差大数量级。,缓和甚至解决线性方程组病态的手段,采用高精度的算法（不是总有效）； 通过行或列的平衡来降低矩阵的条件数（平衡法）； 残差校正法； 通过矩阵的预条件处理来降低矩阵的条件数。,残差校正法步骤：,求解Axb，得到x的近似解x1； 校正x1，令r1bAx1，解A x1 r1； x2x1 x1 ； 令r2bAx2，解A x2 r2； x3x2 x2 ； 。 令rkbAxk，解A xk rk； Xk1xk xk ；。,预条件技术,80年代提出，纯代数观点 M 近似 A, 求解 (左预条件) M y = c 易解 相当于化学反应中寻找高效、廉价的催化剂，能极大地提高迭代方法的速度。,预条件技术(续),代数预条件技术 ILU、SPAI、SOR、多项式 几何预条件技术 某方向压缩粗化、网格均匀化、区域规则化近似 分析预条件技术 变系数常数化、Green函数稀疏近似、强化椭