第六節(jié)收斂性討論續(xù)

1、 nknnnknnnknknnkkknnkkbxaxaaxbxaxaaxbxaxaax)()()()()()()()()(.1 11 11 11 11 12 22 21 12 21 12 22 21 12 21 11 12 21 12 21 11 11 11 11 11 11 1bdxadixkk1 11 11 11 1 )()()().矩陣形式：jacobi jacobi 迭代格式迭代格式分量形式：).2 2.)()1 13 31 1 adi 格式收斂條件.1 11 1 adiulda bdxuldxkk1 11 11 1 )()()(第六節(jié)收斂性討論第六節(jié)收斂性討論 /* on conve

2、rgence of iterative methods */6 on convergence of iterative methods)(11)(1)(414)(313)(21211)1(1bxaxaxaxaaxknnkkkk )(12)(2)(424)(323)1(12122)1(2bxaxaxaxaaxknnkkkk )(13)(3)(434)1(232)1(13133)1(3bxaxaxaxaaxknnkkkk )(1)1(11)1(33)1(22)1(11)1(nknnnknknknnnknbxaxaxaxaax 2 2）矩陣形式）矩陣形式：bduxlxdxkkk1 11 11 11

3、1 )()()()(blduxldxkk1 11 11 1 )()()()(bg分量形式：)1 11 11 1 )(uld 3 3）迭代格式收斂條件）迭代格式收斂條件.)(1 11 1 uld nxxxx.,2 21 1 nyyyy.,2 21 1 ininiiiibxaxaay .2 22 21 1nifor, 2 21 1 ? xyyoutputstopyes ,xyn o, nxxxx.,2 21 1 nifor, 2 21 1 ininiiiibxaxaax .2 22 21 1mk 1 1 kxoutputstopyes ,no1 1 kkjacobi 迭代格式迭代格式gauss -

4、 seidel 迭代格式迭代格式二種方法都存在二種方法都存在收斂性問題收斂性問題。 有例子表明：有例子表明：gauss-seidel法收斂時(shí)，法收斂時(shí)，jacobi法可能法可能不收斂；而不收斂；而jacobi法收斂時(shí)，法收斂時(shí)， gauss-seidel法也可能法也可能不收斂。不收斂。收斂性迭代法求解下面方程組考察用seidelgaussjacobi .),()(迭代兩次并就初始迭代向量tx0 00 00 00 0 1 12 22 21 11 12 22 23 32 21 13 32 21 13 32 21 1xxxxxxxxx 1 12 22 21 11 11 12 22 21 1a 0 0

5、2 22 21 10 01 12 22 20 01 11 1adiuldb)(6 on convergence of iterative methods 0 02 22 21 10 01 12 22 20 01 11 1adiuldb)(.),max(,),max(1 14 43 34 43 31 14 44 42 24 41 1 bb顯然.充分性條件失效2 22 22 20 02 22 20 01 11 12 22 22 22 21 11 12 22 21 11 12 22 22 2 bi0 02 22 22 22 22 23 32 2 )()(0 0 )(b .迭代法收斂jacobi6 o

6、n convergence of iterative methods?)(1 11 1 uld 1 12 22 21 11 11 12 22 21 1a 1 12 22 20 01 11 10 00 01 1ld 0 00 00 01 10 00 02 22 20 0u 1 12 20 00 01 11 10 00 01 11 1)(ld 2 20 00 03 32 20 02 22 20 01 1uldb)(0 02 22 20 00 03 32 20 02 22 22 2 )( bi1 12 2 )(b .發(fā)散seidelgauss 6 on convergence of iterativ

7、e methods!,的收斂性很繁從迭代矩陣討論seidelgaussjacobi ?,迭代格式的收斂性自身就可以判斷能否直接由系數(shù)矩陣seidelgaussjacobia 迭代格式的收斂性！以判斷滿足一定條件時(shí)，就可當(dāng)系數(shù)矩陣seidelgaussjacobia ,定義（對(duì)角占優(yōu)陣）nnijaa )(設(shè)的元素滿足、如果a)(1 1niaaiinijjij, 2 21 11 1 .為嚴(yán)格對(duì)角占優(yōu)矩陣稱a的元素滿足、如果a)(2 2niaaiinijjij, 2 21 11 1 立，且至少有一個(gè)不等式成.為弱對(duì)角占優(yōu)矩陣稱a6 on convergence of iterative method

8、s）定義（可約與不可約陣使得如果存在置換矩陣設(shè),)(paannij (1) 2 22 21 12 21 11 10 0aaaappt.為可約陣階方陣，則稱為階方陣，為其中arnara 2 22 21 11 1.為不可約陣否則，稱a.),式新排列可以化成即對(duì)進(jìn)行若干行列的重為可約陣1 1 (a事實(shí)上可以化為低階方程求解為可約陣，如果.baxa bpxpappttt )(bax tptp(2) )()()()(2 21 12 21 12222121211110 0ddyyaaabpdt xpyt 6 on convergence of iterative methods)()()(1 12 21

9、12 21 11 11 1byaya )()(2 22 22 22 2bya .為不可約的情形下面我們只討論a.為不可約矩陣a,的元素都不為零時(shí)顯然，a定理：陣為不可約陣弱對(duì)角占優(yōu)為嚴(yán)格對(duì)角占優(yōu)陣或如果aa.()det(為非奇異矩陣）aa0 0 .)(給出為嚴(yán)格對(duì)角占優(yōu)陣情形只對(duì)證明a.()det(為奇異矩陣）若aa0 tnxxxxax),(2 21 10 0 有非零解，記作 xxxxxnk,max2 21 16 on convergence of iterative methods0 01 1 jnjkjxakkkjnkjjkjxaxa 1 1 nkjjkjkjnkjjkjjnkjjkjkk

10、kkkkaxxaxaxaxa1 11 11 1 nkjjkjkkaa1 1個(gè)方程有對(duì)于第k6 on convergence of iterative methods定理：陣為不可約陣弱對(duì)角占優(yōu)為嚴(yán)格對(duì)角占優(yōu)陣或如果aa0 0 a.)(給出為嚴(yán)格對(duì)角占優(yōu)陣情形只對(duì)證明a.,迭代都收斂則seidelgaussjacobi 1 11 11 11 1 )()(ulduld（，只需證明 不是迭代矩陣的數(shù)于只需證明任意絕對(duì)值大 1的特征值?。ǎ?(ulduld 1 11 1!)(0 00 01 11 1 uldiuldi（，也就是 )()()(uldlduldi 1 11 1)()()(uldlduldi

11、 1 11 10 01 1 )(ld0 )(uld 往證6 on convergence of iterative methods nnnnnnaaaaaaaaauld 2 21 12 22 22 22 21 11 11 12 21 11 1)(auld niaaanijijijijii, 2 21 11 11 11 1 nijijijijiiiiaaaa1 11 11 1 nijijijijaa1 11 11 1 .)(det(,)(0 0 ulduld 嚴(yán)格對(duì)角占優(yōu)6 on convergence of iterative methods定理：證明nl ,2 21 1的特征值為. 2 0

12、0方法收斂，則的設(shè)sorbax,)(,1 1 lsor方法收斂設(shè)nnll)()det( 2 21 11 12 21 11 1 )()det( llnnn)det()det()det(udldl 1 11 1nl)()det( 1 12 20 01 11 1 6 on convergence of iterative methods定理：證明.,120 的特征值時(shí)往證在l.方法收斂的求解sorbax 則如果對(duì)稱正定，設(shè),2 2 0baxyyly 即的特征向量為對(duì)應(yīng)于設(shè),yyudld )()(1 11 1yldyud)()( 1 1),)(),)(yyldyyud 1 1),(),(),(),()

13、,(ylyydyyuyydyydy ),(),(),(),(),(ylyydyyuyydyydy 6 on convergence of iterative methods0 02 21 1 iniiiyaydy),( :顯然 iyly ),(: 記),(),(),(),(),(ylyydyyuyydyydy ttluaa ,),(tttuldaulda iylylyyyylyuyt ),(),(),(),()()( ii ),)()()()(2 21 12 21 12 21 12 22 22 22 22 2zzzzzzzz ( ii )6 on convergence of iterativ

14、e methods 2 22 22 22 22 2)()()()( 只需證觀察分子分母,2 2)()( 2 1 2 2 就有2 22 2)()()()( 222 2 2)()( 222 )()( 222 2)2 )(的符號(hào)看 2 ),(),(),(),)(),(yuyylyydyyyuldyay 0 00 02 2 ii2 0 01 2 2 6 on convergence of iterative methods定理：陣為不可約陣弱對(duì)角占優(yōu)為嚴(yán)格對(duì)角占優(yōu)陣或如果aa略）證明(.方法收斂的時(shí)，解則當(dāng)sorbax 1 10 0 .的情形的特例，是1 1 sorseidelgaussbax 求解如果對(duì)稱正定由定理知,.方法收斂的sg 6 on convergence of iterative methods本章重點(diǎn)總結(jié)本章重點(diǎn)總結(jié)bdxuldxkk1 11 11 1 )()()(bduxlxdxkkk1 11 11 11 1 )()()()(gbxxkk )()(1 1 一般迭代法1 1 )(b sg )2 2 jacobi)1 1sor )3 3bldxudldxkk1 11 11 11 1 )()()()