1、1.引言 迭代法的基本思想是构造一串收敛到解的序列，即建立一种从已有近似解计算新的近似解的规则。由不同的计算规则得到不同的迭代法，本章介绍单步定常线性迭代法。1(0 )(1)()()() ()(,) , (k=0,1,2,)TijnnnnnkkkkAxbAabbbxM xgMngRxRxM xgxkxAxb对 线 性 方 程 组其 中非 奇 异 矩 阵 ， 构 造 其 形 如的 同 解 方 程 组 ， 其 中为阶 方 阵 ，。任 取 初 始 向 量代 入 迭 代 公 式产 生 向 量 序 列， 当充 分 大 时 ， 以作 为方 程 组的 近 似 解 ， 这 就 是 求 解 线 M性 方 程 组
2、的 单 步 定 常 线 性 迭 代 法 。称 为 迭 代 矩 阵 。( )( )( )( )( )( lim0 lim limknnkkkkknknikxRxRxxxxxxRxRxx定义：设为中的向量序列，如果其中为向量范数，则称序列收敛于 ，记为定理：中的向量序列收敛于中的向量 当且仅当)( )( )( )( )1212( )( )( )( )( )1( ) (1,2, )(,) ,(,) lim010max lim=0 (1,2, ) kikkkkTTnnkkkkkkiijjj nkiikxinxxxxxx xxxxxxinxxxxxxxxin 其中。证：由定义，收敛于 即而对任意，有由极
3、限存在准则得即( ) lim (1,2, )kiikxxin()()()()()()() lim0 lim () (1,2,),(kkkkkkkkijijkAnAnAAAAAAAakAanAA 定义：设为 阶方阵序列，为 阶方阵，如果其中为矩阵范数，则称序列收敛于矩阵 ，记为定理：设)均为 阶方阵，则矩阵序列收敛于矩阵 的充()(1)()()(1)() lim ( ,1,2,) , limlimkijijkkkkkkkkaai jnxMxgxxxxMxgMxgxA 要条件为证明略。定理表明，向量序列和矩阵序列的收敛可以归结为对应分量或对应元素序列的收敛。若按产生的向量序列收敛于向量则有即 是方
4、程组xb的解。引入误差向量xxkk)1()1(则可得)()1(kkM由gMxxkk)()1(gMxx)0()1()(kkkMM问题是在什么条件下所以xxkk)(lim等价于0lim)(kk0lim)(kk也即0kM2.基本迭代法设有bAx 其中A为非奇异矩阵将A分解成NMA其中M是可选择的非奇异矩阵,且使Mx=d容易求解由此,原问题就可转化为等价方程bNxMx得:bMNxMx11可构造迭代法.)2 , 1 , 0()()1()0(kfxBxxkk初始向量bMfAMIAMMNMB1111,)(Jacobi 迭代法 1111221n12112222n2n11n12nn 0 (1, 2,),nnnn
5、iiina xa xa xba xa xa xba xa xa xba若 系 数 矩 阵 非 奇 异 即则 有112213311221123322n112233 nnnnnnnngxb xb xb xgxb xb xb xxb xb xb x,(, ,1, 2,),(1, 2,).ijiijiiiiiabbij i jnginaag 其 中12131111212321221231(0)(1)10(1)(2)( )(1)00 0 , nnnnnnnnnnkkbbbbgbbbbgBgbbbbgxBxgxxxBxgxxxxBx（ ）（ ）若记则方程组可简记为选初值向量代入，代入，如此继续下去，就产生
6、一个向量序列满足( )(0,1,2,)kgkJacobi此过程所给出的迭代法称为迭代法，又称简单迭代法。 Jacobid迭代的矩阵形式 1111000100010002122111221221112bbbbbbbbbbbbnnnnnnnnBAD I-aaaaaaaaaaaaInn1nnn2n12n22211n12111122111 1 12 111222(,)(, , , )TTnnnnggggbDbababa同 样收敛与解1* n0 1 2 B gnnkJacobiBgxxxxxx（）（ ）（ ）迭代，若收敛，则*1*1* () IB xgDAxDbAxb即故如果序列收敛, 则收敛到解.B
7、称迭代矩阵.123123123110272 10283542 10010100101200.10.21010001 1020.100.2100011150.20.201005 xxxJacobixxxxxxBID A例：用迭代法求解解：1(0)(0)(2)(1)(9) (7.2,8.3,8.4)(0,0,0) ,(7.2,8.3,8.4)(9.71,10.70,11.5)(10.9994,11.9994,12.9992)(11,12,13) .TTTTTgD bxBxgxBxgxx(1)取代入迭代式，得x精确解为(0)(0)(0)(0)112(0)1(0)(0)1.(),( ,),(,),.2
8、.1.3.1,2, ()/4.,55.,1,(1,2, ),3 ijnnniiijjiijj iiiAabbbn xxxxNkinxba xaxxxkNkk xxin 输入维数最大容许迭代次数置对若输出 停机；否则转 。若置转 ；否则，输出失败信息，停机。( )(1,kkMxx ）评价：公式简单，每迭代一次只需计算一次矩阵和向量的乘法，不改变的稀疏性，需两组工作单元，存。高斯塞德尔（Gauss-Seidel)迭代法1111221n12112222n2n11n12nn 0 (1, 2,),nnnniiina xa xa xba xa xa xba xa xa xba若 系 数 矩 阵 非 奇 异
9、 即则 有112213311221123322n112233 nnnnnnnngxb xb xb xgxb xb xb xxb xb xb x,(, ,1, 2,),(1, 2,).ijiijiiiiiabbij i jnginaag 其 中(1)( )(1)( )( )( )112213311(1)( )( )( )221123322 (0,1,2, ) kkkkkknnkkkknnxBxg kgxb xb xb xgxb xb xb x迭代公式用方程组表示为(1)( )( )( )1122,11( )(1) kkkknnnn nnnkkJacobixxgxb xb xb x因此，在迭代法的
10、计算过程中，需同时保留两个近似解向量和。若把迭代公式改写成(1)( )( )( )112213311(1)(1)( )( )221123322(1)(1)112 kkkknnkkkknnkknnngxb xb xb xgxb xb xb xxb x(1)(1)2,11(0)( ) ,kkn nnnknxxGaussSeidelJacobigb xbx这样，在整个计算过程中，只需用 个单元存储近似解分量。而且通常认为，近似解可能比老近似解更接近精确解，因此，可望这种迭代会更有效。选取初始向量用上式迭代产生近似解序列这种方法叫迭代法。评价：与相比，只需一组工作单元存放近似解。用矩阵可表示为:gxU
11、xLxkkk)()1()1(0000002121nnbbbL0000002112nnbbbU移项得gxUxLIkk)()1()(又1)det(LI)(LI 所以可逆gLIxULIxkk1)(1)1()()(也即选取 M 为A的下三角部分，即 M =DL，N，则 x=b可等价为（MN)x = bbMNxMx11bMNxMxkk1)(1)1(联系上面已经得到的矩阵迭代形式,为统一起见, 记: A=DLU0000002121nnaaaL0000002112nnaaaUnnaaD0011bUxxLDkk)()1()(等价为bLDUxLDxkk1)(1)1()()(其中UDULDL11,gxUxLIkk
12、)()1()(或fGxxkk)()1(其中即为G-S迭代法的迭代矩阵123123123(0)1(0)(0)12311(1)(0)21321310272 10283542(0,0,0) ,11 (2)727.2000101011 (2)(7.200083)9.02001010 TxxxGaussSeidelxxxxxxxxxxbxxxbx（ ）（ ）（ ）例：用迭代法求解解：仍取代入迭代式，得(1)(1)123(5)11()7.20009.020042)11.644055(10.9989,11.9993,12.9996)(11,12,13) .Txxbxx（如此继续下去，精确解为 Gausese
13、idelJacobiGauseseidelJacobiGauseseidelJacobiJacobiGauseseidelJacobi上例计算结果表明，迭代法比迭代法效果好。事实上，对有些问题迭代法确实比迭代法收敛得快，但也有迭代比迭代收敛得慢，甚至还有迭代收敛，迭代发散的情形。评价：与相比，只需一组工作单元存放近似解。Gauss-Seidel迭代法的计算过程如下：(0)(0)(0)(0)112(0)1111121(0)111.(),(,),(,),.2.1.3. () / () /(2,1) (ijnnnjjjiniiijjijjiijjinnAabbbn xxxxNkxba xaxba x
14、a xainxba 输入维数最大容许迭代次数置计算11(0)(0) /4.,55.,1,(1,2, ),3nnjjnnjiixaxxxkNkk xxin若输出停机；否则转 。若置转 ；否则，输出失败信息，停机。松弛(SOR)法(1)( )(1)121(1)( )( )111(1)( )( )11 (,), 1 ()Tkkkninkkkiijjijjiijj iinkkkiijjijjijj iiiGaussSeidelxxxxxxxGaussSeidelxb xb xgxba xa xxa 为迭代法加速。记其中由迭代公式得到。于是有( )(1)( )(1,2, )kkkinxGaussSeid
15、elkxxxx 可以把看作迭代的修正项，即第 次近似解以此项修正后得到新的近似解 (1)( )(1)1(1)( )11 (1)() (kkkkiiiinkkkiiijjijjjj iiixxxxxxxxba xa xai 松弛法是将乘上一个参数因子 作为修正项而得到新的近似解，具体公式为即1,2, ) 111nAxbGaussSeidel按上式计算的近似解序列的方法称为松弛法，称为松弛因子。当时称为低松弛；是迭代；时称为超松弛法。SOR迭代法也可以看作是G-S迭代法的一种修正. 假设已知:)(kx及)1( kx1,.2 , 1)1(ijxkj首先利用G-S迭代计算预测值)1(kix)(1)(1
16、)1(11)1(kjnijijkjijijiiikixaxabax加权平均可得:)(kix)1(kix)1()()1()1 (kikikixxx)()()1()()1(kikikikixxxx即得再由和的前 i-1个分量(1)( )( )1(1)1( )1( )( )1(1)1( )11111(1)1 () (1)1,() () (1kkkkkkkkkkxxxxD LxD UxD bxxD LxD UxD bID LID LDLxDL松弛法迭代公式的矩阵表示：因为故（） 与存在，有( )11)() () (1) ,kDU xDLbMDLDU松弛法的迭代矩阵为松弛因子的选取对收敛速度影响极大 但
17、目前尚无可供实用的计算最佳松弛因子的方法。通常是根据系数矩阵的性质及实际经验，通过试算来确定松弛因子。(0)12123231(1)(1)( )11(1)( )( )112(1)( )22 1.4,(1,1,1) ,21 2021.8 (1)()0.40.7(1)0.4Tinkkkkiiiijjijjjj iiikkkkkxxxxxxxxxxba xa xaxxxxx 例：取用超松弛法解方程组解：由(1)( )13(1)( )(1)332(0)(9)0.7()(0,1,2,)0.40.7(1.8)(1,1,1)(1.200,1.3996,1.6001) (1.2,1.4,1.6)kkkkkTTT
18、xxkxxxxxx 将代入上式开始迭代，精确解返回返回松弛法计算过程如下：(0)(0)(0)(0)112(0)(0)11111121(0)(0)111.(),(,),(,),.2.1.3. (1)() / (1)() / ijnnnjjjiniiiijjijjiijjiAabbbn xxxxNkxxba xaxxba xa xa 输入维数最大容许迭代次数，参数置计算1(0)1(0)(0) (2,1) (1)() /4.,55.,1,(1,2, ),3nnnnnjjnnjiiinxxba xaxxxkNkk xxin若输出停机；否则转 。若置转 ；否则，输出失败信息，停机。引入误差向量*)()(
19、xxkk则可得)()1(kkB由 等价于xfBxxkk)()1(fBxx)0()1()(kkkBB问题是在什么条件下所以*)(limxxkk等价于0lim)(kk0lim)(kk也即0kB3.迭代法的收敛性bAx 作:( )( )( )( )( )( lim0 lim limknnkkkkknknikxRxRxxxxxxRxRxx定义：设为中的向量序列，如果其中为向量范数，则称序列收敛于 ，记为定理：中的向量序列收敛于中的向量 当且仅当)( )( )( )( )1212( )( )( )( )( )1( ) (1,2, )(,) ,(,) lim010max lim=0 (1,2, ) kik
20、kkkTTnnkkkkkkiijjj nkiikxinxxxxxx xxxxxxinxxxxxxxxin 其中。证：由定义，收敛于 即而对任意，有由极限存在准则得即( ) lim (1,2, )kiikxxin()()()()()()() lim0 lim () (1,2,),(kkkkkkkkijijkAnAnAAAAAAAakAanAA 定义：设为 阶方阵序列，为 阶方阵，如果其中为矩阵范数，则称序列收敛于矩阵 ，记为定理：设)均为 阶方阵，则矩阵序列收敛于矩阵 的充()(1)()()(1)() lim ( ,1,2,) , limlimkijijkkkkkkkkaai jnxMxgxxx
21、xMxgMxgxA 要条件为证明略。定理表明，向量序列和矩阵序列的收敛可以归结为对应分量或对应元素序列的收敛。若按产生的向量序列收敛于向量则有即 是方程组xb的解。 注: 其中 为矩阵的任一种算子范数 (p244定理1 ) 0limlimAAAAkkkk lim0( )1 lim0 lim0 ( ) 0() ( ) lim ( )0 ( )11 ( )1kkkkkkkkkkkAnAAAAAAAAAAAA定理：设 为 阶方阵，则的充要条件为。证：必要性： 若由矩阵收敛的定义知又因由极限存在的准则，有所以。充分性。若，取( )0,21( ) ( )12,limlim0lim0.kkkkkkkkAA
22、AAAAAAA由上一定理知，存在一种矩阵范数，使得而注迭代法基本定理(0)(1)( )( )*( )*( ) (0,1,2,)()1. : , lim kkkkkkxgxMxgkxMnxxxxxMxgx定理：对任意初始向量和右端项 ，由迭代格式产生的向量序列收敛的充要条件是证 必要性 设存在 维向量使得则满足由迭代公式有*(1)*(1)*2(2)*(0)*(0)*( )*(0) ()()() lim()lim()0, lim0 ()1.kkkkkkkkkkxMxgMxgM xxMxxMxxMxxxxxnMM于是有因为为任意 维向量 因此上式成立必须由上一定理*( )*(1)*(0)*(0)(
23、)* :()1,1,0, lim0 ()(), lim ()limkkkkkkkkMMIMngIM xgxxMxgMxxM xxMxxxxxM充分性 若则不是的特征值 因而有于是对任意 维向量方程组有唯一解 记为即并且又因为所以 对任意初始向量都有(0)*(1)( )( )(0)(1)( )( )()=0.1 1, (0,1,2,).kkkkkkkxxxMxgxxgMxMxgkx即由迭代公式产生的向量序列收敛推论对任意初始向量和右端项 ，若由迭代格式产生的向量序列收敛矩阵的谱半径11212 (1,2, ) ( )max( ,) (,)(1,2,), () (iii nnkkkkknAninAA
24、AAAAAAkA 迭代法的收敛与迭代矩阵的特征值有关。定义：设 为 阶方阵，为 的特征值，称特征值的最大值为矩阵 的谱半径，记为称为矩阵 的谱。由特征值的定义知，矩阵的谱是因而)kA定理2AxxARxAAkknkklimlim有对任何由此得P248的定理5(迭代法收敛的充分条件)定理5 设有方程组 和其定常迭代法fBxxfBxxkk)()1(如果B的某种算子范数1 qB则: 1. 迭代法收敛即对任取的有)0(x*)(limxxkkfBxx*)0(*)(*xxqxxkk)1()()(*1kkkxxqqxx)0()1()(*1xxqqxxkk证明证明1212111122 2 02 , det()
25、() det()1 det()()(1)1 () (1nnnnnMMMMMDLDUDLa aa 推论松弛法收敛的必要条件是。证：设松弛法的迭代矩阵由特征值。因为由定理，松弛法收敛必有又因为1122)(1)det()(1)102 nnnnDUa aaM。迭代法收敛与否只决定于迭代矩阵的谱半径，与初始向量及右端项无关。对同一方程组，由于不同的迭代法迭代矩阵不同，可能出现有的方法收敛，有的方法发散的情形。(P252定理定理8)123123123221 2223 1122100 111 010221001000 100220 xxxxxxxxxADL例：对方程组讨论Jacobi迭代法与Gauss-Se
26、idel迭代法的收敛性。解：求迭代矩阵判别其谱半径是否小于 。022 001000U13123 Jacobi022 10122022 110220,( )01,JacobiBIDAIBB迭代法的迭代矩阵为其特征方程为因此有于是所以迭代法收敛。1121 Gauss-Seidel100100 110 ()110221021100022022()11000102302100000222 023(2)00020,DLDLMDLUIM 迭代，由特征方程特征值为232,()21,M故所以迭代发散。 021 121,1,1 BM上例说明了确实只是松弛法收敛的必要条件，而非充要条件，因为Gauss-Seide
27、l迭代记为的情形。判断定理虽然给出了判别迭代收敛的充要条件，但要求逆矩阵和特征值。推论 与 仅分别给出了收敛的充分与必要条件，许多情形下不能起作用。如上例，两个方法均有由推论 无法判别收敛性。对一些特殊的系数矩阵可给出几个常用的判别收敛条件( (特殊方程组迭代法的收敛性特殊方程组迭代法的收敛性P249)P249)11112112222 ()(1,2, ) ,01 10 1 1nijiiijjj inAaaainiAiAAAAAAAAAA定义：若 阶方阵满足且至少有一个 值，使上式中不等号严格成立，则称 为弱对角占优阵。若对所有，上式不等号均严格成立，则称为严格对角占优阵。定义：如果矩阵 不能通
28、过行的互换和相应的列互换成为形式其中，为方阵，则称 为不可约。 例：132 1000 1 10 120 1 1P ITP AP 定理定理6: (对角占优定理对角占优定理 P250)如果矩阵如果矩阵A为严格对角占矩阵或为不可约弱对角占优矩阵为严格对角占矩阵或为不可约弱对角占优矩阵,则则A为非奇异矩阵为非奇异矩阵. . ,1.JacobiGauss-Seidel2.01,3.021012210 1102121115012AxbAAAABA设有线性方程组下列结论成立：若 为严格对角占优阵或不可约弱对角占优阵，则迭代法和迭代法均收敛。若 为严格对角占优阵，则松弛法收敛。若 为对称正定阵，则松弛法收敛的
29、充要条件为。上两例中：为严格对角占优B阵，故Jacobi与Gauss-Seidel迭代均收敛。为非严格对角占优阵，但为对称正定阵，=1.4故松弛法收敛。(P251定理定理7,9,10)例例同时同时G-S迭代法也收敛迭代法也收敛.如如1条件的矩阵，条件的矩阵， 证明证明-11112211,122111223(02)11102211 -02211022Axb AAAABID A例：讨论用三种迭代法求解的收敛性。解：因 为对称且其各阶主子式皆大于零，故 为对称正定矩阵。由判别条件 ，Gauss-Seidel迭代法与松弛法均收敛。 不是弱对角占优阵，故不能用条件 判断。Jacobi迭代法的迭代矩阵为3
30、212311221131 224411221 () (1)021,1, ()12 IBBJacobi 其 特 征 方 程得因 而迭 代 法 不 收 敛 。 310 , 9410100033 , 91500423015( ),()22AxbAJacobiGaussSeidelBMBM改变方程组中方程的次序，即将系数矩阵作行交换，会改变迭代法的收敛性。例：与迭代的迭代矩阵分别为谱半径分别是。均不收敛。特别特别 ,31094 94310AxbA xbAAAA xbJacobiGaussSeidel若交换方程的次序，得的同解方程组为严格对角占优阵，因而对方程组用与迭代求解均收敛。误差估计(1)()()
31、*()*(1)(0)1*1()*(1)*(0)* ,1, 1 ()1,0,) ()() kkkkkkkkxMxgMxxMxxxxMMMIMIMxMxgxxIMgxxMxxMxx定 理 ： 设 有 迭 代 格 式若收 敛 于则 有 误 差 估 计 式证 ： 因故于 是(存 在 ， 方 程 组有 唯 一 解，且(。 从 而 有(0)11(0)1(0)1 ) ) )kkkMxIMgMIMIMxgMIMxx（ ）()*1(0)11111111()* ) ) ) ) )1 )1 1kkkkxxMIMxxIMIMIIMIM IMIMIM IMIMIMIMMMxx（ ）取范数(又因为(取范数(移项得(代入得
32、(1)(0)xxM。( )*(1)(0)(1)(0)(0)(1)4( 1:(1)ln ln00.10.207.20.100.2 ,0 ,8.30.20.2008.410, 0.4, kkMxxxxMkMxxkMMxxMx 由误差估计式根据事先给定的精度 ，可估计出迭代的次数例：若则有1)(0)8.4 12.932,13xk即需要迭代次才能满足精度。(1)( )( )*( )*( )(1)( )*(1)*(1)11(1)(1)1(1)( )( )*1(1) ,1, 1() ) ()kkkkkkkkkkkkkkkxMxgMxxMxxxxMxxM xxM xIMgM IMxMxgM IMxxxxMI
33、Mx定理：设有迭代格式若收敛于则有误差估计式证：因 ( )( )(1)( )(1) .11kkkkkxMxxMMxx当不太接近 时，可用作为停机准则。证明：证明：2.)*()*(*)1()()()1()( kkkkkxxxxBxxBxx|)|*(|*|)1()()()( kkkkxxxxqxx3.)(.)()0()1(1)2()1()1()(xxBxxBxxkkkkk |)0()1(1)1()(xxqxxkkk 1.)()(*)0(*)(*)(*)1(xxBxxxxBxxkkkk则，*)0(*)(xxqxxkk所以返回返回 :, ( ):, , ( ) . :,iiiiiiiiiiiAnAAA
34、uuuAuA uuAAAAn定理设 为任意 阶方阵为任意由向量范数诱导出的矩阵范数 则证对 的任一特征值 及相应的特征向量都有因为 为非零向量 于是有由 的任意性即得证毕定理设 为任意 阶方阵 则对任意正数 存在一种矩阵2, ( ) , ( )( )AAnAAAAA范数使得证明略。对任意 阶方阵 一般不存在矩阵范数使得。但若 为对成矩阵，则有。注:返回,2,1, |1niaanijjijii证明证明: 只证关于简单迭代法的两个，其余两个的证明类似.(1)设A具有严格对角优势，以下证(BJ)1,01存在Daii.)(1存在ULDBJ反证法，设BJ有特征值,| 1., 0| )(| )(|111U
35、LDDULDDULDIBIJ. 0|, 0|1ULDD但3.20,|212222111211nnnnnnaaaaaaaaaULD考查.,|,|,niaaaAnijjijiiii2111而严格对角占优由于所以D+L+U也具有严格对角优势，所以| D+L+U| 0，所以| 1不可能成立，所以|1，即(BJ)1。. 0|ULD3.21 与 矛盾(2) A 不可约且具有对角优势， 证(BJ)1 ， 由定理有A非奇异， 又.0|., 2 , 1, |1成立iinijjijiianiaa.)(1存在ULDBJ（否则A必有一行元素全为零，与A非奇矛盾）用反证法，设BJ有特征值, | 1.同（1）有(3.20),(3.21)。注意 D+L+U中非零元素的位置与A中非零元素的位置完全 相同，而A不可约.所以必有 D+L+U 不可约.返回所以 D+L+U有对角线优势，所以| D+L+U| 0，与（3.20）矛盾。| 1不可能成立，所以|1，即(BJ)1., 2 , 1, |, 1|1成立niaaanijjijiiii
