第四章 解线性方程组的迭代法
对于阶数不高的方程组，直接法非常有效，对于阶数高，而系数矩阵稀疏的线性方程组却存在着困难，在这类矩阵中，非零元素较少，若用直接法求解，就要存贮大量零元素。为减少运算量、节约内存，使用迭代法更有利。本章介绍迭代法的初步内容。
§1 雅克比法、赛得尔法、超松驰法 1．雅克比（Jacobi）迭代法 设有n阶方程组
?a11x1?a12x2???a1nxn?b1?ax?ax???ax?b?2112222nn2 ??????an1x1?an2x2???annxn?bn （4.1）
若系数矩阵非奇异，且aii?0 (i = 1, 2,…, n)，将方程组（4.1）改写成
1?x??1a?b1?a12x2?a13x3???a1nxn?11?1??b2?a22x1?a23x3???a2nxn?x??2a ?21????1?x??na?b1n?an1x1?an2x2???an,n?1xn?1?nn?1?(k?1)(k)(k)(k)??x?b?ax?ax???ax111221331nn?a11?1?(k?1)(k)(k)??x?b1?a21x1(k)?a23x3???a2nxn?2a22 ?????1?(k?1)(k)(k)(k)?x?b?ax?ax???axnn1n1n22n,n?1n?1??ann?然后写成迭代格式
（4.2）
（4.2）式也可以简单地写为
xi(k?1)1?aii??n?(k)?b?ax?i?ijj?j?1??j?i??(0)(i?1,2,?,n)
（4.3）
对（4.2）或（4.3）给定一组初值X序列X(k)(0)(0)T?(x1(0),x2,?xn)后，经反复迭代可得到一向量
(k)T****T*?(x1(k),?xn)，如果X (k)收敛于X?(x1,x2,?xn)，则xi(i?1,2,?,n)就
是方程组（4.1）的解。这一方法称为雅克比（Jacobi）迭代法或简单迭代法，（4.2）或（4.3）称为Jacobi迭代格式。 下面介绍迭代格式的矩阵表示： 设D = diag (a11, a22, …, ann)，将AX = b改写为： AX = (D – (D - A)) x = b DX = (D - A) x + b X = (I – D-1A) x + D-1b
记 B = I – D-1A F = D-1 b 则迭代格式的向量表示为
X(k?1)?BX(k)?F Ｂ称为雅克比迭代矩阵。 2．高斯――赛得尔（Gauss-Seidel）迭代法
显然，如果迭代收敛，xi(k?1)(k?1)应该比xi更接近于原方程的解xi（i = 1, 2,…, n），因此
(k)(k)*在迭代过程中及时地以xi式可写成：
代替xi（i = 1, 2,…, n-1），可望收到更好的效果。这样（4.2）
1?(k?1)(k)(k)(k)??x?b?ax?ax??ax111221331nn?a11?1?(k?1)(k)(k)??x?b2?a21x1(k?1)?a23x3??a2nxn?2a ?22????1?(k?1)(k?1)(k?1)(k?1)?x?b?ax?ax??axnnn11n22n,n?1n?1??ann? （4.5）
（4.5）式可简写成
x(k?1)i1?aiii?1??bi??aijx(jk?1)??j?1?j?i?1?anijx(k)j?? （i = 1, 2,…, n） ?? 此为G－S迭代格式。 G－S迭代格式的矩阵表示： Jacob方法的迭代格式为
x(k?1)?Bx(k)?F
其中 B = I-D-1A F = D-1b 将B写成 B = L + U L是下三角阵，U是上三角阵 从而 x
(k?1)?Lx(k?1)?Ux(k)?F
(I?L)x(k?1)?Ux(k)?F
x(k?1)?(I?L)?1Ux(k)?(I?L)?1F
（4.6）
此时迭代矩阵为 (I - L)-1U 关于上述迭代法的误差控制，可按类似于第二章非线性方程求根的迭代法处理，设?为
允许的绝对误差限，可以检验
maxxi(k?1)?xi(k)??
1?i?n是否成立，以决定计算是否终止，进一步的讨论稍后进行。 实际计算时，如果线性方程组的阶数不高，建立迭代格式也可以不从矩阵形式出发，以避免求逆矩阵的计算。 3．超松驰法 使用迭代法的困难是计算量难以估计，有些方程组的迭代格式虽然收敛，但收敛速度慢而使计算量变得很大。
松驰法是一种线性加速方法。这种方法将前一步的结果xi与高斯――赛得尔方法的迭
(k?1)(k)xi代值~适当进行线性组合，以构成一个收敛速度较快的近似解序列。改进后的迭代方案
是： 迭代
i?11?(k?1)~?bi??aijx(jk?1)?xi?aii?j?1?(k)??ax?ijj?
j?i?1?n加速
xi(k?1)?(1??)xi(k)??~xik?1(i?1,2,?,n)
所以
x(k?1)i?(1??)x(k)i?bi??aijx?aii?j?1???i?1(k?1)j??(k)?ax?ijj?
j?i?1?n （4.7）
这种加速法就是松驰法。其中系数?称松驰因子。可以证明，要保证迭代格式（4.7）
收敛必须要求 0???2 松驰法的矩阵形式的迭代格式为：
x(k?1)?B?x(k)?F?
?1其中 B??(I??L)?(1??)I??U?
F???(I??L)?1b
当? = 1时，即为高斯――赛得尔迭代法，为使收敛速度加快，通常取??1，即为超松驰法。 松驰因子的选取对迭代格式（4.7）的收敛速度影响极大。实际计算时，可以根据系数矩阵的性质，结合经验通过反复计算来确定松驰因子?。
§2 迭代法的收敛条件 由§1中迭代格式的矩阵形式知，方程组AX = b的雅克比迭代法、高斯――赛得尔迭代法和松驰法的矩阵形式都可以写成下式：
X(k?1)?BXk?F
（4.8）
当然，不同的迭代法其迭代矩阵B和F的元素是不同的。所以我们讨论迭代格式（4.8）的收敛性，就具有普遍意义。 下面，我们不加证明地给出迭代格式（4.8）收敛的充分必要条件。 定理1：对任意初始向量X(0)及常向量F，迭代格式（4.8）收敛的充分必要条件是迭代矩阵B的谱半径?(B) < 1。 这一结论在理论上是颇为重要的，但实际用起来不甚方便，为此我们着重研究更为实用的判别迭代格式收敛的充分条件。 考虑迭代向量序列{X(k)}的收敛问题： 若 于是
limX(k)?X*
k??X*?BX*?F
X(k)?X*?B?X(k?1)?X*??B2?X(k?2)?X*????B(Xk(0)
?X)*
收敛的意思是：
limX(k)?X*?limBkX(0)?X*?0
k??k??????依范数收敛是
X(k)?X*?BmX(0)?X*?0 当k??，从而得以下定理：
定理2：若迭代矩阵Ｂ的某种范数B?1则（4.8）确定的迭代法对任意初值X(0)均收
敛于方程组X = BX + F的唯一解x*。
下面给出直接计算xi(k?1)时的收敛性定理。为给出这个定理，先介绍对角占优的概念。
定义1：如果矩阵的每一行中，不在主对角线上的所有元素绝对值之和小于主对角线上元素的绝对值，即
?aj?1j?inij?aiii?1,2,?,n
则称矩阵A按行严格对角占优，类似地，也有按列严格对角占优。 定理3：若线性方程组AX = b的系数矩阵A按行严格对角占优，则雅克比迭代法和高斯――赛得尔迭代法对任意给定初值均收敛。
证明：记ek?maxxj1?j?n(k)?x*j
(k)T为第k次近似值x1,x2,?,xn
（1）由雅克比迭代法
?(k)(k)?的误差，
x(k?1)*iix???xaj?1j?iiinaij(k)j?x*j???aj?1j?inaijiix(jk)?x*j
记
L??j?1j?inaijaii
则有
xi(k?1)?xi*?L?maxx(jk)?x*j
1?j?n上式对 i = 1, 2,…, n成立，故有
ek?1?Lek???Lk?1e
因为A严格对角占优，故L < 1，从而有
limxi(k?1)?xi*?limLk?1xi(0)?xi*?0
k??k??即雅克比方法收敛。
（2）高斯――赛得尔迭代法 考虑高斯――赛得尔方法的误差
xi(k?1)?xi*?
?a?xijj?1i?1(k?1)j?x??*jj?i?1?xnn(k)j?x*j
aii?a?L??j?1i?1i?1ijx(jk?1)?x*jaiiS?j?1?j?i?1?aaijiiijx(jk)?x*jaii记 则
aijaiij?i?1?an
(k)xi(k?1)?xi*?L?maxx(jk?1)?x*?x*j?S?masxjj
1?j?i?1i?1?j?n从而
ek?1?Lek?1?Sek
ek?1S?S??ek?????1?L1?L??k?1?e0
而
L1L?S?S?L?LS?L?????1 ???1?L1?L1?L1?L1?L1?L??所以
limxi(k?1)?xi*?0
k??即：高斯――赛得尔迭代法收敛。 证完
例：用雅克比迭代法和高斯――赛得尔迭代法解线性方程组
?9?1?1??x1??7????????180???x2???7? ??10????9????x3??8?解：所给线性方程组的系数矩阵按行严格对角占优，故雅克比迭代法和高斯――赛得尔
第四章 解线性方程组的迭代法
