病态线性方程组

数值分析朱立永北京航空航天大学数学与系统科学学院Email:[e-mail]:beihang答疑时间：星期三下午2:00－5:00答疑地点：主216数值分析第四讲病态线性方程组求解第二章线性方程组的解法数值分析InScientificComputing↓LargeLinearSystemsAx=bassub-problems/asintermediatestepsGauss-SeidelmethodJacobimethodSORmethodConjugateGradientmethodforsymmetricsystemsGaussianeliminationLUfactorizationCholeskyfactorizationGMRESGCRBi-CGCGSBi-CGSTABBi-CGSTAB2GPBi-CGBi-CGSTAB(L)数值分析perturbation1122238123.000018.000022xxxx11222388.522.999998.000033xxxxperturbationIt’sfunnythatsuchsmallperturbationsinthecoefficientsleadtosobigchangeinthesolution!数值算例提问：求解Ax＝b时，A和b的误差对x有何影响？数值分析由实际问题建立起来的线性方程组Ax=b本身存在模型误差和观测误差，或者是由计算得到的，存在舍入误差等。总之，A,b都会有一定扰动ΔA,Δb,因此实际处理的是A+ΔA或b+Δb，我们需要分析A或b的扰动对解的影响。数值分析矩阵的条件数与病态线性方程组提问：求解Ax＝b时，A和b的误差对x有何影响？1：A非奇异，设精确，b有误差Δb，导致解x有多大误差？bbxxA)(bAx1||||||||||||1bAx||||||||||||||||||||||||1bbAAxxbAx数值分析2：设b精确，A有误差ΔA，导致解x有多大误差？设A非奇异，||ΔA||||A-1||1bxxAA))((||||||||||||||||||||||||1||||||||||||||||11AAAAAAAAxx数值分析3：设b，A分别有误差Δb和ΔA，导致解x有多大误差？设A非奇异，||ΔA||||A-1||1bbxxAA))(()||||||||||||||||(||||||||||||||||1||||||||||||||||11AAbbAAAAAAxx解的相对误差A的相对误差b的相对误差当方程组的系数矩阵A或右端项b受到扰动ΔA,Δb时，引起的解的相对误差完全由A·A-1来决定，它刻画了方程组的解对原始数据的敏感程度。数值分析矩阵的条件数（Conditionnumber）定义：对非奇异矩阵A，称乘积||A||||A-1||为矩阵A的条件数，记为cond（A）＝||A||||A^-1||•||A||||A^-1||是我们遇到的第二个放大因子；•cond（A）的具体大小与||∙||有关，但相对大小一致；•cond（A）的大小本质取决于A，与解题的方法无关；•cond（A）＝∞，如果A是奇异的。数值分析常用的矩阵条件数||||||||)(1AAAcond1111||||||||)(AAAcond2122||||||||)(AAAcond数值分析例：Hilbert阵1211111131211211nnnnnnHcond(H2)=27cond(H3)748cond(H6)=2.9106注：现在用Matlab数学软件可以很方便求矩阵的条件数!数值分析矩阵条件数的一些性质1.cond（A）≥1；2.A非奇异，k≠0，则cond（kA）＝cond（A）；3.A非奇异对称矩阵，则cond（A）2＝|λ1/λn|；4.A是正交矩阵，则cond（A）2＝1；5.A可逆，R正交，则cond(RA)2＝cond(AR)2＝cond(A)2数值分析病态、良态线性方程组定义：对线性方程组Ax＝b，若cond(A)相对很大，则称Ax＝b是病态的线性方程组；若cond(A)相对很小，则称Ax＝b是良态的线性方程组。一个病态线性方程组的例子（见书上）对于严重的病态线性方程组，即使原始数据A和b都没有误差，但如果在求解过程中有舍入误差，所得到的解也会有很大的相对误差。数值分析什么样的线性方程组可能是病态的？注：一般判断矩阵是否病态，并不计算A1，而由经验得出。行列式很大或很小（如某些行、列近似相关）；元素间相差大数量级，且无规则；主元消去过程中出现小主元；特征值相差大数量级。数值分析缓和甚至解决线性方程组病态的手段1.采用高精度的算法（不是总有效）；2.通过行或列的平衡来降低矩阵的条件数（平衡法）；3.残差校正法；4.通过矩阵的预条件处理来降低矩阵的条件数。数值分析残差校正法步骤：1.求解Ax＝b，得到x的近似解x1；2.校正x1，令r1＝b－Ax1，解AΔx1＝r1；3.x2＝x1＋Δx1；4.令r2＝b－Ax2，解AΔx2＝r2；5.x3＝x2＋Δx2；6.。。。7.令rk＝b－Axk，解AΔxk＝rk；8.Xk＋1＝xk＋Δxk；。。。数值分析预条件技术•80年代提出，纯代数观点•M近似A,求解(左预条件)–My=c易解–•相当于化学反应中寻找高效、廉价的催化剂，能极大地提高迭代方法的速度。11MAxMb1()()MAA数值分析预条件技术(续)•代数预条件技术–ILU、SPAI、SOR、多项式•几何预条件技术–某方向压缩粗化、网格均匀化、区域规则化近似•分析预条件技术–变系数常数化、Green函数稀疏近似、强化椭圆型•物理预条件–量纲平衡、物理参数逼近、状态方程近似、某些物理项简化、算子分裂•高级预条件–MG、DDM、快速变换（FFT）、基底变换法数值分析作业•教材第46页习题11、12.数值分析