LU分解法的与特殊方程组的解法.ppt

《LU分解法的与特殊方程组的解法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、LU分解法的与特殊方程组的解法假定我们能把矩阵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分解法的基本思想内容:LU分解.关键词:1.LU分解:将系数矩阵A转变成等价两个矩阵L和U的乘积,其中L和U分别是下三角和上三角矩阵,而且要求U的对角元素都是1.2.紧凑格式:由于可以把L和U两个矩阵压缩到一个数组中,而且还可以存储在原来的系数矩阵A的数组中.这种LU

2、分解常被称为紧凑格式.由LU=A及对L和U的要求可以得到分解的计算公式．根据下式(Doolittle分解)：1l211l31l321………ln1ln2…lnn-11u11u12u13…u1nu22u23…u2n…un-1nu(n-1)nunn=…………aannLUn1an3…a11a12a13…a1na21a22a23…a2na31a32a33…a3nan2A………第j个分量第i个分量根据矩阵乘法及相等的定义,有得公式u1j=a1jj=1,2,…,nli1=ai1/u11i=2,3,…,n在计算机程序中常常用这种方法解线性代数方程组。它的优点是存储量很省。L和U中的三角零元素都不必存储

3、，就是U的对角元素也因为都是1没有必要再记录在程序中，这样只用一个n阶方阵就可以把L和U贮存起来。即：下三角（包括对角元）存储L各元素而上三角存储U的元素。再考察公式S会发现A中任一元素aij只在计算lij（j<=i）和uij（j>i)中用到一次以后就不再出现了，因而完全可以利用原始数组A的单元，一个个逐次贮存L或U中的相应元素，即：a11a12a13…a1nu11u12u13…u1na21a22a23…a2nl21u22u23…u2na31a32a33…a3nl31l32u33…u3nan1an2an3…annln1ln2ln3…unn………...…………......(1)(3)(5

4、)(2n-1)(2)(4)(6)(2n)采用LU分解有如下特点：（1）LU分解与右端向量无关。先分解，后回代。一般说来，分解的运算次数正比于n回代求解正比与n。求遇到多次回代时，分解的工作不必重新做。这样节省计算时间。（2）分解按步进行，前边分解得到的信息为后边所用。（3）[A]阵的存储空间可利用，节省存储。32特殊方程组的解法1.追赶法2.LDLT分解法1.追赶法追赶法与稀疏线性方程组追赶法仍然保持LU分解特性,它是一种特殊的LU分解。充分利用了系数矩阵的特点，而且使之分解更简单,得到对三对角线性方程组的快速解法。因三对角矩阵的非零元素呈“带状”，我们也因此将它叫做带状矩阵。三对角

5、线性方程组：设有方程组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的对角线元素uii0,(i=1,2,,n),将矩阵U

6、的每行依此提出uii2.LDLT分解法由A=AT，得由分解的唯一性有，即，于是可得下面的结论。定理3：若对称矩阵A各阶顺序主子式不为零时,则A可以唯一分解为A=LDLT，这里LT为L的转置矩阵。当A有LDLT分解时，利用矩阵运算法则及相等原理易得计算ljk及dk的公式为k=1,2,,n;j=k+1,k+2,,n为减少乘法次数，引入辅助量ujk=ljkdk,则上面公式可写成平方根法设A为正定矩阵，则它的各阶顺序主子式均为正。由前面的定理知，A必有唯一的LDLT分解式A=LDLT在解对称正定线性方程组时，系数矩阵A的LDLT分解中D又可分解为D=D1/2D1/2，这里D1/2也是对角矩

7、阵