数值分析第讲矩阵的三角分解法.ppt

CramerruleGausseliminationLUfactorizationGauss-JordaneliminationSquareroot/improvedsquareroot追赶法(n+1)!n3/3n3/3n3/2n3/65n-4Row/column/completePivotingOnlyeliminatingelementsinacolumnbelowthediagonaloneNopivotingDirectlyfactorizationcolumnpivotingEliminatingelementsinarowexceptforthediagonalelementAsymmetricandpositivedefiniteNopivotingA三对角，弱对角占优Summary第29页,共30页，星期六，2024年，5月直接法内容总结1：用LU分解（Doolittle）求解线性代数方程组等价于顺序Gauss消元法：Ax＝b?LUx＝b?Ux＝y，Ly＝b；2：用选主元LU分解（Doolittle）求解线性代数方程组等价于选列主元Gauss消元法：Ax＝b?LUx＝Qb?Ux＝y，Ly＝Qb；3：对上半带宽为s、下半带宽为r的带状矩阵作LU分解，那么L为下半带宽为r的下三角矩阵，U为上半带宽为s的上三角矩阵；第30页,共30页，星期六，2024年，5月数值分析数值分析数值分析数值分析数值分析第讲矩阵的三角分解法第四讲

矩阵的三角分解法第二章线性方程组的解法第2页,共30页，星期六，2024年，5月InScientificComputing↓LargeLinearSystemsAx=bassub-problems/asintermediatestepsGauss-SeidelmethodJacobimethodSORmethodConjugateGradientmethodforsymmetricsystemsGaussianeliminationLUfactorizationCholeskyfactorizationGMRESGCRBi-CGCGSBi-CGSTABBi-CGSTAB2GPBi-CGBi-CGSTAB(L)第3页,共30页，星期六，2024年，5月回顾高斯消去法Gauss消元法的第k步：从矩阵理论来看，相当于左乘矩阵指标为k的初等下三角阵第4页,共30页，星期六，2024年，5月因此，整个Gauss消元法相当于左乘了一个单位下三角阵所以有L为单位下三角阵，U为上三角阵第5页,共30页，星期六，2024年，5月矩阵的直接三角分解(LU分解)对解线性方程组有什么帮助？三角方程组，易于求解第6页,共30页，星期六，2024年，5月1、Doolittle分解L为单位下三角，U为上三角比较第1行：比较第1列：第7页,共30页，星期六，2024年，5月比较第2行：比较第2列：第8页,共30页，星期六，2024年，5月比较第k行：比较第k列：K-1次K-1＋1次第9页,共30页，星期六，2024年，5月分解过程完毕，加上两次反代过程总运算量为：第10页,共30页，星期六，2024年，5月存储在矩阵的原来位置，且不影响计算第11页,共30页，星期六，2024年，5月第12页,共30页，星期六，2024年，5月L为下三角，U为单位上三角第13页,共30页，星期六，2024年，5月两次反代过程比较第k列：比较第k行：第14页,共30页，星期六，2024年，5月第15页,共30页，星期六，2024年，5月定理2.4若矩阵A非奇异，则存在置换矩阵Q，使得QA可以作Doolittle分解QA=LU其中L是单位下三角矩阵，U是上三角矩阵。第16页,共30页，星期六，2024年，5月选主元直接三角分解法当需选主元时，PA=LU.设第r-1步已完成,就有第17页,共30页，星期六，2024年，5月第18页,共30页，星期六，2024年，5月选主元三角分解算法：第19页,共30页，星期六，2024年，5月求解Ly=Pb及Ux=y的算法：第20页,共30页，星期六，2024年，5月第21页,共30页，星期六，2024年，5月第22页,共30页，星期六，2024年，5月三对角阵的追赶法（A的前n-1个顺序主子式非