第四章解线性方程组的迭代法

第四章 解线性方程组的迭代法

对于阶数不高的方程组，直接法非常有效，对于阶数高，而系数矩阵稀疏的线性方程组却存在着困难，在这类矩阵中，非零元素较少，若用直接法求解，就要存贮大量零元素。为减少运算量、节约内存，使用迭代法更有利。本章介绍迭代法的初步内容。

§1 雅克比法、赛得尔法、超松驰法

1．雅克比（Jacobi ）迭代法

设有n 阶方程组

???????=+++=+++=+++n n nn n n n n n n b x a x a x a b x a x a x a b x a x a x a 22112222212111212111 （4.1）

若系数矩阵非奇异，且0≠ii a (i = 1, 2,…, n )，将方程组（4.1）改写成 ()()()

?????

??????----=----=----=--11,221112323122221213132121111111n n n n n n nn n n n n n x a x a x a b a x x a x a x a b a x x a x a x a b a x 然后写成迭代格式 ()()()???????????----=----=----=--+++)(11,)(22)(11)1()(2)(323)(121122)1(2)(1)(313)(212111)1(1111k n n n k n k n n nn k n k n n k k k k n n k k k x a x a x a b a x x a x a x a b a x x a x a x a b a x （4.2）

（4.2）式也可以简单地写为

),,2,1(1)(1)1(n i x a b a x k j n i j j ij i ii k i =????

? ??-=∑≠=+ （4.3） 对（4.2）或（4.3）给定一组初值T n x x x X

),,()0()0(2)0(1)0( =后，经反复迭代可得到一向量序列T k n k k x x X ),()()(1)( =，如果X (k )收敛于T n x x x X ),,(**2*1* =，则),,2,1(*n i x i =就

是方程组（4.1）的解。这一方法称为雅克比（Jacobi ）迭代法或简单迭代法，（4.2）或（4.3）称为Jacobi 迭代格式。

下面介绍迭代格式的矩阵表示：

设D = diag (a 11, a 22, …, a nn )，将方程组AX = b 中的系数矩阵表示成三个特殊矩阵的代数和矩阵：

A = D –L-U

其中 ???????

? ??-----=00021323121

n n a a a a a L ??????? ??---=0 0 02112 n n a a a U 由于 ),2,1( 0n i a ii =≠，D 为可逆对角阵，L 、U 分别为严格上、下三角阵，于是 b x U L Dx b x U L D b Ax ++=?=--?=)()(

利用D 可逆，得到等价方程组

b D x U L D x 11)(--++=

则迭代格式的向量表示为

J k J k f X B X +=+)()1(

)(1U L D B J +=- ， b D f J 1-=

J B 称为雅克比迭代矩阵。

2．高斯――赛得尔（Gauss-Seidel ）迭代法 显然，如果迭代收敛，)1(+k i

x 应该比)(k i x 更接近于原方程的解*i x （i = 1, 2,…, n ），因此在迭代过程中及时地以)1(+k i

x 代替)(k i x （i = 1, 2,…, n -1），可望收到更好的效果。这样（4.2）

式可写成： ()()()???????????---=---=---=+--++++++)1(11,)1(22)1(11)1()(2)(323)1(121222)1(2)(1)(313)(212111)1(1111k n n n k n k n n nn k n k n n k k k k n n k k k x a x a x a b a x x a x a x a b a x x a x a x a b a x （4.5）

（4.5）式可简写成

???? ??--=∑∑+=+-=+)(1)1(11)

1(1k j n i j ij k j i j ij i ii k i x a x a b a x （i = 1, 2,…, n ）

此为G －S 迭代格式。

G －S 迭代格式的矩阵表示：

b Ux x L D b x U L D b Ax +=-?=--?=)()(

b L D Ux L D x 11)()(---+-=

S k S k f x B x

+=+)()1( （4.6） U L D B S 1)(--= ， b L D f S 1)(--=

S B 称为高斯-赛德尔迭代矩阵。

关于上述迭代法的误差控制，可按类似于第二章非线性方程求根的迭代法处理，设ε为允许的绝对误差限，可以检验

ε<-+≤≤)()1(1max k i k i n

i x x 是否成立，以决定计算是否终止，进一步的讨论稍后进行。

实际计算时，如果线性方程组的阶数不高，建立迭代格式也可以不从矩阵形式出发，以避免求逆矩阵的计算。

3．超松驰法

使用迭代法的困难是计算量难以估计，有些方程组的迭代格式虽然收敛，但收敛速度慢而使计算量变得很大。

松驰法是一种线性加速方法。这种方法将前一步的结果)(k i x 与高斯――赛得尔方法的迭

代值)1(~+k i x 适当进行线性组合，以构成一个收敛速度较快的近似解序列。改进后的迭代方案是：

迭代

???? ??--=∑∑+=+-=+)(1)1(11)1(1~k j n i j ij k j i j ij i ii k i x a x a b a x

加速 ),,2,1(~)1(1)()1(n i x x x k i k i k i =+-=++ωω

所以 ???? ??--+-=∑∑+=+-=+)(1)1(11)

()

1()1(k j n i j ij k j i j ij i ii k i k i x a x a b a x x ωω （4.7）

这种加速法就是松驰法。其中系数ω称松驰因子。可以证明，要保证迭代格式（4.7）收敛必须要求 20<<ω

当ω = 1时，即为高斯――赛得尔迭代法，为使收敛速度加快，通常取1>ω，即为超松驰法。

松驰因子的选取对迭代格式（4.7）的收敛速度影响极大。实际计算时，可以根据系数

矩阵的性质，结合经验通过反复计算来确定松驰因子ω。

§2 迭代法的收敛条件

由§1中迭代格式的矩阵形式知，方程组AX = b 的雅克比迭代法、高斯――赛得尔迭代法和松驰法的矩阵形式都可以写成下式：

F BX X k k +=+)1( （4.8）

当然，不同的迭代法其迭代矩阵B 和F 的元素是不同的。所以我们讨论迭代格式（4.8）的收敛性，就具有普遍意义。

下面，我们不加证明地给出迭代格式（4.8）收敛的充分必要条件。

定理1：对任意初始向量X (0)及常向量F ，迭代格式（4.8）收敛的充分必要条件是迭代矩阵B 的谱半径(B ) < 1。

这一结论在理论上是颇为重要的，但实际用起来不甚方便，为此我们着重研究更为实用的判别迭代格式收敛的充分条件。

考虑迭代向量序列{X (k )}的收敛问题：

若

*)(lim X X k k =∞→

F BX X +=** 于是

()()

)(*)0(*)2(2*)1(*)(X X B X X B X X B X X k k k k -==-=-=---

收敛的意思是：

()()

0lim lim *)0(*)(=-=-∞→∞→X X B X X k k k k 依范数收敛是

0*)0(*)(→-≤-X X B X X m k 当k →∞，从而得以下定理： 定理2：若迭代矩阵Ｂ的某种范数1

下面给出直接计算)1(+k i x 时的收敛性定理。为给出这个定理，先介绍对角占优的概念。 定义1：如果矩阵的每一行中，不在主对角线上的所有元素绝对值之和小于主对角线上元素的绝对值，即

n i a a

ii n i j j ij ,,2,11 =<∑≠=

则称矩阵A 按行严格对角占优，类似地，也有按列严格对角占优。

定理3：若线性方程组AX = b 的系数矩阵A 按行严格对角占优，则雅克比迭代法和高斯――赛得尔迭代法对任意给定初值均收敛。

证明：记*)(1m ax j k j n j k x x e -=≤≤

为第k 次近似值()T k n k k x x x )()(2)(1,,, 的误差，

（1）由雅克比迭代法

()*)(1*)(1

*)1(j k j n

i

j j ii

ij

j

k j

n

i

j j ii

ij

i

k i x x a

a x

x

a a x x

-≤-=

∑∑≠=≠=+

记

∑

≠==n

i

j j ii

ij a a L 1

则有

*)(1*)1(m ax j k j n

j i k i x x L x x -?≤-≤≤+

上式对 i = 1, 2,…, n 成立，故有

e L Le e k k k 11++≤≤≤

因为A 严格对角占优，故L < 1，从而有

0lim lim *)0(1*)1(=-≤-+∞

→+∞

→i i k k i k i k x x L x x

即雅克比方法收敛。

（2）高斯――赛得尔迭代法 考虑高斯――赛得尔方法的误差

()ii

n

i j j k j ij

ii

j k j i j ij

ii

n

i j j

k j j

k j

i j ij i

k i

a x x a

a x x a

a x x

x x

a x x

∑∑∑∑+=+==+=+==+-+

-≤-+

-=

-1

*)(*)1(1

1

1

*)(*)1(1

1

*)

1(

记

∑∑

+====

=n

i j ii

ij

i j ii

ij a

a S a a L 1

1

1

则

*

)(1*)1(1

1*)1(m ax j k j n

j i j k j i j i k i x x mas S x x L x x -?+-?≤-≤≤++-≤≤+

从而

k k k Se Le e +≤++11

01

1

11e L S e L S e k k k ???

? ??-≤≤-≤++

而

11111111=---<---+=-+-=

??

? ??-L L L L L L L

S L L L S L S 所以

0lim *)1(=-+∞

→i k i k x x

即：高斯――赛得尔迭代法收敛。 证完

例：用雅克比迭代法和高斯――赛得尔迭代法解线性方程组

????

? ??=????? ??????? ??----877901081119321x x x 解：所给线性方程组的系数矩阵按行严格对角占优，故雅克比迭代法和高斯――赛得尔

迭代法都收敛。

D = diag (9, 8, 9) D -1 = diag (1/9, 1/8, 1/9)

???

?

? ??=--009/1008/19/19/10

1A D I

????

?

??=-9/78/79/71

b D

雅克比迭代法的迭代公式为：

????

?

??+????? ??=+9/78/79/7009/1008/19/19/10)()

1(k k X X 取X (0) = (0, 0, 0)T ，由上述公式得逐次近似值如下：

k 0 1 2

3 4

X (i )

?????

??000 ????? ??8889.08750.07778.0 ?????

??9753.09723.09738.0 ?????

??9993.09993.09942.0 ????

?

??9993.09993.09993.0

高斯――赛得尔迭代法：

()()()???

?

??

???+?+=++=++=++++++809178179

1)

1(2)1(1)1(3)

(3)1(1)1(2)

(3)(2)1(1k k k k k k k k k x x x x x x x x x 迭代结果为：

k 0

1

2

3

4

x (i )

????? ??000 ????? ??9753.09722.07778.0 ?????

??9993.09993.09942.0 ?????

??0000.10000.19998.0 ????

?

??000.1000.1000.1

如果矩阵A 严格对角占优，那么高斯――赛得尔迭代法的收敛速度快于雅克比迭代法的收敛速度。 以上定理2、3只是雅克比迭代法和高斯――赛得尔迭代法收敛的充分条件，对于一个给定的系数矩阵A ，两种方法可能都收敛，也可能都不收敛；还可能是雅克比方法收敛而高斯――赛得尔方法不收敛；亦或相反。在计算机上，高斯――赛得尔方法只需要一套存放迭

代向量的单元，而雅克比方法都需两套。 §3 迭代法的误差估计 在§1中曾以检验

ε<-+≤≤)()1(1max k i k i n

i x x

是否成立的办法来估计误差并确定迭代是否终止。它的理论依据是： 定理4：设X *是方程组AX = b 的同解方程X = BX + F 的准确解，若迭代公式

F BX X k k +=+)()1(中迭代矩阵B 的某种范数1<=q B ，则有

1）)1()(*)

(1---≤

-k k k X X q

q

X X

2）)0()1(*

)

(1X X q

q X

X

K k --≤- 证明：先证1）因为 F BX X k k +=+)()1( （4.9）

F BX X k k +=-)1()(

（4.10）

由（4.9）、（4.10）相减得

)1()()()1(-+-≤-k k k k X X q X X

（4.11）

因为F BX X +=*

*

，故

*)(*)1(X X q X X k k -≤-+

另一方面，

()()

*

)(*)(*)(*)1(*)(*

)1(*)()()1()1(X X q X X q X X X X X X X X X X X X k k k k k k k k k --=---≥---≥---=-+++ 再由（4.11）便得:

)1()(*)(1---≤

-k k k X X q

q

X X （4.12）

反复运用（4.11）可得

)0()1(1)1()(X X q X X k k k -≤---

（4.13）

将（4.13）代入（4.12）即有

)0()1(*

)

(1X X q

q X

X

k

k --≤-

第四章 习题

1.什么是求解线性方程组的直接法和迭代法？这两种方法的特点是什么？如果解一 个实际问题，你根据什么决定用直接法还是迭代法？

2．设方程组Ax = b 对应的迭代格式为

???????=-+=--+=-+=+++)

,1,0()2(5.0)3(5.0)4(5.0)(2)(3)1(3)(3)(1)(2)1(2)(2)(1)1(1 k x x x x x x x x x x k k k k k k k k k k ωωω 讨论此迭代格式当参数取何值时收敛，取何值时发散。

3. 已知线性方程组的系数阵A 为

（1）??????????---=321011101A ， （2） ????????

?

?????????=121212112121211A 证明关于矩阵(1)雅可比迭代法收敛，高斯-塞德尔迭代法不收敛；关于矩阵（2）高斯-塞德尔迭代法收敛，雅可比迭代法不收敛。

4. 对方程组

032

13232121≠?????=+=++=+k kx x x kx x x kx

1写出相应的雅可比和高斯-塞德尔迭代格式； 2关于参数k ，讨论1?中的两种格式的敛散性。

5. 设有方程组

???=--=-549710321

21x x x x (1). 问用Jacobi 迭代法和Gauss-Seidel 迭代法求解此方程组是否收敛？

(2). 若把上述方程组交换次序得到新的方程组，再用Jacobi 迭代法和Gauss-Seidel 迭代法求解此方程组是否收敛？

(3).用一个收敛的格式求解此方程组。

6．对方程组Ax = b

????????

??????????-=??????????????????????????????????????--------------626050410100141010014001100410010141001014654321x x x x x x 其精确解为x * = (1, 2, 1, 2, 1, 2)T 。写出解Ax = b 的雅可比、高斯-塞备尔迭代格式，并讨论其敛散性。

7. 设给定方程组Ax=b 的雅可比迭代阵B J = D -1(L + U )为

????

??????-----=022101220J B 试证明解Ax = b 的雅可方法收敛，但相应的高斯-塞德尔方法发散。

8．设方程组Ax = b 中系数矩阵A 为

????

??????=111a a a a a a A 证当121<<-

a 成立时，A 为对称正定的，但解Ax =

b 的雅可比方法只对2

121<<-a 是收敛的。

9.为求解方程组 ?????=+-=--=+-8979783

132121x x x x x x x 试写出收敛的的迭代公式，并说明收敛的原因。解此方程组。????

? ??=000)0(x

410-=ε

10. 设方程组

?????=++-=+--=++2024310321225321

321321x x x x x x x x x

试构造一个收敛的迭代格式，并求解此方程。

310-∞≤ε，T x )0,0,0()0(=

11．用SOR 方法解方组组

?????-=+-=-+-=-34441432

32121x x x x x x x 松弛因子分别取为 = 1.03和 = 1.1，精确解为T

x ??? ??-=21,1,2

1*。要求当 6)

(*105.0-∞?<-k x x 时迭代终止，并且对每一个值确定出迭代次数。

12．分析方程组 ?

??=+=+00.20000.4000.497.34990.6000.72121x x x x 的状态，并对近似解x (1) = (1.667, 3.333)T 进行迭代改善，计算到x (3)（此方程组精确解x *=(2,3)T ）。

13. 已知线性方程组：

?

??=+=+97.198.099.099.199.02121x x x x 试求出系数矩阵A 的条件数 Cond(A)

(1) 若右端向量有扰动T b )00106.0,00097.0( -=δ，试估计解的相对误差。

14. 设X *是方程组AX = b 的同解方程X = BX + F 的准确解，若迭代公式F BX X k k +=+)()1(中迭代矩阵B 的某种范数1

)0()1(*)(1X X B B X X k

k --≤-

15.设 A 、B 为 n 阶非奇异实矩阵，求证

)()()(B Cond A Cond AB Cond ?≤

16. 设A 是n n ? 阶矩阵，求证

A

A 11≥- 17.设A 是n n ? 阶矩阵，求证

)()(A Cond kA Cond = k 是常数

18.设A 非奇矩阵，方程组B AX = 系数矩阵有扰动 实数）,1(-≠=ααδA A ，试证解的相对误差

ααδ+=1X X 第四章 上机实习题

一、编制通用子程序：

（1）雅可比迭代格式；

（2）高斯-塞德尔迭代格式；

（3）SOR 方法格式；

（4）变带宽平方根法解大型稀疏方程组格式。

二、对习题15中的方程组Ax = b ，取初值x (0) = (1,1, 1, 1, 1, 1)T ，要求52)()1(10-+≤-k k x x

（1）用雅可比方法计算

（2）用高斯-塞德尔方法计算； （3）用SOR 迭代法计算( = 1.334, 1.95, 0.95) 最后输出近似解及迭代次数 k 。