南大数值分析课件§2.1 三角分解法

《南大数值分析课件§2.1 三角分解法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§2三角分解法/*MatrixFactorization*/高斯消元法的矩阵形式/*MatrixFormofG.E.*/：Step1:记L1=，则Stepn1:其中Lk=§2MatrixFactorization–MatrixFormofG.E.记为L单位下三角阵/*unitarylower-triangularmatrix*/记U=A的LU分解/*LUfactorization*/Heyhasn’tGEgivenmeenoughheadache?WhydoIhavetoknowitsmatrixform

2、??!WhenyouhavetosolvethesystemfordifferentwithafixedA.Couldyoubemorespecific,please?FactorizeAfirst,thenforeveryyouonlyhavetosolvetwosimpletriangularsystemsand.§2MatrixFactorization–MatrixFormofG.E.定理若A的所有顺序主子式/*determinantofleadingprincipalsubmatrices*/均不为

3、0，则A的LU分解唯一（其中L为单位下三角阵）。证明：由§1中定理可知，LU分解存在。下面证明唯一性。若不唯一，则可设A=L1U1=L2U2，推出Upper-triangularLower-triangularWithdiagonalentries1注：L为一般下三角阵而U为单位上三角阵的分解称为Crout分解。实际上只要考虑A*的LU分解，即，则即是A的Crout分解。§2MatrixFactorization–Doolittle道立特分解法/*DoolittleFactorization*/：——LU

4、分解的紧凑格式/*compactform*/反复计算,很浪费哦……通过比较法直接导出L和U的计算公式。思路§2MatrixFactorization–Doolittle固定i:对j=i,i+1,…,n有lii=1a将i，j对换，对j=i,i+1,…,n有bAlgorithm:DoolittleFactorizationStep1:u1j=a1j;lj1=aj1/u11;(j=1,…,n)Step2:computeandfori=2,…,n1;Step3:ab一般采用列主元法增强稳定性。但注意也必须做相应的行

5、交换。§2MatrixFactorization–Choleski平方根法/*Choleski’sMethod*/：——对称/*symmetric*/正定/*positivedefinite*/矩阵的分解法定义一个矩阵A=(aij)nn称为对称阵，如果aij=aji。定义一个矩阵A称为正定阵，如果对任意非零向量都成立。回顾：对称正定阵的几个重要性质A1亦对称正定，且aii>0若不然，则存在非零解，即存在非零解。对任意,存在,使得,即。其中第i位A的顺序主子阵/*leadingprincip

6、alsubmatrices*/Ak亦对称正定对称性显然。对任意有,其中。A的特征值/*eigenvalue*/i>0设对应特征值的非零特征向量为，则。A的全部顺序主子式det(Ak)>0因为§2MatrixFactorization–Choleski将对称正定阵A做LU分解U=uij=u11uij/uii111u22unn记为A对称即记D1/2=Whyisuii>0?Sincedet(Ak)>0则仍是下三角阵定理设矩阵A对称正定，则存在非奇异下三角阵使得。若限定L对角元为正，则分解唯一。注：对于对称正

7、定阵A，从可知对任意ki有。即L的元素不会增大，误差可控，不需选主元。§2MatrixFactorization–CholeskiAlgorithm:Choleski’sMethodTofactorthesymmetricpositivedefinitennmatrixAintoLLT,whereLislowertriangular.Input:thedimensionn;entriesaijfor1i,jnofA.Output:theentrieslijfor1jiand1inofL.Ste

8、p1Set;Step2Forj=2,…,n,set;Step3Fori=2,…,n1,dosteps4and5Step4Set;Step5Forj=i+1,…,n,set;Step6Set;Step7Output(lijforj=1,…,iandi=1,…,n);STOP.因为A对称，所以只需存半个A，即其中运算量为O(n3/6)，比普通LU分解少一半，但有n次开方。用A=LDLT分解，可省开方时