病态线性方程组.ppt

《病态线性方程组.ppt》由会员分享，可在线阅读，更多相关《病态线性方程组.ppt（20页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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 syst

2、emsGaussian eliminationLU factorizationCholesky factorizationGMRESGCRBi-CGCGSBi-CGSTABBi-CGSTAB2GPBi-CGBi-CGSTAB(L)数值分析数值分析perturbationperturbationIts funny that such small perturbations in the coefficients lead to so big change in the solution!数值算例数值算例提问：求解提问：求解提问：求解提问：求解AxAxb b时，时，时，时，A A和和和和b b的误

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

4、异，设精确，b b有误差有误差有误差有误差 b b，导致解，导致解，导致解，导致解x x有多大有多大有多大有多大误差？误差？误差？误差？数值分析数值分析2 2：设：设：设：设b b精确，精确，精确，精确，A A有误差有误差有误差有误差 A A，导致解，导致解，导致解，导致解x x有多大误差？有多大误差？有多大误差？有多大误差？设设设设A A非奇异，非奇异，非奇异，非奇异，|A|AA|A-1-1|11数值分析数值分析3 3：设：设：设：设b b，A A分别有误差分别有误差分别有误差分别有误差 b b和和和和 A A，导致解，导致解，导致解，导致解x x有多大误有多大误有多大误有多大误差？设差？设

5、差？设差？设A A非奇异，非奇异，非奇异，非奇异，|A|AA|A-1-1|11解的相对误差A的相对误差b的相对误差当方程组的系数矩阵A或右端项b受到扰动A,b时，引起的解的相对误差完全由AA-1来决定，它刻画了方程组的解对原始数据的敏感程度。数值分析数值分析矩阵的条件数（矩阵的条件数（Condition number）定义定义定义定义：对非奇异矩阵：对非奇异矩阵A，称乘积，称乘积|A|A-1|为矩阵为矩阵A的条件数，的条件数，记为记为 cond（A）|A|A-1|A|A-1|A|A-1|是我们遇到的第二个放大因子；是我们遇到的第二个放大因子；是我们遇到的第二个放大因子；是我们遇到的第二个放大因

6、子；condcond（A A）的具体大小与）的具体大小与）的具体大小与）的具体大小与|有关，但相对大小一致；有关，但相对大小一致；有关，但相对大小一致；有关，但相对大小一致；condcond（A A）的大小本质取决于）的大小本质取决于）的大小本质取决于）的大小本质取决于A A，与解题的方法无关；，与解题的方法无关；，与解题的方法无关；，与解题的方法无关；condcond（A A），如果，如果，如果，如果A A是奇异的。是奇异的。是奇异的。是奇异的。数值分析数值分析常用的矩阵条件数常用的矩阵条件数数值分析数值分析例：例：Hilbert 阵阵cond(H2)=27cond(H3)748cond(H

7、6)=2.9 106注：注：现在用现在用MatlabMatlab数学软件可以很方便数学软件可以很方便求矩阵的条件数求矩阵的条件数!数值分析数值分析矩阵条件数的一些性质矩阵条件数的一些性质1.1.condcond（A A）1 1；2.2.A A非奇异，非奇异，非奇异，非奇异，k k00，则则condcond（kAkA）condcond（A A）；）；）；）；3.3.A A非奇异非奇异非奇异非奇异对称对称对称对称矩阵，则矩阵，则矩阵，则矩阵，则condcond（A A）2 2|1 1/n n|；4.4.A A是是是是正交矩阵，则正交矩阵，则正交矩阵，则正交矩阵，则condcond（A A）2 21

8、 1；5.5.A A可逆，可逆，可逆，可逆，R R正交，正交，正交，正交，则则cond(RA)cond(RA)2 2cond(AR)cond(AR)2 2cond(A)cond(A)2 2数值分析数值分析病态、良态线性方程组病态、良态线性方程组定义定义定义定义：对线性方程组：对线性方程组Axb，若，若cond(A)相对很大，则称相对很大，则称Axb是病态的线性方程组；若是病态的线性方程组；若cond(A)相对很小，则称相对很小，则称Axb是良态的线性方程组。是良态的线性方程组。一个病态线性方程组的例子（见书上）一个病态线性方程组的例子（见书上）对于严重的病态线性方程组，即使原始数据对于严重的病

9、态线性方程组，即使原始数据A和和b都没有都没有误差，但如果在求解过程中有舍入误差，所得到的解也误差，但如果在求解过程中有舍入误差，所得到的解也会有很大的相对误差。会有很大的相对误差。数值分析数值分析什么样的线性方程组可能是病态的？什么样的线性方程组可能是病态的？注：注：一般判断矩阵是否病态，并不计算一般判断矩阵是否病态，并不计算A 1，而由经验得出。而由经验得出。行列式很大或很小（如某些行、列行列式很大或很小（如某些行、列近似相关）；近似相关）；元素间相差大数量级，且无规则；元素间相差大数量级，且无规则；主元消去过程中出现小主元；主元消去过程中出现小主元；特征值相差大数量级。特征值相差大数量级

10、。数值分析数值分析缓和甚至解决线性方程组病态的手段缓和甚至解决线性方程组病态的手段1.1.采用高精度的算法（不是总有效）；采用高精度的算法（不是总有效）；采用高精度的算法（不是总有效）；采用高精度的算法（不是总有效）；2.2.通过行或列的平衡来降低矩阵的条件数（平衡法）；通过行或列的平衡来降低矩阵的条件数（平衡法）；通过行或列的平衡来降低矩阵的条件数（平衡法）；通过行或列的平衡来降低矩阵的条件数（平衡法）；3.3.残差校正法；残差校正法；残差校正法；残差校正法；4.4.通过矩阵的预条件处理来降低矩阵的条件数。通过矩阵的预条件处理来降低矩阵的条件数。通过矩阵的预条件处理来降低矩阵的条件数。通过矩

11、阵的预条件处理来降低矩阵的条件数。数值分析数值分析残差校正法步骤：残差校正法步骤：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 易解 相当于化学反应中寻找高效、廉价的催化剂高效、廉价的催化剂，能极大地提高迭代方法的速度。数值分析数值分析预条件技术(续)代数预条件技术代数预条件技术ILU、SPAI、SOR、多项式几何预条件技术几何预条件技术某方向压缩粗化、网格均匀化、区域规则化近似分析预条件技术分析预条件技术变系数常数化、Green函数稀疏近似、强化椭圆型物理预条件物理预条件量纲平衡、物理参数逼近、状态方程近似、某些物理项简化、算子分裂高级预条件高级预条件MG、DDM、快速变换（FFT）、基底变换法数值分析数值分析作业教材第46页习题11、12.数值分析数值分析