q || x ( k ) x ( k 1) || 1 q
3）|| x * x ( k )
q
实际计算中,通常利用 x ( k ) x ( k 1) 作为控制迭代的终止条件.不过要注意,
(k ) ( k 1) * (k ) 当 q 1 时, 1 q较大,尽管 x x 已非常小,但误差向量的模 x x
x M 1 Nx M 1b
我们可以构造序列
x ( k 1) B x ( k ) g
若 x ( k ) x * x* B x * g Ax* b 同时： x ( k 1) x* Bx( k ) Bx* B( x ( k ) x*)
(k )

a 22
(a 21 x1
(k )
a 23 x3
(k )
a1n x n
(k )
b2 )
(k )
1 (k ) (k ) (a n1 x1 a n n 1 x n 1 bn ) a nn
• 数值分析
迭代矩阵
x( k 1) (1 ) x( k ) ( D1Lx( k 1) D1Ux( k ) D1b) x( k 1) ( I D1L) x( k 1) ((1 ) I D1U ) x( k ) D1b ( I D1L)1 ((1 ) I D1U ) x( k ) ( I D1L)1 D1b
• 数值分析
定义 称 R( B) ln ( B) 为迭代法的收敛速度. 定理(迭代法收敛的充分条件) 如果方程组 Ax b 的迭代公式为 x ( k 1) Bx ( k ) f ，且迭代矩阵的某一 种范数 || B || q 1 ，则 x (k ) x * 1）迭代法收敛，即对任取 x ( 0) ，有 lim k 2） || x * x ( k ) ||
• 数值分析
写成分量形式，有
( k 1) x1 x 2 ( k 1) ( k 1) xn
(1 ) x1
(k )
1 (k ) (k ) (a12 x 2 a1n x n b1 ) a11
(1 ) x 2 (1 ) x n
际上可采用试算的方法来确定较好的
松弛因子. 经验上可取1.4<<1.6.
• 数值分析
4.4 迭代法的收敛性
(k ) 定义 设有矩阵序列 A( k ) (aij )nn (k 1,2,) 及 A (aij ) nn ，如果
(k ) lim aij aij k
(i, j 1,2,, n)
对Gauss－Seidel迭代格式 引入松弛因子
x( k 1) D1 ( Lx( k 1) Ux( k ) b)
x( k 1) x( k ) ( D1Lx( k 1) D1Ux( k ) D1b x( k ) )
整理得

x( k 1) (1 ) x( k ) ( D1Lx( k 1) D1Ux( k ) D1b)
• 数值分析 4.1 Jacobi迭代法
a11 x1 a1n xn b1 a x a x b nn n n n1 1
x1 x2 xn 1 (b1 a12 x2 a1n xn ) a11 1 (b2 a21 x1 a23 x3 a1n xn ) a22 1 (bn an1 x1 an , n 1 xn 1 ) ann
• 数值分析
( k 1) x1 x2 ( k 1) ( k 1) xn 1 (k ) (k ) (b1 a12 x2 a1n xn ) a11 1 (k ) (k ) (k ) (b2 a21 x1 a23 x3 a1n xn ) a22 1 (k ) (k ) (bn an1 x1 an , n 1 xn 1 ) ann
BG ( D L) 1U , g ( D L) 1 b
• 数值分析
Jacobi iteration 计算x(k+1)时需要x(k)的 所有分量，因此需开 两组存储单元分别存 放x(k)和x(k+1) Gauss-Seidel iteration 计算xi(k+1)时只需要x(k) 的i+1~n个分量，因 此x(k+1)的前i个分量可 存贮在x(k)的前i个分 量所占的存储单元， 无需开两组存储单元.
qk || || x (1) x ( 0) || 1 q
可能很大,迭代法收敛将是缓慢的.
• 数值分析
特别的,Jacobi 迭代法收敛 (BJ ) 1 G-S迭代法收敛 ( BGS ) 1 SOR迭代法收敛 (BSOR ) 1
• 数值分析
定理 证 而 det(B) =det[(D-L)-1 ((1-)D+U)] =det[(E-D-1L)-1 ]det[(1-)E+D-1U)] =(1-)n 于是 若SOR方法收敛, 则0<<2. 设SOR方法收敛, 则(B)<1,所以 |det(B)| =|12… n|<1
则称 { A ( k ) } 收敛于 A ，记为 lim Ak A k
• 数值分析
一些关于收敛的定义及定理
A ( k ) A || A ( k ) A || 0 ( k ) 定理 lim k
定理 设 B R nn ，则 lim B k 0 ( B) 1 k 其中 ( B) 为 B 的谱半径。 定理(迭代法基本定理）设有方程组 Ax b 对于任意初始向量 x ( 0 ) 及任意 f ，解此方程组的迭 代法 x ( k 1) BX ( k ) f 收敛的充要条件是 ( B) 1
i 1 n 1 (k ) (k ) (bi aij x j aij x j ) aii j 1 j i 1
格式很简单：
xi
( k 1)
• 数值分析 4.2 Gauss－Seidel 迭代法
在Jacobi迭代中，使用最新计算出的分量值,即
( k 1) x1 x 2 ( k 1) ( k 1) xn 1 (k ) (k ) (a12 x 2 a1n x n b1 ) a11 1 ( k 1) (k ) (k ) (a 21 x1 a 23 x3 a1n x n b2 ) a 22 1 ( k 1) ( k 1) (a n1 x1 a n n 1 x n 1 bn ) a nn
B k 1 ( x (0) x*)
k数值分析
定义 （收敛矩阵）
Bk 0
称B为收敛矩阵.
定理：Bk 0 (B) 1
即：矩阵B为收敛矩阵当且仅当B的谱半径<1
由 (B)
B
知，若有某种范数
B 1
则迭代收敛.
|1-|<1,
或
0<<2
• 数值分析
定理 设A是对称正定矩阵, 0<<2时,则解方程组 Ax=b的SOR方法收敛.
• 数值分析
注意的问题
（1）Jacobi迭代法和Gauss-Seidel迭代法的 迭代矩阵不同： BJ =D-1(L+U), B G-S = (D-L) -1U （2）Jacobi迭代法和Gauss-Seidel迭代法 的收敛性没有必然的联系： 即当Gauss-Seidel法收敛时，Jacobi法可能不收 敛； 而Jacobi法收敛时， Gauss-Seidel法也可能不收 敛。
有大量的0元素。对于这类大型稀疏矩阵，在用直接
法时就会耗费大量的时间和存储单元。因此，我们有 必要引入一类新的方法：迭代法.
• 数值分析
对方程组 Ax b 做等价变换 x Bx g 如：令A M N ，则 Ax b ( M N ) x b Mx b Nx
xi
( k 1)
n 1 i 1 ( k 1) (k ) ( aij x j aij x j bi ) aii j 1 j i 1
• 数值分析 迭代矩阵
记
A D L U
A=
D
-U
0 a11 D 0 ann
0 0 a21 0 L 0 a a 0 nn 1 n1
BJ D1 (L U ) I D1 A , g D1b
• 数值分析
迭代矩阵
x( k 1) D1 ( Lx( k 1) Ux( k ) b) ( I D1L) x( k 1) D1Ux( k ) D1b x( k 1) ( I D1L)1 D1Ux( k ) ( I D1L)1 D1b x( k 1) ( D L)1Ux( k ) ( D L)1 b
k 0,1,
计算结果:
x (1) (0.7778, 0.9722, 0.9753) ' x (2) (0.9942, 0.9993, 0.9994) ' x (3) (0.9999, 0.9999, 0.9999) ' x (4) (1.0000,1.0000,1.0000) '
• 数值分析
4.3 逐次超松弛迭代法(SOR)
记 则
x ( k ) x ( k 1) x ( k ) x ( k 1) x ( k ) x ( k )
可以看作在前一步上加一个修正量。若在修正量前乘以一个因子

，有
x( k 1) x( k ) x ( k )
x( k 1) x( k ) ( x( k 1) x( k ) )