文档介绍：第三章解线性方程组的迭代法
/* Iterative Techniques for Solving Linear Systems */
求解
思路
与解 f (x)=0 的不动点迭代相似……
,将等价
改写为形式,建立迭代。从初值出发,得到序列。
计算精度可控,特别适用于求解系数为大型稀疏矩阵/* sparse matrices */ 的方程组。
研究内容:
如何建立迭代格式? 收敛速度?
向量序列的收敛条件? 误差估计?
1
§ Jacobi 法/* Jacobi Iterative Methods */
先看一个例子:
按下式进行迭代
(k=0,1,2, )
例1:
从以上三个方程中分别解出x1, x2, x3
2
任取一初始向量,例如x(0)=(0,0,0)T,得到迭代序列{x(k)} (k=0,1,2,),列表如下表3-1。
容易验证,原方程组的精确解为 x = (1,2,3) T,从上面的计算可看出,{x(k)}收敛于精确解.
k
0
1
2
3
4
5
6
7
8
x1
0
x2
0
x3
0
3
写成矩阵形式:
A =
L
U
D
B
Jacobi 迭代阵
于是对于Jacobi Iterative Methods,可以描述为:
4
Gauss - Seidel Iterative Method
…………
只存一组向量即可。
写成矩阵形式:
B
Gauss-Seidel
迭代阵
§ Gauss - Seidel 法/* Gauss-Seidel Iterative Methods */
5
例2: 用Gauss-Seidel Iterative Methods解方程组
(k=0,1,2, )
解迭代公式为:
用它计算得到的序列{x(k)}列表如表3-2:
可见它对这一方程组比Jacobi迭代法收敛快一些。
k
0
1
2
3
4
5
6
x1
0
x2
0
x3
0
6
§ 松弛法(SOR迭代法) /* Relaxation Methods */
换个角度看Gauss - Seidel 方法:
其中ri(k+1) =
/* residual */
相当于在的基础上加个余项生成。
下面令,希望通过选取合适的来加速收敛,这就是松弛法/* Relaxation Methods */ ,也称为逐次超松弛法,也称为SOR方法。
ii
k
i
k
i
k
i
a
r
x
x
)
1
(
)
(
)
1
(
+
+
+
=
w
= 1
Gauss - Seidel 法
今后可以看到,必须取0<ω<2,当ω取得适当时,对Gauss-Seidel迭代法有加速效果.
7
写成矩阵形式:
松弛迭代阵
例3 用Gauss-Seidel迭代法和取ω=,当
时退出迭代,初值取x(0)=(1,1,1)T 。
由表3-3和表3-4可见,达到同样的精度Gauss-Seidel迭代法要72步,而取ω=,可见当松弛因子选择适当时,SOR法有明显加速收敛作用。
8
§ 迭代法的收敛性/* Convergence of Iterative methods */
的收敛条件
充分条件: ||B|| < 1
必要条件:
?
定理
设
存在唯一解,则从任意出发,
迭代
收敛
0
k
B
9
对任意非零向量成立
证明:
Bk 0
|| Bk || 0
对任意非零向量成立
从任意出发, 记,则
as k
收敛
,可以得出如下定理
定理
设
存在唯一解,则从任意出