研究生數(shù)值分析直接三角分解法.ppt

三角分解法也是直接法，基本思想是： 將系數(shù)矩陣A分解為兩個三角形矩陣L和U的乘積A=LU ，將方程組AX=b的求解問題歸結(jié)為兩個三角形方程組 LY=b與UX=Y的求解問題。,即：先由LY=b求出Y ，然后由UX=Y求出X ，從而獲得AX=b的解。,2 直接三角分解法,(1) A為一般稠密（零元素占很小比例）矩陣的杜利特爾(Doolittlr)和克勞特(Crout)分解法；,(2) A為三對角的追趕法。,把一個n階矩陣A分解成兩個三角形矩陣相乘的形式稱為矩陣的三角分解。,1 Doolittle分解法和Crout 分解法,A=LU，其中L為下三角陣，U為上三角陣。,若U為單位上三角陣(對角元都是1的上三角陣), L為單位下三角陣,則稱為克勞特(Crout)分解。,矩陣三角分解的常見形式是：,作為特例，若L為單位下三角陣(對角元都是1的下三角陣), U為上三角陣，則稱為杜利特爾(Doolittle)分解；,下面分析實現(xiàn)矩陣杜利特爾(Doolittle)分解和克勞特(Crout)分解的條件,討論這些分解的唯一性。,定理2 (矩陣三角分解基本定理),則存在唯一的杜利特爾分解A=LU，其中L 為單位下三角陣，U 為非奇異上三角陣。,設(shè) 。若A的順序主子式,還可以證明存在唯一的克勞特Crout分解,這里L(fēng)為非奇異下三角陣，U為單位上三角陣。,如果A是一般非奇異陣，由列主消元法，A適當(dāng)行交換后，可使A的各階順序主子式 ， 從而實現(xiàn)杜利特爾Doolittle或克勞特Crout分解。,設(shè)方程組AX=b的系數(shù)矩陣的各階順序主子式,，則存在唯一杜利特爾分解,，其中,杜利特爾Doolittle分解法,下面介紹直接根據(jù)A的元素計算L、U元素的分解方法,由矩陣乘法規(guī)則與相等條件,第一步求U的第一行元素和L的第一列元素,第二步求U的第二行元素和L的第二列元素,對那些明確是1或是0的元素不再求。,導(dǎo)出計算 或 的公式。,利用 在上述計算過程中，,第一步計算由 得,第二步計算由 得,（1）,由 得,由 得,（2）,例如,第k步計算U的第k行L的第k列元素的公式為：,在我們利用杜利特爾矩陣分解解線性方程組AX=b時,只要實現(xiàn)矩陣分解A=LU,依次解三角形方程組LY=b與UX=Y即可。,（3）,（4）,（6）,（5）,計算公式：,杜利特爾矩陣分解 求解線性方程組的過程為:,10 實現(xiàn)A=LU分解，即,(a)按計算公式(1),(2)依次計算U的第1行元素 與L的第1列元素,(b) 對k+2,3,n 按計算公式(3),(4)依次計算U的第k行元素 與L的第k列元素,20 求解三角形方程組LY=b，即按計算公式(5)依次計算,30 求解三角形方程組UX=Y，即按計算公式(6)依次計算,為便于記憶，我們給出L、U分解緊湊格式:,在解方程組時,對于右端項b也可不必經(jīng)過中間過程而按緊湊格式的方法直接得出y，因為Ly=b ，所以,它與公式（3）相似。若將b作為增廣矩陣的最后一列元素,那么對增廣矩陣作LU分解, b也作相應(yīng)運算,仍在最后一列,則分解后的最后一列即為y 。 于是,例3：將方程組,解：增廣矩陣為,的系數(shù)矩陣作LU分解，并求方程組的解。,LU分解的緊湊格式為,所以系數(shù)矩陣的三角分解為,等價的三角方程組為,用回代法解得,4 追趕法求解三對角線性方程組,在樣條函數(shù)的計算、微分方程數(shù)值求解中常遇到如下形式的線性代數(shù)方程組：,其中方程組AX=f 的系數(shù)矩陣A的元素滿足條件：,且,（1）,根據(jù)系數(shù)矩陣A的特點，設(shè),其中 為待定系數(shù)。比較A與LU對應(yīng)的元素，有,（2）,由（1）和（2）可以看出,因此有,由,有,一般地，用歸納法可以證明,因此我們從關(guān)系式（2）解出待定系數(shù)為,（3）,由以上推導(dǎo)過程知，方程組AX=f 有唯一解,由（3）式可得計算 的遞推公式,（4）,只要計算出 ，其它待定系數(shù) 與 均可通過已知數(shù) 與 表示。,上述解方程組 AX=f 的過程歸納為：,10 實現(xiàn)A=LU分解,按遞推公式(4)計算,20 求解方程組 LY=f ,相應(yīng)的遞推公式是,（5）,30 求解方程組 UX=Y ,相應(yīng)的遞推公式是,（6）,計算 及 的過程,稱為追的過程，計算方程組的解 的過程稱為趕的過程，因此上述方法稱為追趕法。,例4：用追趕法解方程組,解：按遞推公式（4）計算 得,按遞推公式（5）計算,得