LU分解教学讲解课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,作者：赵俭平,LU,分解法的与特殊方程组的解法,假定我们能把矩阵,A,写成下列两个矩阵相乘的形式：,A=LU,其中,L,为下三角矩阵，,U,为上三角矩阵。这样我们可以把,线性方程组,Ax=b,写成,Ax=,（,LU)x=L(U x)=b,Ly=b,令,U x=y,则原线性方程组,Ax=b,Ux=y,于是可,首先求解向量,y,使,Ly=b,然后求解,Ux=y,从而求解线性方程组,Ax=b,的目的,.,LU,分解法的基本思想,内容,:LU,分解.,关键词:1.,LU,分解:将系数矩阵,A,转变成等价两个矩阵,L,和,U,的乘积,其中,L,和,U,分别是下三角和上三角矩阵,而且要求,U,的对角元素都是1.2.紧凑格式:由于可以把,L,和,U,两个矩阵压缩到一个数组中,而且还可以存储在原来的系数矩阵,A,的数组中.这种,LU,分解常被称为紧凑格式.,由,LU=A,及对,L,和,U,的要求可以得到分解的计算公式根据下式,(Doolittle,分解,),：,1,l,21,1,l,31,l,32,1,l,n1,l,n2,l,nn-1,1,u,11,u,12,u,13,u,1n,u,22,u,23,u,2n,u,n-1n,u,(n-1)n,u,nn,=,a,a,nn,L U,n1,a,n3,a,11,a,12,a,13,a,1n,a,21,a,22,a,23,a,2n,a,31,a,32,a,33,a,3n,a,n2,A,第,j,个分量,第,i,个分量,根据矩阵乘法及相等的定义,有,得公式,u,1j,=a,1j j=1,2,n,l,i1,=a,i1,/u,11 i=2,3,n,在计算机程序中常常用这种方法解线性代数方程组。,它的优点是存储量很省。,L,和,U,中的三角零元素都不,必存储，就是,U,的对角元素也因为都是,1,没有必要再,记录在程序中，这样只用一个,n,阶方阵就可以把,L,和,U,贮存起来。即：下三角（包括对角元）存储,L,各元,素 而上三角存储,U,的元素。,再考察公式,S,会发现,A,中任一元素,aij,只在计算,lij,（,ji),中用到一次以后就不再出现了，因而完全,可以利用原始数组,A,的单元，一个个逐次贮存,L,或,U,中,的相应元素，即：,a,11,a,12,a,13,a,1n,u,11,u,12,u,13,u,1n,a,21,a,22,a,23,a,2n,l,21,u,22,u,23,u,2n,a,31,a,32,a,33,a,3n,l,31,l,32,u,33,u,3n,a,n1,a,n2,a,n3,a,nn,l,n1,l,n2,l,n3,u,nn,.,.,.,(1),(3),(5),(2n-1),(2)(4)(6)(2n),采用,LU,分解有如下特点：,（,1,）,LU,分解与右端向量无关。先分解，后,回代。一般说来，分解的运算次数正比于,n,回代求解正比与,n,。求 遇到多次回代时，分,解的工作不必重新做。这样节省计算时间。,（,2,）分解按步进行，前边分解得到的信息,为后边所用。,（,3,）,A,阵的存储空间可利用，节省存储。,3,2,特殊方程组的解法,1.,追赶法,2.LDLT,分解法,1.,追赶法,追赶法与稀疏线性方程组,追赶法仍然保持,LU,分解特性,它是一种特殊的,LU,分解。充分利用了系数矩阵的特点，而且使之分解更简单,得到对三对角线性方程组的快速解法。,因三对角矩阵的非零元素呈“带状”，我们也因此将它叫做带状矩阵。,三对角线性方程组：,设有方程组,Ax=d,，其中,A,为三对角矩阵。,假设系数矩阵,A,满足条件：,对,A,作,Crout,分解形式为：,第,i,个分量,第,j,个分量,追赶法计算公式,定理,如果上带宽为,q,，下带宽为,p,的,n,阶带状矩阵,A,有,Doolittle,分解。,A=LU,，则,L,是下带宽为,p,的单位下三角矩阵，,U,是上带宽为,q,的上三角矩阵。,下面举实例用追赶法来解三对角方程组。,实际问题中，当求解方程组的系数矩阵是对称矩阵时，则用下面介绍的,LDLT,分解法可以简化程序设计并减少计算量,.,从定理可知,当矩阵,A,的各阶顺序主子式不为零时,A,有唯一的,Doolittle,分解,A=LU.,此时,当然有,所以矩阵,U,的对角线元素,u,ii,0,(i=1,2,n),将矩阵,U,的每行依此提出,u,ii,2.LDLT,分解法,由,A=A,T,，得,由分解的唯一性有，即，于是可得下面的结论。,定理,3,：若对称矩阵,A,各阶顺序主子式不为零时,则,A,可以唯一分解为,A=LDL,T,，这里,L,T,为,L,的转置矩阵。,当,A,有,LDL,T,分解时，利用矩阵运算法则及相等原理易得计算,l,jk,及,d,k,的公式为,k=1,2,n;j=k+1,k+2,n,为减少乘法次数，引入辅助量,u,jk,=l,jk,d,k,则上面公式可写成,平方根法,设,A,为正定矩阵，则它的各阶顺序主子式均为正。由前面的定理知，,A,必有唯一的,LDL,T,分解式,A=LDL,T,在解对称正定线性方程组时，系数矩阵,A,的,LDL,T,分解中,D,又可分解为,D=D,1/2,D,1/2,，这里,D,1/2,也是对角矩阵,