數(shù)值分析第2章_解線性方程組的直接法

1、數(shù)值分析數(shù)值分析1第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分第第3 3章章 解線性方程組的直接法解線性方程組的直接法&3.1 Gauss消去法消去法&3.2 LU分解分解&3.3 三對角方程組的追趕法三對角方程組的追趕法Direct Methods for Solving Linear Systems求解求解bxA 數(shù)值分析數(shù)值分析2第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分其中其中 本章討論本章討論n元線性方程組元線性方程組 nnnnnnnnnnbxaxaxabxaxa

2、xabxaxaxa.22112222212111212111的解法。的解法。 Ax=b111212122212.,.nnnnnnaaaaaaAaaa 12,nxxxx 12nbbbb 方程組的矩陣形式為方程組的矩陣形式為 數(shù)值分析數(shù)值分析3第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分求解求解,n nA xb AR 0det( )A 克萊姆克萊姆（Cramer法則）法則）: :1 2, ,iiDxinD所需乘除法的運(yùn)算量大約為所需乘除法的運(yùn)算量大約為(n+1)!+nn=20時(shí)，每秒時(shí)，每秒1億億次運(yùn)算速度的計(jì)算機(jī)要算次運(yùn)算速度的計(jì)算機(jī)要算30多萬年

3、！多萬年！其中，其中，D=det(A), Di 是用向量是用向量b 代替代替A的第的第i 列后所得矩陣的列后所得矩陣的行列式。行列式。數(shù)值分析數(shù)值分析4第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分 所謂直接解法是指若不考慮計(jì)算過程中的舍入誤差，所謂直接解法是指若不考慮計(jì)算過程中的舍入誤差，經(jīng)過經(jīng)過有限次算術(shù)運(yùn)算有限次算術(shù)運(yùn)算就能求出線性方程組的精確解的方法。就能求出線性方程組的精確解的方法。線性方程組線性方程組Ax=b的一般數(shù)值解法的一般數(shù)值解法1.直接法：直接法：適用于低階稠密方程組適用于低階稠密方程組Gauss消去法消去法、三角三角分解法分解

4、法2.迭代法：迭代法：通過構(gòu)造迭代方程組進(jìn)行迭代。通過構(gòu)造迭代方程組進(jìn)行迭代。適用于大型稀疏方程組適用于大型稀疏方程組非零元素較多，非零元素較多，零元素較少零元素較少上萬階，零元素很多，上萬階，零元素很多，非零元素很少非零元素很少 雅克比迭代法雅克比迭代法 賽德爾迭代法賽德爾迭代法數(shù)值分析數(shù)值分析5第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分3.1 Gauss消去法消去法3.1.1 高斯消去法高斯消去法 高斯消元法是一個(gè)古老的直接法高斯消元法是一個(gè)古老的直接法, 由它改進(jìn)得到的選主由它改進(jìn)得到的選主元法元法, 是目前計(jì)算機(jī)上常用于求低階稠密矩陣方

5、程組的有效是目前計(jì)算機(jī)上常用于求低階稠密矩陣方程組的有效方法方法, 其特點(diǎn)就是通過消元將其特點(diǎn)就是通過消元將一般線性方程組一般線性方程組的求解問題轉(zhuǎn)的求解問題轉(zhuǎn)化為化為三角方程組三角方程組的求解問題。的求解問題。 /* Gaussian Elimination */ 順順序序高高斯斯消消去去法法選選主主元元高高斯斯消消去去法法數(shù)值分析數(shù)值分析6第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分1.1.消元過程：消元過程：用初等行變換將原方程組的系數(shù)矩陣化為用初等行變換將原方程組的系數(shù)矩陣化為 上三角形矩陣（簡稱上三角陣）。上三角形矩陣（簡稱上三角陣）。

6、2.2.回代過程：回代過程：對上三角形方程組的最后一個(gè)方程求解，對上三角形方程組的最后一個(gè)方程求解，將求得的解逐步往上一個(gè)方程代入求解。將求得的解逐步往上一個(gè)方程代入求解。 思思路路首先將首先將A化為上三角陣化為上三角陣/* upper-triangular matrix，再回代求解再回代求解。=1. Gauss（順序）消去法的基本思想（順序）消去法的基本思想不作行交換！不作行交換！ 數(shù)值分析數(shù)值分析7第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分 例例3-1 用消去法解方程組用消去法解方程組 1231231232241239222333 ( )

7、( )( )xxxxxxxxx 第第2步步. 回代過程回代過程 解解121231( ) ( ) ()( ) ( ) 第第1步步. 消元過程，對增廣矩陣進(jìn)行消元消元過程，對增廣矩陣進(jìn)行消元 得等價(jià)的三角形方程組得等價(jià)的三角形方程組 1232332241527222121355( ) ()()xxxxxx 解為解為 2 2 1( , ) .Tx 212412392233 2124502720157 5322( ) ( ) 21245027221210055 數(shù)值分析數(shù)值分析8第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分記記,)()1()1(nnija

8、AA 1( )bb Step 1：設(shè)設(shè) ，計(jì)算因子，計(jì)算因子1110( )a )., 2(/)1(11)1(11niaamii 將增廣矩陣將增廣矩陣/* augmented matrix */第第 i 行行 mi1 第第1 1行行，得到得到)1(1)1(1)1(12)1(11.baaan)2(A) 2(b).,2,()1(11)1()2()1(11)1()2(njibmbbamaaiiijiijij 其中其中Step k：設(shè)設(shè) ，計(jì)算因子，計(jì)算因子且計(jì)算且計(jì)算0( )kkka )., 1(/)()(nkiaamkkkkikik )., 1,()()()1()()()1(nkjibmbbamaa

9、kkikkikikkjikkijkij 共進(jìn)行共進(jìn)行 ？ 步步n 1 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa2. 2. 計(jì)算步驟計(jì)算步驟消元消元數(shù)值分析數(shù)值分析9第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分回代回代)()(/nnnnnnabx ) 1., 1()(1)()( niaxabxiiinijjiijiii數(shù)值分析數(shù)值分析10第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分3. 3. 使用條件使用條件高斯消去法能按順序

10、進(jìn)行到底的充要條件是高斯消去法能按順序進(jìn)行到底的充要條件是 在原方程組的系數(shù)矩陣中如何反映出這個(gè)條件呢在原方程組的系數(shù)矩陣中如何反映出這個(gè)條件呢? ?( )0,1,2,kkkaknA的的k階順序主子矩陣階順序主子矩陣Ak的行列式的行列式 (1)1112111121(2)(2)21222(1)(2)( )2221122( )120det00kkkkkkkkkkkkkkkaaaaaaaaaaaAa aaaaaa，nk, 2 , 1 定理定理 若若A的所有的所有順序主子式順序主子式 /* determinant of leading principal submatrices */均不為均不為0，則

11、高斯消元無需換行即可，則高斯消元無需換行即可進(jìn)行到底，得到唯一解。進(jìn)行到底，得到唯一解。iiiiiaaaaA.)det(1111 使用條件之一使用條件之一 數(shù)值分析數(shù)值分析11第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分 n階矩陣階矩陣A為為嚴(yán)格對角占優(yōu)矩陣嚴(yán)格對角占優(yōu)矩陣是指其每個(gè)主對是指其每個(gè)主對角元的絕對值大于同一行其他元素絕對值之和，即角元的絕對值大于同一行其他元素絕對值之和，即11 2, ,niii jjjiaain 一階嚴(yán)格對角占優(yōu)矩陣指一個(gè)非零數(shù)。一階嚴(yán)格對角占優(yōu)矩陣指一個(gè)非零數(shù)。 定理定理 方程組系數(shù)矩陣方程組系數(shù)矩陣A為嚴(yán)格對角

12、占優(yōu)矩陣則可實(shí)為嚴(yán)格對角占優(yōu)矩陣則可實(shí)現(xiàn)用順序高斯消去法求解?，F(xiàn)用順序高斯消去法求解。使用條件之二使用條件之二 數(shù)值分析數(shù)值分析12第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分由于計(jì)算機(jī)中乘除由于計(jì)算機(jī)中乘除 運(yùn)算的時(shí)間遠(yuǎn)遠(yuǎn)超過加減運(yùn)算的時(shí)間，運(yùn)算的時(shí)間遠(yuǎn)遠(yuǎn)超過加減運(yùn)算的時(shí)間，故估計(jì)某種算法的運(yùn)算量時(shí)，往往只估計(jì)故估計(jì)某種算法的運(yùn)算量時(shí)，往往只估計(jì)乘除的次數(shù)乘除的次數(shù)，而且，而且通常以乘除次數(shù)通常以乘除次數(shù)的的最高次冪最高次冪為運(yùn)算量的為運(yùn)算量的數(shù)量級數(shù)量級。 高斯消去法高斯消去法:Step k：設(shè)設(shè) ，計(jì)算因子，計(jì)算因子且計(jì)算且計(jì)算0)( kk

13、ka)., 1(/)()(nkiaamkkkkikik )., 1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij 共進(jìn)行共進(jìn)行n 1步步 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa)()(/nnnnnnabx ) 1., 1()(1)()( niaxabxiiinijjiijiii(n k) 次次(n k)2 次次(n k) 次次(n k) (n k + 2) 次次nnnknknnk6523)2)(2311 消元乘除次數(shù)：消元乘除次數(shù)：1 次次(n i +1) 次次22)1

14、(1211nninni 回代乘除次數(shù)：回代乘除次數(shù)：高斯消去法的總乘除次數(shù)為高斯消去法的總乘除次數(shù)為 ，運(yùn)算量為，運(yùn)算量為 級。級。nnn31323 33n4. 4. 計(jì)算量計(jì)算量數(shù)值分析數(shù)值分析13第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分Gauss消去法算法消去法算法kkikikikaama/ nkj,1 .*kjikijijamaa kikiibmbb* 消元計(jì)算消元計(jì)算 nki,1 for 1,2,1 nkfor for 回代求解回代求解 nnnnabb/ 1 ,2,1 ni *iiijjbbab for /iiiibba1,jin f

15、or 數(shù)值分析數(shù)值分析14第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分3.1.2 高斯列主元消去法高斯列主元消去法 為避免這種情況的發(fā)生為避免這種情況的發(fā)生, 可通過交換方程的次可通過交換方程的次序，選取絕對值大的元素作主元序，選取絕對值大的元素作主元. 基于這種思想導(dǎo)基于這種思想導(dǎo)出了主元素法出了主元素法在在高斯消去法消去過程中可能出現(xiàn)高斯消去法消去過程中可能出現(xiàn) 的情況，的情況，這時(shí)高斯消去法將無法進(jìn)行；即使主因素這時(shí)高斯消去法將無法進(jìn)行；即使主因素 但但很小很小，其作除數(shù)，其作除數(shù) ，也會(huì)導(dǎo)致其它元素?cái)?shù)量級的，也會(huì)導(dǎo)致其它元素?cái)?shù)量級的嚴(yán)重增

16、長和舍入誤差的擴(kuò)散嚴(yán)重增長和舍入誤差的擴(kuò)散.( )0kkka( )0kkka/* Pivoting Strategies */數(shù)值分析數(shù)值分析15第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分例例 單精度解方程組單精度解方程組 211021219xxxx/* 精確解為精確解為 和和 */.1000.00. 1101191 x8個(gè)個(gè).8999.99. 0212 xx8個(gè)個(gè)用高斯消元法計(jì)算：用高斯消元法計(jì)算：911212110/ aam999212210101010.0 . 011 ma8個(gè)個(gè)92121012 mb 9991010011100, 112

17、 xx小主元小主元 可能導(dǎo)致計(jì)算可能導(dǎo)致計(jì)算失敗。失敗。數(shù)值分析數(shù)值分析16第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分 完完全主元消去法全主元消去法/* Complete Pivoting */每一步選絕對值最大的元素為主元素，保證每一步選絕對值最大的元素為主元素，保證1| ikmStep k: 選取選取;0|max|, ijnjikjiaakk If ik k then 交換第交換第 k 行與第行與第 ik 行行; If jk k then 交換第交換第 k 列與第列與第 jk 列列; 消元消元列交換改變了列交換改變了 xi 的順序，須記錄的

18、順序，須記錄交換次序交換次序，解完后，解完后再換回來。再換回來。選主元時(shí)要花費(fèi)較多機(jī)器時(shí)間選主元時(shí)要花費(fèi)較多機(jī)器時(shí)間數(shù)值分析數(shù)值分析17第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分 列主元消去法列主元消去法/* Partial Pivoting */省去換列的步驟，每次僅選一列中最大的元。省去換列的步驟，每次僅選一列中最大的元。0|max|, iknikkiaak例：例： 211111091,112 xx 110211 11102119 列主元法沒有全主元法穩(wěn)定。列主元法沒有全主元法穩(wěn)定。0,112 xx例：例： 2111010199 99991

19、010010101注意：這兩個(gè)方程組注意：這兩個(gè)方程組在數(shù)學(xué)上在數(shù)學(xué)上嚴(yán)格等價(jià)嚴(yán)格等價(jià)。 數(shù)值分析數(shù)值分析18第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分定理定理 系數(shù)矩陣為對稱嚴(yán)格對角占優(yōu)，則系數(shù)矩陣為對稱嚴(yán)格對角占優(yōu)，則 全是主元。全是主元。( ),1,2,kkkakn (1)(2)( )1122det( 1)mnnnAa aa 列主元法的消元列主元法的消元過程過程 計(jì)算過程有計(jì)算過程有2次行交換，故次行交換，故m=2，主元為主元為5，-1.6，2 det A=(-1)25(-1.6)2=16 m為消元過程中交換行的次數(shù)。為消元過程中交換行的

20、次數(shù)。3 5 4 5 7 34 4 2A573201.60.40.40022列主元消去法常用來求行列式列主元消去法常用來求行列式數(shù)值分析數(shù)值分析19第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分3.2 LU分解分解定義定義3-1 若若n階矩陣階矩陣A可分解為一個(gè)可分解為一個(gè)下三角矩陣下三角矩陣 L 和一個(gè)和一個(gè)上三角上三角矩陣矩陣U 的乘積，即的乘積，即A=LU則稱這種分解為方陣則稱這種分解為方陣A的一種的一種 LU 分解分解，通常也稱為方陣，通常也稱為方陣A的的三三角分解法角分解法。1o 若若L為單位下三角矩陣，則稱為為單位下三角矩陣，則稱為A的

21、的Doolittle分解；分解；2o 若若U為單位上三角矩陣，則稱為為單位上三角矩陣，則稱為A的的Crout分解。分解。MMAUU 單單位位下下三三角角陣陣高高斯斯消消元元法法上上三三角角陣陣1LM 記記), 2 , 1(0)(nkakkkA的順序主子式不為零什么條件下存在什么條件下存在LU分解？分解？數(shù)值分析數(shù)值分析20第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分201 ,(, , ),.kDLULUAnAknA 順順序序主主子子式式單單位位下下三三角角矩矩陣陣矩矩陣陣的的分分解解設(shè)設(shè) 為為 階階矩矩陣陣 如如果果 的的則則 可可分分解解為為一

22、一個(gè)個(gè)和和上上三三角角矩矩一一個(gè)個(gè)單單位位的的乘乘積積，且且這這種種分分解解是是唯唯一一陣陣的的定定理理3 32 2) )- - ( (例例 設(shè)設(shè) 討論討論a 取何值時(shí)，矩陣取何值時(shí)，矩陣A可作可作LU 分解分解。 12 21aA解解 當(dāng)當(dāng)A的順序主子式不為零，矩陣的順序主子式不為零，矩陣A有有LU 分解分解。 所以，有所以，有10a (1)2 20a 1a 3a 數(shù)值分析數(shù)值分析21第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分 非奇異矩陣不一定存在非奇異矩陣不一定存在LU分解。分解。0110A解解 A是是非奇異矩陣，假設(shè)有非奇異矩陣，假設(shè)有LU

23、分解分解01101010bdac 比較等式兩端第比較等式兩端第1列，可得列，可得 上二式不能同時(shí)成立，即非奇異矩陣上二式不能同時(shí)成立，即非奇異矩陣A不存在不存在LU分解。分解。0,b 1ab 例例 數(shù)值分析數(shù)值分析22第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分3.2.1 Doolittle（杜利特爾）分解（杜利特爾）分解 Doolittle Factorization直接直接LU分解法分解法通過比較法直接導(dǎo)出通過比較法直接導(dǎo)出L 和和 U 的計(jì)算公式。的計(jì)算公式。思思路路 nnnnnnnnuuullaaaa.1.11.1111211111 ),

24、min(1jikjkkiul jia L、U 的元素的確定的元素的確定111 2(, , ),iiuain ), 2(/,11111111niualulaiiii 得得U 的第的第1行元素行元素得得L 的第的第1列元素列元素?cái)?shù)值分析數(shù)值分析23第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分 ),min(1jikjkkijiula固定固定 i : :對對 j = i, i+1, , n 有有ijkjikikijuula 11lii = 1kjikikijijulau 11將將 i ，j 對換，對對換，對 j = i, i+1, , n 有有iijik

25、iikjkjiulula 11iiikkijkjijiuulal/ )(11 2, 3, , kn對對計(jì)計(jì)算算數(shù)值分析數(shù)值分析24第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分111213212223313233 2 2 31 4 7 7 1 25uuuALlUuullu， 4 1 例例1112132131222221 12232321 13323231 1222333331 1332233421 ,2,2,3,2,1222,72 23,72 3111()(4( 1)2)233,5( 1)32 16nruuullrual uual ulal uur

26、ual ul u Doolittle Factorization數(shù)值分析數(shù)值分析25第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分LU分解求解線性方程組分解求解線性方程組 , AXbLUXbLYbUXY 112122313211(1)111211122222111 1nnn nnnnnnnnnyblybllLYblllybuuuxyuuxyUXYuxy三三角角方方程程組組數(shù)值分析數(shù)值分析26第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分11-11 , 2, 3, , (1) iiijijjinYybyy

27、bl解解 ： 1 , 1, , 1 2 nnnnniijjiiij iinyXxuyxu xu（ ）解解 ：對方程組求解對方程組求解, ,只要得到了系數(shù)矩陣的三角分解形只要得到了系數(shù)矩陣的三角分解形式式, ,再利用再利用前代前代算法和算法和回代回代算法解兩個(gè)三角方程組算法解兩個(gè)三角方程組即得即得. .P計(jì)算量計(jì)算量乘除法大約乘除法大約n33 3次，和高斯消去法計(jì)算量基本相同次，和高斯消去法計(jì)算量基本相同. . 每解一個(gè)方程組每解一個(gè)方程組Ax=b，僅需要僅需要增加增加n2次乘除法運(yùn)算次乘除法運(yùn)算. . 數(shù)值分析數(shù)值分析27第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月1

28、4日日7時(shí)時(shí)22分分例例 用用LU分解法求解方程組分解法求解方程組123123123223347712457xxxxxxxxx 解解 先對系數(shù)矩陣進(jìn)行先對系數(shù)矩陣進(jìn)行LU分解分解 A=LU 100223210031121006LU，求解兩個(gè)三角形方程組，求解兩個(gè)三角形方程組， , bLy yUx 得得11212332127yyyyyy 12323322333566xxxxxx 123356yyy 321122xxx 數(shù)值分析數(shù)值分析28第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分 例例 用三角分解法解用三角分解法解 .20181451325232

29、1321xxx解解,11111 au,21/2/112121 ual,122512212222ulau,21212 au,31313 au31/3/113131ual,432213212323ulau,51/)231(/)(2212313232uulal.24)4()5(335233213313333ululau2400410321153012001A.LU從而從而求解求解 ,)20,18,14(TyL,)72,10,14(TxU,)72,10,14(Ty得得求解求解.)3,2, 1(Tx 得得數(shù)值分析數(shù)值分析29第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7

30、時(shí)時(shí)22分分例例 用三角分解法用三角分解法 求解下列方程組求解下列方程組123412312341346262414535xxxxxxxxxxxxxx 解解 系數(shù)矩陣系數(shù)矩陣6211241011411 013A 131616 6211 1032313151103710910 937 19174111311165911161037L 62111021333379101019174U 6323519174y 1111x 數(shù)值分析數(shù)值分析30第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分選主元的三角分解法選主元的三角分解法 直接三角分解當(dāng)直接三角分解當(dāng) 時(shí)

31、計(jì)算將中斷，時(shí)計(jì)算將中斷，0rru當(dāng)當(dāng) 絕對值很小時(shí)，計(jì)算可能引起舍入誤差的累積絕對值很小時(shí)，計(jì)算可能引起舍入誤差的累積. . rru如果如果 非奇異，可通過交換非奇異，可通過交換 的行實(shí)現(xiàn)矩陣的行實(shí)現(xiàn)矩陣 的的 分解分解. .AAPALU直接三角分解法直接三角分解法( )0(1,2, )kkkakn不滿足不滿足列主元所在行與第列主元所在行與第k行交換行交換乘以初等交換陣乘以初等交換陣數(shù)值分析數(shù)值分析31第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分3.2.2 Crout（）分解）分解,LUA 111211112121222212221212111

32、.nnnnnnnnnnnnaaaluuaaalluAaaalll 假設(shè)假設(shè)其中其中L為下三角矩陣，為下三角矩陣， U為單位上三角矩陣，為單位上三角矩陣，Crout Factorization數(shù)值分析數(shù)值分析32第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分3.2.3 Cholesky（楚列斯基楚列斯基）分解）分解平方根法平方根法定義定義3-2 若矩陣若矩陣 ,nnAR 滿滿 足足2( ) A的的各各階階順順序序主主子子式式都都為為正正 (1) , TAA 則稱則稱A為對稱正定矩陣。為對稱正定矩陣。例例 判判斷斷矩矩陣陣410141014A 的的正正

33、定定性性。 解解 TAA， A為為對對稱稱矩矩陣陣， 即即A為為對對稱稱正正定定矩矩陣陣。 140A ，24 411150()()A ，3560A 數(shù)值分析數(shù)值分析33第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分A為為對稱正定陣，則存在唯一的對稱正定陣，則存在唯一的LU分解分解U =uij=u11uij / uii111u22unn記為記為UD A 對稱對稱TUL 即即TLDLA 記記 D1/2 =11u22unnu2/1LDL 則則 仍是下三角陣仍是下三角陣TLLA nnRL 定理定理 設(shè)矩陣設(shè)矩陣A對稱正定，則存在非奇異下三角陣對稱正定，則存

34、在非奇異下三角陣 使得使得 。若限定。若限定L對角元為正，則分解唯一。對角元為正，則分解唯一。TLLA 11211112322222111nnuuuuuuuu數(shù)值分析數(shù)值分析34第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分3353595917A例：例：對矩陣對矩陣 進(jìn)行楚列斯基分解。進(jìn)行楚列斯基分解。解：解： A為對稱矩陣，且為對稱矩陣，且12330,6040AAA ， A對稱正定。對稱正定。1i 11113la 131221311111352,3,33aajljlll 1112111112112122221222221212nnnnnnnnnn

35、nnnnaaallllaaallllaaallll數(shù)值分析數(shù)值分析35第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分332522 233L2222333331325217()(2 2)33lall3,i 2i ，2222221532lal 3j ，323231 2122151()(93)2 232lal ll 3353595917A1111211212222212nnnnnnnnllllllllllll數(shù)值分析數(shù)值分析36第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分矩陣矩陣LLT分解的實(shí)際計(jì)算公式：分

36、解的實(shí)際計(jì)算公式：1 2kn , ,for12,jkkn for12,ikkn forikikkkaaa mjmjmkjkaaaa 1mj jn ,forkkkkaa 數(shù)值分析數(shù)值分析37第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分解解61410242212231212312112312 064171024424321321321xxxxxxxxx 例例 解線性方程組解線性方程組 113212112312A1232413172110,yyy 解解123251yyy 得得123212231511xxx 再再解解，123121xxx 得得212 21

37、23 21231 數(shù)值分析數(shù)值分析38第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分 Cholesky分解法求解方程組中需說明的幾個(gè)問題分解法求解方程組中需說明的幾個(gè)問題工作量：約為工作量：約為LU分解的分解的一半一半； 不必選主元：不必選主元：A的的正定性正定性和算法的和算法的穩(wěn)定性穩(wěn)定性穩(wěn)定性：是數(shù)值穩(wěn)定的；穩(wěn)定性：是數(shù)值穩(wěn)定的；()ikiilaik缺陷：存在缺陷：存在開平方開平方運(yùn)算。運(yùn)算。改進(jìn)方法：改進(jìn)方法： LDLT 分解分解改進(jìn)的平方根法改進(jìn)的平方根法數(shù)值分析數(shù)值分析39第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5

38、月月14日日7時(shí)時(shí)22分分 改進(jìn)的平方根法改進(jìn)的平方根法 避免開方運(yùn)算避免開方運(yùn)算TAL D L 即即 1212122112111111.nnnnnldldllAdll .1112121221122111 nnnnnllldldlddlddA nkkjTikijLLDa1)()( nkjkkikldl1 11.jkjjjijjkkikldlldl數(shù)值分析數(shù)值分析40第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分 l.l. );1,2, 1(/11ijdldlaljjkjkkikijijni,2,1 對于對于 2.2. .112ikkikiiidla

39、d引進(jìn)引進(jìn) ,jijijdlt按行計(jì)算按行計(jì)算 元素的公式：元素的公式： TL ,111ad 1.1. );1,2, 1(11ijltatjkjkikijij 2.2. );1,2, 1(/ijdtljijij 3.3. 11ikikikiiiltadni,3,2 對于對于 ,TTLA nkkjTikijLLDa1)()( nkjkkikldl1 11.jkjjjijjkkikldlldl數(shù)值分析數(shù)值分析41第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分3nt2nt1nt32t31t21t1dStep12dStep23dStep321l31l1nl

40、32l2nl3nlndStepn 333231222111aaaaaaA對對稱稱 332312211dlldld 33323122211aaaatd 3332312211attdld 3332312211aaadld元素的儲(chǔ)存比消去法節(jié)省一半，但比平方根法多用一個(gè)單元內(nèi)存，元素的儲(chǔ)存比消去法節(jié)省一半，但比平方根法多用一個(gè)單元內(nèi)存， LDLT的計(jì)算順序的計(jì)算順序數(shù)值分析數(shù)值分析42第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分 LDLT分解公式：分解公式：Axb TLDL xb TLybDL xy 求解方程組求解方程組等價(jià)方程組等價(jià)方程組1TLybL

41、 xD y 11112 3, ,iiainaa for1 21ji , ,for11imimkkkmiiiaavaa ()jijjjva a 11iiiiiikkkaaa v 12miin ,for數(shù)值分析數(shù)值分析43第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分; 1, 1111 adi, 1, 22121 ati; 2, 1/212122212121 ltaddtl, 1, 1, 3213132323131 ltatati; 3, 5 . 0/, 1/323231313332323213131 ltltaddtldtl 15 . 01111L

42、321D 128415 . 01111321yyy 644321yyy 64415 . 01111321321xxx 211321xxx12311141328 .12 4.512xxx 例例 用用LDLT解方程組解方程組解解數(shù)值分析數(shù)值分析44第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分12311141328 .12 4.512xxx 例例 用用LDLT解方程組解方程組解解 5 . 421231111 1 211 3211211 15 . 01111L 321D 128415 . 01111321yyy 644321yyy 64415 . 011

43、11321321xxx 211321xxx數(shù)值分析數(shù)值分析45第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分3.3 三對角方程組的追趕法三對角方程組的追趕法系數(shù)矩陣為對角占優(yōu)的三對角線方程組系數(shù)矩陣為對角占優(yōu)的三對角線方程組,12112111122211 nnnnnnnnnffffxxxxbacbacbacb簡記為簡記為 .A xf 其中，當(dāng)其中，當(dāng) 且：，,01時(shí)ijaji 0; 1 cba1)();1,3 ,2(0,)( nicacabbiiiii, 0. nnabc)(LU分解會(huì)是什么樣子？分解會(huì)是什么樣子？數(shù)值分析數(shù)值分析46第第3章章 解

44、線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分,LUA 其中其中L為下三角矩陣，為下三角矩陣，U為單位上三角矩陣為單位上三角矩陣. . 由系數(shù)陣由系數(shù)陣A的特點(diǎn)，可以將的特點(diǎn)，可以將A分解為兩個(gè)三角陣的乘積，分解為兩個(gè)三角陣的乘積，即即 設(shè)設(shè) nnnnnbacbacbacbA11122211,11111221 nnn 其中其中 為待定系數(shù)為待定系數(shù). . iii,由矩陣乘法由矩陣乘法,11111 cb )1,2(niciii ),2(,1nibaiiiiii 或分解為：或分解為：L為單位下三角矩陣，為單位下三角矩陣，U為上三角矩陣為上三角矩陣. . 數(shù)值分析數(shù)值

45、分析47第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分計(jì)算公式計(jì)算公式1111111, bcc b1iiiiba 1 iiiiiiiccba 1nnnnba i = 2, 3, , n-1求解求解 等價(jià)于求解兩個(gè)三角形方程組：等價(jià)于求解兩個(gè)三角形方程組： ,fAx ;,)1(yfLy求.,)2(xyUx求數(shù)值分析數(shù)值分析48第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分三對角線方程組的三對角線方程組的追趕法公式追趕法公式： 1. 1. 計(jì)算計(jì)算 的遞推公式的遞推公式 i111/bc);1,3,2()/(

46、1niabciiiii 2. 2. 解解 fLy ,/111bfy );,3,2()/()(11niabyafyiiiiiii 3. 3. 解解 yUx ,nnyx).1 ,2,2,1(1nnixyxiiii121nnyyy21趕：趕：11xxxnn追：追：數(shù)值分析數(shù)值分析49第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分 解解2112112112A 12 3111232 111232232 111123223432 11112322334342 1111232233434542 1122 111123223433454211A11 所所以以123

47、411121121021020 xxxx 例例3-7 應(yīng)用追趕法求解線性方程組應(yīng)用追趕法求解線性方程組數(shù)值分析數(shù)值分析50第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分123411132435421000yyyy 解解方方程程，123412131415yyyy 得得1234112212331344151111xxxx 再再解解方方程程，123445352515xxxx 得得數(shù)值分析數(shù)值分析51第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分 解解 3123123123A 13 11331132 11311

48、631132 1113113911631132 11133922113911631132 3913939221139116311321113 1332 11111113A392211632391391139311所以所以 91511731231231234321xxxx例例11 解線性方程組解線性方程組數(shù)值分析數(shù)值分析52第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分小小 結(jié)結(jié)數(shù)值分析數(shù)值分析53第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分矩陣三角分解法矩陣三角分解法高斯消去過程實(shí)現(xiàn)了高斯消去過程實(shí)現(xiàn)

49、了A的一個(gè)三角因子分解的一個(gè)三角因子分解A=LU，其中其中L一個(gè)單位下三角陣，一個(gè)單位下三角陣， U為為上三角陣上三角陣. .此分解此分解稱為稱為A的的Doolittle分解分解.定理定理 若若A的所有順序主子式的所有順序主子式 均不為均不為0，則，則 A 的的 LU 分解唯一（其中分解唯一（其中 L 為為單位單位下三角陣）。下三角陣）。nnRL 定理定理 設(shè)矩陣設(shè)矩陣A對稱正定，則存在非奇異下三角陣對稱正定，則存在非奇異下三角陣 使得使得 。若限定。若限定 L 對角元為正，則分解對角元為正，則分解唯一。這種分解稱為平方根分解或喬累斯基分解。唯一。這種分解稱為平方根分解或喬累斯基分解。TLLA

50、 數(shù)值分析數(shù)值分析54第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分直直 接接 法法 的的MATLAB 用用 法法1. 求求解解bAx bAx ，輸出方程的解x. 2. LU分分解解 使用列主元素消元法進(jìn)行。u =chol(A)： 對 正 定 對 稱 矩 陣 A 的 Cholesky 分解 ， 輸 出 u 為 上 三 角 陣 U， 使 A=UTU x,y=lu(A)： 輸出x為一交換陣與單位下三角陣 之積L，y 為上三角陣U，使LUA. . x,y,p=lu(A)：輸出 x 為單位下三角陣 L，y 為 上三角陣 U，p 為一交換陣 P，使LUPA . . 數(shù)值分析數(shù)值分析55第第3章章 解線性方程組的直接法解線性方程組的直接法2022年年5月月14日日7時(shí)時(shí)22分分分析：分析：（1）若A可逆,則PA可分解為一個(gè)單位下三角陣L 和一 個(gè)上三角陣U 的積 PA=LU 這種分解是唯一的，稱矩陣LU分解。 P由單位陣經(jīng)若干 次行交換得到。 （2）解矩陣方程Ax=b, 則 PAx=Pb 即 LU x=Pb 例例(1) 將矩陣A進(jìn)行LU分解, (2) 解矩陣方程Ax=b,4321,98754113211143214321bA其中bLPUx111)(LPbLx1111-1L ,U其中數(shù)值分析數(shù)值分析56第第3章章 解線性方程組的直接法解線性方