误差向量
ε(k)=x(k)-x*=Bkε(0), ε(0)=x(0)-x*.
由设ρ(B)<1，应用定理3，有
lim Bk
k
0,于是对于任意x(0) 有lkim k
0,
即lim xk x*.
k
必要性. 设对任意x(0) 有 lim xk x*, k
其中x(k+1)=Bx(k)+f.显然，极限x*是线性方程组（1.7）的解，且对
2x3(k )
20) /
x(k 1) 2
(4 x1( k )
x3(k )
33)
8 /11
的收敛性。
x(k 1) 3
(6 x1( k )
3x2(k )
36)
/12
解 先求迭代矩阵B0的特征值。由特征方程
3 1
84
det(I
- B0)
4 11
1 0 11
11
24
可得
可得 det(I - B0 ) 3 0.034090909 0.039772727 0，
误差向量 (k) x (k) x* B k (x(0) x*) B k (0)
得 || (k) |||| B k |||| (0) ||, || (0) || 0于是
|| (k) || || B k || || (0) ||
所以 || B k || 是迭代k次后误差向量 (k)的范数与初始误差
4
11
1
x2
33
.
6 3 12 x3 36
精确解x*=(3,2,1)T. 改写(1.2)为
x1
x2
1 8
(3x2
2 x3
20),
1 11
( 4
x1
x3
33),
x3
1 12
(6 x1
3x2
36).
或写为x=B0x+f,即
x1
x2
x3
0
4 11
6 12
3 8
0
3 12
2 8
迭代法的基本定理是在理论上是重要的，由于ρ(B)<‖B‖，下面 利用矩阵B的范数建立判别迭代法收敛的充分条件 定理6（迭代法收敛的充分条件） 设有线性方程组
x=Bx+f, B∈Rn×n, 及一阶定常迭代法
x(k+1)=Bx(k)+f. 如果有B的某种算子范数‖B‖=q<1,则
（1）迭代法收敛，即对任意x(0)，
1
11
0
x1 x2 x3
20
8 33 11
36
12
.
(1.3)
任取初值,如x(0)=(0,0,0)T,代入(1.3)得到x(1)= (2.5,3,3)T. 反复迭代
x1(k 1) (3x2(k ) 2x3(k ) x2(k 1) (4x1(k ) x3(k
20) / ) 33)
越小, ln (B)越大，迭代法收敛越快。
（1.12）可用
k ln s ln 10
R(B) R(B)
作为迭代法（1.11）式所需的迭代次数的估计。
• 例如在例1中迭代矩阵B的谱半(B) 0.3592。
若要求
|| (k) || (0)
下面给出迭代法收敛的一个充分必要条件。
定理5 设有方程组
x Bx f 及一阶定常迭代法
(1.7)
x(k1) Bx(k ) f
(1.8)
则对任意初始向量x(0)迭代法(1.8)收敛 (B) 1.
证明 充分性.设ρ(B)<1，易知Ax=f（其中A=I-B）有唯一解，记
为x*,则
x*=Bx*+f,
定
理
1
lim
k
A
k
A lim k
Ak
A
0，其中 || || 为矩阵
的任一算子范数 .
定理2
lim
k
Ak
0
x
Байду номын сангаас
Rn
,
lim
k
Ak
x
0.
证明：对任一种矩阵从属范数有
|| Ak x |||| Ak |||| x || .
若 lim k
Ak
0,则 lim || k
Ak
||
0，故对一切x Rn ,
近似解的方法称为迭代法(一阶定常迭代法).
(2)若 lim x(k)存在(记为x*)，则称此迭代法收敛,显然x *
k
是解,否则迭代法发散.
由以上讨论，需研究 {x(k)}的收敛性 .
引进误差向量ε(k) x(k) x*,则由(1.6) (1.5)得 ε(k1) Bε(k) Bk ε(0).
另一方面对任意ε>0,记
Bε= [ρ(B)+ε]-1B,
显然由ρ(Bε)<1.由定理3有
lim
k
Bk
0,
所以存在正整数N=N(ε),使
K>N时，
Bk
|| Bk || (B) k 1,
即k>N时有
1
(B) || Bk || k (B)
由ε任意性即得定理结论
迭代法及其收敛性 设有方程组Ax b,其中A为非奇异矩阵，下面建立它
两边取对数得
ln
||
Bk
1
|| k
1
ln
k
即
k
ln 1
s ln 10
1
ln || B k || k ln || B k || k
(1.12)
1
它表明迭代次数k与 ln || B k || k 成反比。
1
定 义 4 迭代法平均收敛速度定义为Rk (B) ln || Bk ||k .
有
lim
k
||
Ak
x
||
0.所以就有定理的右边成立。
反
之，若定理的右
边成立
，取x为第j个坐标向量e
，
j
则 lim k
Ak e j
0, 表示Ak的第j列元素极限均为零，当
j
1,2,
, n时就证明了lim k
Ak
0，证毕。
下面讨论一种与迭代法x(k1) Bx(k) f有关的矩阵序列 的收敛性，这种序列由矩阵的幂构成，即{Bk }，其中B Rnn. 定 理 3 设矩阵B (bi(jk) ) Rnn , 则下列三个条件等价: (1) lim Bk 0;
向量 (0)的范数之比的最大值。这样迭代k次后，平均每
1
次迭代误差向量范数的压缩率可看成是|| B k ||k ,若有迭
代k次后有
|| (k) || || B k || , || (0) ||
其中 1, 10-s.
1
1
1
因为 (B) 1，故 || B k || k 1，由 || B k || k k
k
x(k) i
xi
(i 1,2, , n)
则称向量序列{x(k)}收敛于x，记为lim x(k) x. k
显然，lim x(k) x lim || x(k) - x || 0,其中|| || 为任意一种向量范数。
k
k
定 义 3 设矩阵序列 Ak (ai(jk ) ) Rnn , A (aij ) Rnn，若
收敛： lim ε(k) 0 lim Bk 0.
k
k
要研究B满足什么条件下Bk 0(k ).
定 义 2 设向量序列{x(k )} Rn，x(k ) (x1(k ) , x2(k ) , , xn(k ) )T Rn ,
若存在x (x1, x2 , , xn )T Rn , 使
lim
序列x ( k )逐步逼近此方程的精确解。
(1.4)
一般地，由Ax b变形得到等价的 x Bx f .
设有唯一解x*,则
x* Bx *f
(1.5)
又设任取初值x (0) , 则可构造迭代序列
x(k 1) Bx(k ) f
(1.6)
定义1 (1)对于方程组x Bx f，用公式(1.6)逐步代入求
的迭代法。 将A分裂为A M N,其中M为可选择的非奇异矩阵，
且使Mx d容易求解，一般选择为A的某种近似，称M为 分裂矩阵。于是Ax b x M 1Nx M 1b,也就是 x Bx f .从而可构造一阶定常迭代法 :
x(k 1) Bx(k ) f 其中B M 1N M 1(M A) I M 1A, f M 1b. 称B I M 1A为迭代法的迭代矩阵，选取M阵，就得到解 Ax b的各种迭代法。
零元素多，适合用迭代法。
我们将介绍迭代法的一般理论及雅可比迭代法、高 斯—塞德尔迭代法、超松弛迭代法，研究它们的收 敛性。
例1 求解线性方程组
8 x1 4 x1
3x2 2 11x2
x3 x3
20, 33,
6x1 3x2 12x3 36.
(1.2)
记为Ax=b,即
8 3 2 x1 20
例5
迭代法x ( k 1)
Bx(k )
f
, 其中B
0.9 0.3
00.8，f
12,显然 B 1.1，
B 1.2，B 1.043，B 1.54，，表明B的各种范数均大于1，但
1
2
F
由于（B） 0.9 1,故由此迭代法产生的迭代序列 x(k) 是收敛的。
下面考察迭代法的收敛速度，假定(B) 1，由于
第6章 解线性代数方程组的迭代法
§1 引言
考虑线性方程组
也就是
a11x1 a12x2 a1nxn b1
a21x1 a22x2
a2nxn
b2
an1x1 an2x2 annxn bn