数值分析-线性代数方程组的迭代解法

及矩阵 A Rn，n 有 || Ax ||t || A ||s|| x ||t
都成立，则称矩阵范数 || ||s和向量范数 || ||相t 容.
注意：为了保证矩阵范数和向量范数相容，最常用的矩阵范数
是由相应向量范数导出的.
4.1.3 矩阵范数和矩阵序列的极限
定理4 设 || |是| R中n 的向量范数，对于任何 A Rn，n若
4.1.2 向量范数和向量序列的极限
定义2 (向量范数) 如果在 Rn中定义了实值函数，记为 || ，||
对所有 x, y Rn以及 R，若满足 （1） || x || 0，当且仅当 x 0时， || x || (0非负性) ；
（2） || x ||| | || x |(|齐次性)；
（3） || x y |||| x || || y(|三| 角不等式). 则称 || x ||为向量 x的范数 (或模).
于是有
c1 || x(k) x* || || x(k) x* || c2 || x(k) x* ||
lim ||
k
x(k)
x* || 0
lim ||
k
x(k)
x*
||
0
4.1.2 向量范数和向量序列的极限
例1 计算向量 x (5,1,3)的T 常用范数.
解
|| x || 5
|| x ||1 9
（3）|| A B |||| A || || B；||(三角不等式) （4） || AB |||| A || || B；|| 则称 || A ||为矩阵 A 的范数.
4.1.3 矩阵范数和矩阵序列的极限
相容性： 设有矩阵范数 || ||s和向量范数 || ||，t 如果对任何向量 x Rn

数值分析--第6章解线性方程组的迭代法第6章 解线性方程组的迭代法直接方法比较适用于中小型方程组。

对高阶方程组，即使系数矩阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序复杂等不足。

迭代法则能保持矩阵的稀疏性，具有计算简单，编制程序容易的优点，并在许多情况下收敛较快。

故能有效地解一些高阶方程组。

1 迭代法概述迭代法的基本思想是构造一串收敛到解的序列，即建立一种从已有近似解计算新的近似解的规则。

由不同的计算规则得到不同的迭代法。

迭代法的一般格式(1)()(1)()(,,,),0,1,k k k k m kF k +--==x x x x式中(1)k +x 与()(1)(),,,k k k m --x x x 有关，称为多步迭代法。

若(1)k +x 只与()k x 有关，即(1)()(),0,1,k k kF k +==x x称为单步迭代法。

再设kF 是线性的，即(1)(),0,1,k kk kk +=+=x B x f式中n nk ⨯∈B R ，称为单步线性迭代法。

kB 称为迭代矩阵。

若k B 和kf 与k 无关，即(1)(),0,1,k k k +=+=x Bx f称为单步定常线性迭代法。

本章主要讨论具有这种形式的各种迭代方法。

1.1 向量序列和矩阵序列的极限由于nR 中的向量可与nR 的点建立——对应关系，由点列的收敛概念及向量范数的等价性，可得到向量序列的收敛概念。

定义6.1 设(){}k x 为n R 中的向量序列，nx R ∈，如果()lim 0k k x x →∞-=其中为向量范数，则称序列(){}k x 收敛于x ，记为()lim k k x x →∞=。

定理6.1 nR 中的向量序列(){}k x 收敛于nR 中的向量x 当且仅当()lim (1,2,,)k i i k x x i n →∞==其中()()()()1212(,,,),(,,,)k k k k T Tnnx x x x x x x x ==。

第三章
（一） （二） （四） （五） (六)
线性方程组的迭代解法
主要内容： 主要内容：
迭代法的一般形式 雅可比（Jacobi）迭代法 雅可比（Jacobi） 松弛法 迭代法的收敛条件 小结
高斯-赛德尔(Gsuss Seidel)迭代法 (Gsuss（三） 高斯-赛德尔(Gsuss-Seidel)迭代法
，如此下去， x ( 9 ) = Bx (1) + g = (10.9994 ,11.9994 ,12.9992 ) T 易知，方程组的精确解为
x = (11,12 ,13 ) T
迭代结果（当迭代次数增大时）越来越接近精确解。
例：用Jacobi迭代法求解方程组
8 x1 − 3x2 + 2 x3 = 20 4 x1 + 11x2 − x3 = 33 6 x + 3 x + 12 x = 36 2 3 1
，精确解为 x = ( 3, 2,1)
T
解：按迭代过程
( k +1) 1 x1 = (3 x2 ( k ) − 2 x3( k ) + 20) 8 ( k +1) 1 = (−4 x1( k ) + x3( k ) + 33) x2 11 ( k +1) 1 x3 = (−6 x1( k ) − 3 x2 ( k ) + 36) 12
公式（3-4）表示为
~ ~ x ( k + 1 ) = L x ( k + 1 ) + U x ( k ) + g , ( k = 0 ,1, 2 , L )
b1n 0 0 b12 0 O M ~ b21 0 ~ 其中L = ,U = M M O b M M O n −1n b b L 0 L 0 n1 n 2

a13 L a23 L 0L
O
a1n a2n
a3n M
0
0
a12 a11
a13 L a11
a1n a11
a21 a22
0
a23 L a22
a2 n a22
BJ
a31 a33
a32 a33
0
L
a3n a33
M
M
M
OM
an1 ann
an2 ann
an3 ann
j 1
n
aij x(jk )
j i1
bi )
x ( k 1) 1
1 a11
(a12 x2(k)
a13 x3(k )
a14 x4(k )
a1n xn(k )
b1 )
x ( k 1) 2
1 a22
(a21 x1(k1)
a23 x3(k )
a24 x4(k )
a2n xn(k )
b2 )
x ( k 1) 2
2
得 x(1) = ( 0.5000, 2.8333, -1.0833 )T
M
x(9) = ( 2.0000, 3.0000, -1.0000 )T
举例（续）
SOR 迭代格式
x1( k x2( k
1) 1)
x(k) 1
x(k) 2
1
2 x1(k)
x(k) 2
2
8
x ( k 1) 1
Jacobi 迭代
令 A = D - L- U， 其中 D diag(a11, a22,K , ann),
0
L
a21
M
an1
0 a12 L
0 OO
,