病态线性方程组

1、数值分析数值分析朱立永朱立永北京航空航天大学 数学与系统科学学院Email: numerical_Password:beihang答疑时间：星期三下午2:005:00答疑地点：主216数值分析数值分析第四讲病态线性方程组求解第二章 线性方程组的解法数值分析数值分析In Scientific ComputingLarge Linear SystemsAx=bas sub-problems/as intermediate stepsGauss-Seidel methodJacobi methodSOR methodConjugate Gradient methodfor symmetric sys

2、temsGaussian eliminationLU factorizationCholesky factorizationGMRESGCRBi-CGCGSBi-CGSTABBi-CGSTAB2GPBi-CGBi-CGSTAB(L)数值分析数值分析perturbation1122238123.000 018.000 022xxxx 11222388.522.999998.000033xxxxperturbationIts funny that such small perturbations in the coefficients lead to so big change in the so

3、lution!数值算例数值算例数值分析数值分析由实际问题建立起来的线性方程组Ax=b本身存在模型误差和观测误差，或者是由计算得到的，存在舍入误差等。总之，A,b都会有一定扰动A, b, 因此实际处理的是A+ A或b+ b ，我们需要分析A或b的扰动对解的影响。数值分析数值分析bbxxA)(bAx1|1bAx|1bbAAxxbAx 数值分析数值分析bxxAA)(|1|11AAAAAAAAxx数值分析数值分析bbxxAA)()|(|1|11AAbbAAAAAAxx解的相对误差A的相对误差b的相对误差当方程组的系数矩阵A或右端项b受到扰动A, b时，引起的解的相对误差完全由AA-1来决定，它刻画了方

4、程组的解对原始数据的敏感程度。数值分析数值分析：对非奇异矩阵：对非奇异矩阵A，称乘积，称乘积|A| |A-1|为矩阵为矩阵A的条件数，的条件数，记为记为 cond（A） |A| |A-1|数值分析数值分析|)(1AAAcond1111|)(AAAcond2122|)(AAAcond数值分析数值分析例：例：Hilbert 阵阵1211111131211211nnnnnnHcond (H2) = 27cond (H3) 748cond (H6) = 2.9 106注：注：现在用现在用MatlabMatlab数学软件可以很方便数学软件可以很方便求矩阵的条件数求矩阵的条件数! !数值分析数值分析数值分

5、析数值分析：对线性方程组：对线性方程组Axb，若，若cond(A)相对很大，则称相对很大，则称Axb是病态的线性方程组；若是病态的线性方程组；若cond(A)相对很小，则称相对很小，则称Axb是良态的线性方程组。是良态的线性方程组。一个病态线性方程组的例子（见书上）一个病态线性方程组的例子（见书上）对于严重的病态线性方程组，即使原始数据对于严重的病态线性方程组，即使原始数据A和和b都没有都没有误差，但如果在求解过程中有舍入误差，所得到的解也误差，但如果在求解过程中有舍入误差，所得到的解也会有很大的相对误差。会有很大的相对误差。数值分析数值分析注：注：一般判断矩阵是否病态，并不计算一般判断矩阵是

6、否病态，并不计算A 1，而由经验得出。，而由经验得出。 行列式很大或很小（如某些行、列行列式很大或很小（如某些行、列近似相关）；近似相关）； 元素间相差大数量级，且无规则；元素间相差大数量级，且无规则； 主元消去过程中出现小主元；主元消去过程中出现小主元； 特征值相差大数量级。特征值相差大数量级。数值分析数值分析数值分析数值分析1. 求解求解Axb，得到，得到x的近似解的近似解x1；2. 校正校正x1，令，令r1bAx1，解，解A x1 r1；3. x2x1 x1 ；4. 令令r2bAx2，解，解A x2 r2；5. x3x2 x2 ；6. 。7. 令令rkbAxk，解，解A xk rk；8. Xk1xk xk ；。；。数值分析数值分析预条件技术 80年代提出，纯代数观点 M 近似 A, 求解(左预条件) M y = c 易解 相当于化学反应中寻找高效、廉价的催化剂高效、廉价的催化剂，能极大地提高迭代方法的速度。11M AxM b1()( )MAA数值分析数值分析预条件技术(续) 代数预条件技术代数预条件技术 ILU、SPAI、SOR、多项式 几何预条件技术几何预条件技术 某方向压缩粗化、网格均匀化、区域规则化近似 分析预条件技术分析预条件技术变系数常数化、Green函数稀疏近似、强化椭圆型 物