直接法算法設計中矩陣分解技巧的應用

1、 直接法求解線性方程組直接法的適用范圍直接法算法設計中矩陣分解技巧的應用特殊線性方程的算法設計與分析直接法所得“精確解”的精度分析 1. 直接法的適用范圍 直接法：就是經過有限步算術運算，可求得方程組精確解的方法（若計算過程中沒有舍入誤差），如克萊姆法則就是一種直接法，直接法中具有代表性的算法是高斯(Gauss)(Gauss)消去法。 直接法這個“直接”往往代表著解法思想簡單，直接了當。它往往能求各種方程，是一種通吃的解法，像克萊姆法則、高斯(Gauss)(Gauss)消去法，它們很強大，但也有缺點。這個缺點往往是致命的，有些方程它能解，但人們往往不敢用它去解。為什么呢？它們在計算高階方程組計

2、算量太大啦所以直接法比較適合解中低階的矩陣對于大型矩陣我們往往采取其它方法。如迭代法 在實際應用中選擇算法往往從三個方面考慮：(1) 解的精度高；(2) 計算量??；(3)所需計算機內存小。 但這些條件相互間是矛盾而不能兼顧的，因此實際計算時應根據問題的特點和要求及所用計算機的性能來選擇算法。一般說，系數矩陣為中、小型滿矩陣，用直接法較好；當系數矩陣為大型、稀疏矩陣時，有效的解法是下節(jié)要討論的迭代法。 2.直接法算法設計中矩陣分解技巧的應用 矩陣三角分解法矩陣三角分解法是高斯消去法解線性方程的變形解法 矩陣三角分解原理 應用高斯消去法解應用高斯消去法解n階線性方程組階線性方程組Ax=b, 經過經

3、過n步步消元之后消元之后, , 得出一個等價的上三角型方程組得出一個等價的上三角型方程組A(n) x=b(n), 對上三角形方程組用逐步回代就可以求出對上三角形方程組用逐步回代就可以求出解來。上述過程可通過矩陣分解來實現。解來。上述過程可通過矩陣分解來實現。 將非奇異陣將非奇異陣A分解成一個下三角陣分解成一個下三角陣L和一個上三角和一個上三角陣陣U的乘積的乘積 A=LU稱為對矩陣稱為對矩陣A的三角分解，又的三角分解，又稱稱LU分解。分解。)() 3(3) 3(33) 2(2) 2(23) 2(22) 1 (1) 1 (13) 1 (12) 1 (1121323121,1111nnnnnnnna

4、aaaaaaaaaUmmmmmLLUaaaaaaaaaaaaaaaaAnnnnnnnn321333323122322211131211其中其中方程組方程組Ax=b的系數矩陣的系數矩陣A經過順序消元逐步經過順序消元逐步化為上三角型化為上三角型A(n),相當于用一系列初等變換左相當于用一系列初等變換左乘乘A的結果。事實上，第的結果。事實上，第1列消元將列消元將A(1)=A化化為為A(2)，若令：，若令：10000100010001131211nmmmL), 3 , 2(,) 1 (11) 1 (11niaamii則根據距陣左乘有則根據距陣左乘有L1A(1)=A(2)第第2列消元將列消元將A(2)化

5、為化為A(3)，若令：，若令：1000010001000012322nmmL), 4 , 3(,)2(22)2(22niaamii經計算可知經計算可知 L2A(2)=A(3),依此類推依此類推,一般有一般有LkA(k)=A(k+1)11111,1nkkkkmmL于是矩陣于是矩陣 經過消元化為上三角陣經過消元化為上三角陣 的過程可表示為的過程可表示為上述矩陣上述矩陣 是一類初等矩陣是一類初等矩陣, ,它們都是單位下三角陣，且其逆矩陣也是單位它們都是單位下三角陣，且其逆矩陣也是單位下三角陣下三角陣, ,只需將只需將 改為改為 , ,就得到就得到 。即。即 ) 1 (AA)(nA)(1221nnnA

6、ALLLL) 1, 2 , 1(nkLkikm), 2, 1(nkkimik1kL11111, 11nkkkkmmL于是有于是有 LUULLLALLLAnnn)()(111211)(111211)() 3 (3) 3 (33) 2(2) 2(23) 2(22) 1 (1) 1 (13) 1 (12) 1 (1121323121,1111nnnnnnnnaaaaaaaaaaUmmmmmL其中其中 L L為由乘數構成的單位下三角陣，為由乘數構成的單位下三角陣，U U為上三角陣，為上三角陣，由此可見，在由此可見，在 的條件下的條件下，高斯消去法實質上是將方程組的系數矩陣，高斯消去法實質上是將方程組的

7、系數矩陣A A分分解為兩個三角矩陣的乘積解為兩個三角矩陣的乘積A=LUA=LU。這種把非奇異矩。這種把非奇異矩陣陣A A分解成一個下三角矩陣分解成一個下三角矩陣L L和一個上三角矩陣和一個上三角矩陣U U的乘積稱為矩陣的三角分解，又稱的乘積稱為矩陣的三角分解，又稱LULU分解。分解。 顯然，如果顯然，如果 , ,由行列式由行列式的性質知，方程組系數矩陣的性質知，方程組系數矩陣A A的前的前n-1n-1個順序主子個順序主子矩陣矩陣 非奇異，即順序主子非奇異，即順序主子式不等于零，即式不等于零，即) 1, 2 , 1(0)(nkakkk) 1, 2 , 1(0)(nkakkk)1, 2, 1(nk

8、Ak0)det()1(111 aA), 3 , 2(0)det()()2(22)1(11kiaaaAiiii其中其中 iiiiiaaaaAaA1111111),(（A A的主子陣）的主子陣） 反之反之, ,可用歸納法證明可用歸納法證明, ,如果如果A A的順序主子式的順序主子式 ), 2 , 1(0)det()()2(22)1(11kiaaaAiiii則則 ), 2 , 1(0)(kiaiii于是得到下述定理：于是得到下述定理： 把把A分解成一個單位上三角陣分解成一個單位上三角陣L和一個下和一個下三角陣三角陣U的乘積稱為的乘積稱為杜利特爾（杜利特爾（Doolittle）分解分解。其中其中 nn

9、nnnnuuuuuuUlllL222112112121,111若把若把A分解成一個下三角陣分解成一個下三角陣L和一個單位上和一個單位上三角陣三角陣U的乘積稱為的乘積稱為克克洛特分解洛特分解Crout） 其中其中 111,211221222111nnnnnnuuuUllllllL 用三角分解法解方程組 求解線性方程組求解線性方程組Ax=b時時,先對非奇異矩陣先對非奇異矩陣A進行進行LU分解使分解使A=LU，那么方程組就化為，那么方程組就化為 LU x=b 從而使問題轉化為求解兩個簡單的的三角方程組從而使問題轉化為求解兩個簡單的的三角方程組 L y=b 求解求解 y U x=y 求解求解 x 這就

10、是求解線性方程組的三角分解法的基本思想。這就是求解線性方程組的三角分解法的基本思想。下面只介紹杜利特爾（下面只介紹杜利特爾（Doolittle）分解法。）分解法。設設A=LU為為nnnnnnnnnnnuuuuuulllaaaaaaaaa2221121121212122221111111111 由矩陣乘法規(guī)則由矩陣乘法規(guī)則niuaii, 2 , 111niulaii, 3 , 21111 由此可得由此可得U的第的第1行元素和行元素和L的第的第1列元素列元素niauii, 2 , 111niualii,3 ,21111 再確定再確定U的第的第k行元素與行元素與L的第的第k列元素列元素, ,對對于于

11、k=2,3, ,n計算：計算： 計算計算U的第的第k行元素行元素 11krrjkrkjkjulau（j=k,k+1,j=k,k+1,n,n） 計算計算L L的第的第k k列元素列元素 kkkrrkirikikuulal11（i=k,k+1,i=k,k+1,n,n） nnnnnnnnnnnuuuuuulllaaaaaaaaa2221121121212122221111111111利用上述計算公式便可逐步求出利用上述計算公式便可逐步求出U與與L的各元素的各元素求解求解 Ly=b , Ly=b , 即計算即計算: : 1111),3 ,2(ikkikiiniylbyby 求解求解 Ux=y , Ux

12、=y , 即計算：即計算： )1 ,2, 1(1niuxuyxuyxiinikkikiinnnn 顯然顯然, 當當 時時, 解解Ax=b直接三角分解法計算才能完成。設直接三角分解法計算才能完成。設A為非奇異矩陣為非奇異矩陣, 當當 時計算將中斷或時計算將中斷或者當者當 絕對值很小時，按分解公式計算絕對值很小時，按分解公式計算可能引起舍入誤差的積累，因此可采用與可能引起舍入誤差的積累，因此可采用與列主元消去法類似的方法，對矩陣進行行列主元消去法類似的方法，對矩陣進行行交換，則再實現矩陣的三角分解。交換，則再實現矩陣的三角分解。 用直接三角分解法解用直接三角分解法解Ax=b大約需要大約需要 次乘除

13、法。次乘除法。 ), 2 , 1(0nkukk0kkukku3/3n例例3.8 用三角分解法解方程組用三角分解法解方程組 542631531321321xxx121321111111UL求解求解 Ly=b 得得 y= 2，2，1T 求解求解 Ux=y 得得 x= -1，0，1 T所以方程組的解為所以方程組的解為 101321xxx特殊方程的算法設計與分析p1平方根法p2改進平方根法 平方根法平方根法1簡介簡介平方根法又叫平方根法又叫Cholesky分解法，是求解對稱正定線性方分解法，是求解對稱正定線性方程組最常用的方法之一。程組最常用的方法之一。我們知道，對于一般方陣，為了消除我們知道，對于一般方陣，為了消除LU分解的局限性和分解的局限性和誤差的過分積累，而采用了選主元的方法。但對于對稱誤差的過分積累，而采用了選主元的方法。但對于對稱正定矩陣而言，選主元卻是完全不必要的。而平方根法正定矩陣而言，選主元卻是完全不必要的。而平方根法就可以簡便的解決這類問