第三講 線性方程組的解法3

1、矩陣的“范數(shù)”是對向量和矩陣的大小的一種度量,可以看作是是二維和三維向量長度概念的推廣。數(shù)域:數(shù)的集合,對加法、乘法和除法（除數(shù)不為零）封閉。線性空間:線性代數(shù)中向量空間概念的抽象和推廣,定義了元素的加法與乘法，且滿足8條運(yùn)算規(guī)律。向量空間 3.5 向量和矩陣的范數(shù)向量和矩陣的范數(shù)n維向量的非空集合，對于加法及數(shù)乘兩種運(yùn)算封閉。定義, xRnn中任意一個(gè)向量維向量空間對于xR若存在一個(gè)實(shí)數(shù)與它對應(yīng)，且滿足(1) ()0, 00;xxx正定性且;,)()2(RRxxxn，齊次性.,)()3(nRyxyxyx，三角不等式.的范數(shù)為向量則稱xxnC對于復(fù)線性空間中的向量范數(shù)可以類似定義.一、一、向量

2、的范數(shù)向量的范數(shù)TnnnxxxxCR),(,)(21設(shè)中在向量空間的范數(shù)有常用的向量 x2x2122221)(nxxx范數(shù)或歐氏范數(shù)的 2x1xnxxx21范數(shù)的1xxinix1max范數(shù)的x-(1)-(2)-(3)pxppnppxxx121)(,1xpp的范數(shù)。2x和1x顯然時(shí)的特例和在是21ppxp由于由于pxx所以也是的特例-(4)()pxxp 時(shí)（三角不等式的驗(yàn)證困難一些）（三角不等式的驗(yàn)證困難一些）例題例題 求下列向量的各種常用范數(shù)求下列向量的各種常用范數(shù)Tx)1,3 ,4 , 1(解解:1x421xxx92x21242221)(xxx3327 xiix41max4范數(shù)的性質(zhì)范數(shù)的性

3、質(zhì)性質(zhì)性質(zhì)1yxyxRyxn則,性質(zhì)性質(zhì)2,nnRxxxMmxRm xxM x 中任意兩種范數(shù)和總存在兩個(gè)與 無關(guān)的正常數(shù)和 ，使有2性質(zhì) 稱為范數(shù)的等價(jià)性質(zhì)。Px為了方便，經(jīng)常采用如下簡單記號或。證明稍復(fù)雜些證明稍復(fù)雜些 定義定義(向量序列收斂向量序列收斂) , 2 , 1,21kxxxxknkkk設(shè)有向量序列nxxxx21和向量 (12), lim1,2,kiiki inxxin若對所有， ，都有 xxxxkkklim,記作收斂于則稱向量序列可用向量范數(shù)的大小判斷向量序列的收斂性?？捎孟蛄糠稊?shù)的大小判斷向量序列的收斂性。定理定理 nkRxx對上的任何一種向量范數(shù)，向量序列 收斂于 的充要條

4、件是 時(shí)當(dāng)kxxk0證明證明： limkkxxni, 2 , 1 0kxxk limkiikxx lim0kiikxx（） kxxxxkk則00 *lim0kkkxxxxk 即 使，存在上任何一種范數(shù)對, 0,mMRn xxMxxxxmkkk定義,ARnn中任意一個(gè)矩陣對于空間對應(yīng)，且滿足與若存在唯一一個(gè)實(shí)數(shù)ARA (1) ()0 00;AAA正定性，(2) ();AAR齊次性，(3) ()ABAB三角不等式，.的范數(shù)為矩陣則稱AAn nC復(fù)空間中的矩陣范數(shù)可以類似定義.,)4(nnRBABAAB，二、二、矩陣的范數(shù)矩陣的范數(shù)定義（相容范數(shù)）定義（相容范數(shù)）n nnRR假設(shè)在中規(guī)定了一種矩陣范

5、數(shù)，在中規(guī)定n nRA了一種向量范數(shù)，若對中的任何一個(gè)矩陣，恒有不等式中的任何一個(gè)向量和xRnxAAx成立，則說上述矩陣范數(shù)和向量范數(shù)是相容的相容的。 定義（算子范數(shù)，誘導(dǎo)范數(shù)，從屬范數(shù)）定義（算子范數(shù)，誘導(dǎo)范數(shù)，從屬范數(shù)）,nn nvxRARx設(shè)且給出一種向量范數(shù)則稱n0RmaxvvxvxAxAxA為矩陣 的算子范數(shù)?？梢宰C明它滿足矩陣范數(shù)的可以證明它滿足矩陣范數(shù)的4個(gè)條件個(gè)條件()vvvAxAx1) 1 (Aniijnja11max,大值的每列絕對值之和的最A(yù)的列范數(shù)稱AA)2(njijnia11max,大值的每行絕對值之和的最A(yù)的行范數(shù)稱A2)3(A)(maxAATmax()TTA AA

6、 A為的最大特征值.2A稱 的范數(shù)-(5)-(6)-(7)可以得到從屬于1-范數(shù)、2-范數(shù)、 -范數(shù)的矩陣范數(shù)nnijaAn)(階方陣設(shè)21112ninjijFaA不難驗(yàn)證其滿足定義2的4個(gè)條件。是一種矩陣范數(shù)因此FA稱為Frobenius范數(shù),簡稱F-范數(shù)（又稱為Schur范數(shù)）還有一種常用的矩陣范數(shù)，類似向量的 2-范數(shù)1122tr()tr()TTFAA AAA，而且可以驗(yàn)證tr為矩陣的跡。 1(12) maxn niii ninARnAA 設(shè)， ， ，為矩陣的 個(gè)特征值，稱為矩陣 的譜半徑。定義定義定理定理An nAR矩陣的譜半徑不超過 的任一種算子范數(shù)。Axx證明證明vvvvvAxxx

7、Ax vvAAA例題求矩陣A的各種常用范數(shù)110121021A解:1Aniijnja11max25234252 ,5 ,2max1njAnjijnia11max42 ,4 ,3max1ni2A)(maxAAT由于的特征值因此先求AATAAT110121021110122011211190102特征方程為)det(AAIT2111901020的特征值為可得AAT9361. 0,9211. 2,1428. 93211428. 9)(maxAAT2A)(maxAAT0237. 3FAtr()TA A2926056. 31AA2AFA容易計(jì)算容易計(jì)算計(jì)算較復(fù)雜計(jì)算較復(fù)雜;對矩陣元素的對矩陣元素的變化比

8、較敏感變化比較敏感;性質(zhì)較好性質(zhì)較好;使用最廣泛使用最廣泛.不是算子范數(shù)不是算子范數(shù)較少使用較少使用三、方程組的性態(tài)和條件數(shù)三、方程組的性態(tài)和條件數(shù)用數(shù)值方法解線性方程組時(shí)，計(jì)算結(jié)果有時(shí)不準(zhǔn)確。用數(shù)值方法解線性方程組時(shí)，計(jì)算結(jié)果有時(shí)不準(zhǔn)確。原因主要可能在兩個(gè)方面原因主要可能在兩個(gè)方面。1. 計(jì)算方法設(shè)計(jì)不合理；2. 方程組本身有問題，再好的方法也無濟(jì)于事。關(guān)于第一個(gè)原因，我們在前面已經(jīng)有這方面的例子，例如用Gauss消去法解線性方程組(用3位十進(jìn)制浮點(diǎn)數(shù)計(jì)算）210001. 02121xxxx關(guān)于第二個(gè)原因，請看下例：例4. 如下兩個(gè)方程組00001. 800001. 628622121xxx

9、x1121xx00002. 899999. 528622121xxxx21021xx12722121xxxx例5. 如下兩個(gè)方程組003. 10009. 12722121xxxx3121xx00006. 399998. 021xx定義 ,.AxbAb對于線性方程組如果系數(shù)矩陣 或常數(shù)項(xiàng) 的元素的微小變化,就會引起方程組解的巨大變化,則稱該方程組是 病態(tài) 的,否則稱為 良態(tài) 的1. bb常數(shù)項(xiàng) 的擾動對方程組解的影響,AxbAx設(shè)為一線性方程組為非奇異為其精確解xbb則解也應(yīng)存在誤差存在誤差若常數(shù)項(xiàng),即有bbxxA)(bxAbAx1bAx1bA1Axb xA bAx1bbAAxx1-(8)-(9

10、)-(10)所以又因?yàn)榭傻?8)和(9)兩式相乘,得相對誤差上式表明，由常數(shù)項(xiàng)產(chǎn)生的誤差,最多可將解的相對誤差放大 倍。1 AA2. AA系數(shù)矩陣 的擾動對方程組解的影響bxxAA)(xAA則解也應(yīng)存在誤差存在誤差若系數(shù)矩陣,0 xAxAxA)(xxAxAbxAxAAxAx11AA如果假設(shè)則)(1xxAAxxxAAxxAAx11)(xAAxAA111111AAAAAAAAAAAAxx111-(11)3. ,AAbb系數(shù)矩陣 有擾動同時(shí)右端項(xiàng) 有擾動，則此時(shí)解也應(yīng)存在誤差x定義稱為非奇異矩陣設(shè),A.,為某種范數(shù)其中的條件數(shù)為A1cond( )AAA同理可推導(dǎo)得bbAAAAAAxx111bbxxA

11、A顯然1cond( )AAA1 AAI1即任意方陣的條件數(shù)不小于即任意方陣的條件數(shù)不小于1根據(jù)范數(shù)的不同也有不同的條件數(shù):1111cond( )AAA1cond( )AAA1222cond( )AAA)(1)(minmaxAAAATT)()(minmaxAAAATTcond(A)xbxb-(12)xx-(13)根據(jù)矩陣范數(shù)定義,(10)式和(11)式可表示為cond( )AAA)1(時(shí)AA-(14)cond( )AbA由系數(shù)矩陣 和常數(shù)項(xiàng) 的擾動引起的解的相對誤差放大倍數(shù)不超過倍1cond A1AAAAcond( )A即條件數(shù)是刻劃原始數(shù)據(jù)變化對解的影響的指標(biāo).cond( ),A一般越大 解的

12、相對誤差也可能越大cond( ),AAxb因此很大時(shí)就可能是 病態(tài) 方程組 6.2 線性方程組的迭代法線性方程組的迭代法用直接法解線性方程組時(shí)要對系數(shù)矩陣不斷變換如果方程組的階數(shù)很高,則運(yùn)算量將會很大,并且大量占用計(jì)算機(jī)資源.因此對線性方程組bAx 有必要尋找更經(jīng)濟(jì)、適用的數(shù)值解法，迭代方法就是一種適合這個(gè)要求的方法.(,)n nnnARbRxR-(1)如果能將線性方程組(1)變換為等價(jià)形式xBxd-(2),n nnnBRdRxR其中則可以對線性方程組(2),采用以下迭代格式:(1)( )kkxBxd),2 , 1 ,0(k-(3)( )kx迭代法產(chǎn)生一個(gè)迭代序列，如果其極限存在,*)(lim

13、xxkk則稱迭代法收斂, x*就是方程組的解。 否則稱為發(fā)散。即一、簡單迭代法(Jacobi迭代法)設(shè)線性方程組(1)的一般形式為11212111bxaxaxann22222121bxaxaxannnnnnnnbxaxaxa2211),2 , 1(0niaii設(shè)ix則可從上式解出,1111()()nniiijjiiijjjjiiiij ixba xxba xaa-(4)(11)()()1(njkjijiiikikixabaxx根據(jù)上式作迭代過程(1,2, ; 0,1,2,)ink1122diag(,)nnDaaa令則(4)式轉(zhuǎn)化為矩陣形式)()(1)()1(kkkAxbDxxbDAxDxxkk

14、k1)(1)()1(1)1()1()kkxDDA xDb-(5)令0000002121nnaaaL0000002112nnaaaUULDAULADA的下三角部分的負(fù)矩陣A的上三角部分的負(fù)矩陣則有故迭代過程(5)化為bDxULDxkk1)(1)1()(11 (), EDLUdDb令，于是有(1)() (0,1,2,)kkxExdk等價(jià)線性方程組為xExdbAx 簡單迭代法的更一般形式可以采用如下方法得到11 ACDCCDxbCxDxbxCDxCbxExd令，為非奇異。則方程組變?yōu)?（）),2 , 1 ,0(k-(6)稱稱(6)式為解線性方程組式為解線性方程組(1)的的Jacobi迭代法。迭代法。

15、JacobiE為迭代法的迭代矩陣.(1)( )kkxExd取迭代格式例題 用Jacobi迭代法求解方程組,運(yùn)算保留4位小數(shù)1233204121114238321xxx解:4121114238A4000110008D31084410,1111110241E()DLU1dDb335 .2(0)0 0 0 ,JacobiTx取初值使用迭代法(1)()kkxExd),2 , 1 ,0(nk x1= 2.5000 3.0000 3.0000 x2= 2.8750 2.3636 1.0000 x3= 2.1364 2.0455 0.9716 x4 = 3.0241 1.9478 0.9205 x5 = 3

16、.0003 1.9840 1.0010 x6 = 2.9938 2.0000 1.0038 x7 = 2.9990 2.0026 1.0031 x8 = 3.0002 2.0006 0.9998 x9 = 3.0003 1.9999 0.9997 x10 = 3.0000 1.9999 0.9999x11 = 3.0000 2.0000 1.0000 x12 = 3.0000 2.0000 1.0000迭代結(jié)果如下：迭代結(jié)果如下：0000.10000.20000.3321xxx方程組的解為方程組的解為二、迭代法收斂的條件若將迭代格式改寫為如下形式 nknnnknknknknnkkkknnkkk

17、dxcxcxcxdxcxcxcxdxcxcxcx2211122222121121121211111( )或(k+1)(k)xCxd迭代格式（*）何時(shí)收斂，若收斂又收斂到何處？考察如下式子，(1)( )( )(1)( )(1)( )(1)2(1)(2)(1)(0) () kkkkkkkkkkkxxCxdCxdC xxCxxCxxCxx1, C 顯然有，若則迭代收斂。(1)( )*limlim, kkkkxCxdxCxd即有*,x若迭代序列收斂到則有即若迭代收斂，必收斂到方程組的解。 1102 , max1niji nicx 充分條件在迭代格式(*)中 若則迭代對任意初始值都是收斂的。2113 1

18、nnijijc充分條件若，則迭代格式(*)收斂。 1101 ,max1niji njcx 充分條件在迭代格式（ ）中若，則迭代對任意初始值都是收斂的。具體地，我們可給出如下結(jié)論具體地，我們可給出如下結(jié)論進(jìn)一步分析Jacobi迭代法的迭代過程,三、Gauss-Seidel迭代法 nknnnknknknknnkkkknnkkkdxcxcxcxdxcxcxcxdxcxcxcx2211122222121121121211111(1)(1)(1)(1)121(1)()()()121(1)(1)(1)(1)121,?kkkkiikkkkiikkkkiixxxxxxxxxxxx我們會發(fā)現(xiàn)在之前已經(jīng)求出，但當(dāng)

19、求時(shí) 仍用進(jìn)行迭代，能否求時(shí)，利用進(jìn)行迭代呢 1111 11221111221 1222221111 122kkkknnkkkknnkkkknnnnnnnxc xc xc xdxc xc xc xdxc xc xc xd構(gòu)造下列迭代格式 1111 (1,2, ).inkkkiijjijjijj ixc xc xdin或稱上式為高斯稱上式為高斯賽德爾（賽德爾（Gauss-Seidel）迭代格式。）迭代格式。Gauss-Seidel迭代法收斂的條件：迭代法收斂的條件：前面的三個(gè)充分條件依然成立。迭代過程的終止：迭代過程的終止： 1| |? (1,2, ).kkkiiixxxin 給定精度，判斷 |

20、(1)1()1 () kkxDLU xDb當(dāng)時(shí),UL注意到 的為下三角為上三角,皆不含對角線上式上式的Gauss-Seidel 迭代格式為bUxLxDxkkk)()1(1)1(-(7)例題 用Gauss-Seidel迭代法求解例1.解:(0)0,0,0 ,Gauss-SeidelTx取初值使用迭代法(1)()()1231( 32)2.58kkkxxx (1)(1)()2134131111kkkxxx (1)(1)(1)3121(2)34kkkxxx 1233204121114238321xxxx1 =2.5000 2.0909 1.2273x2=2.9773 2.0289 1.0041x3 =

21、3.0098 1.9968 0.9959x4 =2.9998 1.9997 1.0002x5 =2.9998 2.0001 1.0001x6 =3.0000 2.0000 1.0000 x7 =3.0000 2.0000 1.0000通過迭代,至第7步得到滿足精度的解x7從例1和例2可以看出,Gauss-Seidel迭代法的收斂速度比Jacobi迭代法要快。四、嚴(yán)格對角占優(yōu)矩陣的Jacobi和G-S迭代法ijAan n定義 設(shè)是一個(gè)階矩陣，若), 2 , 1(1niaanijjijii則稱A為嚴(yán)格對角占優(yōu)矩陣。4 AxdAn n定理設(shè)方程組，若 為階嚴(yán)格對角占優(yōu)矩陣，則一定存在收斂的Jacob

22、i和G-S迭代格式。22212221()njjjjxa xba11()niijjijiijixa xba11111111()njjjjxa xba11()nnnjjnjnnj nxa xbaixi個(gè)方程分離出從第易見， 滿足收斂的充分條件1。xExb1,E五、超松弛（SOR）迭代法加速收斂方法1(1)(1)()1inkkkiijjijjijjixc xc xd考慮解線性方程組的Gauss-Seidel迭代法1(1)(1)()1inkkkiijjijjijjixc xc xd記 1 (1,2, )niijjijxc xdin現(xiàn)在考慮迭代加速的情形。假設(shè)變形方程組為上式稱為超松弛法(SOR迭代法),稱為松弛因子1SORGS當(dāng)時(shí)，格式即為迭代格式；12當(dāng)時(shí)，稱為超松弛迭代法；01當(dāng)時(shí)，稱為低松弛（欠松弛）迭代格式。(1)(1)()()(1)()2, 1 () kkkiiikkkiiixxxxxx取一因子，一般0構(gòu)造如下迭代（）(1,2,; 1,2,)ink例題用G-S法和SOR法求下列方程組的解,45.