第4章 线性方程组和矩阵特征值的迭代解法
线性代数计算方法中的迭代解法（即迭代法）是一类重要方法。其基本思想是构造适当的矩阵序列或向量序列，使其逐步逼近所求问题的精确解，故又称矩阵迭代方法。在求解阶数较高且零系数较多的大型稀疏线性代数方程组时，迭代法是很有效的。矩阵特征值问题的求解通常也要用迭代法。本章着重介绍求解线性代数方程组常用的简单迭代法及其收敛条件，并对计算矩阵特征值问题的雅可比方法和QR方法作一些介绍。
4.1 线性代数方程组的迭代解法
线性方程组(3.1)的迭代解法其基本思想与一元非线性方程的迭代解法类似，即构造适当的迭代公式，任选一个初始向量x(0)进行迭代计算，使生成的向量序列x(0),x(1),?，x(k),?收敛于方程组的精确解。
4.1.1 简单迭代法的一般形式
设方程组(3.1)的系数矩阵非奇异，把它化为等价的方程组
x?Mx?g (4.1) 其中
?m11?m21 M?????mn1按(4.1)构造迭代公式
m12m22?mn2?m1n??g1??x1??g??x??m2n?2?,g???,x??2?
?????????????mnn?g?n??xn? x(k?1)?Mx(k)?g,k?0,1,2,? (4.2)
(k)(k)T,?,xn](k?0,1,?)。任取初始向量x(0)，用(4.2)逐次计算近似解向量其中x(k)?[x1(k),x2x(1),x(2),?,x(k),?,这种方法称为简单迭代法，称(4.2)为简单迭代公式，M为迭代矩阵。
公式的分量形式是
?x1(k?1)?(k?1)?x2???x(k?1)?n(k)(k)?m11x1(k)?m12x2???m1nxn?g1(k)(k)?m21x1(k)?m22x2???m2nxn?g2????(k)(k)?mn1x1(k)?mn2x2???mnnxn?gn
65
即 xi(k?1)??mijx(jk)?gi,i?1,2,?,n,j?1n(k?0,1,2,?) (4.3)
如果x(k)的各分量存在极限
limxi(k)?xi?,i?1,2,?,n (4.4)
k?????T则称向量序列{x(k)}收敛于向量x??[x1,x2,?,xn]，并记为
limx(k)?x? (4.5)
k??这时，称简单迭代法(4.2)是收敛的，否则就是发散的。
当(4.2) 收敛时，容易看出x?满足方程组(4.1)，从而必定是原方程组(3.1)的解。实际计算时，一般用
maxxi1?i?n(k)?xi(k?1)?? (4.6)
来控制迭代结束，取x(k)为满足要求的近似解，其中?是指定的精度要求。这样做的理论根据将在后面(4.23)中指出。
例如下面左边的方程组可改写为右边的同解方程组
0.5x2?4?0.2x1?x2?3?x1? ? ?
?x1?0.5x2?4?x2??0.2x1?3(0)取x1(0)?x2?0，可构造迭代公式
(k?1)(k)?0.5x2?4?x1? ， k?0,1,2,..... ?(k?1)(k)?x??0.2x?31?2这是分量形式。若写成矩阵形式就是(4.2),其中
0.5??0?4?M??,g?,?????0.20??3?x(k)?x1(k)???(k)? ?x2?M就是迭代矩阵。容易计算出
(1)(2)(1)(3)(2)?0.5x2?4?5.5?0.5x2?4?5.1?x1?4??x1??x1?，?(2)，?(3),?? ?(1)(1)(2)???x?3x??0.2x?3?2.2x??0.2x?3?1.911?2?2?2设精度要求为??0.005，计算结果如表4.1所示。
表4.1 k 0 0 0 1 4 3 2 5.5 2.2 3 5.1 1.9 4 4.95 1.98 5 4.99 2.01 6 5.005 2.002 7 5.001 1.999 …… …… …… x1(k) x2(k) (7)(6)由于x1(7)?x1(6)??,x2?x2??,故求得方程组的解为 (7)x1?x1(7)?5.001,x2?x2?1.999
(k)上例中的迭代公式是收敛的，当k??时，x1(k)和x2的值越来越靠近准确解5和2。
66
对给定的方程组，可以构造各种迭代公式，下面介绍两种常用的简单迭代公式。
4.1.2 雅可比迭代法
设方程组(3.1)的系数矩阵A非奇异，其主对角元素aii?0(i?1,2,?,n)，并且绝对值相对来说比较大，我们从方程组的第i个方程
ai1x1?ai2x2???aiixi???ainxn?bi,i?1,2,?,n 中解出xi，得到等价的方程组 xi???j?1j?inaijaiixj?bi,i?1,2,?,n (4.7) aii即 x?Bx?f (4.8) 其中
??0???a21?a B??22?????an1???ann由(4.7)构造迭代公式
?a12a110a13a11a?23a22???an3annn?an2anna1n??b1??a?a11???11?a2n??b2????a22?a22?,f???? ?????????????bn??0??a??nn????bi,i?1,2,?,n,(k?0,1,2,?) (4.9) aii x其矩阵形式为
(k?1)i???aijaiij?1j?ix(jk)? x(k?1)?Bx(k)?f,k?0,1,2,? (4.10)
我们称(4.9)或(4.10)为雅可比(Jacobi)迭代公式，B为雅可比迭代矩阵。任取初始向量
(0)(0)Tx(0)?[x1(0),x2,?,xn]，按上述迭代公式逐次计算x(1),x(2),?，这就是雅可比迭代法，这是一种简单迭代法。
例4.1 用雅可比迭代法求解方程组
?x3?9?10x1? ?2x?10x?x?7 ?123??x2?5x3?4?精度要求为?=0.005，用5位有效数字计算。 解 将方程组写成等价的方程组
67
?x1?0.1x3?0.9 ??x2?0.2x?0.1x?13?0.7 ?x3?0.2x2?0.8构造雅可比迭代公式
?x(k?1)1x(k)1?0.3?0.9 ??x(k?1)?0.2x(k)(k)1?0.1k?0,1,?
?2x3?0.7?x(k?1)(k)3?0.2x2?0.8取初始向量x(0)?0?[0,0,0]T进行迭代，计算结果如表4.2
表4.2 k 0 1 2 3 4 5 ? x(k)1 0 0.9 0.98 0.994 0.999 2 0.999 80 ? x(k)2 0 0.7 0.96 0.99 0.998 0.999 64 ? x(k)3 0 0.8 0.94 0.992 0.998 0.999 60 ?
由于 x(5))(5)(4)(5)(4)1?x(41?0.00,5x2?x2?0.005,x3?x3?0.005 所以x(5)满足精度要求，即得
x1?0.99980,x2?0.99964,x3?0.99960
与精确解x??x??12?x3?1相比较，
上述计算解x1,x2,x3都具有3位有效数字。 简单迭代法在计算机上实现时，注意到计开始算x(k)只用到x(k?1)，无须保存x(k?2)及以前输入A,b,x,?,N0的计算结果，故一般只用两个一维数组x和y分别存放相继两次的迭代向量x(k?1)k?1和x(k)，当进行下一步迭代时，将y的值存入x取代旧的结果，将新的计算值存入yni?(?j?aijxj?bi)/aiij??1iky，依次循环进行计算。为了防止迭代发i?1,x??ky?12,?n散时陷入死循环，可以事先设一个最大迭F代次数N0，若迭代N0次仍达不到精度要1max?i?nyi?xi??Fk?N0求，则输出表示迭代失败的标志，并停止TT计算。
输出y1,y2,?,yn输出失败信息 雅可比迭代法的计算框图见图4.1。对于一般形式的简单迭代法(4.3)，计算框图结束类似，只需将图4.1中“输入A,b,?.”改
图4.1 雅可比迭代法的计算框图
68
