第六章解大型稀疏线性方程组的迭代法
教学目的 1. 掌握Jacobi迭代法，G-S迭代法解大型线性方程组的方法及其收敛性的判别方法；2. 掌握SOR迭代法及收敛的必要条件(0<ω<2 )；3. 了解三种迭代法之间的改进关系从而掌握该思想方法；4. 理解迭代法基本定理。
教学重点及难点 重点是三种迭代法及收敛性的判别方法；难点是迭代法基本定理及三种迭代法收敛定理的证明。 教学时数 8学时 教学过程
第六章解大型稀疏线性方程组的迭代法迭代法是一种不断套用一个迭代公式，逐步逼近方程组的精确解（真解）的方法。适合解大型稀疏线性方程组。大型稀疏线性方程组直接法：解低阶稠密线性方程组，?电工学中的网络问题；?用差分法或有限元法解偏微分方程边值问题时得到的方程组。迭代法优点：O(n)计算量：⑴计算量小，近似解精度高。⑵占用内存单元较少。⑶设计程序简单（适合计算机计算）。考虑问题：⑴如何构造解Ax?b的有效迭代法？⑵收敛性与收敛速度怎样？3 §1 引言、例子为非奇异阵，方程组Ax?b的精确解为x*，即Ax*?b。迭代法的定义：(k)定义1（1）用逐步代入（构造向量序列{x}）设A?Rn?n?x(0)任取初始向量B是迭代矩阵?(1)*(k)(0)x是x的k步近似Bx?f?x?Bk?1)(k)?x((k?BxBx(k)??ff,,((k??11,2,??k,2,?))?(1.10)求近似解的方法，称为迭代法（或称为一阶定常迭代法）。(k)*(0)x?x，称迭代法（2）如果对任意初始近似x，都有limk??(1.10)为收敛，否则称迭代法为发散。§2 迭代法研究的问题：(k)x收敛)。（1）构造各种解Ax?b的有效迭代法(有效：（2）研究迭代法的收敛性及收敛速度。§3 注：(1.10)为迭代公式，简记为：
(2.1)设A?Rn?n非奇异。问题：用迭代法解线性方程组Ax?b。将A分离（裂）为三部分，即令A??aij?,aii?0，基本思想：n?n?a11?A??????a22??0??0?????a210?????????????????an,n??a??a0??n1n,n?1?????a120????a1n????D?L?U?an?1,n??0?§2 基本迭代法(2.2)(2.3)常用的是将A分裂为A?M?N其中M为可选择的非奇异阵使Mx?d容易求解,一般M选为A的某Ax?b??Mx?Nx?b或x?M?1Nx?M?1b。种近似,于是?1?1?1?1若记B?MN?M(M?A)?I?MA?,??f?Mb，B是迭代矩阵，则?x(0)?（可任意取）?(k?1)(k)注：M的选法不?Bx?f(k?0,1,?)?x?(2.4)同，得到各种不同的迭代?1B?I?MA?法。?f?M?1b?并取初始向量x?(0) 2.1 雅可比(Jacobi)迭代法(2.3)A?M?N(2.4)B?I?MA1.理论分析：若取M?D(对角阵)，则由(2.3)得A?D?N,?1?1?1由(2.4)得B?I?DA?D?D?A??D?L?U??J?，A?D?L?U?1f?Mb?Db(0)?1?1?x?(k?1)(k)?Bx?f(k?0,1,?)?xJacobi迭代法：??1(2.5)?B?D(L?U)?J?1??f?Db(k)(k)(k)(k)T若记Jacobi迭代法的分量形式：x?(x1,?,xi,?,xn)称为Jacobi迭代法的迭代阵x(k?1)?Bx(k)?f(k?0,1,?)由（2.５）有aiixi(k?1)Dx(k?1)i?1?(L?U)xnij(k)?b，即n?bi??aj?1x(k)j??aj?i?1ijx(k)j?bi??aj?1j?iijxj?k?,?i?1,2,?,n??当aii?0时，得到Jacobi迭代法计算公式 2.求解Ax?b的Jacobi迭代法计算公式：(0)(0)(0)T??x?(x1,?,xn)(2.6)??n1(k)?x(k?1)?(bi??aijxj)?i?aiij?1??i?1,2,?,n?j?i?此公式还有另一种推导方式k?0,1,?,表示迭代次数。注：(k)(1)Jacobi迭代法,每迭代一次主要是计算一次矩阵乘向量Bx。（2)计算过程中，原始数据A始终不变。(k?1))x(3)计算中需要两组工作单元x(n),y(n)用来保存x(k及。公式推导（另外方法）?a11x1?a12x2???a1nxn?b1?a21x1?a22x2???a2nxn?b2Ax?b??????????????????ax?ax???ax?bn22nnnn?n11aii?0??a11x1?b1?a12x2???a1nxn?a22x2?b2?a21x1???a2nxn????????????????ax?b?ax???axnn22nn??1n?1?nnn? n?1x?(b?a1jxj)?1?1a11?a11x1?b1?a12x2???a1nxni?2??n?1?a22x2?b2?a21x1???a2nxnx?(b2??a2jxj)Ax?b????2ai?122????????????????j?2??ax?b?ax???axnn22nn??1n?1?nnn???????????n1(0)n?1?(k?1)(k)于是xi给定，xi?(bi?aijxj)?x?1(b?ax)?njjnnaiij?1?ai?1nn?j?i(i?1,2,?,n)?(1)Jacobi迭代法实际上是由近似解x(k)?(x1(k),?,xi(k),?,xn(k))T说明：的n-1分量x1(k),?,xi(?k1),xi(?k1),?,xn(k)计算x(k?1)?(x1(k?1),?,xi(k?1),?,xn(k?1))T的第i（i=1,2,?,n）个分量。(2)若{x*(k)}收敛于x，则x*(k?1)比x(k)(k?1)(k)更接近于x。则xi比xi更*考虑问题：(k?1)x(ik?1),?,x(k?1))T的第i个分量x(k?1)时,它的前i?1个计算x(k?1)?(x1(k?1),?,xiin(k?1)(k?1)(k?1)(k?1)分量x1,?,xi?1均已求出，设想用x1,?,xi?1,代替Jacobi(k)(k)(k)T迭代法中的x(k)?(x1(k),?,xi(k),?,xn)的前i?1个分量:x1,?,xi?1。 接近于xi。A?D?L?U(2.3)A?M?2.2 高斯-塞德尔迭代法（G-S）取分裂阵M?D?L(下三角阵),由(2.3)得A??D?L??N。?1?1?1由(2.4)得B?I?(D?L)A?(D?L)((D?L)?A)?(D?L)U?G于是得到解Ax?b的G-S迭代法：N其中G 称为G-S迭代法的迭代阵?x(0)?(k?1)(k)?Bx?f?x??1?B?(D?L)U?G?1??f?(D?L)b(2.4)B?I?M?1A(2.7)x(k?1)?Bx(k)?f(k?0,1,?)?1f?M(k)(k)(k)?1b?(D?L)b(k)T若记G-S迭代法的分量形式：x?(x1,?,xi,?,xn)，(k?1)(k?1)(k)?Lx?Ux?b由（2.7）式有(D?L)x(k?1)?Ux(k)?b或Dx当aii?0时得到以下解Ax?b的G-S迭代法计算公式:?x(0)?(x1(0),?xn(0))T?i?1?(k?1)1(k?1)x?(b?ax??iiijj?aiij?1?n其中k =1,2,?表示迭代次数aijxj(k)?)(i?1,2,?,n)(2.8)j?i?1 或写成增量修正的形式：(k?1)(k)iaii??x??xi(k)j?1(k)?xi?x?xii?i?11(k?1)((kk))?(bi??aijxj???aaijijxxjj)(i?1,2,?,n)(2.9)??xi??aiij?1jj??iix其中k =1,2,?i表示迭代次数nn(2.8)(k?1)?1i?1(bi??aijxj(k?1)n??aj?i?1ijxj(k))优点：(1)由(2.8)可知,计算x(k?1)第i个分量时,利用已经计算出的最新(k)(k?1)(k?1)分量xj(j?1,2,?,i?1)，因此，计算xi就可冲掉xi,于是利)x(k?1)分量。用G-S迭代法解只需要一组工作单元，用来保存x(k或G-S迭代存贮少。(2)G-S迭代法每迭代一次主要计算一次矩阵乘向量。计算量小，(3)当J-迭代与G-S迭代都收敛时，G-S迭代的收敛速度快。G-S迭代法可看作J迭代法的一种修正或改进。 例2用Jacobi迭代法，G-S迭代法解下述方程组?8x1?x2?x3?8?T?x?(1,1,1)精确解?2x1?10x2?x3?11或Ax?b(k?1)(k)(k)?x1?(8?x2?x3)/8??(k?1)?x1?x2?5x3??3(k)(k)x2?(11?2x1?(3?x1(k)（1）Jacobi迭代公式：??(k)其中，x(k)(k)(k)T?x3)/10(k)?x3(k?1)?x2)/5?(x1,x2,x3),(k?0,1,?)表6-1(0)，计算结果见表6-1。x(5)x(k)(k)(k)(k)xx(1)x(2)x(3)x(4)x10001.11.11.062500.992500..989598951.00450.9981251.001951.00069381.0000151.000015x2x300.961.0200..66??00..99649964且有x(5)?x?0.0007 （2）G-S迭代公式(k?1)(k)(k)?x1?(8?x2?x3)/8?(k?1)(k?1)(k)?(11?2x1?x3)/10?x2?(k?1)(k?1)(k?1)?(3?x1?x2)/5?x3(k)(k)(k)(k)Tx?(x1,x2,x3),(k?0.1,?),其中，计算结果见:表6-2x(k)(k)(k)(k)x(0)x(1)x(2)x(3)x(4)x10001.0.90.980.991.0..99899801.000250.999750..99996875999968750x2x31..000006250000062510..99999599999501.且有||x(3)?x*||??0.00025||xx(5)(4)?x||??3.2?10??*?5?x?0.0007注：由此例看出，用G-S迭代法解此方程组比用Jacobi方法解此Ax=b收敛快（即在初始向量x(0)相同，达到同样精度，所需迭代次数较少），这个结论只当A满足一定条件时才是对的。有些方程组,用J-迭代法收敛，而用G-S迭代法却是发散的。例如P347习题6中1.（b）。