數(shù)值分析 LU分解法

1、§3 LU分解法Gauss消去法的變形知識(shí)預(yù)備：1矩陣的初等行變換、初等矩陣及其逆、乘積 2矩陣的乘法 3上三角矩陣的乘積、單位下三角矩陣的乘積 4單位下三角矩陣的逆、可逆的上三角矩陣的逆一、Gauss消去法的矩陣解釋Gauss消去法實(shí)質(zhì)上是將矩陣A分解為兩個(gè)三角矩陣相乘。我們知道，矩陣的初等行變換實(shí)質(zhì)就是左乘初等矩陣。第一輪消元：相當(dāng)于對(duì)A（1）左乘矩陣L1，即其中第二輪消元：對(duì)應(yīng)于一般地 （1）其中 整個(gè)消元過程為（2）從而其中L是單位下三角矩陣，即（3）【注】消元過程等價(jià)于A分解成LU的過程回代過程是解上三角方程組的過程。二、矩陣的三角分解1、若將A分解成LU，即A=LU，其中

2、L為單位下三角矩陣,U為非奇異上三角矩陣,則稱之為對(duì)A的Doolittle分解。當(dāng)A的順序主子式都不為零時(shí)，消元運(yùn)算可進(jìn)行，從而A存在唯一的Doolittle分解。證明：若有兩種分解，A=L1U1，A=L2U2，則必有L1=L2，U1=U2。因?yàn)長(zhǎng)1U1=L2U2，而且L1，L2都是單位下三角矩陣，U1,U2都是可逆上三角矩陣,所以有因此 即L1=L2，U1=U2、2、若L是非奇異下三角矩陣，U是單位上三角矩陣時(shí)，A存在唯一的三角分解，A=LU，稱其為A的Crout分解（對(duì)應(yīng)于用列變換實(shí)施消元）三、直接分解（LU分解）算法LU分解算法公式按矩陣乘法第一步：利用A中第一行、第一列元素確定U的第一

3、行、L的第一列元素。由 得 u1j=a1j ) li1=ai1/u11)第r步:利用A中第r行、第r列剩下的元素確定U的第r行、L的第r列元素（r=2，3，n）.由得U的第r行元素為由得(4)直接分解的緊湊格式： u11 u12 u13 u1n 1 l21 u22 u23 u2n 2 l31 l32 ln1 ln2 unn n方程組的三角分解算法（LU分解）對(duì)于方程組Ax=b，設(shè)A=LU (Doolittle分解)。由于 1、求解Ly=b： （5）2、求解Ux=y：（6）LU分解算法步1，輸入A，b；步2，對(duì)j=1,2,n 求 對(duì)i=2,3,n 求步3,對(duì)r=2,3,n 做（3.1）-(3.2

4、):（3.1）（3.2）步4，步5，步6，輸出結(jié)束。例子與程序：【例】用LU分解求解方程組解：對(duì)系數(shù)矩陣A進(jìn)行LU分解因此先解。再解程序：LU_factorization%Not Select Column LU_factorizationclear alln=3;a=2 2 3;4 7 7;-2 4 5;b=3;1;-7;%n=3;a=1 4 7;2 5 8;3 6 11;b=1;1;1;%LU_factorazationfor i=2:n a(i,1)=a(i,1)/a(1,1);endafor r=2:n for j=r:n s=0.; for k=1:r-1 s=s+a(r,k)*a(

5、k,j); end a(r,j)=a(r,j)-s; end for i=r+1:n s=0.; for k=1:r-1 s=s+a(i,k)*a(k,r); end a(i,r)=(a(i,r)-s)/a(r,r); end a end%Extract Lower/Upper Triangular Partl=tril(a);for i=1:n l(i,i)=1;endu=triu(a);lu%Linear Lower Triangular Equation Solution y=lb%Linear Upper Triangular Equation Solutionx=uy 四、列主元LU分解 當(dāng)用LU分解法解方程組時(shí)，從第r(r=1,2,n)步分解計(jì)算公式可知 當(dāng)很小時(shí)，可能引起舍入誤差的累積、擴(kuò)大。因此，可采用與列主元消去法類似方法，將直接三角分解法修改為列主元三角分解法（與列主元消去法在理論上是等價(jià)的），它通過交換A的行實(shí)現(xiàn)三角分解PA=LU，其中P為置換陣。設(shè)第r-1步分解計(jì)算己完成，則有第r步計(jì)算時(shí)為了避免用絕對(duì)值很小的數(shù)作除數(shù)，引進(jìn)中間量：則有：（1） 選主元：確定（2） 交換兩行：交換A的第r行與第行元素（相當(dāng)于先交換原始矩陣A第r行與第行元素后，再進(jìn)行分解計(jì)算得到的結(jié)果，且）（3） 進(jìn)行分解計(jì)算附：列主元