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

2、x)1,2, 3(*求解(qi ji)方程組 其中(qzhng) ,321xxxx.363320b現(xiàn)將(1.2)改寫(gixi)為 第2頁/共49頁第三頁，共50頁。4).3636(121),334(111),2023(81213312321xxxxxxxxx（1.3）或?qū)憺?, fxBx0,01231261110114828300B其中(qzhng) .12361133820f第3頁/共49頁第四頁，共50頁。5 將這些值代入(1.3) 式右邊 (若(1.3)式為等式(dngsh)即求得方程組的解，但一般不滿足). 任取初始值，例如取 . Tx)0,0,0()0(,)3, 3,5.2(),(

3、)1(3)1(2)1(1)1(TTxxxx再將 分量代入(1.3)式右邊得到 ，反復(fù)利用這個(gè)計(jì)算程序，得到一向量序列和一般的計(jì)算公式(迭代公式) )1(x)2(x,)(3)(2)(1)()1(3)1(2)1(1)1()0(3)0(2)0(1)0(kkkkxxxxxxxxxxxx 得到(d do)新的值 第4頁/共49頁第五頁，共50頁。6,8/ )2023()(3)(2)1(1kkkxxx,11/ )334()(3)(1)1(2kkkxxx（1.4）.12/ )3636()(2)(1)1(3kkkxxx簡寫(jinxi)為 ,)(0)1(fxBxkk其中 表示迭代次數(shù) k).,2, 1 ,0(

4、k 迭代(di di)到第10次有 ;)9998813.0,999838.1,000032.3()10(Tx第5頁/共49頁第六頁，共50頁。7 從此例看出，由迭代法產(chǎn)生的向量序列 逐步逼近)(kx方程組的精確解 .*x 對于任何由 變形得到的等價(jià)方程組 ，fBxxbAx 迭代法產(chǎn)生的向量序列 不一定都能逐步逼近方程組的解 . )(kx*x*).(000187.0)10()10()10(xx 如對方程組.53,521221xxxx第6頁/共49頁第七頁，共50頁。8構(gòu)造(guzo)迭代法.53,52)(1)1(2)(2)1(1kkkkxxxx則對任何(rnh)的初始向量，得到的序列都不收斂.

5、對于給定方程組 ，fBxx設(shè)有唯一解 ，*x.*fBxx（1.5）又設(shè) 為任取的初始向量，)0(x,2, 1 ,0,)()1(kfBxxkk（1.6）其中 表迭代次數(shù). k則 按下述公式(gngsh)構(gòu)造向量序列 第7頁/共49頁第八頁，共50頁。9 定義(dngy)1(1) 對于給定的方程組 ，fBxx逐步代入求近似解的方法稱為迭代法迭代法( (或稱為一階定常迭代法，這里 與 無關(guān)). Bk (2) 如果 存在(記為 )，)(limkkx*x顯然 就是方程組的解，否則稱此迭代法發(fā)散迭代法發(fā)散. *x用公式(gngsh)(1.6)稱此迭代法收斂(shulin)， 研究 的收斂性. )(kx 引

6、進(jìn)誤差向量 *,)1()1(xxkk由(1.6)減去(1.5)式，得 ，),2, 1 ,0()()1(kBkk第8頁/共49頁第九頁，共50頁。10 要考察 的收斂性, 就要研究 在什么條件下有)(kxB0lim)(kk.0lim(零矩陣)kkB亦即要研究 滿足什么條件時(shí)有B)1()(kkB遞推得 .)0(kB第9頁/共49頁第十頁，共50頁。11 設(shè)有 ,bAx （2.1）其中， 為非奇異矩陣. nnijaAR)( 將 分裂為 A,NMA（2.2）其中， 為可選擇的非奇異矩陣，且使 容易求解，MdMx 一般選擇為 的某種近似，稱 為分裂矩陣分裂矩陣. AM第10頁/共49頁第十一頁，共50頁

7、。12 于是，求解 轉(zhuǎn)化為求解 ，bAx bNxMx.11bMNxMxbAx求解即求解(qi ji)可構(gòu)造(guzo)一階定常迭代法 ,2, 1 ,0,)()1()0(kfBxxxkk），（初始向量（2.3）其中(qzhng) NMB1.1bMf)(1AMM,1AMI稱 為迭代法的迭代矩陣.AMIB1第11頁/共49頁第十二頁，共50頁。13 選取 陣，就得到解 的各種迭代法. MbAx 設(shè) , 并將 寫為三部分 ),2, 1(0niaiiAnnaaaA22110000, 121,211, 112nnnnnnaaaaaa（2.4）.ULD00001,212, 11 , 121nnnnnnaaa

8、aaa第12頁/共49頁第十三頁，共50頁。14 由 ，選取 為 的對角元素部分，M),2, 1(0niaiiA解 的雅可比(Jacobi)迭代法 bAx 即選取 (對角陣)， ，DM NDA,2, 1 ,0,)()1()0(kfBxxxkk），（初始向量（2.5）其中(qzhng) ADIB1 稱 為解 的雅可比迭代法的迭代陣. JbAx 由(2.3)式得到(d do).1bDf)(1ULD,J第13頁/共49頁第十四頁，共50頁。15 研究(ynji)雅可比迭代法(2.5)的分量計(jì)算公式. ,),()()()(1)(Tknkikkxxxx記 由雅可比迭代(di di)公式(2.5), 有

9、,)()()1(bxULDxkk或 ).,2, 1(1)(11)()1(nibxaxaxainijkjijijkjijkiii于是，解 的雅可比迭代法的分量計(jì)算公式為 bAx 第14頁/共49頁第十五頁，共50頁。16,),()0()0(1)0(Tnxxx,/1)()1(iinijjkjijikiaxabx（2.6）., 1 ,0),2, 1(表示迭代次數(shù))(kni 由(2.6)式可知，雅可比迭代法計(jì)算公式簡單，每迭代一次只需計(jì)算一次矩陣和向量的乘法且計(jì)算過程中原始矩陣 始終不變.A第15頁/共49頁第十六頁，共50頁。17(下三角(snjio)陣)， 選取分裂矩陣 為 的下三角部分，MA即選

10、取 LDM,NMA于是由(2.3)式得到解bAx ,2, 1 ,0,)()1()0(kfBxxxkk（初始向量），（2.7）其中(qzhng) ,G稱 為解 的高斯-塞德爾迭代法的迭代陣. ULDG1)(bAx 的高斯-塞德爾(Gauss-Seidel)迭代法 .)(1bLDfULD1)(ALDIB1)(第16頁/共49頁第十七頁，共50頁。18 研究高斯(o s)-塞德爾迭代法的分量計(jì)算公式. ,),()()()(1)(Tknkikkxxxx由(2.7)式有 ,)()()1(bUxxLDkk或 ,)()1()1(bUxLxDxkkk).,2, 1(1)(11)1()1(nixaxabxani

11、jkjijijkjijikiii即 記 第17頁/共49頁第十八頁，共50頁。19于是解 的高斯-塞德爾迭代法計(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頁第十九頁，共50頁。20而由高斯-塞德爾迭代(di di)公式可知， 雅可比迭代法不使用變量的最新信息計(jì)

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

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

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

15、解 的逐次超松弛迭代法(Successive Over Relaxation Method, 簡稱SOR方法). bAx ).)1()(1UDLD6.3 逐次逐次(zh c)超松弛迭代法超松弛迭代法 第23頁/共49頁第二十四頁，共50頁。25 解 的SOR方法為 bAx ,2, 1 ,0,)()1()0(kfxLxxkk（初始向量），（2.10）其中(qzhng) ),)1()(1UDLDL.)(1bLDf 研究解 的SOR迭代法的分量計(jì)算公式. bAx ,),()()()(1)(Tknkikkxxxx記 第24頁/共49頁第二十五頁，共50頁。26,)1()()()1(bxUDxLDkk或

16、 ).()()()1()()1(kkkkkDxUxLxbDxDx由(2.10)式可得 由此，得到解 的SOR方法的計(jì)算公式 bAx ,),()0()0(1)0(Tnxxx,/1)(11)1()()1(iinijkjijijkjijikikiaxaxabxx（2.11）為松弛因子.), 1 ,0;, 1(kni第25頁/共49頁第二十六頁，共50頁。27或 ,),()0()0(1)0(Tnxxx,)()1(ikikixxx,/1)(11)1(iinijkjijijkjijiiaxaxabx（2.12）為松弛因子.), 1 ,0;, 1(kni 關(guān)于(guny)SOR迭代法 ， 有 (1) 顯然，

17、當(dāng) 時(shí)，SOR方法即為高斯-塞德爾迭代法. 1第26頁/共49頁第二十七頁，共50頁。28 (2) SOR方法每迭代一次主要運(yùn)算量是計(jì)算(j sun)一次矩陣與向量的乘法. (3) 當(dāng) 時(shí)，稱為超松弛法；當(dāng) 時(shí)，稱為低松弛法. 11 (4) 在計(jì)算機(jī)實(shí)現(xiàn)(shxin)時(shí)可用 )()1(11maxmaxkikiniinixxx控制迭代終止，或用 控制迭代終止. )()(kkAxbr SOR迭代法是高斯-塞德爾迭代法的一種(y zhn)修正. 第27頁/共49頁第二十八頁，共50頁。29 設(shè)已知 及已計(jì)算 的分量 )(kx)1( kx).1,2, 1()1(ijxkj (1) 首先用高斯-塞德爾迭

18、代法定義輔助量 ,)1( kix./1)(11)1()1(iinijkjijijkjijikiaxaxabx（2.13） (2) 再由 與 加權(quán)平均定義 ，)(kix)1(kix)1( kix)1()()1()1(kikikixxx將(2.13)代入(2.14)得到解 的SOR迭代(2.11)式. bAx 即 （2.14）).()()1()(kikikixxx第28頁/共49頁第二十九頁，共50頁。30 例例3 3,111141111411114111144321xxxx它的精確解為 .)1, 1, 1, 1(*Tx取 ，迭代公式為 0)0(x;4/ )41()(4)(3)(2)(1)(1)1

19、(1kkkkkkxxxxxx用SOR方法(fngf)解方程組 解解;4/ )41()(4)(3)(2)1(1)(2)1(2kkkkkkxxxxxx;4/ )41()(4)(3)1(2)1(1)(3)1(3kkkkkkxxxxxx.4/ )41()(4)1(3)1(2)1(1)(4)1(4kkkkkkxxxxxx第29頁/共49頁第三十頁，共50頁。31取 ，3.1,)999999120,999999530,000003101,999996460()11(T.x.1046.052)11(取其他 值，迭代次數(shù)如下表. 第11次迭代(di di)結(jié)果為 第30頁/共49頁第三十一頁，共50頁。321

20、099 . 1144 . 1538 . 1113 . 1337 . 1122 . 1236 . 1171 . 1175 . 1220 . 110*10*52)(52)(最少迭代次數(shù))的迭代次數(shù)滿足誤差松弛因子的迭代次數(shù)滿足誤差松弛因子16表xxxxkk 從此例看到，松弛因子選擇得好，會使SOR迭代法的收斂大大加速. 本例中 是最佳松弛因子. 3.1第31頁/共49頁第三十二頁，共50頁。33 6.3.1 6.3.1 一階定常迭代法的基本一階定常迭代法的基本(jbn)(jbn)定理定理 設(shè) ,bAx （3.1）其中 為非奇異矩陣，nnijaAR)(記 為(3.1)精確解，*x.fBxxbAx于是

21、(ysh) .*fBxx（3.2）且設(shè)有等價(jià)(dngji)的方程組第32頁/共49頁第三十三頁，共50頁。34 設(shè)有解 的一階定常迭代法 bAx .)()1(fBxxkk（3.3） 問題是： 迭代矩陣 滿足什么條件時(shí)，由迭代法產(chǎn)生的向量序列 收斂到 B)(kx.*x 引進(jìn)(ynjn)誤差向量 ).,2, 1 ,0(*)()(kxxkk由(3.3)式減(3.2)式得到誤差向量(xingling)的遞推公式 ,)()1(kkB).,2, 1 ,0()0()(kBkk第33頁/共49頁第三十四頁，共50頁。35 由6.1節(jié)可知，研究(ynji)迭代法(3.3)收斂性問題就是要研究(ynji)迭代矩陣

22、 滿足什么條件時(shí)，有B(零矩陣).0limkkB 定義(dngy)2設(shè)有矩陣序列 及 , nnkijkaAR)()(nnijaAR)(如果 個(gè)數(shù)列極限存在且有 2n),2, 1,(lim)(njiaaijkijk則稱 收斂于 ，kAA.limAAkk記為 第34頁/共49頁第三十五頁，共50頁。36 例例4 4,01A且設(shè) ，考查其極限. 1 解解由于，當(dāng) 時(shí)，有 1設(shè)有矩陣(j zhn)序列 ,02222A,0,1kkkkkA.0000limlimkkkkAA.0limkk所以(suy)第35頁/共49頁第三十六頁，共50頁。37 矩陣序列極限概念可以用矩陣算子(sun z)范數(shù)來描述. 定

23、理(dngl)1 0limlimAAAAkkkk 證明(zhngmng).0limlimAAAAkkkk再利用矩陣范數(shù)的等價(jià)性，可證定理對其他算子范數(shù)亦對. 定理定理2 2AAkklim 對任何向量 都有nxR.limAxxAkk其中為矩陣的任意一種算子范數(shù). 顯然有 （證明略）第36頁/共49頁第三十七頁，共50頁。38 定理(dngl)3設(shè) , nnijbBR)(則 (零矩陣)的0limkkB充分必要條件是矩陣 的譜半徑 B.1)(B 證明(zhngmng)由矩陣 的若當(dāng)標(biāo)準(zhǔn)型，存在非奇異矩陣 使 BP,211JJJJBPPr其中(qzhng)若當(dāng)塊 ,11iinniiiiJ第37頁/共4

24、9頁第三十八頁，共50頁。39且 ，nnrii1,1PJPB其中(qzhng) .21krkkkJJJJ于是(ysh) ).,2, 1(0lim0limriJBkikkk 下面考查 的情況. kiJ顯然(xinrn)有,1PPJBkk引進(jìn)記號 ).(R000,ittktntktIE第38頁/共49頁第三十九頁，共50頁。40 顯然(xinrn)有， ,0,IEt由于 , 1, tiiEIJktikiEIJ)(1 ,),(0,tkEkt當(dāng).)(,1,ktktEE 因此(ync) kjjtjkijkEC01 ,)(10,tjjtjkijkECttkikiktkitkkikkitkitkkikkik

25、kiCCCCCC11)2(211)1(12211),2, 1(ri第39頁/共49頁第四十頁，共50頁。41其中(qzhng) )!( !jkjkCjk利用極限 ，)0, 10(0limrcckkrk.10limjkjkkC所以 的充要條件是 ，0limkikJ),2, 1(1rii.1)(B.!)1()1(jjkkk得到(d do)即 第40頁/共49頁第四十一頁，共50頁。42 定理(dngl)4,fBxx（3.4）(迭代法基本(jbn)定理)設(shè)有方程組 及一階定常迭代法 .)()1(fBxxkk（3.5）對任意選取初始向量 ，)0(x矩陣 的譜半徑 B.1)(B迭代法(3.5)收斂(sh

26、ulin)的充要條件是 證明證明設(shè) ，1)(B易知fAx )有唯一解，BIA記為 ，*x充分性. (其中則 ,*fBxx第41頁/共49頁第四十二頁，共50頁。43誤差(wch)向量 *)()(xxkk由設(shè) ，1)(B.0limkkB,)0(kB. *)0()0(xx應(yīng)用(yngyng)定理3，有 于是對任意 ,)0(x有 ，0limkk 必要性. 設(shè)對任意 有 )0(x*,lim)(xxkk其中 .)()1(fBxxkk.*lim)(xxkk即 顯然，極限 是方程組(3.4)的解，*x且對任意 有 )0(x*)()(xxkk).(0)0(kBk第42頁/共49頁第四十三頁，共50頁。44由定理(dngl)2知 ,0limkkB再由定理3，即得 .1)(B 推論(tuln)設(shè) ，bAx 其中 為非奇異矩陣ULDA且 非奇異，則 D (1) 解方程組的雅可比迭代法收斂的充要條件是 ，1)(J).(1ULDJ其中 (2) 解方程組的高斯(o s)-塞德爾迭代法收斂的充要條件是, 1)(G.)(1ULDG其中 (3) 解方程組的SOR方法收斂的充要條件是 ，1)(L).)1()(1UDLDL其中 第43頁/共49頁第四十四頁，共50頁。45 例例5 5迭代矩陣 的特征方程為 J, 0039772727. 0034090909. 0)det(3J