1、LU分解法的與特殊方程組的解法,假定我們能把矩陣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分解法的基本思想,內(nèi)容:LU分解. 關(guān)鍵詞: 1.LU分解 :將系數(shù)矩陣A轉(zhuǎn)變成等價兩個矩陣L和U的乘積 ,其中L和U分別是下三角和上三角矩陣 ,而且要求U的對角元素都是1. 2.緊湊格式:由于可以把L和U兩個矩陣壓縮到一個數(shù)組中,

2、而且還可以存儲在原來的系數(shù)矩陣A的數(shù)組中.這種LU分解常被稱為緊湊格式.,由LU=A及對L和U的要求可以得到分解的計算公式根據(jù)下式(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,=, ,a,ann,L U,第j個分量,第i個分量,根據(jù)矩陣乘法及相等的定義,有,得公式 u1j=a1j j=1,2,n li1=ai1 / u11 i=2,3,n,在計算機程序中常常用這種方法解線性代數(shù)方程組。 它的優(yōu)點是存儲量很省。L和U中的三角零元素都不 必存儲，就是U

3、的對角元素也因為都是1沒有必要再 記錄在程序中，這樣只用一個n階方陣就可以把L和 U貯存起來。即：下三角（包括對角元）存儲L各元 素 而上三角存儲U的元素。 再考察公式S會發(fā)現(xiàn)A中任一元素aij只在計算lij（ji)中用到一次以后就不再出現(xiàn)了，因而完全 可以利用原始數(shù)組A的單元，一個個逐次貯存L或U中 的相應(yīng)元素，即： 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)

4、,(3),(5),(2n-1),(2) (4) (6) (2n),采用LU分解有如下特點： （1）LU分解與右端向量無關(guān)。先分解，后 回代。一般說來，分解的運算次數(shù)正比于n 回代求解正比與n。求 遇到多次回代時，分 解的工作不必重新做。這樣節(jié)省計算時間。 （2）分解按步進行，前邊分解得到的信息 為后邊所用。 （3）A陣的存儲空間可利用，節(jié)省存儲。,3,2, 特殊方程組的解法,1.追趕法 2.LDLT分解法,1.追趕法,追趕法與稀疏線性方程組 追趕法仍然保持LU分解特性,它是一種特殊的LU分解。充分利用了系數(shù)矩陣的特點，而且使之分解更簡單,得到對三對角線性方程組的快速解法。 因三對角矩陣的非零元

5、素呈“帶狀”，我們也因此將它叫做帶狀矩陣。,三對角線性方程組：,設(shè)有方程組Ax=d，其中A為三對角矩陣。 假設(shè)系數(shù)矩陣A滿足條件：對A作Crout分解形式為：,第i個分量,第j個分量,追趕法計算公式,定理 如果上帶寬為q，下帶寬為p的n階帶狀矩陣A有Doolittle分解。A=LU，則L是下帶寬為p的單位下三角矩陣，U是上帶寬為q的上三角矩陣。,下面舉實例用追趕法來解三對角方程組。,實際問題中，當(dāng)求解方程組的系數(shù)矩陣是對稱矩陣時，則用下面介紹的LDLT 分解法可以簡化程序設(shè)計并減少計算量. 從定理可知,當(dāng)矩陣A的各階順序主子式不為零時,A有唯一的Doolittle分解A=LU.此時,當(dāng)然有,所以矩陣U的對角線元素uii 0,(i=1,2,n),將矩陣U的每行依此提出uii,2. LDLT分解法,由A=AT，得 由分解的唯一性有， 即，于是可得下面的結(jié)論。,定理3：若對稱矩陣A各階順序主子式不為零時, 則A可以唯一分解為A= LDLT ，這里,LT為L的轉(zhuǎn)置矩陣。 當(dāng)A有LDLT分解時，利用矩陣運算法則及相等原理易得計算ljk及dk的公式為,k=1,2,n; j=k+1,k+2,n,為減少乘法次數(shù)，引入輔助量 ujk= ljkdk,則上面公式可寫成,平方根法 設(shè)A為正定矩陣，則它的各階順序主