5.LU分解ppt课件

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