線性方程組與矩陣特征值求解的數(shù)值方法

1、第二章第二章 線性方程組與矩陣特征值線性方程組與矩陣特征值求解的數(shù)值方法求解的數(shù)值方法l 引言引言l 高斯消元法高斯消元法l 矩陣分解法矩陣分解法l 向量范數(shù)與矩陣范數(shù)向量范數(shù)與矩陣范數(shù)l 迭代法求解迭代法求解l 方程組的病態(tài)問題與誤差分析方程組的病態(tài)問題與誤差分析l 方陣特征值計(jì)算方陣特征值計(jì)算1 引言引言 在自然科學(xué)和工程技術(shù)中，有很多問題的解決都需要用到線性方程組的求解。因此，求解線性方程組的問題是一個在科學(xué)技術(shù)中常見的普遍問題。 一般地，這些線性方程組的系數(shù)矩陣大致可分為兩類： 1）低階稠密矩陣 2）大型稀疏矩陣解線性方程組的數(shù)值解法：有直接法直接法和迭代法和迭代法兩類。直接法：計(jì)算過

2、程沒有舍入誤差，經(jīng)過有限次四則運(yùn)算直接法：計(jì)算過程沒有舍入誤差，經(jīng)過有限次四則運(yùn)算可求得方程組的精確解。可求得方程組的精確解。（實(shí)際計(jì)算有舍入誤差）高斯消元法，矩陣分解法迭代法：核心是迭代求解的收斂條件和收斂速度。迭代法：核心是迭代求解的收斂條件和收斂速度。雅可比（Jacobi）迭代，高斯-賽德爾（Gauss-Seidel）迭代2 高斯消元法高斯消元法 )(11163)(1852)(174332123211321ExxxExxxExxx解：解： 1116318521741A313212)( 3)()( 2)(EEEEEE 基本思想方法基本思想方法：例例2.1 用消去法解方程組用消去法解方程組由

3、由行初等變換行初等變換將系數(shù)矩陣約化為三角將系數(shù)矩陣約化為三角矩陣；矩陣；用用回代回代的方法求解方程組。的方法求解方程組。（1）消元：）消元： 1741323)( 2)(EEE ， 163017411630 21060 0200高斯消元法高斯消元法是求解方程組的古典方法。(2.1)一、高斯消元法一、高斯消元法結(jié)論：結(jié)論：整個計(jì)算過程可分為兩部分：（1）消元：把原方程組轉(zhuǎn)化為系數(shù)矩陣為上三角矩陣的方程組；（2）回代：由系數(shù)矩陣為上三角矩陣的方程組求解對于一般情形對于一般情形： m個方程，個方程，n個未知數(shù)的線性方程組個未知數(shù)的線性方程組的高斯消元法的高斯消元法 mnmnmmnnnnbxaxaxa

4、bxaxaxabxaxaxa22112222212111212111(2.2)（2）回代求解，得：）回代求解，得：。03 x，312 x，311 x，其其系系數(shù)數(shù)矩矩階階 mnmmnnaaaaaaaaaA212222111211。 mbbbb21，)1()1()1(, )(bbaAAij 若記若記,21 mxxxx(1)(1)(2.2)Axb則可寫為，即 )1()1(2)1(1)1(2)1(22)1(21)1(1)1(12)1(11mnmmnnaaaaaaaaa )1()1(2)1(1mbbb mxxx21（1）第）第1步步(k=1)，)2() 1(11) 1(11miaamii ，具體計(jì)算公

5、式為：具體計(jì)算公式為： njmiamaajijiji, 3 , 2, 3 , 2)1(11)1()2( ，（m-1)(n-1)次乘法運(yùn)算次乘法運(yùn)算高斯消元法高斯消元法： )1()1(2)1(1)1(2)1(22)1(21)1(1)1(12)1(11mnmmnnaaaaaaaaa )1()1(2)1(1mbbb mxxx210)1(11 a設(shè)設(shè) ，計(jì)算乘數(shù)，計(jì)算乘數(shù) (m-1)次除法運(yùn)算次除法運(yùn)算對增廣矩陣對增廣矩陣 進(jìn)行進(jìn)行行初等變換行初等變換：，),3 , 2(11mirrmriii A), 3 , 2()1(11)1()2(mibmbbiii （m-1)次乘法運(yùn)算次乘法運(yùn)算(1)(1)(1

6、)(1)111211(1)(1)(1)(1)212222(1)(1)(1)(1)12nnmmmnmaaabaaabAaaab增廣矩陣增廣矩陣A)2()2(2)2(2)2(22mnmnaaaa記為記為(2)(2)Axb（2 2）第）第k步（步（ ）), 1min(, 2 , 1nmssk ， )1()1(bxA )1(1)1(12)1(11naaa， )2()2(2)1(1mbbb mxxx210, 0)1(1, 1)1(11 kkkaa設(shè)已完成上述消元過程第設(shè)已完成上述消元過程第1 1步，步，第第2步，步，第，第k-1-1步，且步，且 )1()1(bxA 得到與原方程組得到與原方程組 等價(jià)的方

7、程組。等價(jià)的方程組。( )( )kkAxb，其其中中 )2(2)2(22)1(1)1(12)1(11)(nnkaaaaaA。 )()()2(2)1(1)(kmkkkbbbbb)()()()(kmnkmkkknkkkaaaa于是，即有：，設(shè)設(shè)0)( kkka(1)(1)kkAxb，), 1()()(mkiaamkkkkikik 計(jì)算乘數(shù)計(jì)算乘數(shù) 對對 進(jìn)行進(jìn)行行初等變換行初等變換,使使 第第k列列 以下元素約為零以下元素約為零,)(kA)(kkka( )( )()kkAb,（m-k）次除法運(yùn)算）次除法運(yùn)算即即 ，得到與原方程組等價(jià)的方程組，得到與原方程組等價(jià)的方程組(1, )iik kirm r

8、r ikm 第第 k步具體計(jì)算：步具體計(jì)算：對于 ，則有： 其中其中 元素計(jì)算公式為：元素計(jì)算公式為： )1()1(, kkbA nkjmkiamaakkjikkjikji, 1, 1)()()1( ，), 1()()()1(mkibmbbkkikkiki 與與 前前k行元素相同，行元素相同， 的左上角的左上角k階陣階陣)1( kA)(kA)1( kA )()(1)1(11)(11kkkkkkaaaA為上三角陣。為上三角陣。（m-k)次乘法運(yùn)算次乘法運(yùn)算（m-k)(n-k)次乘法運(yùn)算次乘法運(yùn)算(1)(1)kkAxb)1()()1()(kkkkkkbbLAAL第第k步約化公式：步約化公式： （3

9、 3）繼續(xù)上述約化過程，）繼續(xù)上述約化過程，且設(shè)且設(shè)), 2 , 1(0)(skakkk (1)(1)ssAxb （i） 當(dāng)當(dāng)m n時，時，s = n，且設(shè)，且設(shè) ，則，則), 2 , 1(0)(nkakkk ， （ii）當(dāng)）當(dāng)m = n時，時， s = n-1,且設(shè)且設(shè) ，則，則) 1, 2 , 1(0)( nkakkk，直到完成第直到完成第S步計(jì)算，得到與原方程組等價(jià)的方程組步計(jì)算，得到與原方程組等價(jià)的方程組其中其中 為上梯形，具有以下三種情況（為上梯形，具有以下三種情況（討論討論）：）：)1( sAUaaaaaaAnmnnnnnS )()2(2)2(22)1(1112)1(11)1(0U

10、aaaaaaAnnnnnn )()2(2)2(22)1(1)1(12)1(11)( (iii) (iii)當(dāng)當(dāng)m n時，時，s = m-1，且設(shè)，且設(shè) , ,則則 ) 1, 2 , 1(0)( mkakkk，UaaaaaaaaAmmnmmmmnnm )()()2(2)2(22)1(1)1(1)1(12)1(11)(說明：說明： (1)上述約化過程，可用矩陣變換來實(shí)現(xiàn)，即上述約化過程，可用矩陣變換來實(shí)現(xiàn)，即 1111, 1mkkkkmmL其其中中)1( kA), 1(mkimik )(kA 由由 約化到約化到 , ,實(shí)際上是由乘數(shù)實(shí)際上是由乘數(shù) 構(gòu)成初構(gòu)成初與與 相乘得到相乘得到 ，即即 )1(

11、 kA)(kA )1()()1()(kkkkkkbbLAAL等下三角陣等下三角陣kL )()(1)()(1)(11)(1)()(1)()1(1)1(11, 1)(1111kmnkmkkmkknkkkkkkkkknkkkkkknmkkkkkaaaaaaaaaaammAL)1( kA )()()1(1)1(11kknkkknaaaa)1()1(1)1(1)1(11 kmnkmkknkkkkaaaa 即即UALLLS 12為高斯變換，為高斯變換，sLLL,21其中其中，即即給給定定bxA ，在在), 2 , 1(0)(skakkk （上梯形）（上梯形）), 1(skLk 條件下存在高斯變換條件下存在

12、高斯變換 ，使將，使將A 約化為上梯形。約化為上梯形。（2）元素元素 稱為稱為約化的主元素約化的主元素，且原方程組約化為等價(jià)方，且原方程組約化為等價(jià)方)(kkka為為非非奇奇異異陣陣，特特別別當(dāng)當(dāng)nnRA 時時，且且)1, 1(0)( nkakkk bxA )(/nnnnnnabx) 1 , 2 , 2, 1( nni由由消元過程消元過程和和回代過程回代過程構(gòu)成了構(gòu)成了高斯消元法高斯消元法。)1()1( sSbxA程組程組 過程稱為過程稱為消元過程消元過程， )()2(2)1(121)()1(1)1(12)1(11nnnnnnnbbbxxxaaaa用用回代法回代法求解：求解：)(1)()(/

13、)(iiinijjiijiiiaxabx 因此上述約化過程，可用矩陣變換來描述為：因此上述約化過程，可用矩陣變換來描述為： （3 3）若）若Ax=b, ,其中其中 非奇異矩陣，若此時非奇異矩陣，若此時 為零。為零。nnRA )1(11a，但但0)det( A，),3 , 2(011 ,1miai 所以所以A第第1 1列一定存在元素列一定存在元素bA,11irr 此時可交換（此時可交換（ ）第）第1 1 行與第行與第i1行元素（即行元素（即 ）。）。然后進(jìn)行消元計(jì)算。于是然后進(jìn)行消元計(jì)算。于是 ，且，且 右下角矩陣為右下角矩陣為n-1)2()1(AA)2(A階階非奇異矩陣。當(dāng)非奇異矩陣。當(dāng) 時，

14、直接進(jìn)行消元計(jì)算時，直接進(jìn)行消元計(jì)算, ,), 3 , 2(0)(nkakkk ， （用高斯變換約化）：（用高斯變換約化）：，設(shè)設(shè)), 1min(,nmsRAnm 0)( kkka結(jié)論：結(jié)論：定理定理1 sLlL,21則存在初等下三角陣則存在初等下三角陣 ,使使UALLLs 12(上梯形上梯形)成立。成立。，), 2 , 1(sk 時，時，可采用上述方法同樣處理?？刹捎蒙鲜龇椒ㄍ瑯犹幚?。( )0 (2,3, )kkkakL n，當(dāng)當(dāng)，設(shè)設(shè)bxA ，其中其中nnRA 定理定理2 (1)如果如果 ，則通過高斯消去法（不進(jìn)行，則通過高斯消去法（不進(jìn)行), 2 , 1(0)(nkakkk ，交換兩行的

15、初等變換）可交換兩行的初等變換）可將將 化為等價(jià)的三角方程組?；癁榈葍r(jià)的三角方程組。bxA )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11nnnnnnnnbbbxxxaaaaaa 回代計(jì)算：回代計(jì)算： )()(/nnnnnnabx)1, 2 , 1( nk ), 1(/)()(nkiaamkkkkikik 消元計(jì)算：消元計(jì)算：), 1()()()1(nkibmbbkkikkjki nkjnkiamaakkjijkijkij, 1, 1)()()1( ；)(1)()(/ )(iiinijjiijiiiaxabx ) 1 , 2 , 2, 1( nni （2）如果）如果

16、A為非奇異矩陣，則可通過帶行交換的高斯消去為非奇異矩陣，則可通過帶行交換的高斯消去法，將法，將 化為等價(jià)的三角形方程組?；癁榈葍r(jià)的三角形方程組。bxA 即，即，Gauss消元法中消元法中, ,( )0kkka若，直接消元計(jì)算，若若0)( kkka注：注：則要求在算法中增加一判斷，并進(jìn)行則要求在算法中增加一判斷，并進(jìn)行行交換行交換。) ,2 , 1()( kakkk是否是零，可以根據(jù)順序主子式來判斷。是否是零，可以根據(jù)順序主子式來判斷。二、高斯主元消去法二、高斯主元消去法例例2.2 用高斯消去法解方程組用高斯消去法解方程組 9 . 07 . 0103 . 0212111xxxx精確到精確到101

17、0位真解位真解：Tx)7000000000. 0,2000000000. 0(* 9 . 0117 . 01103 . 0),(11bA解法解法1 1（高斯消去法）（高斯消去法）消元：消元：121121103333333333. 0103 . 01 m12103333333333. 011 舍去舍去/ /被被“吃吃”舍去舍去/ /被被“吃吃”12103333333333. 07 . 09 . 0 07 . 01103 . 01112103333333333. 0 12102333333333. 0 計(jì)算解：計(jì)算解： 。 0000000000. 07000000000. 012xx主元選擇的重要

18、性主元選擇的重要性要求用具有舍入的要求用具有舍入的1010位浮點(diǎn)數(shù)進(jìn)行計(jì)算。位浮點(diǎn)數(shù)進(jìn)行計(jì)算。絕對值很小絕對值很小計(jì)算解與真解相差太大計(jì)算解與真解相差太大, , 失敗原因失敗原因是用很小的數(shù)是用很小的數(shù)(1)11110.3 10a作除數(shù)，作除數(shù)，使得使得舍入誤差舍入誤差太大，從而計(jì)算結(jié)果不可靠。太大，從而計(jì)算結(jié)果不可靠。解法解法2 用行變換的高斯消去法用行變換的高斯消去法. .消元：消元： 7 . 01103 . 09 . 0111112rr)103 . 01103 . 0(111121 m 7 . 0109 . 011。 2000000000. 07000000000. 012xx計(jì)算解計(jì)算

19、解: : 7 . 0103 . 09 . 0211121xxxx 9 . 07 . 0103 . 0212111xxxx 該結(jié)果較好。該例子說明，在采用高斯消去法解方程組時，應(yīng)該結(jié)果較好。該例子說明，在采用高斯消去法解方程組時，應(yīng) 。對一般系數(shù)矩陣，最好保持乘數(shù)。對一般系數(shù)矩陣，最好保持乘數(shù))(kkka元元素素避避免免采采用用絕絕對對值值很很小小主主| 1ikm，因此在高斯消去法中引進(jìn)選主元素技巧。，因此在高斯消去法中引進(jìn)選主元素技巧。 9 . 0117 . 01103 . 0),(11bA111 1 0.3 10 沒有被舍去沒有被舍去/ /被被“吃吃”1. 完全主元素消去法完全主元素消去法

20、選主元消元法：選主元消元法：。，0|max|1111 ijnjnijiaa11jxx 與與注注意意調(diào)調(diào)換換，設(shè)設(shè)bxA ，nnRA 為非奇異矩陣，為非奇異矩陣，第一步：第一步：。元元素素仍仍記記為為且且兩兩未未知知量量，并并作作記記錄錄，iijbabA,使使,11ji選選主主元元：)1(行行元元素素，行行與與第第第第交交換換時時即即當(dāng)當(dāng)交交換換行行列列111),(,1,)2(ibAi （3 3）消元計(jì)算：）消元計(jì)算：，), 3 , 2(1111niaamii ，), 3 , 2(1111niamaii ib列列元元素素。列列與與第第第第交交換換時時當(dāng)當(dāng)111),(,1jbAj 1 ia), 3

21、 , 2(11nibmbii 在在A中選取絕對值最大的元素作為主元素，即確定中選取絕對值最大的元素作為主元素，即確定 第第k 步：重復(fù)進(jìn)行，設(shè)已完成第步：重復(fù)進(jìn)行，設(shè)已完成第1 1步步第第k-1 的選主元，使的選主元，使 A， 增廣陣。增廣陣。b A， 約化為約化為:b nnnnkkknkknkkbaabaababaaabAbA222111211)()(,第第k步的步驟：步的步驟：。步步選選主主元元區(qū)區(qū)域域方方框框?yàn)闉榈诘?,2, 1 nkk使使選選主主元元：即即確確定定,)1(kkji0max ijnjknikjiaakk，行行元元素素，行行與與第第第第交交換換時時即即當(dāng)當(dāng)交交換換行行列列k

22、kkkikbAki),(,)2()()( （3 3）消元計(jì)算：）消元計(jì)算：), 1(nkiaamkkikik ), 1,(nkjiamakjikij ib列列元元素素。列列與與第第第第交交換換時時當(dāng)當(dāng)kkkkjkbAkj),(,)()( ija), 1(nkibmbkiki 回代求解：回代求解：調(diào)調(diào)換換后后的的次次序序。則則是是未未知知數(shù)數(shù)其其中中nnxxxyyy,2121 ) 1 , 2 , 1(/ )(/1niayabyabyiinijjijiinnnn對于完全選主元素消去法：對于完全選主元素消去法：計(jì)算量大。計(jì)算量大。 nnnnnnbbbyyyaaaaaa212122211211經(jīng)過上述

23、過程，方程組約化為：經(jīng)過上述過程，方程組約化為：。該該方方法法數(shù)數(shù)值值穩(wěn)穩(wěn)定定)1( kim缺點(diǎn)：缺點(diǎn)：優(yōu)點(diǎn)：優(yōu)點(diǎn)：改進(jìn)方法改進(jìn)方法：。且此時且此時1 kim列主元消去列主元消去法，法，討論：討論：設(shè)已完成第設(shè)已完成第1步步第第k-1步計(jì)算，得到與原方程步計(jì)算，得到與原方程組組等價(jià)的方程組等價(jià)的方程組 ，其其中中)()(kkbxA )()()()()()()2(2)2(2)2(22)1(1)1(1)1(12)1(11)()(,nnknnknkkknknkkknnkkbaabaabaabaaabA方框內(nèi)為第方框內(nèi)為第k步選主元素區(qū)域。步選主元素區(qū)域。2 列主元素消去法列主元素消去法以下步驟類似完

24、全選主元素消去法。以下步驟類似完全選主元素消去法。例例2.3 用列主元素消去法解方程組用列主元素消去法解方程組 分析：分析：由精確解看出有兩位有效數(shù)字，因此，用由精確解看出有兩位有效數(shù)字，因此，用4 4位浮點(diǎn)數(shù)進(jìn)位浮點(diǎn)數(shù)進(jìn) 021313222226321321321xxxxxxxxx。精精確確解解：)0 . 5, 8 . 3, 6 . 2(321 xxx 012113333. 06667. 022226,bA)1667. 0,3333. 0(3121 mm 3334. 0333. 1667. 10667. 13333. 00001. 00222632rr 667. 13333. 00001.

25、003334. 0333. 1667. 102226解解 ：消元：消元： )00005999. 06667. 10001. 0(32 m 667. 13333. 0003334. 0333. 16667. 1022263334. 000005999. 0667. 1 舍去或著說被舍去或著說被“吃吃”行計(jì)算。行計(jì)算。 回代計(jì)算解：回代計(jì)算解： 602. 2801. 3003. 5123xxx高斯選主元消去法的步驟：高斯選主元消去法的步驟： 667. 13333. 0003334. 0333. 16667. 102226bA，注：注：該解若取兩位有效數(shù)字，則與真解完全相同。該解若取兩位有效數(shù)字，則

26、與真解完全相同。優(yōu)點(diǎn)：優(yōu)點(diǎn)：數(shù)值穩(wěn)定。數(shù)值穩(wěn)定。修正方法：修正方法：消元消元；回代回代。列主元高斯列主元高斯- -約當(dāng)（約當(dāng)（Gauss-Jordam）消去法）消去法, ,將將A A化成一個單位矩陣，不需回代?；梢粋€單位矩陣，不需回代。缺點(diǎn)：缺點(diǎn)：既消元；又回代。既消元；又回代。3 矩陣分解矩陣分解法法 一、一、 矩陣的三角分解矩陣的三角分解 列主元高斯消去法實(shí)質(zhì)上是對方程組進(jìn)行等價(jià)變形，即是對列主元高斯消去法實(shí)質(zhì)上是對方程組進(jìn)行等價(jià)變形，即是對定理定理3 3 系數(shù)矩陣施行系數(shù)矩陣施行行初等變換行初等變換，這些，這些初等變換初等變換又可以用矩陣表示。因此又可以用矩陣表示。因此矩陣的矩陣的三角

27、分解三角分解是列主元高斯消去法的另一種表示方法，或著說是列主元高斯消去法的另一種表示方法，或著說高斯消去法的變形，即是高斯消去法高斯消去法的變形，即是高斯消去法緊湊格式緊湊格式的矩陣表示（矩陣的的矩陣表示（矩陣的nnRA 設(shè)設(shè)，) 1, 2 , 1( 0 nkDk，如果，如果A順序主子式順序主子式其中，其中，L為單位下三角陣，為單位下三角陣，U為上三角矩陣。為上三角矩陣。說明：說明：則則A可可唯一唯一分解為兩個三角矩陣相乘，即分解為兩個三角矩陣相乘，即。LUA A為非奇異為非奇異陣陣, ,則則A可唯一分解為兩個三角矩陣相乘可唯一分解為兩個三角矩陣相乘, ,否則，分解不是唯一的。否則，分解不是唯

28、一的。三角分解），它在解方程組的直接法中起著重要的作用。三角分解），它在解方程組的直接法中起著重要的作用。 對矩陣對矩陣A A實(shí)行初等行變換相當(dāng)于用初等矩陣左乘實(shí)行初等行變換相當(dāng)于用初等矩陣左乘A A，于，于是對是對Ax=bAx=b做第一次消元后，做第一次消元后， 化為化為 化為化為 ，即，即 ，其中，其中(1)(2)(1)(2)11,L AALbb(1)(2)(1)(2),AAbb矩陣的三角分解矩陣的三角分解 LULU分解分解2113111000100010001nmLmm (1)(1)(1)(1)1111211(1)(1)(1)(1)2212222(1)(1)(1)(1)12nnnnnnn

29、nxaaabxaaabxaaab第第k k步的初等矩陣為步的初等矩陣為1,10000100010001kkknkLmm 1kkkL AA 1kkkL bb并且并且重復(fù)這一過程，最后得到重復(fù)這一過程，最后得到 11211121nnnnLL L AALL Lbb將上三角矩陣將上三角矩陣 記為記為U U，則，則 ，其中，其中 nA111121nAL LL ULU21111313212112,11111nnnn nmmmLL LLmmm則，則，L L為單位下三角矩陣。為單位下三角矩陣。 高斯消去法實(shí)質(zhì)上是產(chǎn)生了一個將高斯消去法實(shí)質(zhì)上是產(chǎn)生了一個將A A分解為兩個三角形分解為兩個三角形矩陣相乘的因式分解

30、。如果矩陣相乘的因式分解。如果A A是非奇異陣，則是非奇異陣，則LULU分解是唯一分解是唯一的，否則分解不唯一。的，否則分解不唯一。直接三角分解法解線性方程組（直接三角分解法解線性方程組（ ）的具體流程：）的具體流程：11(1,2, )iiuainAxb1111(1, )iilauin 1.2. 計(jì)算U的第r行，L的第r列元素 r=2,3,n11(,1, )rririrkkikual uir rn3.11(,1, ;)riririkkrrrklal uuir rn rn( (一一)LU)LU分解分解，先先求求、LUA 11111;(2,3, );iiiikkkybybl yin1;(1,2,1

31、);nnnnniiikkiik ixyuxyu xuinn ( (二二)x)x的計(jì)算的計(jì)算。再再求求解解、 yxUbyL2例例 用直接三角分解法解方程組用直接三角分解法解方程組 1231471258136111xxx 1111121213131,4,7uauaua111111212111313111/1/1 121 231 3laula ula u，解解:(:(一一) )矩陣矩陣LULU分解分解111111;(1, );(1,2, )iiiiuainlauin(1)(1)故：故：222221 12232321 13222221 1222323231 1222333331 1332 233333

32、31 1332 235 2 438 2 76()/(5 2*4)/( 3) 1()/2() 11 3*7 2*( 6) 2()/2 1ual uual ulal uulal uuual ul ulal ul u 1111(,1, )(,1, ;)rririrkkikriririkkrrrkual uir rnlal uuir rn rn(2)(2)經(jīng)計(jì)算：經(jīng)計(jì)算：1471147258213636113212ALU (3)(1, 1,0)TLyby求解，得，(4)( 1/3,1/3,0)TUxyx 求解，得方程組的解。( (二二) )求解求解x x：從而從而1111;(2,3, );iiiikk

33、kybybl yin1;(1,2,1);nnnnniiikkiik ixyuxyu xuinn 311173121A例例 設(shè)設(shè) ，試將，試將A進(jìn)行三角分解。進(jìn)行三角分解。解解： 由高斯消去法得到由高斯消去法得到 11131211mmL 111322mL， 11131 11111113133121 mm，11132 m，則有則有 20041012112UALLULLAA1211 可可以以寫寫成成ULLA112)( 也也可可以以寫寫成成U 111111131U 111131。UU 1111311141311LU（1 1）方法比較）方法比較，先先求求、LUA 1消元法：消元法：。即即解解后后回回代代

34、、bLxU1,2 消元法的公式只有一組，便于計(jì)算機(jī)計(jì)算。消元法的公式只有一組，便于計(jì)算機(jī)計(jì)算。需需要要乘乘除除法法的的次次數(shù)數(shù)其其中中直直接接三三角角分分解解法法解解)(nnRAbxA 消元法與三角分解法間的關(guān)系：消元法與三角分解法間的關(guān)系： 。階階順順序序主主子子式式不不等等于于零零至至的的，設(shè)設(shè)對對nAbxA1 三角分解法三角分解法：。再再求求解解、 yxUbyL2，即即先先消消元元、),(),(),(),(1111bLUbALbLUbA （2 2）計(jì)算次數(shù)）計(jì)算次數(shù)次次乘乘除除法法。同同高高斯斯消消去去法法，大大約約33n注：注： ，只只需需求求解解分分解解，對對不不同同的的的的完完成成

35、), 2 , 1(mjbxAjLUAj 問問題題，因因?yàn)闉橐灰坏┑┤墙欠址纸饨夥ǚㄟm適合合解解), 2 , 1(mjbxAj 。即即求求解解 jjjjyxUbyL)(2次次乘乘除除法法n討討論論高斯高斯-約當(dāng)約當(dāng)法除外法除外次次乘乘法法222)1(211nnnnknk 次次乘乘除除法法222)1(21nnnnknk CholeskyCholesky分解分解：，有有且且0),(, 0)2( xxAxRxn對稱正定矩陣對稱正定矩陣的一種三角分解方法。的一種三角分解方法。對稱正定陣的定義及性質(zhì)：對稱正定陣的定義及性質(zhì)：定義定義)(對對稱稱正正定定陣陣滿滿足足：如如果果設(shè)設(shè)ARAnn, 為為對對稱

36、稱正正定定陣陣。則則稱稱 A；AAT ) 1 (A為對稱為對稱正定陣正定陣(4)(4)A的特征值的特征值 。), 2 , 1( 0)(niAi (1 1)A是非奇異矩陣，且是非奇異矩陣，且A-1亦是對稱正定陣；亦是對稱正定陣；(2 2)A的順序主子陣的順序主子陣Ak 是對稱正定陣是對稱正定陣(k=1,2,n)；), 2 , 1( 0)det(nkAk (3 3)A的順序主子的順序主子式都大于零，即式都大于零，即 對稱正定陣的判別方法對稱正定陣的判別方法( (充分條件充分條件) )正正定定陣陣為為對對稱稱AA為對稱矩陣為對稱矩陣0)( AAi 的的特特征征值值A(chǔ)為對稱矩陣為對稱矩陣，), 2 ,

37、 1( 0)det(nkAk 二、二、 矩陣矩陣CholeskyCholesky分解分解定理定理4為為對對稱稱正正定定若若nnRA （對稱正定矩陣的（對稱正定矩陣的Cholesky分解）分解）。TLLA 陣，則存在唯一的具有正對角元的下三角陣陣，則存在唯一的具有正對角元的下三角陣L ，使得，使得平方根法解線性方程組：平方根法解線性方程組：( (與直接三角分解法類似與直接三角分解法類似) )思路思路：；為為分分解解對對稱稱正正定定陣陣TLLAA )1( .xyxLybyLT，求求，求求bxLLbxAT 求求解解求求解解)2(求求解解方方程程組組 nnnnnnaaaaaaaaaA212222111

38、211令令jjijjkjkiknkjkikijlllllla 111則則。的的元元素素ijlL設(shè)設(shè)n階對稱正定矩陣階對稱正定矩陣A有分解有分解 ,先用先用待定系數(shù)法待定系數(shù)法求求L的元的元TLLA nnnnnnnnllllllllllll2221211121222111，時時，當(dāng)當(dāng))0( jkljk步步可可直直接接求求得得經(jīng)經(jīng)n該分解稱為喬勒斯基（該分解稱為喬勒斯基（CholeskyCholesky）分解。）分解。 ijl素素 。求解對稱正定方程組求解對稱正定方程組Ax=b的的平方根法平方根法( (計(jì)算公式計(jì)算公式) ) ：分解計(jì)算：分解計(jì)算： ：TLLA ), 2 , 1(ni 2/1112

39、)()2( ikikiiiilal,)()1(11jjjkjkikijijlllal )(1, 2 , 1(ijij ，), 2 , 1()() 3(11nilylbyiiikkikii 。) 1 , 2 , 1,()() 4(1 nnilxlyxiinikkkiii xyxLybyLT求求，求求，jjijjkjkiknkjkikijlllllla 111), 2 , 1(ni 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 1 1、數(shù)值穩(wěn)定。、數(shù)值穩(wěn)定。 2 2、計(jì)算量小，大約為、計(jì)算量小，大約為 次乘除法，是一般矩陣次乘除法，是一般矩陣A的的LU分解計(jì)算量的一半。分解計(jì)算量的一半。63n 缺點(diǎn)：缺點(diǎn)：計(jì)算計(jì)算lii時要開平

40、方。時要開平方。求解：求解： 通過改進(jìn)方法避免通過改進(jìn)方法避免(0)jkjkl當(dāng)時，yxyx 4 向量范數(shù)與矩陣范數(shù)向量范數(shù)與矩陣范數(shù) 向量、向量、矩陣與線性方程組有著密切的關(guān)系，矩陣與線性方程組有著密切的關(guān)系，向量、矩陣范數(shù)向量、矩陣范數(shù)是是解方程組以及研究與探討解方程組以及研究與探討方程組方程組本身性質(zhì)的工具。本身性質(zhì)的工具。定義定義（向量范數(shù)）：（向量范數(shù)）： 的的某某個個實(shí)實(shí)值值非非負(fù)負(fù)或或?qū)τ谟谙蛳蛄苛縩nCxRx （1）正定性）正定性 ；或或記記為為 00,0 xxx（2）齊次性）齊次性 ；或或，其其中中)(CRxx （3）三角不等式）三角不等式 ?；蚧騨nCRyxyxyx ,

41、?；蚧蚰ＤＲ灰粋€個向向量量范范數(shù)數(shù)或或上上是是稱稱nnCRxxN|)( 一、向量范數(shù)的定義一、向量范數(shù)的定義 ，若若滿滿足足：函函數(shù)數(shù)xxN 常用的向量范數(shù)常用的向量范數(shù)：)(),(1nnTnCxRxxx 或或設(shè)設(shè)；inixxxN 1max|)(； niixxxN111|)(（1）向量的）向量的“”范數(shù)：范數(shù)：（2）向量的）向量的“1”范數(shù)：范數(shù)：；2/1122/122)(),()( niixxxxxN,nRx 稱為向量的稱為向量的能量范數(shù)能量范數(shù)。（3）向量的）向量的“2”范數(shù)：范數(shù)：（4）向量的能量范數(shù)：）向量的能量范數(shù)：為為對對稱稱正正定定陣陣，設(shè)設(shè)nnRA 211,2/1)(),()(

42、 njijiijAAxxaxxAxxN二、向量序列的極限二、向量序列的極限設(shè)有向量序列設(shè)有向量序列 )(kx，Tnxxx),(1 若若n個數(shù)列收斂，即個數(shù)列收斂，即，收收斂斂于于則則稱稱*)(xxk，記記為為 xxkk)(lim對對應(yīng)應(yīng)分分量量。分分量量收收斂斂到到即即是是*)(xxk設(shè)有向量序列設(shè)有向量序列，), 2 , 1(102102)(nkxkkk 則有則有 。 22lim)(kkx定義定義1. 定義定義例例4.1，及及向向量量 x), 1(lim)(nixxikik 或說向量序列或說向量序列 的收斂的收斂)(kx，設(shè)設(shè)nRyx ,稱非負(fù)實(shí)數(shù)稱非負(fù)實(shí)數(shù) 之間之間yx,為為|),(yxy

43、xd 2. 距離距離為向量的任何一種意義下為向量的任何一種意義下范數(shù)范數(shù)。| 距離，距離，其中其中且記且記 ，Tknkkxxx),()()(1 定理定理5)(kx設(shè)設(shè)為為Rn中一向量序列，且中一向量序列，且 ，則則nRx v| 其其中中為向量的任一種范數(shù)。為向量的任一種范數(shù)。 證明：證明：), 1(limlim)()(nixxxxikikkk )( 0max)(1 kxxikini當(dāng)當(dāng)。當(dāng)當(dāng))(0)( kxxk ,0lim)()( kxxxxvkkk當(dāng)當(dāng)時時，當(dāng)當(dāng) v), 1(0lim)(nixxikik 由范數(shù)的等價(jià)性有：由范數(shù)的等價(jià)性有： ,0lim2)()( kxxxxkkk當(dāng)當(dāng) 。當(dāng)當(dāng)

44、 kxxxxkkk0lim1)()(對對v =1也可采用以下證法也可采用以下證法), 1( 0limlim)()(nixxxxikikkk 0)( ikixx01)( niikixx。當(dāng)當(dāng))(01)( kxxk注：注：), 1(ni 定義定義 （矩陣范數(shù)）（矩陣范數(shù)）nnRA 矩矩陣陣的某個非負(fù)實(shí)值函數(shù)的某個非負(fù)實(shí)值函數(shù)，AAN )(若對任意的若對任意的nn矩陣矩陣A，B滿足下述條件：滿足下述條件：，0 A；且且00 AA；RAA ,。BABA 。模模上上的的一一個個矩矩陣陣范范數(shù)數(shù)是是則則稱稱)()(nnRAN 由于在許多應(yīng)用問題中，矩陣和向量是由于在許多應(yīng)用問題中，矩陣和向量是相聯(lián)系的，現(xiàn)

45、引進(jìn)一種相聯(lián)系的，現(xiàn)引進(jìn)一種和向量范數(shù)是相容的，即對和向量范數(shù)是相容的，即對 ，nnnRARx ,有不等式有不等式xAxA （1） 正定性正定性 ： （2） 齊次性齊次性 ： （3） 三角不等式三角不等式 ： 1. 矩陣范數(shù)的一般定義矩陣范數(shù)的一般定義(類似于向量范數(shù)類似于向量范數(shù))矩陣的矩陣的算子范數(shù)算子范數(shù)。它是由向量范數(shù)。它是由向量范數(shù)誘導(dǎo)誘導(dǎo)出來的，并且這種矩陣范數(shù)出來的，并且這種矩陣范數(shù)矩陣范數(shù)與向量范數(shù)的相容性條件矩陣范數(shù)與向量范數(shù)的相容性條件三、矩陣的范數(shù)三、矩陣的范數(shù) 2. 矩陣的算子范數(shù)矩陣的算子范數(shù) ，設(shè)設(shè)nnnRARx ,且有一且有一向量范數(shù)向量范數(shù)相應(yīng)的定義一個矩陣的非

46、負(fù)函數(shù)：相應(yīng)的定義一個矩陣的非負(fù)函數(shù)：vvRxxvxxAAANn 0max)(（最大比值）（最大比值） 為矩陣為矩陣A的關(guān)于向量范數(shù)的關(guān)于向量范數(shù)定理定理6 向量范數(shù)，則向量范數(shù)，則 上上是是nnvRAAN )(一個一個矩陣范數(shù)矩陣范數(shù)且滿足且滿足相容條件相容條件： ；vvvxAxA )1(。),()2(nnvvvRBABAAB 的的算子范數(shù)算子范數(shù)或或誘導(dǎo)范數(shù)誘導(dǎo)范數(shù)。vx)(AN稱稱上上的的為為設(shè)設(shè)nvRx定義定義 ( 矩陣的算子范數(shù)矩陣的算子范數(shù))v| （i）因?yàn)椋┮驗(yàn)?，0 x。0, 0 vvxxA, 0 vvxxA所所以以00, 0 xAAx且且證明：證明： 上上是是先先證證nnRA

47、AN 一個矩陣范數(shù)一個矩陣范數(shù)( 滿足三個條件滿足三個條件)， 。00 vAA 0 x0 A，0max0 vvRxxvxxAAn0 vxA0 vA（ii） vvxvxxAA 0max RAxxAvvvx ,max0,nnRBA vvxvxxBABA|max0 。vvvvvxBAxxBxA 0max（iii） 以下證明滿足相容性：以下證明滿足相容性：，因因?yàn)闉関vxvxxAA0max ，所所以以vvvAxxA （1）vvvAxAx即。（2） vvxBAxAB)()( vvvvBAxxAB )(所所以以成成立立，0 xvvvvvxBAxBA 由由x的任意性知的任意性知 。vvvvxvBAxxABA

48、B )(max0誘導(dǎo)范數(shù)的誘導(dǎo)范數(shù)的矩陣相容性矩陣相容性誘導(dǎo)范數(shù)與其相應(yīng)誘導(dǎo)范數(shù)與其相應(yīng)的向量范數(shù)相容的向量范數(shù)相容，則則設(shè)設(shè)nnnRARx ,； njijnixaxxAA110maxmax)1(； niijnjxaxxAA111101maxmax)2(。)(max)3(max2202AAxxAATx 的的最最大大特特征征值值。為為其其中中AAAATT)(max A的行范數(shù)的行范數(shù)的列范數(shù)的列范數(shù)的的“2”范數(shù)范數(shù)或或的譜范數(shù)的譜范數(shù)3. 矩陣范數(shù)公式矩陣范數(shù)公式4. 矩陣范數(shù)的等價(jià)性矩陣范數(shù)的等價(jià)性，則則設(shè)設(shè)nnRA ， |1) 1 (2AnAAn。 |1) 2(1AnAAnnnRA 設(shè)設(shè)的

49、特征值為的特征值為|max)(1iniA 稱稱為為A的譜半徑。的譜半徑。，設(shè)設(shè)nnRA )1(，則則|)(AA | A其其中中向量相容性條件的矩陣范數(shù)（算子范數(shù)）。向量相容性條件的矩陣范數(shù)（算子范數(shù)）。nnRA 設(shè)設(shè))2(為對稱矩陣，則為對稱矩陣，則。)(|2AA 四、譜半徑四、譜半徑1. 1. 矩陣譜半徑定義：矩陣譜半徑定義： nii3 , 2 , 1 2. 特征值界：特征值界：證明：證明：（1），0 x，使使xxA ，|xA ，即即|A 。所所以以|)(AA 設(shè)設(shè) 為為A的任一特征值，于是，存在的任一特征值，于是，存在 |xAxx 且且為滿足矩陣、為滿足矩陣、注注：1）由于矩陣的）由于矩陣

50、的2范數(shù)與譜半徑有關(guān)，常稱范數(shù)與譜半徑有關(guān)，常稱“2”范數(shù)為譜模。范數(shù)為譜模。若若 為為A的特征值，的特征值， (2)ATA=A2,且且ATA也是也是對稱的，對稱的，設(shè)設(shè)|)(0 A最最大大特特征征根根，必必是是220A 222maxmax00|()()|( )TAA AAA。2）譜模（范數(shù)）是對稱矩陣）譜模（范數(shù)）是對稱矩陣A特征值的上界。特征值的上界。則則 為為A2 的特征根，的特征根，2 又又A為對稱矩陣，則為對稱矩陣，則5 迭代法求解迭代法求解迭代法迭代法是一種不斷套用一個迭代公式，逐步逼近方程組的是一種不斷套用一個迭代公式，逐步逼近方程組的精確精確解（真解）的方法。解（真解）的方法。

51、適合解大型稀疏線性方程組適合解大型稀疏線性方程組。直接法：解低階稠密線性方程組直接法：解低階稠密線性方程組迭代法優(yōu)點(diǎn)：迭代法優(yōu)點(diǎn)：計(jì)算量小，近似解精度高計(jì)算量小，近似解精度高。占用內(nèi)存單元較少占用內(nèi)存單元較少。設(shè)計(jì)程序簡單（適合計(jì)算機(jī)計(jì)算）。設(shè)計(jì)程序簡單（適合計(jì)算機(jī)計(jì)算）。定義定義（1 1）用逐步代入）用逐步代入(0)(1)(0)(1)( ),(1,2,)kkxxB xfxBxfk+=+=+=L任取初始向量求近似解的方法，稱為求近似解的方法，稱為迭代法迭代法（或稱為（或稱為一階定常迭代法一階定常迭代法）。）。 迭代法的定義：迭代法的定義：B是迭代矩陣是迭代矩陣nnRA 設(shè)設(shè)為非奇異陣，為非奇異

52、陣， 方程組方程組 的精確解為的精確解為 即即。bAx *，*xbAx 是是 的的k步近似步近似*x)(kx)(kx（構(gòu)造向量序列（構(gòu)造向量序列 ） （2 2）如果對任意初始近似）如果對任意初始近似 ，都有，都有 稱迭代法稱迭代法)0(x，*)(limxxkk 迭代法研究的問題：迭代法研究的問題： （1 1）構(gòu)造各種解構(gòu)造各種解 的的有效迭代法有效迭代法(有效：有效： 收斂收斂)。bAx )(kx為為收斂收斂，否則稱迭代法為，否則稱迭代法為發(fā)散發(fā)散。（2 2）研究迭代法的研究迭代法的收斂性收斂性及及收斂速度收斂速度。 一、基本迭代法構(gòu)造一、基本迭代法構(gòu)造 基本思想：基本思想： ，令令0, ii

53、nnijaaA將將A分離（裂）為三部分，即分離（裂）為三部分，即用迭代法解線性方程組用迭代法解線性方程組 。bAx 0001,121,2211nnnnnaaaaaaA 000, 1112nnnaaaULD 常用的是將常用的是將A分裂為分裂為 NMA 問題問題：其中其中 為可選擇的非奇異陣使為可選擇的非奇異陣使 容易求解容易求解, ,一般一般 選為選為 的某的某dMx AMM種種近似近似, ,于是于是bNxMxbAx ?；蚧騜MNxMx11 若記若記)(11AMMNMB ，則則并并取取初初始始向向量量)0( x(0)(1)( )11(0,1,)kkx xBxfkBIM AfM b+-=+=-=

54、L（可任意?。┳ⅲ鹤ⅲ?的選法不同，得的選法不同，得到各種不同的迭代法。到各種不同的迭代法。M，bM f1 A MI,1 二、二、Jacobi迭代法迭代法1.1.理論分析：理論分析： 若取若取 ( (對角陣對角陣) )，則有，則有 , ,DM NDA 于是于是 ADIB1 ，J ULDADD 11稱為稱為JacobiJacobi迭迭代法的迭代陣代法的迭代陣Jacobi迭代法迭代法： bDfJULDBkfBxxxkk11)() 1() 0()(), 1 , 0(bDbMf11 于是，有于是，有 ，即，即bxULDxkk )()1()( ni , 2 , 1 ,1111)()()1( nijjkj

55、ijiijnijkjijkjijikiiixabxaxabxa若若 則得到則得到JacobiJacobi迭代計(jì)算公式迭代計(jì)算公式 0 iia2.2.求解求解 的的Jacobi迭代法計(jì)算公式：迭代法計(jì)算公式： Axb= xabaxxx xnijjkjijiiikiTn)(1),(1)() 1()0()0(1)0( ni, 2 , 1 表表示示迭迭代代次次數(shù)數(shù)。, 1 , 0 k注：注：(1)(1)Jacobi迭代法迭代法, ,每迭代一次主要是計(jì)算一次矩陣乘向量每迭代一次主要是計(jì)算一次矩陣乘向量 。)(kBx(2)(2)計(jì)算過程中，原始數(shù)據(jù)計(jì)算過程中，原始數(shù)據(jù)A始終不變。始終不變。(3)(3)計(jì)算

56、中需要兩組工作單元計(jì)算中需要兩組工作單元 用來保存用來保存 及及 。 )(),(nynx)(kx)1( kx解向量初值解向量初值說明說明：(1)(1)Jacobi迭代法實(shí)際上是由近似解迭代法實(shí)際上是由近似解Tknkikkxxxx),()()()(1)( Tknkikkxxxx),() 1() 1() 1(1) 1( 的的n-1-1分量分量)()(1)(1)(1,knkikikxxxx 計(jì)算計(jì)算的第的第i（i=1,2,n）個分量。個分量。更更接接近近于于比比，則則收收斂斂于于若若*)()1(*)()2(xxxxxkkk 更更比比則則)()1(kikixx 。接接近近于于*ix三、三、 高斯高斯-

57、塞德爾迭代法（塞德爾迭代法（G-S） 取分裂陣取分裂陣 ( (下三角陣下三角陣),),則有則有LDM NLDA ，于是，于是ALDIB1)( bLDfGULDBfBxxxkk11)()1()0()()(其中其中G 稱為稱為G- -S迭代法的迭代陣迭代法的迭代陣于是，有于是，有 或或bUxxLDkk )()1()(bUxLxDxkkk )()1()1(當(dāng)當(dāng) 時得到以下時得到以下解解 的的G-SG-S迭代法計(jì)算公式迭代法計(jì)算公式: : 0 iiabAx 其中其中k =1,2,=1,2,表表示迭代次數(shù)示迭代次數(shù)), 2 , 1(ni )(1),(1)(11)1()1()0()0(1)0(nijkji

58、jijkjijiiikiTnxaxabaxxxxGULDALDLD 11)()()(G-S迭代法可看作迭代法可看作JacobiJacobi迭代法的一種修正或改進(jìn)。迭代法的一種修正或改進(jìn)。 (1) (1)由由(2.8)(2.8)可知可知, ,計(jì)算計(jì)算 第第i個分量時個分量時, ,利用已經(jīng)計(jì)算出的最利用已經(jīng)計(jì)算出的最新新)1( kx優(yōu)點(diǎn)：優(yōu)點(diǎn)：(2)(2)G-S迭代法每迭代一次主要計(jì)算一次矩陣乘向量。迭代法每迭代一次主要計(jì)算一次矩陣乘向量。計(jì)算量小計(jì)算量小(3)(3)當(dāng)當(dāng)J-J-迭代與迭代與G-SG-S迭代都收斂時，迭代都收斂時，G-S迭代的收斂速度快迭代的收斂速度快。用用G-S迭代法解只需要一組

59、工作單元，用來保存迭代法解只需要一組工作單元，用來保存 或或 分量。分量。)1( kx)(kx分量分量 ，因此，計(jì)算，因此，計(jì)算 就可沖掉就可沖掉 , ,于是利于是利)1, 2 , 1()1( ijxkj)1( kix)( kixG-S迭代存貯少。迭代存貯少。 351110288321321321xxxbAxxxxxxx或或Tx)1 , 1 , 1( 精確解精確解例例5.1 用用Jacobi迭代法，迭代法，G-S迭代法解下述方程組迭代法解下述方程組（1）Jacobi迭代公式：迭代公式： 5/ )3(10/ )211(8/ )8()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkk

60、kkkkkkxxxxxxxxx其中，其中， ，計(jì)算結(jié)果見表，計(jì)算結(jié)果見表1。 ), 1 , 0( ,),()(3)(2)(1)( kxxxxTkkkk表表1 ( )(0)(1)(2)(3)(4)(5)( )1( )2( )301.01.06250.99250.998125 1.000693801.10.960.98951.001951.00001500.61.021.00450.99641.000015kkkkxxxxxxxxxx且有且有 0007. 0)5( xx 5/ )3(10/ )211(8/ )8()1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkx