經(jīng)濟(jì)學(xué)解線性方程組的迭代法PPT課件

1、16.1 迭代法的基本概念迭代法的基本概念 考慮線性方程組 ,bAx （1.1）其中 為非奇異矩陣，當(dāng) 為低階稠密矩陣時(shí)，第5章所討論的選主元消去法是有效方法. AA 但對(duì)于 的階數(shù) 很大，零元素較多的大型稀疏矩陣方程組，例如求某些偏微分方程數(shù)值解所產(chǎn)生的線性方程組來說，利用迭代法求解則更為合適. An 迭代法通常都可利用 中有大量零元素的特點(diǎn). A第1頁/共49頁2 例例1 1.361236,33114,20238321321321xxxxxxxxx（1.2）記為 , bAx ,12361114238A方程組的精確解是 . Tx)1,2, 3(*求解方程組 其中 ,321xxxx.36332

2、0b現(xiàn)將(1.2)改寫為 第2頁/共49頁3).3636(121),334(111),2023(81213312321xxxxxxxxx（1.3）或?qū)憺?, fxBx0,01231261110114828300B其中 .12361133820f第3頁/共49頁4 將這些值代入(1.3) 式右邊 (若(1.3)式為等式即求得方程組的解，但一般不滿足). 任取初始值，例如取 . Tx)0,0,0()0(,)3, 3,5.2(),()1(3)1(2)1(1)1(TTxxxx再將 分量代入(1.3)式右邊得到 ，反復(fù)利用這個(gè)計(jì)算程序，得到一向量序列和一般的計(jì)算公式(迭代公式) )1(x)2(x,)(3

3、)(2)(1)()1(3)1(2)1(1)1()0(3)0(2)0(1)0(kkkkxxxxxxxxxxxx 得到新的值 第4頁/共49頁5,8/ )2023()(3)(2)1(1kkkxxx,11/ )334()(3)(1)1(2kkkxxx（1.4）.12/ )3636()(2)(1)1(3kkkxxx簡(jiǎn)寫為 ,)(0)1(fxBxkk其中 表示迭代次數(shù) k).,2, 1 ,0(k 迭代到第10次有 ;)9998813.0,999838.1,000032.3()10(Tx第5頁/共49頁6 從此例看出，由迭代法產(chǎn)生的向量序列 逐步逼近)(kx方程組的精確解 .*x 對(duì)于任何由 變形得到的等

4、價(jià)方程組 ，fBxxbAx 迭代法產(chǎn)生的向量序列 不一定都能逐步逼近方程組的解 . )(kx*x*).(000187.0)10()10()10(xx 如對(duì)方程組.53,521221xxxx第6頁/共49頁7構(gòu)造迭代法.53,52)(1)1(2)(2)1(1kkkkxxxx則對(duì)任何的初始向量，得到的序列都不收斂. 對(duì)于給定方程組 ，fBxx設(shè)有唯一解 ，*x.*fBxx（1.5）又設(shè) 為任取的初始向量，)0(x,2, 1 ,0,)()1(kfBxxkk（1.6）其中 表迭代次數(shù). k則 按下述公式構(gòu)造向量序列 第7頁/共49頁8 定義定義1 1(1) 對(duì)于給定的方程組 ，fBxx逐步代入求近似解

5、的方法稱為迭代法( (或稱為一階定常迭代法，這里 與 無關(guān)). Bk (2) 如果 存在(記為 )，)(limkkx*x顯然 就是方程組的解，否則稱此迭代法發(fā)散. *x用公式(1.6)稱此迭代法收斂， 研究 的收斂性. )(kx 引進(jìn)誤差向量 *,)1()1(xxkk由(1.6)減去(1.5)式，得 ，),2, 1 ,0()()1(kBkk第8頁/共49頁9 要考察 的收斂性, 就要研究 在什么條件下有)(kxB0lim)(kk.0lim(零矩陣)kkB亦即要研究 滿足什么條件時(shí)有B)1()(kkB遞推得 .)0(kB第9頁/共49頁106.2 Jacobi Jacobi迭代法與迭代法與Gau

6、ss-SeidelGauss-Seidel迭迭代法代法 設(shè)有 ,bAx （2.1）其中， 為非奇異矩陣. nnijaAR)( 將 分裂為 A,NMA（2.2）其中， 為可選擇的非奇異矩陣，且使 容易求解，MdMx 一般選擇為 的某種近似，稱 為分裂矩陣. AM第10頁/共49頁11 于是，求解 轉(zhuǎn)化為求解 ，bAx bNxMx.11bMNxMxbAx求解即求解可構(gòu)造一階定常迭代法 ,2, 1 ,0,)()1()0(kfBxxxkk），（初始向量（2.3）其中 NMB1.1bMf)(1AMM,1AMI稱 為迭代法的迭代矩陣.AMIB1第11頁/共49頁12 選取 陣，就得到解 的各種迭代法. M

7、bAx 設(shè) , 并將 寫為三部分 ),2, 1(0niaiiAnnaaaA22110000, 121,211, 112nnnnnnaaaaaa（2.4）.ULD00001,212, 11 , 121nnnnnnaaaaaa第12頁/共49頁13 6.2.1 雅可比迭代法雅可比迭代法 由 ，選取 為 的對(duì)角元素部分，M),2, 1(0niaiiA解 的雅可比(Jacobi)迭代法 bAx 即選取 (對(duì)角陣)， ，DM NDA,2, 1 ,0,)()1()0(kfBxxxkk），（初始向量（2.5）其中 ADIB1 稱 為解 的雅可比迭代法的迭代陣. JbAx 由(2.3)式得到.1bDf)(1U

8、LD,J第13頁/共49頁14 研究雅可比迭代法(2.5)的分量計(jì)算公式. ,),()()()(1)(Tknkikkxxxx記 由雅可比迭代公式(2.5), 有 ,)()()1(bxULDxkk或 ).,2, 1(1)(11)()1(nibxaxaxainijkjijijkjijkiii于是，解 的雅可比迭代法的分量計(jì)算公式為 bAx 第14頁/共49頁15,),()0()0(1)0(Tnxxx,/1)()1(iinijjkjijikiaxabx（2.6）., 1 ,0),2, 1(表示迭代次數(shù))(kni 由(2.6)式可知，雅可比迭代法計(jì)算公式簡(jiǎn)單，每迭代一次只需計(jì)算一次矩陣和向量的乘法且計(jì)

9、算過程中原始矩陣 始終不變.A第15頁/共49頁16(下三角陣)， 6.2.2 高斯高斯- -塞德爾迭代法塞德爾迭代法 選取分裂矩陣 為 的下三角部分，MA即選取 LDM,NMA于是由(2.3)式得到解bAx ,2, 1 ,0,)()1()0(kfBxxxkk（初始向量），（2.7）其中 ,G稱 為解 的高斯-塞德爾迭代法的迭代陣. ULDG1)(bAx 的高斯-塞德爾(Gauss-Seidel)迭代法 .)(1bLDfULD1)(ALDIB1)(第16頁/共49頁17 研究高斯-塞德爾迭代法的分量計(jì)算公式. ,),()()()(1)(Tknkikkxxxx由(2.7)式有 ,)()()1(b

10、UxxLDkk或 ,)()1()1(bUxLxDxkkk).,2, 1(1)(11)1()1(nixaxabxanijkjijijkjijikiii即 記 第17頁/共49頁18于是解 的高斯-塞德爾迭代法計(jì)算公式為 bAx (初始向量),Tnxxx),()0()0(1)0(,/1)(11)1()1(iinijkjijijkjijikiaxaxabx（2.8）)., 1 ,0;, 1(kni或 ,),()0()0(1)0(Tnxxx,)()1(ikikixxx,/1)(11)1(iinijkjijijkjijiiaxaxabx（2.9）)., 1 ,0;, 1(kni第18頁/共49頁19而由

11、高斯-塞德爾迭代公式可知， 雅可比迭代法不使用變量的最新信息計(jì)算 ，)1( kix計(jì)算 的第 個(gè)分量)1( kxi 時(shí)，)1( kix利用了已經(jīng)計(jì)算出的最新分量 .) 1, 2 , 1()1(ijxkj 由(2.8)可知，高斯-塞德爾迭代法每迭代一次只需計(jì)算一次矩陣與向量的乘法. 高斯-塞德爾迭代法可看作雅可比迭代法的一種改進(jìn). 算法算法1 1(高斯-塞德爾迭代法) 設(shè) ，bAx 其中 為非奇異矩陣且nnAR0iia),2, 1(ni本算法用高斯-塞德爾迭代法解 ，bAx 第19頁/共49頁20), 1(0.0.1nixi 迭代一次，這個(gè)算法需要的運(yùn)算次數(shù)至多與矩陣 的非零元素的個(gè)數(shù)一樣多.

12、A數(shù)組 開始存放 , )(nx)0(x,)(kx后存放0N為最大迭代次數(shù). 0,2, 1.2Nk對(duì)于ni, 1對(duì)于iinijjijijjijiiaxaxabx/111第20頁/共49頁21 例例2 2按高斯-塞德爾迭代公式,8/ )2023()(3)(2)1(1kkkxxx迭代7次，得 ，Tx)9999932.09999987.1000002.3()7(.361236,33114,20238321321321xxxxxxxxx（1.2）用高斯-塞德爾迭代法解線性方程組(1.2). Tx)0,0,0()0(取 ， ,11/ )334()(3)1(1)1(2kkkxxx) , 1 ,0(.12/

13、)3636()1(2)1(1)1(3kxxxkkk第21頁/共49頁22 由此例可知，用高斯-塞德爾迭代法，雅可比迭代法解線性方程組(1.2)(且取 )均收斂.0)0(x 而高斯-塞德爾迭代法比雅可比迭代法收斂較快(即取 相同，達(dá)到同樣精度所需迭代次數(shù)較少).)0(x 但這結(jié)論只當(dāng) 滿足一定條件時(shí)才是對(duì)的. A.1002.2*6)7(xx且 第22頁/共49頁23 6.3.1 解大型稀疏線性方程組的逐次超松弛解大型稀疏線性方程組的逐次超松弛迭代法迭代法 選取分裂矩陣 為帶參數(shù)的下三角陣 M),(1LDM其中 為可選擇的松弛因子. 0 于是，由(2.3)可構(gòu)造一個(gè)迭代法，其迭代矩陣為 ALDIL

14、1)(從而得到解 的逐次超松弛迭代法(Successive Over Relaxation Method, 簡(jiǎn)稱SOR方法). bAx ).)1()(1UDLD6.3 逐次超松弛迭代法 第23頁/共49頁24 解 的SOR方法為 bAx ,2, 1 ,0,)()1()0(kfxLxxkk（初始向量），（2.10）其中 ),)1()(1UDLDL.)(1bLDf 研究解 的SOR迭代法的分量計(jì)算公式. bAx ,),()()()(1)(Tknkikkxxxx記 第24頁/共49頁25,)1()()()1(bxUDxLDkk或 ).()()()1()()1(kkkkkDxUxLxbDxDx由(2.

15、10)式可得 由此，得到解 的SOR方法的計(jì)算公式 bAx ,),()0()0(1)0(Tnxxx,/1)(11)1()()1(iinijkjijijkjijikikiaxaxabxx（2.11）為松弛因子.), 1 ,0;, 1(kni第25頁/共49頁26或 ,),()0()0(1)0(Tnxxx,)()1(ikikixxx,/1)(11)1(iinijkjijijkjijiiaxaxabx（2.12）為松弛因子.), 1 ,0;, 1(kni 關(guān)于SOR迭代法 ， 有 (1) 顯然，當(dāng) 時(shí)，SOR方法即為高斯-塞德爾迭代法. 1第26頁/共49頁27 (2) SOR方法每迭代一次主要運(yùn)算

16、量是計(jì)算一次矩陣與向量的乘法. (3) 當(dāng) 時(shí)，稱為超松弛法；當(dāng) 時(shí)，稱為低松弛法. 11 (4) 在計(jì)算機(jī)實(shí)現(xiàn)時(shí)可用 )()1(11maxmaxkikiniinixxx控制迭代終止，或用 控制迭代終止. )()(kkAxbr SOR迭代法是高斯-塞德爾迭代法的一種修正. 第27頁/共49頁28 設(shè)已知 及已計(jì)算 的分量 )(kx)1( kx).1,2, 1()1(ijxkj (1) 首先用高斯-塞德爾迭代法定義輔助量 ,)1( kix./1)(11)1()1(iinijkjijijkjijikiaxaxabx（2.13） (2) 再由 與 加權(quán)平均定義 ，)(kix)1(kix)1( kix

17、)1()()1()1(kikikixxx將(2.13)代入(2.14)得到解 的SOR迭代(2.11)式. bAx 即 （2.14）).()()1()(kikikixxx第28頁/共49頁29 例例3 3,111141111411114111144321xxxx它的精確解為 .)1, 1, 1, 1(*Tx取 ，迭代公式為 0)0(x;4/ )41()(4)(3)(2)(1)(1)1(1kkkkkkxxxxxx用SOR方法解方程組 解;4/ )41()(4)(3)(2)1(1)(2)1(2kkkkkkxxxxxx;4/ )41()(4)(3)1(2)1(1)(3)1(3kkkkkkxxxxxx

18、.4/ )41()(4)1(3)1(2)1(1)(4)1(4kkkkkkxxxxxx第29頁/共49頁30取 ，3.1,)999999120,999999530,000003101,999996460()11(T.x.1046.052)11(取其他 值，迭代次數(shù)如下表. 第11次迭代結(jié)果為 第30頁/共49頁311099 . 1144 . 1538 . 1113 . 1337 . 1122 . 1236 . 1171 . 1175 . 1220 . 110*10*52)(52)(最少迭代次數(shù))的迭代次數(shù)滿足誤差松弛因子的迭代次數(shù)滿足誤差松弛因子16表xxxxkk 從此例看到，松弛因子選擇得好，

19、會(huì)使SOR迭代法的收斂大大加速. 本例中 是最佳松弛因子. 3.1第31頁/共49頁326.3 迭代法的收斂性迭代法的收斂性 6.3.1 一階定常迭代法的基本定理一階定常迭代法的基本定理 設(shè) ,bAx （3.1）其中 為非奇異矩陣，nnijaAR)(記 為(3.1)精確解，*x.fBxxbAx于是 .*fBxx（3.2）且設(shè)有等價(jià)的方程組第32頁/共49頁33 設(shè)有解 的一階定常迭代法 bAx .)()1(fBxxkk（3.3） 問題是： 迭代矩陣 滿足什么條件時(shí)，由迭代法產(chǎn)生的向量序列 收斂到 B)(kx.*x 引進(jìn)誤差向量 ).,2, 1 ,0(*)()(kxxkk由(3.3)式減(3.2

20、)式得到誤差向量的遞推公式 ,)()1(kkB).,2, 1 ,0()0()(kBkk第33頁/共49頁34 由6.1節(jié)可知，研究迭代法(3.3)收斂性問題就是要研究迭代矩陣 滿足什么條件時(shí)，有B(零矩陣).0limkkB 定義定義2 2設(shè)有矩陣序列 及 , nnkijkaAR)()(nnijaAR)(如果 個(gè)數(shù)列極限存在且有 2n),2, 1,(lim)(njiaaijkijk則稱 收斂于 ，kAA.limAAkk記為 第34頁/共49頁35 例例4 4,01A且設(shè) ，考查其極限. 1 解解由于，當(dāng) 時(shí)，有 1設(shè)有矩陣序列 ,02222A,0,1kkkkkA.0000limlimkkkkAA

21、.0limkk所以第35頁/共49頁36 矩陣序列極限概念可以用矩陣算子范數(shù)來描述. 定理定理1 1 0limlimAAAAkkkk 證明證明.0limlimAAAAkkkk再利用矩陣范數(shù)的等價(jià)性，可證定理對(duì)其他算子范數(shù)亦對(duì). 定理定理2 2AAkklim 對(duì)任何向量 都有nxR.limAxxAkk其中為矩陣的任意一種算子范數(shù). 顯然有 （證明略）第36頁/共49頁37 定理定理3 3設(shè) , nnijbBR)(則 (零矩陣)的0limkkB充分必要條件是矩陣 的譜半徑 B.1)(B 證明證明由矩陣 的若當(dāng)標(biāo)準(zhǔn)型，存在非奇異矩陣 使 BP,211JJJJBPPr其中若當(dāng)塊 ,11iinniiii

22、J第37頁/共49頁38且 ，nnrii1,1PJPB其中 .21krkkkJJJJ于是 ).,2, 1(0lim0limriJBkikkk 下面考查 的情況. kiJ顯然有,1PPJBkk引進(jìn)記號(hào) ).(R000,ittktntktIE第38頁/共49頁39 顯然有， ,0,IEt由于 , 1, tiiEIJktikiEIJ)(1 ,),(0,tkEkt當(dāng).)(,1,ktktEE 因此 kjjtjkijkEC01 ,)(10,tjjtjkijkECttkikiktkitkkikkitkitkkikkikkiCCCCCC11)2(211)1(12211),2, 1(ri第39頁/共49頁40其

23、中 )!( !jkjkCjk利用極限 ，)0, 10(0limrcckkrk.10limjkjkkC所以 的充要條件是 ，0limkikJ),2, 1(1rii.1)(B.!)1()1(jjkkk得到即 第40頁/共49頁41 定理定理4 4,fBxx（3.4）(迭代法基本定理)設(shè)有方程組 及一階定常迭代法 .)()1(fBxxkk（3.5）對(duì)任意選取初始向量 ，)0(x矩陣 的譜半徑 B.1)(B迭代法(3.5)收斂的充要條件是 證明證明設(shè) ，1)(B易知fAx )有唯一解，BIA記為 ，*x充分性. (其中則 ,*fBxx第41頁/共49頁42誤差向量 *)()(xxkk由設(shè) ，1)(B.

24、0limkkB,)0(kB. *)0()0(xx應(yīng)用定理3，有 于是對(duì)任意 ,)0(x有 ，0limkk 必要性. 設(shè)對(duì)任意 有 )0(x*,lim)(xxkk其中 .)()1(fBxxkk.*lim)(xxkk即 顯然，極限 是方程組(3.4)的解，*x且對(duì)任意 有 )0(x*)()(xxkk).(0)0(kBk第42頁/共49頁43由定理2知 ,0limkkB再由定理3，即得 .1)(B 推論推論設(shè) ，bAx 其中 為非奇異矩陣ULDA且 非奇異，則 D (1) 解方程組的雅可比迭代法收斂的充要條件是 ，1)(J).(1ULDJ其中 (2) 解方程組的高斯-塞德爾迭代法收斂的充要條件是, 1)(G.)(1ULDG其中 (3) 解方程組的SOR方法收斂的充要條件是 ，1)(L).)1()(1UDLDL其