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分解法的基本思想分解法的基本思想作者：赵俭平&内容内容:LU分解分解.&关键词关键词: 1.LU分分解解 :将系数矩阵将系数矩阵A转变成等价两个矩阵转变成等价两个矩阵L和和U的乘的乘积积 ,其中其中L和和U分别是下三角和上三角矩阵分别是下三角和上三

2、角矩阵 ,而且要而且要求求U的对角元素都是的对角元素都是1. 2.紧凑格式紧凑格式:由于可以把由于可以把L和和U两个矩阵压缩到一个两个矩阵压缩到一个数组中数组中,而且还可以存储在原来的系数矩阵而且还可以存储在原来的系数矩阵A的数的数组中组中.这种这种LU分解常被称为紧凑格式分解常被称为紧凑格式.作者：赵俭平&由由LU=A及对及对L和和U的要求可以得到分解的计算公的要求可以得到分解的计算公式根据下式式根据下式(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 un

3、n=aannL Un1an3 a11 a12 a13 a1na21 a22 a23 a2na31 a32 a33 a3n an2 A作者：赵俭平ijjjjiiiiijiauuullllULj000,0,1,213211第j个分量第i个分量nkjikkjikkjikijulula1,max1作者：赵俭平根据矩阵乘法及相等的定义根据矩阵乘法及相等的定义,有有 niulululanjuulululainkkkikkikijjnkkkjkkjkj, 2, 2 , 11111111111111111111得公式 u1j=a1j j=1,2,n li1=ai1 / u11 i=2,3,niiikkijkn

4、kikkijkkijkjiijikkjiknkikkjikkjkijululululauulululajiji111111111,有时当1iil作者：赵俭平ijuulalijulauDoolittleiiikkijkjiikkjikijijji/)(1111分解公式得作者：赵俭平在计算机程序中常常用这种方法解线性代数方程组。在计算机程序中常常用这种方法解线性代数方程组。它的优点是存储量很省。它的优点是存储量很省。L和和U中的三角零元素都不中的三角零元素都不必存储，就是必存储，就是U的对角元素也因为都是的对角元素也因为都是1没有必要再没有必要再记录在程序中，这样只用一个记录在程序中，这样只用一个

5、n阶方阵就可以把阶方阵就可以把L和和U贮存起来。即：下三角（包括对角元）存储贮存起来。即：下三角（包括对角元）存储L各元各元素素 而上三角存储而上三角存储U的元素。的元素。再考察公式再考察公式S会发现会发现A中任一元素中任一元素aij只在计算只在计算lij（ji)中用到一次以后就不再出现了，因而完全中用到一次以后就不再出现了，因而完全可以利用原始数组可以利用原始数组A的单元，一个个逐次贮存的单元，一个个逐次贮存L或或U中中的相应元素，即：的相应元素，即： a11 a12 a13 a1n u11 u12 u13 u1n a21 a22 a23 a2n l21 u22 u23 u2n a31 a3

6、2 a33 a3n l31 l32 u33 u3n an1 an2 an3 ann ln1 ln2 ln3 unn.(1)(3)(5)(2n-1)(2) (4) (6) (2n)作者：赵俭平采用采用LU分解有如下特点：分解有如下特点：（1）LU分解与右端向量无关。先分解，后分解与右端向量无关。先分解，后回代。一般说来，分解的运算次数正比于回代。一般说来，分解的运算次数正比于n回代求解正比与回代求解正比与n。求。求 遇到多次回代时，分遇到多次回代时，分解的工作不必重新做。这样节省计算时间。解的工作不必重新做。这样节省计算时间。（2）分解按步进行，前边分解得到的信息）分解按步进行，前边分解得到的信

7、息为后边所用。为后边所用。（3）A阵的存储空间可利用，节省存储。阵的存储空间可利用，节省存储。32作者：赵俭平& 特殊方程组的解法特殊方程组的解法1.追赶法2.LDLT分解法作者：赵俭平1.追赶法追赶法&追赶法与稀疏线性方程组& 追赶法仍然保持LU分解特性,它是一种特殊的LU分解。充分利用了系数矩阵的特点，而且使之分解更简单,得到对三对角线性方程组的快速解法。&因三对角矩阵的非零元素呈“带状”，我们也因此将它叫做带状矩阵。 作者：赵俭平nnnnnnnnnnnnnnnnnbacbacbacbAdxbxadxcxbxadxcxbxadxcxb111222111111111232221212111对

8、应的系数矩阵三对角线性方程组：三对角线性方程组：作者：赵俭平设有方程组Ax=d，其中A为三对角矩阵。假设系数矩阵A满足条件：对A作Crout分解形式为：11111211122111122211nnnnnnnnnnbacbacbacb作者：赵俭平ijjiijiaUL01000,0,0,011 的计算公式推得计算由比较系数所得关系式定义，有：即根据矩阵乘法及相等时待定常数。比较其中iiiiiiiiiiiiiiianiacniabaacabBa,) 1, 2(), 2(,;,)(,111111第i个分量第j个分量作者：赵俭平), 2()(), 3 , 2(,)1, 2 , 1(1111111nibc

9、niabaacbaniaiiiiiiiiiii追赶法计算公式追赶法计算公式作者：赵俭平分解进行也可对三对角矩阵的过程可称为赶的解将计算的过程可称为追及将计算计算公式从而得之对角方程组的解出及时，可由当求解分解后的实现DoolittleAxxxdAxyyynixyxyxniabyadyadyabcacyUxdLyLUAdAxCroutAnnnniiiinniiiiiiiiiiii11211211111111111)1 ,2,1(),2()()(作者：赵俭平定理定理 如果上带宽为如果上带宽为q，下带宽为，下带宽为p的的n阶带状矩阵阶带状矩阵A有有Doolittle分解。分解。A=LU，则，则L是下

10、带宽为是下带宽为p的单位下三角矩阵，的单位下三角矩阵，U是上带宽为是上带宽为q的上三角矩阵。的上三角矩阵。 解出。及可由时，当，表示，则三对角方程的矩阵若记的计算公式，为：和的及的元素于是得计算，有：由矩阵乘法及相等定义分解形式阵yUxdLyLUAdAxddddpbqnkcqapbqqUpLnkcbpqaqpbqqqqpppbacbacbacbDoolittleTnkkkkkkkkkiiikkkkkkkkknnnnnnnn),(), 3 ,2(), 3 ,2(111121111111111111122113211122211作者：赵俭平时不能进行。的缺点，即当消元法消元法，因此也存在为追赶法来

11、源于间和存贮空间，但是因计算时的特殊求解过程，节省次乘除法运算。追赶法，只需增加组程次，若另外增加一个方有计算量、乘除法次数仅求解公式也比较简单，分解。因而较特别或消元法中的变形追赶法实际上也是。组的方法亦称为追赶法用这组公式解线性方程，角方程组的递推公式：综合以上，求解出三对计算公式为：三对角矩023451 , 1)(, 3 , 21 , 2, 1)(, 3 , 22111111111111kkkkkknnnkkkkkkkkkkkkkkkkknnkkkkqGaussGaussndAxnDoolittleCroutGaussnkqxcyxqyxypdynkcpbqqapdybqnnkqxcyx

12、qyxnkypdydy作者：赵俭平下面举实例用追赶法来解三对角方程组。2123211323223232112211212112120212124443322211434322121yqpyqpyqpyqADoolittlexxxxxxxxx所以为三对角矩阵分解形式用12) 1( *11123)3333. 0( *0233333. 023333. 0*113333. 031211234xxxx作者：赵俭平的计算量。我们的特征，将可大大减少的线性形式时，注意到我们解次乘除法运算。因此在消元法大约为次乘除运算；而用需用追赶法做此类题，只多。消元法的计算量要少很追赶法的运算量比AdAxGaussGau

13、ss3616作者：赵俭平实际问题中，当求解方程组的系数矩阵是对称矩阵时，则用下面介绍的LDLT 分解法可以简化程序设计并减少计算量. 从定理可知,当矩阵A的各阶顺序主子式不为零时,A有唯一的Doolittle分解A=LU.此时,当然有,所以矩阵U的对角线元素uii 0,(i=1,2,n),将矩阵U的每行依此提出uii2. LDLT分解法分解法作者：赵俭平这里则有,UDU nnuuuD22111111111222222311111131112nnnnnnuuuuuuuuuuuuU由A=AT，得由分解的唯一性有， 即，于是可得下面的结论。 ULDDLULDUULDTTTTTT)(LUT作者：赵俭平

14、定理定理3：若对称矩阵：若对称矩阵A各阶顺序主子式不为零时各阶顺序主子式不为零时, 则则A可以唯一分解为可以唯一分解为A= LDLT ，这里，这里1111121323121nnnnllllllLndddD21,LT为L的转置矩阵。 当A有LDLT分解时，利用矩阵运算法则及相等原理易得计算ljk及dk的公式为作者：赵俭平11112/ )(kmkmkmjmjkjkkmmkmkkkddllaldlad k=1,2,n; j=k+1,k+2,nkjkjkkmkmjmjkjkkmkmkmkkkdulluauluad/1111nkkjnk, 2, 1, 2 , 1为减少乘法次数，引入辅助量为减少乘法次数，

15、引入辅助量 ujk= ljkdk,则上面公式可写成则上面公式可写成作者：赵俭平例1 用 LDLT 分解法来解方程组 解 本题是对称线性方程组，故可用 LDLT 分解法求解，由其求解公式1641464245321321321xxxxxxxxx5, 1111adk8 . 0/, 4, 2121212121dulauj2 . 0/, 1, 3131313131dulauj作者：赵俭平14285. 2, 332323131333luluadk333333. 0,166667. 0,333334. 0333334. 0,714284. 0214286. 0, 6 . 0, 4 . 0, 21233322

16、11xxxzyzyzy8 . 2, 22121222luadk14286. 1/2 . 3, 32323221313232dulluauj作者：赵俭平平方根法设 A 为正定矩阵，则它的各阶顺序主子矩阵均为正定。由前面的定理知，A 必有唯一的 Doolittle 分解式 A=LU其中 L 为单位下三角矩阵，U上三角矩阵， 。记 D=diag(u:),因 A=AT，于是作者：赵俭平平方根法平方根法 设设A为正定矩阵，则它的各阶顺序主子式均为正。由前面的定理知，为正定矩阵，则它的各阶顺序主子式均为正。由前面的定理知，A必有必有唯一的唯一的LDLT分解式分解式 A=LDLT 在解对称正定线性方程组时，系数矩阵在解对称正定线性方程组时，系数矩阵A的的LDLT分解中分解中D又可分解为又可分解为D=D1/2 D1/2，这里这里D1/2也是对角矩阵也是对角矩阵TTTLDLDLDLDLDLA)(21212121.,21称为平方根法组的方法分解解线性方程用三角阵称为下三角矩阵分解的这种分解称为正定矩阵则令CholeskyCholeskyLCholeskyALLALLD