经济学解线性方程组的迭代法学习教案

1、会计学1经济学解线性方程组的迭代法经济学解线性方程组的迭代法第一页，共50页。2 考虑(kol)线性方程组 ,bAx （1.1）其中 为非奇异矩阵，当 为低阶稠密矩阵时，第5章所讨论的选主元消去法是有效方法. AA 但对于 的阶数 很大，零元素较多的大型稀疏矩阵方程组，例如求某些偏微分方程数值解所产生的线性方程组来说，利用迭代法求解则更为合适. An 迭代法通常都可利用 中有大量零元素的特点. 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现将(1.2)改写(gixi)为 第2页/共49页第三页，共50页。4).3636(121),334(111),2023(81213312321xxxxxxxxx（1.3）或写为 , 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)式右边得到 ，反复利用这个计算程序，得到一向量序列和一般的计算公式(迭代公式) )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其中 表示迭代次数 k).,2, 1 ,0(

4、k 迭代(di di)到第10次有 ;)9998813.0,999838.1,000032.3()10(Tx第5页/共49页第六页，共50页。7 从此例看出，由迭代法产生的向量序列 逐步逼近)(kx方程组的精确解 .*x 对于任何由 变形得到的等价方程组 ，fBxxbAx 迭代法产生的向量序列 不一定都能逐步逼近方程组的解 . )(kx*x*).(000187.0)10()10()10(xx 如对方程组.53,521221xxxx第6页/共49页第七页，共50页。8构造(guzo)迭代法.53,52)(1)1(2)(2)1(1kkkkxxxx则对任何(rnh)的初始向量，得到的序列都不收敛.

5、对于给定方程组 ，fBxx设有唯一解 ，*x.*fBxx（1.5）又设 为任取的初始向量，)0(x,2, 1 ,0,)()1(kfBxxkk（1.6）其中 表迭代次数. k则 按下述公式(gngsh)构造向量序列 第7页/共49页第八页，共50页。9 定义(dngy)1(1) 对于给定的方程组 ，fBxx逐步代入求近似解的方法称为迭代法迭代法( (或称为一阶定常迭代法，这里 与 无关). Bk (2) 如果 存在(记为 )，)(limkkx*x显然 就是方程组的解，否则称此迭代法发散迭代法发散. *x用公式(gngsh)(1.6)称此迭代法收敛(shulin)， 研究 的收敛性. )(kx 引

6、进误差向量 *,)1()1(xxkk由(1.6)减去(1.5)式，得 ，),2, 1 ,0()()1(kBkk第8页/共49页第九页，共50页。10 要考察 的收敛性, 就要研究 在什么条件下有)(kxB0lim)(kk.0lim(零矩阵)kkB亦即要研究 满足什么条件时有B)1()(kkB递推得 .)0(kB第9页/共49页第十页，共50页。11 设有 ,bAx （2.1）其中， 为非奇异矩阵. nnijaAR)( 将 分裂为 A,NMA（2.2）其中， 为可选择的非奇异矩阵，且使 容易求解，MdMx 一般选择为 的某种近似，称 为分裂矩阵分裂矩阵. AM第10页/共49页第十一页，共50页

7、。12 于是，求解 转化为求解 ，bAx bNxMx.11bMNxMxbAx求解即求解(qi ji)可构造(guzo)一阶定常迭代法 ,2, 1 ,0,)()1()0(kfBxxxkk），（初始向量（2.3）其中(qzhng) NMB1.1bMf)(1AMM,1AMI称 为迭代法的迭代矩阵.AMIB1第11页/共49页第十二页，共50页。13 选取 阵，就得到解 的各种迭代法. MbAx 设 , 并将 写为三部分 ),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)的分量计算公式. ,),()()()(1)(Tknkikkxxxx记 由雅可比迭代(di di)公式(2.5), 有

9、,)()()1(bxULDxkk或 ).,2, 1(1)(11)()1(nibxaxaxainijkjijijkjijkiii于是，解 的雅可比迭代法的分量计算公式为 bAx 第14页/共49页第十五页，共50页。16,),()0()0(1)0(Tnxxx,/1)()1(iinijjkjijikiaxabx（2.6）., 1 ,0),2, 1(表示迭代次数)(kni 由(2.6)式可知，雅可比迭代法计算公式简单，每迭代一次只需计算一次矩阵和向量的乘法且计算过程中原始矩阵 始终不变.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)-塞德尔迭代法的分量计算公式. ,),()()()(1)(Tknkikkxxxx由(2.7)式有 ,)()()1(bUxxLDkk或 ,)()1()1(bUxLxDxkkk).,2, 1(1)(11)1()1(nixaxabxani

11、jkjijijkjijikiii即 记 第17页/共49页第十八页，共50页。19于是解 的高斯-塞德尔迭代法计算公式为 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)公式可知， 雅可比迭代法不使用变量的最新信息计

12、算 ，)1( kix计算 的第 个分量)1( kxi 时，)1( kix利用了已经计算出的最新分量 .) 1, 2 , 1()1(ijxkj 由(2.8)可知，高斯(o s)-塞德尔迭代法每迭代一次只需计算一次矩阵与向量的乘法. 高斯-塞德尔迭代法可看作雅可比迭代法的一种(y zhn)改进. 算法算法1 1(高斯-塞德尔迭代法) 设 ，bAx 其中 为非奇异矩阵且nnAR0iia),2, 1(ni本算法用高斯-塞德尔迭代法解 ，bAx 第19页/共49页第二十页，共50页。21), 1(0.0.1nixi 迭代一次，这个算法需要的运算次数至多与矩阵 的非零元素的个数一样多. A数组 开始存放

13、, )(nx)0(x,)(kx后存放0N为最大迭代次数. 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 而高斯-塞德尔迭代法比雅可比迭代法收敛较快(即取 相同，达到同样精度所需迭代次数较少).)0(x 但这结论只当 满足一定条件时才是对的. A.1002.2*6)7(xx且 第22页/共49页第二十三页，共50页。24 选取分裂矩阵 为带参数的下三角阵 M),(1LDM其中 为可选择的松弛因子. 0 于是，由(2.3)可构造一个(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迭代法的分量计算公式. bAx ,),()()()(1)(Tknkikkxxxx记 第24页/共49页第二十五页，共50页。26,)1()()()1(bxUDxLDkk或

16、 ).()()()1()()1(kkkkkDxUxLxbDxDx由(2.10)式可得 由此，得到解 的SOR方法的计算公式 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 关于(guny)SOR迭代法 ， 有 (1) 显然，

17、当 时，SOR方法即为高斯-塞德尔迭代法. 1第26页/共49页第二十七页，共50页。28 (2) SOR方法每迭代一次主要运算量是计算(j sun)一次矩阵与向量的乘法. (3) 当 时，称为超松弛法；当 时，称为低松弛法. 11 (4) 在计算机实现(shxin)时可用 )()1(11maxmaxkikiniinixxx控制迭代终止，或用 控制迭代终止. )()(kkAxbr SOR迭代法是高斯-塞德尔迭代法的一种(y zhn)修正. 第27页/共49页第二十八页，共50页。29 设已知 及已计算 的分量 )(kx)1( kx).1,2, 1()1(ijxkj (1) 首先用高斯-塞德尔迭

18、代法定义辅助量 ,)1( kix./1)(11)1()1(iinijkjijijkjijikiaxaxabx（2.13） (2) 再由 与 加权平均定义 ，)(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(取其他 值，迭代次数如下表. 第11次迭代(di di)结果为 第30页/共49页第三十一页，共50页。321

20、099 . 1144 . 1538 . 1113 . 1337 . 1122 . 1236 . 1171 . 1175 . 1220 . 110*10*52)(52)(最少迭代次数)的迭代次数满足误差松弛因子的迭代次数满足误差松弛因子16表xxxxkk 从此例看到，松弛因子选择得好，会使SOR迭代法的收敛大大加速. 本例中 是最佳松弛因子. 3.1第31页/共49页第三十二页，共50页。33 6.3.1 6.3.1 一阶定常迭代法的基本一阶定常迭代法的基本(jbn)(jbn)定理定理 设 ,bAx （3.1）其中 为非奇异矩阵，nnijaAR)(记 为(3.1)精确解，*x.fBxxbAx于是

21、(ysh) .*fBxx（3.2）且设有等价(dngji)的方程组第32页/共49页第三十三页，共50页。34 设有解 的一阶定常迭代法 bAx .)()1(fBxxkk（3.3） 问题是： 迭代矩阵 满足什么条件时，由迭代法产生的向量序列 收敛到 B)(kx.*x 引进(ynjn)误差向量 ).,2, 1 ,0(*)()(kxxkk由(3.3)式减(3.2)式得到误差向量(xingling)的递推公式 ,)()1(kkB).,2, 1 ,0()0()(kBkk第33页/共49页第三十四页，共50页。35 由6.1节可知，研究(ynji)迭代法(3.3)收敛性问题就是要研究(ynji)迭代矩阵

22、 满足什么条件时，有B(零矩阵).0limkkB 定义(dngy)2设有矩阵序列 及 , nnkijkaAR)()(nnijaAR)(如果 个数列极限存在且有 2n),2, 1,(lim)(njiaaijkijk则称 收敛于 ，kAA.limAAkk记为 第34页/共49页第三十五页，共50页。36 例例4 4,01A且设 ，考查其极限. 1 解解由于，当 时，有 1设有矩阵(j zhn)序列 ,02222A,0,1kkkkkA.0000limlimkkkkAA.0limkk所以(suy)第35页/共49页第三十六页，共50页。37 矩阵序列极限概念可以用矩阵算子(sun z)范数来描述. 定

23、理(dngl)1 0limlimAAAAkkkk 证明(zhngmng).0limlimAAAAkkkk再利用矩阵范数的等价性，可证定理对其他算子范数亦对. 定理定理2 2AAkklim 对任何向量 都有nxR.limAxxAkk其中为矩阵的任意一种算子范数. 显然有 （证明略）第36页/共49页第三十七页，共50页。38 定理(dngl)3设 , nnijbBR)(则 (零矩阵)的0limkkB充分必要条件是矩阵 的谱半径 B.1)(B 证明(zhngmng)由矩阵 的若当标准型，存在非奇异矩阵 使 BP,211JJJJBPPr其中(qzhng)若当块 ,11iinniiiiJ第37页/共4

24、9页第三十八页，共50页。39且 ，nnrii1,1PJPB其中(qzhng) .21krkkkJJJJ于是(ysh) ).,2, 1(0lim0limriJBkikkk 下面考查 的情况. kiJ显然(xinrn)有,1PPJBkk引进记号 ).(R000,ittktntktIE第38页/共49页第三十九页，共50页。40 显然(xinrn)有， ,0,IEt由于 , 1, tiiEIJktikiEIJ)(1 ,),(0,tkEkt当.)(,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)定理)设有方程组 及一阶定常迭代法 .)()1(fBxxkk（3.5）对任意选取初始向量 ，)0(x矩阵 的谱半径 B.1)(B迭代法(3.5)收敛(sh

26、ulin)的充要条件是 证明证明设 ，1)(B易知fAx )有唯一解，BIA记为 ，*x充分性. (其中则 ,*fBxx第41页/共49页第四十二页，共50页。43误差(wch)向量 *)()(xxkk由设 ，1)(B.0limkkB,)0(kB. *)0()0(xx应用(yngyng)定理3，有 于是对任意 ,)0(x有 ，0limkk 必要性. 设对任意 有 )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)设 ，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