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

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