《現(xiàn)代數(shù)值計(jì)算》課件5.3 直接三角分解方法

1、5.3 直接三角分解法5.3.3 平方根法5.3.1 一般矩陣的直接三角分解法5.3.2 三對(duì)角方程組的追趕法5.3 直接三角分解法5.3.1 一般矩陣的直接三角分解法三角分解的緊湊形式 將高斯消去法改寫(xiě)為緊湊形式，可以直接從矩陣A的元素得到計(jì)算L、U元素的遞推公式，而不需任何中間步驟，這就是所謂直接三角分解法. 一旦實(shí)現(xiàn)了矩陣A的LU分解，那么求解Ax=b的問(wèn)題就等價(jià)于求解兩個(gè)三角形方程組 (1)Ly=b，求y； (2)Ux=y，求x 1.不選主元的三角分解法 設(shè)A為非奇異矩陣，且有分解式A=LU，其中L為單位下三角陣，U為上三角陣，即如果U的第1至k-1列和L的第1至k-1列已經(jīng)算出，則由

2、可得U的第k行元素同理，由ukj =akj ,j =k,k+1, ,n。 （5.3.3） akj = ,i=k+1,k+2,n, （5.3.1）（5.3.2）由A的第1行和第1列可計(jì)算出U的第1行和L的第1列，即可得L的第k列元素交替使用（5.3.3）和 （5.3.4），就能逐次計(jì)算出U（按行）和L（按列）的全部元素，而且可以把它們存放在矩陣A對(duì)應(yīng)的位置上（L的對(duì)角線(xiàn)元素不必存放）。這就完成了A的LU分解。 lik=(aik )/ ukk ,i =k+1,k+2, ,n。 由（5.3.1）- （5.3.4）求得L和U后，解方程組Ax=b 化為求解LUx=b，若記Ux=y，則有Ly=b。于是可分

3、兩部解方程組LUx=b，只要逐次向前代入的方法即可求得y。第二步求解Ux=y，只要逐次用向后回代的方法即可求得x。設(shè) x=（x1 ，x2， xn) T, y=（y1, y2, yn) T, b= (b1 ，b2， bn) T, 則有計(jì)算公式（5.3.4）（5.3.5）（5.3.6） 以上解方程組的計(jì)算與順序Gauss消去法相當(dāng)。如果有一系列方程組，其系數(shù)矩陣都是相同的，右端向量b不同，則只須進(jìn)行一次LU分解計(jì)算。上述解方程的方法稱(chēng)為L(zhǎng)U分解法，也稱(chēng)杜利特爾(Doolittle)方法。 解 由LU分解的緊湊格式（5.3.1）-（ 5.3.4 ）計(jì)算可得例5.5 用LU分解法求解解下三角方程組 L

4、y = b，即解(單位)上三角方程組 Ux= y，即二 Crout分解（） 設(shè)A為非奇異矩陣，A還有一種分解式A=LU，其中L為下三角陣，U為單位上三角陣，即 先計(jì)算L的第一列，再計(jì)算U的第一行，其余類(lèi)此。得到以下公式， 實(shí)現(xiàn) A=LU，則 Ax=b 可以化為 LUx=b。令 Ux=y，則 Ly=b。 由 Ly=b解出 yi: 再由 Ux=y 解出 xi: 例5.5用Crout分解求解方程組：解 設(shè) A=LU，即解下三角方程組 Ly = b，即解(單位)上三角方程組 Ux= y，即在數(shù)值求解常微分方程邊值問(wèn)題、熱傳導(dǎo)方程和建立三次樣條函數(shù)時(shí)，都會(huì)要解三對(duì)角方程組：AX=b5.3.2 三對(duì)角方程

5、組的追趕法并且滿(mǎn)足條件(i)保證方程組不能降階，條件(ii)保證三角分解可做到底。(5.3.7)下面討論三角分解(1)如果A滿(mǎn)足Gauss消去法的條件,可用LU (Doolittle)分解法求解. 并且, L和U有如下形式(5.3.8)按乘法展開(kāi) (5.3.9)計(jì)算次序?yàn)?而解原方程組Ax=b可分為兩步Ly=d和Ux=y,計(jì)算公式為稱(chēng)這一過(guò)程為“追”的過(guò)程. (5.3.10)(5.3.11)稱(chēng)為(5.3.9)、(5.3.10)和(5.3.11)為求解三對(duì)角形方程組的追趕法,又稱(chēng)為T(mén)homas算法。追趕法求解 Ax=f 僅需5n-4次乘除運(yùn)算。工作量較小。追趕法能實(shí)現(xiàn)的條件是ui0，i=1,2,

6、n.下面給出追趕法的一個(gè)充分條件。定理5.6 設(shè)三對(duì)角矩陣A有(5.3.7)的表達(dá)式,且滿(mǎn)足則A非奇異,且有(2)*如果A滿(mǎn)足Gauss消去法的條件,也可用LU (Crout)分解法求解. 并且, L和U有如下形式(5.3.8*)按乘法展開(kāi) 則可計(jì)算 計(jì)算次序?yàn)?(5.3.9*)(5.3.10*)而解原方程組Ax=b可分為兩步Ly=d和Ux=y,計(jì)算公式為稱(chēng)這一過(guò)程為“追”的過(guò)程. 由此可依次求得L和U的所有元素.(5.3.11*)例 用追趕法求解三對(duì)角線(xiàn)性方程組AX=b，其中作Doolitle分解解作Crout分解解練習(xí) 用追趕法求解三對(duì)角方程組- Crout 分解 解 由Ly=f 解出y又

7、由Ux=y解出x 5.3.3 平方根法 工程實(shí)際計(jì)算中,線(xiàn)性方程組的系數(shù)矩陣常常具有對(duì)稱(chēng)正定性.(5.3.12)總結(jié)上述討論有2.若A為對(duì)稱(chēng)正定矩陣, det(Ak)0,(k=1,2,n), （5.3.13）記 于是對(duì)角陣D還可分解稱(chēng)（5.3.13）式為矩陣A的喬累斯基(Cholesky)分解。利用A的Cholesky分解式來(lái)求解方程組Ax=b的方法稱(chēng)為Cholesky方法或平方根法，這是因?yàn)橛?jì)算過(guò)程含開(kāi)方運(yùn)算。 下面我們用直接分解方法來(lái)確定計(jì)算L元素的遞推公式。因?yàn)?其中l(wèi)ii0(i=1,2,n)由矩陣乘法及l(fā)jk=0(當(dāng)jk),得于是得到解對(duì)稱(chēng)正定方程組Ax=b的平方根法計(jì)算公式：（5.3

8、.15）（5.3.14）對(duì)于 j=1,2,n, 按逐列計(jì)算L的元素的計(jì)算步驟,設(shè)第1列至第j-1列已經(jīng)計(jì)算得到,則有 平方根法的原理基于矩陣的LU分解,所以它也是Gauss消去法的變形.但由于利用了矩陣正定的性質(zhì),減少了計(jì)算量。平方根法的乘除法運(yùn)算次數(shù)為(n3+9n2+2)/6,加減法次數(shù)為(n3+6n2-7n)/6 。另外還有n次開(kāi)方運(yùn)算，其所含乘除法和加減法次數(shù)可分別看成n的常數(shù)倍。平方根需n3 /6次乘除法，與Gauss消去法相比減少了一半。3. 求解Ax=b，即求解兩個(gè)三角形方程組 (1)Ly=b，求y； （2）LTx=y，求x 解 不難驗(yàn)證系數(shù)矩陣是對(duì)稱(chēng)正定的，按（5.3.14）和（5.3.15）依次計(jì)算得 例5.6 用平方根法求解解Ly=(6, -0.5, 1.25)T ,得y=(3, 0.5, -1) T ，再解LTx=y可以得到x=(2,1,-1)T 。 （5.3.14）則可避免開(kāi)方根運(yùn)算，稱(chēng)為改進(jìn)的平方根法。 它既適合于求接對(duì)稱(chēng)正定方程組，也適合于求解A對(duì)稱(chēng)且其順序主子式全不為零的方程組。分解式的計(jì)算公式為(j=1,2,n) 如果對(duì)矩陣采用定理4.7的（5.3.12）分解式， 即其中j=1時(shí)，求和部分為零。這樣求解方程組Ax=b化為求解Ly=b和LTx=D-1y.4.改進(jìn)的平方根法解Ly=b得y=(6,1,