6.2.3迭代法的收敛性

数值分析(计算方法)

三、迭代法的收敛性设解线性方程组的迭代格式

x( k 1) Bx( k ) f而方程组的精确解为 x*, 则 x* Bx * f

将两式相减,得x( k 1)

x* Bx

(k )

(k ) B ( x x*) Bx *

令 ( k ) x( k ) x *

k 0 ,1,2 ,

数值分析(计算方法)

则

( k 1) B ( k ) B 2 ( k 1) B k 1 ( 0 )(0)

注意

x

(0)

x * 为非零常数向量

因此迭代法收敛的充要条件lim ( k 1 ) lim( x( k 1 ) x *) 0k k

可转变为

lim Bk

k 1

0

定理1.迭代格式收敛的充要条件为lim B 0k k

数值分析(计算方法)

§4 Convergence of Iterative methods

(0) 定理 设 x Bx f 存在唯一解，则从任意 x 出发， ( k 1) (k ) Bx f 收敛 B k 0 迭代 x || B k x || m 0 || Bk || 0 证明： Bk 0 ax x 0 || x || But hey, you don’t x || B x || 0 对任意非零向量 seriously expect me to compute Bk 成立 whenever I want to check k B x convergence, 0 对任意非零向量 the do you? x 成立k

(0) T (0) ( 0 ) ( i ) e x x)*,则 从任意 x 出发， 记 x (0...1 ... 0 ““ ” ” :取 ：对任意非零向量 k (k ) (k ) k ( 0) B x || k b ||0 e B e 则 0 x as k ||i B ij 有 第 位 || 0

(k ) { x } 收敛

|| x ||

数值分析(计算方法)

根据矩阵与其Jordan标准形及特征值的关系,可知lim B k 0k

B的所有特征值的绝对值 小于1

即

( B) 1

因此

定理.

迭代格式收敛的充要条件为

( B) 1又因为矩阵的谱半径不超过其任一种算子范数,即

( B) B

于是又可得到

数值分析(计算方法)

§4 Convergence of Iterative methods

定理 (充分条件)若存在一个矩阵范数使得 || B || = q < 1,则迭代收敛，且有下列误差估计： (k ) ( k ) ( k 1 ) q || x x || ① || x * x || 1 q

(k ) (1) ( 0 ) qk ② || x * x || || x x || 1 q

证明： ① x * x ( k ) B( x * x ( k 1) ) B( x * x ( k ) x ( k ) x ( k 1) )

|| x * x ( k ) || q(|| x * x ( k ) || || x ( k ) x ( k 1) ||)

( k ) ( k 1) ( k 1) ( k 2) ( 0) k 1 (1) B( x x ) ... B ( x x ) ② x x

( k ) ( k 1) ( 1) ( 0 ) k 1 || x x || q || x x ||

数值分析(计算方法)

在计算时,迭代终止的时间可以用上式判别例. 判别下列方程组用J法和G-S法求解是否收敛 1 1 2 2 1 2 2 x1 1 1 x2 1 x 1 1 3

解:

(1) 求Jacobi法的迭代矩阵0 1 0 0 0 1 0 2 1 2 0 2 2

1 0 2 0 2 2 1 0

1 1 BJ D ( L U ) 0 0

0 1 2

数值分析(计算方法)

显然BJ的几种常用算子范数BJ 1, det det( I BJ ) 1 2

因此不能用范数只能用特征值判断

2 2

2 1 3 0

所以

|) 0 1 0 ( BJ ) max(|

即Jaobi迭代法收敛(2) 求Gauss-Seidel法的迭代矩阵 1 BG ( D L) 1U 1 2 0 1 2 0 0 1 1

0 0 0

2 0 0

2 1 0

数值分析(计算方法)

0 BG 0 0

2 2 0

2 3 2

同样用特征值判断

0

2

( BG ) max(| |) 2 1

所以Gauss-Seidel迭代法发散在前面的例子中,G-S法收敛速度比J法要高 但本例却说明G-S法发散时而J法却收敛 因此,不能说G-S法比J法更好

数值分析(计算方法)

另外,给出系数矩阵对角占优线性方程组的一个结论定理.若线性方程组 Ax b的系数矩阵A为严格对角占优 矩阵, 则Jacobi 法和G S法均收敛

证: 因为系数矩阵 A严格对角占优 , 所以|aii | |aij | i 1,2 ,3, , nj i

1 |aij | 1 i 1,2 ,3, , n |aii | j i

(1)对于Jacobi迭代法,其迭代矩阵为 BJ D 1 ( L U )

数值分析(计算方法)

0 a21 BJ a22 a n1 a nn

a12 a11 0 an 2 ann

a1 n a11 a2 n a22 0

1 |aij | 1 BJ max i |a | ii j i

Jacobi迭代法收敛 (2)对于G—S迭代法,其迭代矩阵为 BG ( D L) 1U由于BG的形式不易确定 , 不能使用范数,而用特征值

数值分析(计算方法)

BG的特征值 满足 det( I BG ) 0

即

det[ I ( D L) 1U ] 0

从而 det(D L) 1 det[ ( D L) U ] 0因此 由于det[ ( D L) U ] 0

|aii | |aij |j ii 1 n

可得

| | |aii | | | |aij | | | |aij |j 1 j i 1

| | |aij | j 1

i 1

j i 1

|a | (| | 1) |a |ij j i 1 ij

n

n

数值分析(计算方法)

如果| | 1, 则有

| | |aii | | | |aij | j 1

i 1

j i 1

|a |ij

n

则[ ( D L) U ]为严格对角占优矩阵 从而det[ ( D L) U ] 0所以| | 1, 即 ( BG ) 1,

矛盾

G—S迭代法收敛