数值分析讲义
第三章线性方程组的解法
§3.0 引言
§3.1 雅可比(Jacobi)迭代法
§3.2 高斯-塞德尔(Gauss-Seidel)迭代法
§3.3 超松驰迭代法§3.7 三角分解法
§3.4 迭代法的收敛性§3.8 追赶法
§3.5 高斯消去法§3.9 其它应用
§3.6 高斯主元素消去法§3.10 误差分析
§3 作业讲评3 §3.11 总结
§3.0 引言
重要性：解线性代数方程组的有效方法在计算数学和科学计算中具有特殊的地位和作用.如弹性力学、电路分析、热传导和振动、以及社会科学及定量分析商业经济中的各种问题.
分类：线性方程组的解法可分为直接法和迭代法两种方法.
(a) 直接法：对于给定的方程组，在没有舍入误差的假设下，能在预定的运算次数内求得精确解.最基本的直接法是Gauss消去法，重要的直接法全都受到Gauss消去法的启发.计算代价高.
(b) 迭代法：基于一定的递推格式，产生逼近方程组精确解的近似序列.收敛性是其为迭代法的前提，此外，存在收敛速度与误差估计问题.简单实用,诱人.
§3.1 雅可比Jacobi 迭代法 (AX =b )
1
基本思想:
与解f (x )=0 的不动点迭代相类似,将AX =b 改写为X =BX +f 的形式,建立雅可比方法的迭代格式：X k +1=BX (k )+f ,其中，B 称为迭代矩阵.其计算精度可控,特别适用于求解系数为大型稀疏矩阵(sparse matrices)的方程组. 2
问题:
(a) 如何建立迭代格式？
(b) 向量序列{X k }是否收敛以及收敛条件? 3 例题分析:
考虑解方程组⎪⎩⎪
⎨⎧=+--=-+-=--2.453.82102
.72103
21321321x x x x x x x x x (1)
其准确解为X *={1, 1.2, 1.3}. 建立与式(1)相等价的形式：
⎪⎩⎪
⎨⎧++=++=++=84.02.01.083.02.01.072
.02.01.02
13312321x x x x x x x x x (2) 据此建立迭代公式：
⎪⎩⎪⎨⎧++=++=++=+++84
.02.01.083.02.01.072.02.01.0)(2)(1)1(3
)(3
)(1)1(23)(2)1(1k k k k k k k
k k x x x x x x x x x (3) 取迭代初值0)
0(3
)0(2)0(1===x x x ,迭代结果如下表. JocabiMethodP31.cpp
迭代次数 x1 x2 x3
0 0 0 0
1 0.7
2 0.8
3 0.84
2 0.971 1.07 1.15
3 1.057 1.1571 1.2482
4 1.0853
5 1.18534 1.28282
5 1.095098 1.195099 1.294138
6 1.098338 1.19833
7 1.298039
7 1.099442 1.199442 1.299335
8 1.099811 1.199811 1.299777
9 1.099936 1.199936 1.299924
10 1.099979 1.199979 1.299975
11 1.099993 1.199993 1.299991
12 1.099998 1.199998 1.299997
13 1.099999 1.199999 1.299999
14 1.1 1.2 1.3
15 1.1 1.2 1.3
4Jocobi迭代公式:
设方程组AX=b, 通过分离变量的过程建立
Jocobi迭代公式，即
)
,,2,1()(1
)
,,2,1(0,11
n i x a b a x n i a b x a n i
j j j ij i ii
i ii n
i i j ij =∑-==≠∑=≠== 由此我们可以得到Jacobi 迭代公式：
),,2,1()(1
1)
1(n i x a b a x
n i
j j k i ij i ii
k i
=∑-=≠=+
[Jacobi 迭代公式的算法] 1: 初始化. n , (a ij ), (b j ), (x 1) , M . 2: 执行k =1直到M 为止. ① 执行i =1直到n 为止.
ii n
i
j j j ij i i a x a b u /)(1∑-←≠= ;
② 执行i =1直到n 为止.
i i u x ← ;
③
输出k , (x i ).
另外，我们也可以建立Jacobi 迭代公式的矩阵形式. 设方程组AX =b ,
其中，A =(a ij )n 为非奇异阵，
X =(x 1,x 2,…,x n )T , b =(b 1,b 2,…,b n )T
将系数阵A 分解为: A =U +D +L ,
U 为上三角矩阵，D 为对角矩阵，L 为下三角矩阵.
于是AX =b 可改写为 (U +D +L )X =b
⇔ X =D -1b -D -1(U +L )X
由此可得矩阵形式的Jocobi 迭代公式： X k +1=BX (k )+f □
§3.2 高斯-塞德尔Gauss-Seidel 迭代法
注意到利用Jocobi 迭代公式计算)
1(+k i
x 时，已经计算好
)(1)(2)(1,,,k i k k x x x - 的值，而Jocobi 迭代公式并不利用这些最新的近似值计
算，仍用)
(1)(2)
(1
,,,k i k k x x x - .这启发我们可以对其加以改进,即在每个分量的
计算中尽量利用最新的迭代值，得到
),,2,1()(1111)1()
1(n i x a x a b a x
n i j k j
ij i j k j ij i ii
k i
=∑-∑-=+=-=++
上式称为Gauss-Seidel 迭代法. 其矩阵形式是
X =-(D +L )-1UX +(D +L )-1b , X k +1=BX (k )+f .
迭代次数 x1 x2 x3 0 0 0 0 1 0.72 0.902 1.1644 2 1.04308 1.167188 1.282054 3 1.09313 1.195724 1.297771
