数值分析第讲矩阵的三角分解法.ppt
数值分析第讲矩阵的三角分解法现在学习的是第1页，共30页第四讲矩阵的三角分解法第二章 线性方程组的解法现在学习的是第2页，共30页In Scientific ComputingLarge Linear SystemsAx=bas sub-problems/as intermediate stepsGauss-Seidel methodJacobi methodSOR methodConjugate Gradient methodfor symmetric systemsGaussian eliminationLU factorizationCholesky factorizationGMRESGCRBi-CGCGSBi-CGSTABBi-CGSTAB2GPBi-CGBi-CGSTAB(L)现在学习的是第3页，共30页回顾高斯消去法回顾高斯消去法Gauss消元法的第k步：从矩阵理论来看，相当于左乘矩阵指标为k的初等下三角阵现在学习的是第4页，共30页因此，整个Gauss消元法相当于左乘了一个单位下三角阵所以有L为单位下三角阵，U为上三角阵现在学习的是第5页，共30页矩阵的直接三角分解(LU分解)对解线性方程组有什么帮助？三角方程组，易于求解现在学习的是第6页，共30页1、Doolittle分解分解L为单位下三角，U为上三角比较第1行：比较第1列：现在学习的是第7页，共30页比较第2行：比较第2列：现在学习的是第8页，共30页比较第k行：比较第k列：K-1次K-11次现在学习的是第9页，共30页分解过程完毕，加上两次反代过程总运算量为：现在学习的是第10页，共30页存储在矩阵的原来位置，且不影响计算现在学习的是第11页，共30页现在学习的是第12页，共30页L为下三角，U为单位上三角现在学习的是第13页，共30页两次反代过程比较第k列：比较第k行：现在学习的是第14页，共30页现在学习的是第15页，共30页定理定理2.4 若矩阵若矩阵A非奇异，则存在置换矩阵非奇异，则存在置换矩阵Q，使得使得QA可以作可以作Doolittle分解分解 QA=LU其中其中L是单位下三角矩阵，是单位下三角矩阵，U是上三角矩阵。是上三角矩阵。现在学习的是第16页，共30页选主元选主元直接三角分解法直接三角分解法当需选主元时，PA=LU.设第r-1步已完成,就有现在学习的是第17页，共30页现在学习的是第18页，共30页选主元三角分解算法选主元三角分解算法：现在学习的是第19页，共30页求解求解Ly=PbLy=Pb及及Ux=yUx=y的算法的算法：现在学习的是第20页，共30页现在学习的是第21页，共30页现在学习的是第22页，共30页三对角阵的追赶法三对角阵的追赶法（A的前的前n-1个顺序主子式非零）个顺序主子式非零）在数值求解常微分方程边值问题、热传导方程和建立三次样条函数时，都会要解三对角方程组：AX=bAX=b现在学习的是第23页，共30页所以，有计算过程如下：说明说明:稳定性（对角占优）；运算量5n-4次乘除法；存贮（一维数组）.现在学习的是第24页，共30页平方根法平方根法应用有限元法解结构力学问题时，最后归结为求解线性代数方程组，系数矩阵往往对称正定。平方根法是一种对称正定矩阵的三角分解法，广泛用于求解系数矩阵为对称正定的线性代数方程组。设A为对称矩阵,且顺序主子式不为零，则现在学习的是第25页，共30页若A为对称正定矩阵,则现在学习的是第26页，共30页现在学习的是第27页，共30页解AX=b的平方根法平方根法:称为平方根法，因为带了开方运算，因此不常用现在学习的是第28页，共30页Cramer ruleGauss eliminationLU factorizationGauss-Jordan eliminationSquare root/improved square root追赶法(n+1)!n3/3n3/3n3/2n3/65n-4Row/column/complete PivotingOnly eliminating elements in a column below the diagonal oneNo pivotingDirectly factorization column pivotingEliminating elements in a row except for the diagonal elementA symmetric and positive definiteNo pivotingA三对角，弱对角占优Summary现在学习的是第29页，共30页直接法内容总结直接法内容总结1 1：用：用：用：用LULU分解（分解（分解（分解（DoolittleDoolittle）求解线性代数方程组等价于顺序）求解线性代数方程组等价于顺序）求解线性代数方程组等价于顺序）求解线性代数方程组等价于顺序Gauss Gauss 消消消消元法：元法：元法：元法：AxAxb b LUx LUxb b Ux Uxy y，LyLyb b；2 2：用选主元：用选主元：用选主元：用选主元LULU分解（分解（分解（分解（DoolittleDoolittle）求解线性代数方程组等价于选列主元）求解线性代数方程组等价于选列主元）求解线性代数方程组等价于选列主元）求解线性代数方程组等价于选列主元GaussGauss消元法：消元法：消元法：消元法：AxAxb b LUx LUxQb Qb Ux Uxy y，LyLyQbQb；3 3：对上半带宽为：对上半带宽为：对上半带宽为：对上半带宽为s s、下半带宽为、下半带宽为、下半带宽为、下半带宽为r r的带状矩阵作的带状矩阵作的带状矩阵作的带状矩阵作LULU分解，那么分解，那么分解，那么分解，那么L L为下半为下半为下半为下半带宽为带宽为带宽为带宽为r r的下三角矩阵，的下三角矩阵，的下三角矩阵，的下三角矩阵，U U为上半带宽为为上半带宽为为上半带宽为为上半带宽为s s的上三角矩阵的上三角矩阵的上三角矩阵的上三角矩阵；现在学习的是第30页，共30页
