5.LU分解PPT演示课件.ppt

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分解法的基本思想分解法的基本思想2n n内容内容:LU分解分解.n n关键词关键词: 1.LU分解分解 :将系数矩阵将系数矩阵A转变成等价两个矩转变成等价两个矩阵阵L和和U的乘积的乘积 ,其中其中L和和U分别是下三角和分别是下三角和上三角矩阵上三角矩阵 ,而且要求而且要求U的对角元素都是的对角元素都是1. 2.紧凑格式紧凑格式:由于可以把由于可以把L和和U两个矩阵压缩两个矩阵压缩到一个数组中到一个数组中,而且还可以存储在原来的系而且还可以存储在原来的系数矩阵数矩阵A的数组中的数组中.这种这种LU分解常被称为紧分解常被称为紧凑格式凑格式.3n n由由由由LU=ALU=A及对及对及对及对L L和和和和U U的要求可以得到分解的计算公的要求可以得到分解的计算公的要求可以得到分解的计算公的要求可以得到分解的计算公式．根据下式式．根据下式式．根据下式式．根据下式(Doolittle(Doolittle分解分解分解分解) )：：：： 1 l21 1 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 A………4第j个分量第i个分量5根据矩阵乘法及相等的定义根据矩阵乘法及相等的定义,有有 得公式 u1j=a1j j=1,2,…,n li1=ai1 / u11 i=2,3,…,n67在计算机程序中常常用这种方法解线性代数方程组。

在计算机程序中常常用这种方法解线性代数方程组它的优点是存储量很省它的优点是存储量很省L和和U中的三角零元素都不中的三角零元素都不必存储，就是必存储，就是U的对角元素也因为都是的对角元素也因为都是1没有必要再没有必要再记录在程序中，这样只用一个记录在程序中，这样只用一个n阶方阵就可以把阶方阵就可以把L和和U贮存起来即：下三角（包括对角元）存储贮存起来即：下三角（包括对角元）存储L各元各元素素 而上三角存储而上三角存储U的元素再考察公式再考察公式S会发现会发现A中任一元素中任一元素aij只在计算只在计算lij（（j<=i））和和uij（（j>i)中用到一次以后就不再出现了，因而完全中用到一次以后就不再出现了，因而完全可以利用原始数组可以利用原始数组A的单元，一个个逐次贮存的单元，一个个逐次贮存L或或U中中的相应元素，即：的相应元素，即： 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求 遇到多次回代时，分遇到多次回代时，分解的工作不必重新做这样节省计算时间解的工作不必重新做这样节省计算时间2）分解按步进行，前边分解得到的信息）分解按步进行，前边分解得到的信息为后边所用为后边所用3））[A]阵的存储空间可利用，节省存储阵的存储空间可利用，节省存储329 特殊方程组的解法特殊方程组的解法1.追赶法2.LDLT分解法101.追赶法n n追赶法与稀疏线性方程组n n 追追赶赶法法仍仍然然保保持持LULU分分解解特特性性, ,它它是是一一种种特特殊殊的的LULU分分解解充充分分利利用用了了系系数数矩矩阵阵的的特特点点，，而而且且使使之之分分解解更更简简单单, ,得得到对三对角线性方程组的快速解法到对三对角线性方程组的快速解法n n因三对角矩阵的非零元素呈“带状”，我们也因此将它叫做带状矩阵 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的对角线元素uii 0,(i=1,2,,n),将矩阵U的每行依此提出uii2. LDLT分解法分解法21由A=AT，得由分解的唯一性有， 即，于是可得下面的结论 22定理定理3 3：若对称矩阵：若对称矩阵A A各阶顺序主子式不为零时各阶顺序主子式不为零时, , 则则A A可以唯一分解为可以唯一分解为A= LDLA= LDLT T ，这里，这里LT为L的转置矩阵 当A有LDLT分解时，利用矩阵运算法则及相等原理易得计算ljk及dk的公式为23 k=1,2,,n; j=k+1,k+2,,n为减少乘法次数，引入辅助量为减少乘法次数，引入辅助量 ujk= ljkdk,则上面公式可写成则上面公式可写成24252627平方根法平方根法 设设A为为正正定定矩矩阵阵，，则则它它的的各各阶阶顺顺序序主主子子式式均均为为正正。

由由前前面面的定理知，的定理知，A必有唯一的必有唯一的LDLT分解式分解式 A=LDLT 在在解解对对称称正正定定线线性性方方程程组组时时，，系系数数矩矩阵阵A的的LDLT分分解解中中D又又可分解为可分解为D=D1/2 D1/2，这里，这里D1/2也是对角矩阵也是对角矩阵28。