第三章解線(xiàn)性方程組的直接法PPT課件

1、nnnnnnnnbbbbxxxXaaaaaaaaaA2121212222111211nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111（3.1） 1 1三角形方程組的解法三角形方程組的解法nnnnnnbxaxaxabxaxabxa221122221211111 （3.2）nnnnnnnnbxabxaxabxaxaxa2222211212111（3.3） 2 2高斯消去法高斯消去法1,3322111, 223232221211, 11313212111nnnnnnnnnnnnnnaxaxaxaxaaxaxaxaxaaxaxaxaxankinkj

2、aaaankkjaaakkjkikkijkijkkkkkjkkj, 11, 11, 1,)()1()1()()1()1()(1 , 1 1)()(1,)(1,nkxaaxaxnkjjkkjknkknnnn列主元消去法計(jì)算步驟：列主元消去法計(jì)算步驟：1、輸入矩陣階數(shù)輸入矩陣階數(shù)n，增廣矩陣增廣矩陣 A(n,n+1);2、對(duì)于對(duì)于nk, 2 , 1(1) 按列選主元：選取按列選主元：選取 l 使使 0maxikniklkaa(2) 如果如果 ，交換，交換 A(n,n+1) 的第的第k行與底行與底l 行元素行元素kl (3) 消元計(jì)算消元計(jì)算 ：nkiaamkkikik, 1 1, 1 , 1, n

3、kjnkiamaakjikijij3、回代計(jì)算回代計(jì)算1 , 1, 11,nnixaaxnijjijnii4 4無(wú)回代過(guò)程的主元消去法無(wú)回代過(guò)程的主元消去法算法：算法：第一步：選主元，在第一列中選絕對(duì)值最大的元素，設(shè)第第一步：選主元，在第一列中選絕對(duì)值最大的元素，設(shè)第k行為主元行，行為主元行， 將主元行換至第一行，將第一個(gè)方程中將主元行換至第一行，將第一個(gè)方程中x1的系數(shù)變?yōu)榈南禂?shù)變?yōu)?，并從，并從 其余其余個(gè)方程中消去個(gè)方程中消去x1。第二步：在第二列后第二步：在第二列后n 1個(gè)元素中選主元，將第二個(gè)方程中個(gè)元素中選主元，將第二個(gè)方程中x2的的 系數(shù)變?yōu)橄禂?shù)變?yōu)?，并從其它，并從其它個(gè)方程中

4、消去個(gè)方程中消去x2。第第k步：在第步：在第k列后列后n k個(gè)元素中選主元，換行，將第個(gè)元素中選主元，換行，將第k個(gè)方程個(gè)方程xk的系數(shù)的系數(shù) 變?yōu)樽優(yōu)?，從其它，從其它個(gè)方程中消去變量個(gè)方程中消去變量xk，nkkinkkjaaaankkjaaakkjkikkijkijkkkkkjkkj, 1, 1, 11, 1,1, 1,)()1()1()()1()1()(消元公式為：消元公式為：對(duì)對(duì)k = 1, 2, , 按上述步驟進(jìn)行到第按上述步驟進(jìn)行到第n步后，方程組變?yōu)椋翰胶?，方程組變?yōu)椋?(1,)(1, 22)(1, 11nnnnnnnnaxaxax即為所求的解即為所求的解5無(wú)回代消去法的應(yīng)用無(wú)回

5、代消去法的應(yīng)用（1）解線(xiàn)性方程組系解線(xiàn)性方程組系設(shè)要解的線(xiàn)性方程組系為：設(shè)要解的線(xiàn)性方程組系為：AX = b1, AX = b2, AX = bmniaaabxxXaaaaAinninininnnnn, 2, 1)(1,)(1, 2)(1, 111111上述方程組系可以寫(xiě)為上述方程組系可以寫(xiě)為AX = B = (b1, , bm)因此因此X = A-1B 即為線(xiàn)性方程組系的解。即為線(xiàn)性方程組系的解。 在計(jì)算機(jī)上只需要增加幾組右端常數(shù)項(xiàng)的存貯單元，在計(jì)算機(jī)上只需要增加幾組右端常數(shù)項(xiàng)的存貯單元，其結(jié)構(gòu)和解一個(gè)方程組時(shí)一樣。其結(jié)構(gòu)和解一個(gè)方程組時(shí)一樣。行行n21nnnnnnaaaaaaaaa2122

6、22111211)(1,)1(1,)(1,2)1(1,2)(1, 1)1(1, 1mnnnnmnnmnnaaaaaa系數(shù)系數(shù)右端右端（2）求逆矩陣求逆矩陣設(shè)設(shè)A = (aij)n n是非奇矩陣是非奇矩陣，A 0，且令且令nnijXAX)(1由于由于 AA-1 = AX = I因此，求因此，求A-1的問(wèn)題相當(dāng)于解下列線(xiàn)性方程組的問(wèn)題相當(dāng)于解下列線(xiàn)性方程組1010,0012112111nnnnnxxxAxxxA相當(dāng)于相當(dāng)于（1）中中m = n, B = I 的情形。的情形。 （3）求行列式的值求行列式的值用高斯消去法將用高斯消去法將 A化成化成)()1(11)()2(22)1(11nnnnnnaa

7、aaaA2 2 解三對(duì)角方程組的追趕法解三對(duì)角方程組的追趕法nnnnnnnnnnnnkkkkkkkdxbxadxcxbxadxcxbxadxcxbxadxcxb 111112111232221212111nnnnnkkkbacbacbacbacbA11122211nkarbaydyarbcrbdybcrkkkkkkkkkkkk, 3, 21111111111 , 2, 11nnkxryxyxkkkknn 高斯消元法的矩陣形式高斯消元法的矩陣形式: :Step 1:)0(/111111 aaamii3 矩陣的三角分解及其在解方程組中的應(yīng)用矩陣的三角分解及其在解方程組中的應(yīng)用記記 L1 =1.11

8、121nmm L11 =1.11121nmm記記 AA)1(于是于是)1(1)1(22)1(21)1(1)1(12)1(11)1(11)1(1)1(11)1(21)1(111nnnaAaaaaaaaaLA)1(1111)1(221)1(11)1(2211)1(111)1(111001arcAraAcraIacTTTn)2()2(22)2(12)2(11)2()2(2)2(2)2(22)1(1)1(12)1(110AAAAaaaaaaannnnn)3()3(22)3(12)3(11)2(3322)2(221112)2(222)2(20000001AAAAAcraraIacALTTnTTStep

9、n 1:)()2(2)2(22) 1 (1) 1 (12) 1 (11121.nnnnnnnaaaaaaALLLLk =1.11, 1knkkmm 其中其中 1kL1.11, 1knkkmm 111211.nLLL111jim,記為記為L(zhǎng)記記 U =)()2(2)2(22)1(1)1(12)1(11.nnnnnaaaaaaLUA 定理定理1：（矩陣的三角分解）設(shè)：（矩陣的三角分解）設(shè)A為為n n實(shí)矩陣，如果實(shí)矩陣，如果解解AX = b用高斯消去法能夠完成（限制不進(jìn)行行的交用高斯消去法能夠完成（限制不進(jìn)行行的交換，即換，即 ），則矩陣），則矩陣A可分解可分解為單位下三角矩陣為單位下三角矩陣L與上

10、三角知陣與上三角知陣U的乘積。的乘積。A = LU且這種分解是唯一的。且這種分解是唯一的。nkakkk, 2, 1, 0)(定理定理2：約化主元素：約化主元素（ , i = 1, 2, , k） 充要條件是矩陣充要條件是矩陣A A的順序主子式的順序主子式0)(iiia, 0, 0222112112111aaaaDaD01111kkkkkaaaaD 杜杜立特分解法立特分解法 /* Doolittle Factorization */： LU 分解的緊湊格式分解的緊湊格式反復(fù)計(jì)算反復(fù)計(jì)算,很浪費(fèi)哦很浪費(fèi)哦 通過(guò)比較法直接導(dǎo)出通過(guò)比較法直接導(dǎo)出L 和和 U 的計(jì)算公式。的計(jì)算公式。思思路路 nnnn

11、nnnnuuullaaaa.1.11.1111211111 ),min(1jikjkkiul jia直接三角分解法解直接三角分解法解AX = b的計(jì)算公式的計(jì)算公式niauii, 2 , 111niualii, 2 , 11111對(duì)于對(duì)于r = 2, 3, , n計(jì)算計(jì)算（2）計(jì)算計(jì)算U的第的第r行元素行元素 ), 1,( 11nrriulaurkkirkriri（3）計(jì)算計(jì)算L的第的第r 列元素列元素 (r n), 1()(11nriuulalrrrkkrikirir(1), 3 , 2(111niylbybykikikii) 1, 2, 1(1niuxuyxuyxiiknikikiinnn

12、n(4)(5)4 4 平方根法平方根法1矩陣的矩陣的LDR分解分解定理定理3：如果：如果n階矩陣階矩陣A的所有順序主子式均不等于零，的所有順序主子式均不等于零，則矩陣則矩陣A存在唯一的分解式存在唯一的分解式A = LDR其中其中L和和R分別是分別是n階單位下三角陣和單位上三角陣，階單位下三角陣和單位上三角陣，D是是n階對(duì)角元素階對(duì)角元素的不為零的對(duì)角陣，上述分解也稱(chēng)為的不為零的對(duì)角陣，上述分解也稱(chēng)為A的的LDR分解分解。 2平方根法平方根法如果如果A為對(duì)稱(chēng)正定矩陣為對(duì)稱(chēng)正定矩陣，則存在一個(gè)實(shí)的非奇異則存在一個(gè)實(shí)的非奇異下三角矩陣下三角矩陣，使使A=LLT ，且當(dāng)限定的對(duì)角元素為正時(shí)且當(dāng)限定的對(duì)

13、角元素為正時(shí)，這種分解是唯一的這種分解是唯一的。定理定理4：（對(duì)稱(chēng)正定矩陣的三角分解）（對(duì)稱(chēng)正定矩陣的三角分解）將將對(duì)稱(chēng)對(duì)稱(chēng) 正定陣正定陣 A 做做 LU 分解分解U =uij=u11uij / uii111u22unn記為記為UD A 對(duì)稱(chēng)對(duì)稱(chēng)TUL 即即TLDLA 記記 D1/2 =11u22unnu2/1LDL 則則 仍是下三角陣仍是下三角陣TLLA nnRL 定理定理 設(shè)矩陣設(shè)矩陣A對(duì)稱(chēng)正定，則存在非奇異下三角陣對(duì)稱(chēng)正定，則存在非奇異下三角陣 使得使得 。若限定。若限定 L 對(duì)角元為正，則分解唯一。對(duì)角元為正，則分解唯一。TLLA 對(duì)于對(duì)稱(chēng)正定陣對(duì)于對(duì)稱(chēng)正定陣 A ，從，從 可知對(duì)任意

14、可知對(duì)任意k i 有有 。即即 L 的元素不會(huì)增大，誤差可控，不的元素不會(huì)增大，誤差可控，不需選主元。需選主元。 ikikiila12iiikal |用平方根法解線(xiàn)性代數(shù)方程組的算法用平方根法解線(xiàn)性代數(shù)方程組的算法（1）對(duì)矩陣對(duì)矩陣A進(jìn)行進(jìn)行Cholesky分解分解，即即A=LLT，由矩陣乘法由矩陣乘法：對(duì)于對(duì)于 i = 1, 2, n 計(jì)算計(jì)算21112ikikiiiilal1, 2, 111ijlllaljjjkikikijij（2）求解下三角形方程組求解下三角形方程組 iikikikiilylby11（3）求解求解LTX = y) 1 , 1,(1nnilxlyxiiknikkiii3改

15、進(jìn)平方根法改進(jìn)平方根法 11111112231131222111323121nnnnnllllldddllllAikdlskkikik其中其中11112121222111nnnnnlldssdsd改進(jìn)平方根法解對(duì)稱(chēng)正定方程組的算法改進(jìn)平方根法解對(duì)稱(chēng)正定方程組的算法 11111111,3,2ikikikiiiijjijijkjjkikijijlsaddsllsasniad對(duì)于令令LTX = y，先解下三角形方程組先解下三角形方程組LDY = b得得), 2, 1(11nidyldbyiikikikkkii解上三角形方程組解上三角形方程組LTX = Y得得 ) 1, 2 , 1,(1nnixlyx

16、nikkikii5 5 向量和矩陣的范數(shù)向量和矩陣的范數(shù) 1 1向量的范數(shù)向量的范數(shù)定義定義1 1：設(shè)設(shè)X R n， 表示定義在表示定義在Rn上的一個(gè)實(shí)值函數(shù)上的一個(gè)實(shí)值函數(shù)，稱(chēng)之為稱(chēng)之為X的范數(shù)的范數(shù)，它具有下列性質(zhì)它具有下列性質(zhì)：XaaX（3）三角不等式三角不等式：即對(duì)任意兩個(gè)向量即對(duì)任意兩個(gè)向量X、Y R n，恒有恒有 YXYX(1) (1) 非負(fù)性非負(fù)性：即對(duì)一切即對(duì)一切X R n，X 0, 0(2) (2) 齊次性齊次性：即對(duì)任何實(shí)數(shù)即對(duì)任何實(shí)數(shù)a R，X R n， 設(shè)設(shè)X = (x1, x2, xn)T，則有則有nxxxX211（1）222212nTxxxXXX（2）inixX1m

17、ax（3）三個(gè)常用的范數(shù)：三個(gè)常用的范數(shù)：定理定理5：定義在定義在Rn上的向量范數(shù)上的向量范數(shù) 是變量是變量X分量的分量的 一致連續(xù)函數(shù)一致連續(xù)函數(shù)。 X)(xfX 定理定理6 6：在在Rn上定義的任一向量范數(shù)上定義的任一向量范數(shù) 都與范數(shù)都與范數(shù) 等價(jià)等價(jià)， 即存在正數(shù)即存在正數(shù) M 與與 m ( Mm ) 對(duì)一切對(duì)一切X Rn，不等式不等式X1X11XMXXm成立成立。推論推論：Rn上定義的任何兩個(gè)范數(shù)都是等價(jià)的。上定義的任何兩個(gè)范數(shù)都是等價(jià)的。 111XXXnXnXX1XnXX2對(duì)常用范數(shù)，容易驗(yàn)證下列不等式：對(duì)常用范數(shù)，容易驗(yàn)證下列不等式： 定義定義2：設(shè)給定設(shè)給定Rn中的向量序列中的

18、向量序列 ，即即kX , ,X ,10kXX其中其中TknkkkxxxX)()(2)(1,若對(duì)任何若對(duì)任何i (i = 1, 2, n )都有都有*)(limikikxx則向量則向量 TnxxX),(*1*limXXkk稱(chēng)為向量序列稱(chēng)為向量序列 的極限的極限，或者說(shuō)向量序列或者說(shuō)向量序列 依坐標(biāo)收斂于向量依坐標(biāo)收斂于向量，記為記為kXkX定理定理7：向量序列：向量序列Xk依坐標(biāo)收斂于依坐標(biāo)收斂于X*的充要條件是的充要條件是0lim*XXkk向量序列依范數(shù)收斂與依坐標(biāo)收斂是等價(jià)的。向量序列依范數(shù)收斂與依坐標(biāo)收斂是等價(jià)的。2 2矩陣的范數(shù)矩陣的范數(shù)定義定義3：設(shè)設(shè)A為為n 階方陣階方陣，Rn中已定

19、義了向量范數(shù)中已定義了向量范數(shù) ， 則稱(chēng)則稱(chēng) 為矩陣為矩陣A A的范數(shù)或模的范數(shù)或模， 記為記為 。AXx1supAAXAx1sup矩陣范數(shù)的基本性質(zhì)：矩陣范數(shù)的基本性質(zhì)： （1）當(dāng)）當(dāng)A = 0時(shí)，時(shí)， 0，當(dāng)，當(dāng)A 0時(shí)，時(shí)， 0AA（2）對(duì)任意實(shí)數(shù)和任意對(duì)任意實(shí)數(shù)和任意A，有，有AkkA （3）對(duì)任意兩個(gè)對(duì)任意兩個(gè)n階矩陣階矩陣A、B有有BABA（4）對(duì)任意向量對(duì)任意向量X Rn，和任意矩陣和任意矩陣A，有有XAAX（5）對(duì)任意兩個(gè)對(duì)任意兩個(gè)n階矩陣階矩陣A、B，有有BAAB定理定理8：設(shè)：設(shè)n 階方陣階方陣A = (aij)n n，則，則（）與）與 相容的矩陣范數(shù)是相容的矩陣范數(shù)是1x

20、niijjaA11max（）與）與 相容的矩陣范數(shù)是相容的矩陣范數(shù)是2x12A其中其中 1為矩陣為矩陣ATA的最大特征值。的最大特征值。（）與）與 相容的矩陣范數(shù)是相容的矩陣范數(shù)是xnjijiaA1max3A 的范數(shù)與的范數(shù)與A 的特征值之間的關(guān)系的特征值之間的關(guān)系定理定理9：矩陣：矩陣A 的任一特征值的絕對(duì)值不超過(guò)的任一特征值的絕對(duì)值不超過(guò)A的范數(shù)。的范數(shù)。 定義定義4：矩陣：矩陣A 的諸特征值的最大絕對(duì)值稱(chēng)為的諸特征值的最大絕對(duì)值稱(chēng)為A的譜半徑，的譜半徑，iiA11max)(AA )(記為：記為：求解求解 時(shí)，時(shí)，A 和和 的誤差對(duì)解的誤差對(duì)解 有何影響？有何影響？bxA bx 設(shè)設(shè) A

21、精確，精確， 有誤差有誤差 ，得到的解為，得到的解為 ，即，即bb xx bbxxA )(bAx 1 |1bAx 絕對(duì)誤差放大因子絕對(duì)誤差放大因子|xAxAb 又又|1bAx |1bbAAxx 相對(duì)誤差放大因子相對(duì)誤差放大因子6 線(xiàn)性方程組的性態(tài)和解的誤差分析線(xiàn)性方程組的性態(tài)和解的誤差分析2 Error Analysis for . bxA 設(shè)設(shè) 精確，精確，A有誤差有誤差 ，得到的解為，得到的解為 ，即，即bA xx bxxAA )( bxxAxxA )()( )(1xxAAx |11AAAAAAxxx bxAAxAA )()(xAxAA )(xAxAAIA )(1xAAAAIx 111)( Wait a minute Who said that ( I + A 1 A ) is invertible?(只要只要 A充分小，使得充分小，使得)1|11 AAAA |1|1|1111AAAAAAAAAAAAxx 是關(guān)鍵是關(guān)鍵的誤差放大因子，稱(chēng)為的誤差放大因子，稱(chēng)為A的的條件數(shù)條件數(shù)，記為，記為cond (A) ,越越 則則 A 越病態(tài)，越病態(tài)，難得準(zhǔn)確解。難得準(zhǔn)確解。|1 AA大大定義定義5：設(shè)：設(shè)A 為為n 階非奇矩陣，稱(chēng)數(shù)階非奇