《5.LU分解ppt课件》由会员分享，可在线阅读，更多相关《5.LU分解ppt课件（28页珍藏版）》请在金锄头文库上搜索。
1、LULU分解法的与特殊方程组的解法分解法的与特殊方程组的解法分解法的与特殊方程组的解法分解法的与特殊方程组的解法1假定我们能把矩阵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分解法的基本思想分解法的基本思想2n n内容内容内容内容:LU:LU分解分解分解分解. .n n关键词关键词关键词关键词: 1.: 1.LULU分解分解分解分
2、解 : :将系数矩阵将系数矩阵将系数矩阵将系数矩阵A A转变成转变成转变成转变成等价两个矩阵等价两个矩阵等价两个矩阵等价两个矩阵L L和和和和U U的乘积的乘积的乘积的乘积 , ,其中其中其中其中L L和和和和U U分别是下三角和上三角矩阵分别是下三角和上三角矩阵分别是下三角和上三角矩阵分别是下三角和上三角矩阵 , ,而且要求而且要求而且要求而且要求U U的对角元素都是的对角元素都是的对角元素都是的对角元素都是1. 2.1. 2.紧凑格式紧凑格式紧凑格式紧凑格式: :由于可以把由于可以把由于可以把由于可以把L L和和和和U U两个矩阵压缩到一个数组中两个矩阵压缩到一个数组中两个矩阵压缩到一个数
3、组中两个矩阵压缩到一个数组中, ,而且还可以存储在原来的系数而且还可以存储在原来的系数而且还可以存储在原来的系数而且还可以存储在原来的系数矩阵矩阵矩阵矩阵A A的数组中的数组中的数组中的数组中. .这种这种这种这种LULU分解常被称为紧凑格式分解常被称为紧凑格式分解常被称为紧凑格式分解常被称为紧凑格式. .3n n由由由由LU=ALU=A及对及对及对及对L L和和和和U U的要求可以得到分解的计算公式根据下式的要求可以得到分解的计算公式根据下式的要求可以得到分解的计算公式根据下式的要求可以得到分解的计算公式根据下式(Doolittle(Doolittle分分分分解解解解) )： 1 l21 1
4、 l31 l32 1 ln1 ln2 lnn-1 1 u11 u12 u13 u1n u22 u23 u2n un-1n u(n-1)n unn=aannL Un1an3 a11 a12 a13 a1na21 a22 a23 a2na31 a32 a33 a3n an2 A4第j个分量第i个分量5根据矩阵乘法及相等的定义根据矩阵乘法及相等的定义,有有 得公式 u1j=a1j j=1,2,n li1=ai1 / u11 i=2,3,n67在计算机程序中常常用这种方法解线性代数方程组。在计算机程序中常常用这种方法解线性代数方程组。它的优点是存储量很省。它的优点是存储量很省。L和和U中的三角零元素都
5、不中的三角零元素都不必存储，就是必存储，就是U的对角元素也因为都是的对角元素也因为都是1没有必要再没有必要再记录在程序中，这样只用一个记录在程序中，这样只用一个n阶方阵就可以把阶方阵就可以把L和和U贮存起来。即：下三角（包括对角元）存储贮存起来。即：下三角（包括对角元）存储L各元各元素素 而上三角存储而上三角存储U的元素。的元素。再考察公式再考察公式S会发现会发现A中任一元素中任一元素aij只在计算只在计算lij（ji)中用到一次以后就不再出现了，因而完全中用到一次以后就不再出现了，因而完全可以利用原始数组可以利用原始数组A的单元，一个个逐次贮存的单元，一个个逐次贮存L或或U中中的相应元素，即
6、：的相应元素，即： a11 a12 a13 a1n u11 u12 u13 u1n a21 a22 a23 a2n l21 u22 u23 u2n a31 a32 a33 a3n l31 l32 u33 u3n an1 an2 an3 ann ln1 ln2 ln3 unn.(1)(3)(5)(2n-1)(2) (4) (6) (2n)8采用采用LU分解有如下特点：分解有如下特点：（1）LU分解与右端向量无关。先分解，后分解与右端向量无关。先分解，后回代。一般说来，分解的运算次数正比于回代。一般说来，分解的运算次数正比于n回代求解正比与回代求解正比与n。求。求 遇到多次回代时，分遇到多次回代时
7、，分解的工作不必重新做。这样节省计算时间。解的工作不必重新做。这样节省计算时间。（2）分解按步进行，前边分解得到的信息）分解按步进行，前边分解得到的信息为后边所用。为后边所用。（3）A阵的存储空间可利用，节省存储。阵的存储空间可利用，节省存储。329 特殊方程组的解法特殊方程组的解法1.追赶法2.LDLT分解法101.1.追赶法追赶法n n追赶法与稀疏线性方程组追赶法与稀疏线性方程组n n 追追赶赶法法仍仍然然保保持持LULU分分解解特特性性, ,它它是是一一种种特特殊殊的的LULU分分解解。充充分分利利用用了了系系数数矩阵的特点，而且使之分解更简单矩阵的特点，而且使之分解更简单, ,得到对三
8、对角线性方程组的快速解法。得到对三对角线性方程组的快速解法。n n因三对角矩阵的非零元素呈因三对角矩阵的非零元素呈“ “带状带状” ”，我们也因此将它叫做带状矩阵。，我们也因此将它叫做带状矩阵。 11三对角线性方程组：三对角线性方程组：12设有方程组Ax=d，其中A为三对角矩阵。假设系数矩阵A满足条件：对A作Crout分解形式为：13第i个分量第j个分量14追赶法计算公式追赶法计算公式1516定定理理 如如果果上上带带宽宽为为q，下下带带宽宽为为p的的n阶阶带带状状矩矩阵阵A有有Doolittle分分解解。A=LU，则则L是是下带宽为下带宽为p的单位下三角矩阵，的单位下三角矩阵，U是上带宽为是
9、上带宽为q的上三角矩阵。的上三角矩阵。 1718下面举实例用追赶法来解三对角方程组。1920实际问题中，当求解方程组的系数矩阵是对称矩阵时，则用下面介绍的LDLT 分解法可以简化程序设计并减少计算量. 从定理可知,当矩阵A的各阶顺序主子式不为零时,A有唯一的Doolittle分解A=LU.此时,当然有,所以矩阵U的对角线元素uii 0,(i=1,2,n),将矩阵U的每行依此提出uii2. LDLT分解法分解法21由A=AT，得由分解的唯一性有， 即，于是可得下面的结论。 22定理定理3 3：若对称矩阵：若对称矩阵A A各阶顺序主子式不为零时各阶顺序主子式不为零时, , 则则A A可以唯一分解为
10、可以唯一分解为A= LDLA= LDLT T ，这里，这里LT为L的转置矩阵。 当A有LDLT分解时，利用矩阵运算法则及相等原理易得计算ljk及dk的公式为23 k=1,2,n; j=k+1,k+2,n为减少乘法次数，引入辅助量为减少乘法次数，引入辅助量 ujk= ljkdk,则上面公式可写成则上面公式可写成24252627平方根法平方根法 设设A为为正正定定矩矩阵阵，则则它它的的各各阶阶顺顺序序主主子子式式均均为为正正。由由前前面面的的定定理理知知，A必必有有唯唯一的一的LDLT分解式分解式 A=LDLT 在在解解对对称称正正定定线线性性方方程程组组时时，系系数数矩矩阵阵A的的LDLT分分解解中中D又又可可分分解解为为D=D1/2 D1/2，这里，这里D1/2也是对角矩阵也是对角矩阵28
