从而 ||x(k+1) -x(k)|| =||(x(k+1) -x*)-(x(k) -x*)|| ||x(k) -x*||-||x(k+1) -x*|| ||x(k) -x*||-q||x(k) -x*||
=(1-q) ||x(k) -x*||
数学学院 信息与计算科学系
故得
1 q ( k 1) (k ) x x x x x ( k ) x ( k 1) 1 q 1 q k q q x ( k ) x x ( k ) x ( k 1) x (1) x(0) 1 q 1 q


数学学院 信息与计算科学系
二、迭代法的收敛性
定义2 如果
lim A
k
k
(k )
A O
则称矩阵序列｛A(k)｝依范数收敛于A，记
lim A( k ) A
由范数的等价性可以推出，矩阵序列｛A(k)｝ 依某种范数收敛，则依任何一种范数它都收敛，故 下面不强调是在那种范数意义下收敛。
x
k 1
Bx( k ) f
k 0,1,2
其中B称为迭代矩阵。
数学学院 信息与计算科学系
若序列｛x(k)｝收敛，即
lim x ( k ) x
k
显然有
x Bx f
此极限 x＊就是方程组 Ax=b 的解。 定义1 如果序列｛x(k)｝的极限存在(记 x＊)， 则称迭代法收敛，x＊就是方程组 Ax=b 的解，否则 称此迭代法发散。
数学学院 信息与计算科学系
x(k+1) -x*= B( x(k) -x* ) , x(k+1) –x(k)= B( x(k) –x(k-1) )
即有
x ( k 1) x B x ( k ) x q x ( k ) x
x ( k 1) x ( k ) B x ( k ) x ( k 1) q x ( k ) x ( k 1)
j 1 j 1 k j
n
可以看出，当(B)<1愈小时， jk 0(k ) 愈 快，即 e ( k ) 0 愈快，故可用(B)来刻画迭代法收 敛速度的快慢。
数学学院 信息与计算科学系
现在来确定迭代次数k，使
s ( B ) 10 k
取对数得 定义3 称
(k )
有了误差估计式，在实际计算时，对于预先给 定的精度 ，若有
x ( k 1) x ( k )
则就可以认为x(k+1)是方程组满足精度的近似解. 此 外，还可以用第二个式子来事先确定需要迭代的次 数以保证 ||e(k)||<。
Ax b 为方程组Ax=b 的解，即
k
lim x k x
数学学院 信息与计算科学系
把矩阵A 分解成矩阵N 和P 之差，即 A=N-P 其中N为非奇异矩阵，于是，方程组 Ax=b 便可以表 示成 Nx=Px+b 即有 1 1 x N Px N b Bx f 1 1 其中 B N P; f N b 据此，我们便可以建立迭代公式
q x x ( k ) x ( k 1) 1 q

x(k+1) = Bx(k) + f 收敛，且有误差估计式
x( k )
k q x x (1) x (0) 1 q
证 因 (B)||B||=q<1, 所以迭代格式收敛, 且有 设 lim x (k) =x*，由 x(k+1) = Bx(k) + f ， 得 x* = Bx* + f ，则
数学学院 信息与计算科学系
三、迭代法的收敛速度
考察误差向量 e(k) =x(k) -x＊=Bk ·e(0) 设B有n个线性无关的特征向量及相应2 ,, n
k n
由 得
e (0) a j j
e
(k )
B e
j 1 k (0)
aj B j aj j
数学学院 信息与计算科学系
2） 由1)知，迭代格式收敛 lim Bk=O ， 即lim||Bk||=0 ，从而存在 k ，使 || B k || <1，由谱半 径的性质有 故得 [( B )]k = (B k ) ||B k ||<1， ( B )<1，
因(B)=inf{||B||}且(B)<1，存在 >0及使 || B || ( B )+ <1， 又 || Bk|| ||B||k ，有 lim||Bk||=0 ， 故 lim B k =0，由1）知，迭代格式收敛。
数学学院 信息与计算科学系
定理1
1） 迭代格式 x(k+1) = Bx(k) + f 收敛 lim Bk=O； 2） 迭代格式 x(k+1) = Bx(k) + f 收敛 ( B )<1。 1） 设 lim x(k) =x*， 则 x* = Bx* + f ,
证
x(k+1) -x*= B( x(k) -x*)， x(k) -x*= Bk( x(0) -x*) ， 故 lim x (k) =x* lim Bk=O；
s ln10 k ln ( B )
R( B) ln ( B)
为迭代法 x(k+1) = Bx(k) + f 的收敛速度。 由此看出，当(B)<1愈小，速度R(B)就愈大， 所需要的迭代次数也就愈少。
数学学院 信息与计算科学系
定理 2
x
(k )
若 ||B||=q<1，则对任意x(0) 迭代格式
数学学院 信息与计算科学系 第七节 迭代法及其收敛性
一、迭代法的一般格式
前面介绍了解线性方程组 Ax=b 的一些直接方法， 下面介绍解方程组的另一类方法—迭代法。 所谓迭代法就是对任意给定初始近似 x 0 , 按某种 规则逐次生成序列 x 0 , x 1 , x 2 x k , 使极限