矩阵三角分解法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,一、直接法概述,直接法是将原方程组化为一个或若干个三角形,方程组的方法，共有若干种,对于线性方程组,其中,系数矩阵,未知量向量,1,根据,Cramer(,克莱姆,),法则,若,determinantal,行列式的记号,若用初等变换法求解,则对其增广矩阵作行初等变换,:,经过,n-1,次,2,同解,即,以上求解线性方程组的方法称为,Gauss,消去法,则,都是三角,形方程组,上述方法称为,直接三角形分解法,3,2 Matrix Factorization Doolittle,道立特分解法,/* Doolittle Factorization */,：,LU,分解的紧凑格式,/* compact form */,反复计算,很浪费哦,通过比较法直接导出,L,和,U,的计算公式。,思路,4,2 Matrix Factorization Doolittle,固定,i,:,对,j,=,i,i,+1, ,n,有,l,ii,= 1,a,固定,j,，对,i,=,j,j,+1, ,n,有,b,5,上述解线性方程组的方法称为,直接三角分解法的,Doolittle,法,例,1.,用,Doolittle,法解方程组,解,:,由,Doolittle,分解,6,Doolittle,法在计算机上实现是比较容易的,但如果按上述流程运算仍需要较大的存储空间,:,7,因此可按下列方法存储数据,:,8,直接三角分解的,Doolittle,法可以用以下过程表示,:,存储单元,(,位置,),9,紧凑格式的,Doolittle,法,10,例,2.,用紧凑格式的,Doolittle,法解方程组,(,例,1),解,:,11,所以,12,Matrix Factorization Choleski,平方根法,/* Choleskis Method */,：,对称,/* symmetric */,正定,/* positive definite */,矩阵的分解法,定义,一个矩阵,A,= (,a,ij,),n,n,称为,对称阵,，如果,a,ij,=,a,ji,。,定义,一个矩阵,A,称为,正定阵,，如果 对任意非零向量 都成立。,回顾：,对称正定阵的几个重要性质,A,1,亦对称正定，且,a,ii, 0,若不然，则,存在非零解，即,存在非零解。,对任意,存在,使得,即 。,其中,第,i,位,A,的顺序主子阵,/*,leading principal submatrices */,A,k,亦对,称正定,对称性显然。对任意 有,其中 。,A,的特征值,/*,eigen value */,i, 0,设对应特征值,的非零特征向量,为 ，则 。,A,的全部顺序主子式,det (,A,k,), 0,因为,13,一、对称正定矩阵的三角分解,(Cholesky,分解,),记为,14,Diagonal:,对角,15,因此,所以,综合以上分析,则有,16,定理,1. (Cholesky,分解,),且该分解式唯一,这种关于对称正定矩阵的分解称为,Cholesky,分解,17,二、对称正定线性方程组的解法,线性方程组,则线性方程组,(10),可化为两个三角形方程组,18,对称正定方程,组的,平方根法,19,例,1.,用平方根法解对称正定方程组,解,:,20,即,21,三、平方根法的数值稳定性,用平方根法求解对称正定方程组时不需选取主元,由,可知,因此,平方根法是数值稳定的,事实上,对称正定方程组也可以用顺序,Gauss,消去法求解,而不必加入选主元步骤,22,2 Matrix Factorization Tridiagonal System,追赶法解,三对角,方程组,/* Crout Reduction for Tridiagonal Linear System */,Step 1,:,对,A,作,Crout,分解,直接比较等式两边的元素，可得到计算公式。,Step 2,:,追,即解 ：,Step 3,:,赶,即解 ：,与,G.E.,类似，一旦,i,= 0,则算法中断，故并非任何,三对角阵都可以用此方法分解。,23,有一类方程组,在今后要学习的插值问题和边值问题中,有着重要的作用,即三对角线方程组,其形式为,:,其中,-(1),24,以下以,Crout,分解导出三对角线方程组的解法,设,25,例,1.,用追赶法解三对角线方程组,解,:,26,1,1,1,1,27,因此原线性方程组的解为,28,