第5章01迭代公式的建立

1、第五章第五章 线性代数方程组的迭代法线性代数方程组的迭代法 5.1 5.1 迭代公式的建立迭代公式的建立 5.2 5.2 向量和矩阵的范数向量和矩阵的范数 5.3 5.3 迭代过程的收敛性迭代过程的收敛性 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111 写成矩阵形式写成矩阵形式 Ax=b 其中其中1112111212222212, bnnnnnnnnaaaxbaaaxbAxaaaxb5.1 5.1 迭代公式的建立迭代公式的建立 设设线性代数方程组线性代数方程组迭代法就是用某种迭代法就是用某种极限过程极限过程去去逐步逼近逐步逼近线性方程组精

2、确解的方法。线性方程组精确解的方法。 基本思想基本思想：对给定的方程组：对给定的方程组Axb，写成等价的形式，写成等价的形式 xGxd 构造一个迭代公式构造一个迭代公式 (1)( )kkxGxd 当给定初始向量当给定初始向量 (0)x，进行迭代，生成向量序列进行迭代，生成向量序列 (1)(2)( ),kxxx 当向量序列当向量序列收敛到某个收敛到某个极限向量极限向量 x，即，即( )limkkxx 则则x是方程组是方程组Axb的的精确解精确解，即满足，即满足 *Axb 对给定的方程组对给定的方程组Axb，如何写成等价的形式，如何写成等价的形式xGxd 例如：设例如：设AMN，则有，则有()MN

3、 xb，MxNxb，11xMNxMb，写成，写成迭代公式迭代公式(1)( )kkxGxd 其中其中1GMN，1dM b。 又 ， 如又 ， 如 方 程 组方 程 组Axb， 写 成， 写 成0,AxbxxAxb，()xIA xb写成写成迭代公式迭代公式(1)( )kkxGxd 其中其中GIA，db 。 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111设设线性方程组线性方程组其中系数矩阵其中系数矩阵非奇异非奇异，且主对角元，且主对角元aii0，(i =1,2,n)，由第，由第i 个方程解出个方程解出xi，有，有111221331111 122

4、111()1()nnnnnnnnnnnxba xa xa xaxba xa xaxa5.1.1 雅可比迭代公式雅可比迭代公式11() , (1,2, )niiijjjiij ixba xina建立迭代格式建立迭代格式(1)( )( )( )11122133111(1)( )( )( )2221 1233222(1)( )( )( )1 122111()1()1()kkkknnkkkknnkkkknnnnnnnnnxba xa xa xaxba xa xa xaxba xa xaxa写成写成取初值取初值 ，进行迭代。，进行迭代。这种方法称为这种方法称为雅可比雅可比(Jacobi)迭代公式迭代公式

5、。(0)(0)(0)12,nxxx), 2 , 1(, )(11)()1(nixabaxnijjkjijiiiki ), 2 , 1(, )(11)()1(nixabaxnijjkjijiiiki 雅可比迭代公式雅可比迭代公式即即(i=1,2,n)1(1)( )( )111() , (1,2, )inkkkiiijjijjjj iiixba xa xina )(11)()()1(njkjijiiikikixabaxx雅可比迭代雅可比迭代的的算法框图算法框图(1)( )11()(1,2, )nkkiiijjjiij ixba xain例例 用雅可比迭代法求解方程组用雅可比迭代法求解方程组 123

6、1231231023210152510 xxxxxxxxx解解 从从3个方程分离出个方程分离出1232133120.20.10.30.20.11.50.20.42xxxxxxxxx构造雅可比迭代公式构造雅可比迭代公式 (1)( )( )123(1)( )( )213(1)( )( )3120.20.10.30.20.11.5 ,0,1,2,0.20.42kkkkkkkkkxxxxxxkxxx(0)T00,0,0 x(1)10.3x(1)21.5x(1)32x迭代计算迭代计算(1)( )( )123(1)( )( )213(1)( )( )3120.20.10.30.20.11.50.20.42

7、kkkkkkkkkxxxxxxxxx(2)(1)(1)123(2)(1)(1)213(2)(1)(1)3120.20.10.30.80.20.11.51.760.20.422.66xxxxxxxxx k 0 1 2 3 4 5 x1(k)00.30.80 0.91800.97160.9894 x2(k)01.51.76 1.9260 1.97001.9897 x3(k)02.02.662.8640 2.95402.9823 5.1.2 高斯高斯- -塞德尔迭代塞德尔迭代 雅可比迭代收敛时，新值雅可比迭代收敛时，新值xi(k+1) 比老值比老值xi(k) 更准确；更准确；在雅可比迭代中，算出新值

8、在雅可比迭代中，算出新值xi(k+1)后，用新值后，用新值xi(k+1)代代替用于后面计算的老值替用于后面计算的老值xi(k) ，期望这样会收敛得更，期望这样会收敛得更快些，即为快些，即为高斯高斯- -塞德尔塞德尔(Gauss-Seidel)迭代。迭代。设计思想：设计思想：高斯高斯- -塞德尔迭代公式：塞德尔迭代公式： ), 2 , 1(, )(11)(11) 1() 1(nixaxabaxnijkjijijkjijiiiki 高斯高斯- -塞德尔迭代公式的塞德尔迭代公式的特点特点是：一旦求出变元是：一旦求出变元xi的的某个新值某个新值xi(k+1)后，就改用后，就改用新值新值xi(k+1)代

9、替代替老值老值xi(k)进行进行这一步以后剩下的计算。因此，可将新值存放在老这一步以后剩下的计算。因此，可将新值存放在老值所占用的单元内，公式可表为下列动态形式：值所占用的单元内，公式可表为下列动态形式： 11()/,(1,2, )iiijjiiijj iba xaxin用两次迭代的用两次迭代的偏差偏差 来控制迭来控制迭代过程的终止。代过程的终止。 1maxiii nyx ), 2 , 1(, )(11)(11) 1() 1(nixaxabaxnijkjijijkjijiiiki 高斯高斯-塞德尔塞德尔迭代迭代算法框图算法框图1(1)(1)( )111()(1,2, )inkkkiiijjij

10、jjj iiixba xa xain 例例 用高斯用高斯- -塞德尔迭代法求解方程组塞德尔迭代法求解方程组解解 方程组化为等价的方程组方程组化为等价的方程组 1231231231023210152510 xxxxxxxxx1232133120.20.10.30.20.11.50.20.42xxxxxxxxx构造构造高斯高斯- -塞德尔塞德尔迭代公式迭代公式 (1)( )( )123(1)(1)( )213(1)(1)(1)3120.20.10.30.20.11.5,0,1,2,0.20.42kkkkkkkkkxxxxxxkxxx(0)T00,0,0 x )1(1x )1(2x )1(3x迭代计

11、算：迭代计算：1.562.684 )2(1x(2)2x(2)3x2.953870.88041.94448高斯高斯- -塞德尔塞德尔迭代公式迭代公式 0.3(1)( )( )123(1)(1)( )213(1)(1)(1)3120.20.10.30.20.11.50.20.42kkkkkkkkkxxxxxxxxx计算结果计算结果: k 0 1 2 3 x1(k)00.30.8804 0.98428 x2(k)01.561.944481.99224 x3(k)02.6842.953872.99375 小结小结一般情况下高斯一般情况下高斯- -塞德尔迭代法比雅可比迭代法塞德尔迭代法比雅可比迭代法好；

12、好；但情况并不总是这样，也有高斯但情况并不总是这样，也有高斯- -塞德尔迭代法塞德尔迭代法比雅可比迭代法收敛得慢，甚至有雅可比迭代比雅可比迭代法收敛得慢，甚至有雅可比迭代法收敛而高斯法收敛而高斯- -塞德尔迭代法反而发散的例子。塞德尔迭代法反而发散的例子。5.1.3 超松弛法超松弛法(SORSuccessive Over-Relaxation)将高斯将高斯-塞德尔迭代前一步计算结果塞德尔迭代前一步计算结果()kix与这一步与这一步的计算结果的计算结果(1)kix适当加权平均， 可期望得到更好的近似适当加权平均， 可期望得到更好的近似值值(1)kix，即有，即有松弛法松弛法，其迭代格式，其迭代格

13、式 迭代迭代 )(1111)()1()1(ijnijkjijkjijiiikixaxabax 加速加速)()1()1()1(kikikixxx 1,2,in 或合或合并并写成写成迭代迭代- -加速加速的形式的形式 1(1)()(1)()11(1)()inkkkkiiiijjijjjj iiixxba xa xa 参数参数称为称为松弛因子。松弛因子。 可以证明，为了保证迭代过程收敛，必须要求可以证明，为了保证迭代过程收敛，必须要求02。 迭代迭代- -加速加速的形式的形式 1(1)()(1)()11(1)()inkkkkiiiijjijjjj iiixxba xa xa 1) 1时迭代格式就是高

14、斯时迭代格式就是高斯- -塞塞德尔迭代格式德尔迭代格式。 2) 0 0 1叫叫低松弛因子。低松弛因子。 3) 由于迭代值由于迭代值(1)kix 通常比通常比kix精确，所以在加速精确，所以在加速公式中加大公式中加大(1)kix 的比重，尽可能扩大它的效果，的比重，尽可能扩大它的效果，取松弛因子取松弛因子12，叫，叫超松弛法超松弛法。 1(1)(1)( )( )11()(1)inkkkkiiijjijjijj iiixba xa xxa 松弛因子松弛因子的取值对迭代加速公式的收敛的取值对迭代加速公式的收敛速度影响极大。速度影响极大。 实际计算时，可以根据方程组的系数矩阵的实际计算时，可以根据方程

15、组的系数矩阵的性质，并结合实践计算的经验来选取合适的松弛性质，并结合实践计算的经验来选取合适的松弛因子。因子。 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111 矩阵形式矩阵形式 Ax=b 其中其中1112111212222212, bnnnnnnnnaaaxbaaaxbAxaaaxb5.1.4 迭代公式的矩阵表示迭代公式的矩阵表示n个未知量个未知量n个方程的线性代数方程组个方程的线性代数方程组111212122212nnnnnnaaaaaaALDUaaa令系数矩阵令系数矩阵11121212221,1000000nnnn nnnaaaaaa

16、aaa其中其中D为为对角阵对角阵，L和和U分别为严格分别为严格下三角阵下三角阵和严格和严格上上三角阵三角阵。 L+U=A - D1212121,1111122122000000111nnnn nnnnnaaaaULaaaaaaDDaa雅可比迭代公式雅可比迭代公式分量形式分量形式(1)( )( )( )11122133111(1)( )( )( )2221 1233222(1)( )( )( )1 122111()1()1()kkkknnkkkknnkkkknnnnnnnnnxba xa xa xaxba xa xa xaxba xa xaxa1(1)( )( )111() , (1,2, )i

17、nkkkiiijjijjjj iiixba xa xina 矩阵形式矩阵形式(1)1( )( )()xxxkkkDbLU雅可比迭代的矩阵形式雅可比迭代的矩阵形式(1)1( )( )()xxxkkkDbLU雅可比雅可比迭代矩阵迭代矩阵 11( )()xkD bDLU将将L+U= A - D代入代入(1)11( )()xxkkD bDDA1( )1()kID AD bx(1)( )xxdkkG写成写成1GID A1dD b121311111111112123222222222212300,0dnnnnnnnnnnnnnnaaabaaaaaaabaaaaGaaabaaaa雅可比迭代的矩阵形式为雅可比

18、迭代的矩阵形式为(1)( )xxdkkGG为为雅可比迭代矩阵雅可比迭代矩阵。 1GID A1dD b高斯高斯- -塞德尔塞德尔法的迭代格式法的迭代格式 1(1)(1)( )111()inkkkiiijjijjjj iiixba xa xa 用分列式用分列式 A=D+L+U 则则 (1)(1)( )kkkDxbLxUx，(1)( )()kkDL xbUx， （1,2,kn） (1)1( )1()()kkxDLUxDLb 11(),()GDLU dDLb 松弛法的迭代格式松弛法的迭代格式 1(1)( )(1)( )11(1)()inkkkkiiiijjijjjj iiixxba xa xa 用分列式用分列式 A=D+L+U 则则 (1)( )(1)( )(1)()kkkkDx