2.4 迭代法
迭代法的一般形式及 其收敛性
谱半径
迭代法收敛的充 要条件
迭代法
Jacobi 迭代法 Gauss-Seidel 迭代法
逐次超松弛迭代法
相关概念 2.4.1 迭代法的一般形式及其收敛性
a.设 nn 矩阵 G 的特征值是 1,2 ,,n ，称
为矩阵 G 的谱半径。
(G)max 1in
i
迭代公式
四、 本章测验题
用 Doolittle 分解法求解下列方程组
x1 x2 3x3 10 4x1 2x2 5x3 20 - x1 4x2 3x3 12
解：对方程的系数矩阵 A 进行 LU 分解：
1 1 3 1 1 3 1 1 3 1 1 3
A
4
2
5
3
2
5
3
-1
-
4
a1 b1
d1
d2 a2 c2
A
cn1
cn
dn an
的线性方程组 Ax=b 称为拟三对角线性方程组。
2.3 矩阵的条件数与病态线性方程组
矩阵的条件数 与线性方程组
的性态
条件数：对非奇异矩阵 A ，称量 A A1 为 矩阵 A 的条件数，记作 cond( A) A A1
常用的条件数： cond( A)
d.定理 2.13 GS 法收敛的充分必要条件是 (GG ) 1。
定理 2.14 如果 GG 1,则 GS 法收敛。 定理 2.15 如果方程组的系数矩阵 A 是主对角线按行（或按列）严格占优阵，则用 GS
法求解必收敛。 2.4.4 逐次超松弛迭代法
c.迭代公式:
x
(k
1)
( 1
DL)
1
11
DU
A
A1
，
cond(A)2
A
A1
2
矩阵的条件数 与病态线性方 程组
关于病态线 性方程组的
求解问题
采用高精度的算术运算 平衡方法 残差校正法
相关概念： 2.3.1 矩阵的条件数与线性方程组的形态
a.定理 2.6 设 A 、 A Rnn ，b、 b Rn ，A 非奇异，b 0 ，x 是方程组 A,x=b
Ly=b， Ux=y
先由 Ly=b 解出向量 y，再由 Ux=y 解出向量 x，这就是原方程组的解向量。
矩阵 A 分解为 LU 的形式称为矩阵 A 的三角分解。
2.Doolittle 分解法：如果上诉分解式中 L 是单位下三角阵，U 是上三角矩阵，则称为矩阵 A
的 Doolittle（杜立特尔）分解。
x
(
k
)
( 1
DL)
1
b
（
k
0,1,）
b.迭代矩阵：
GS
(
1
DL)
1
11
DU
c.分量形式：
x (k 1) i
i 1 j 1
aij aii
x (k 1) j
1 1
xi(
k
)
n aij a ji1 ii
x
(k j
)
bi aii
（
i1,2,,n;k 1,2, ）
d.定理 2.17 SOR 方法收敛的充分必要条件是 (GG ) 1。
过
程
程
（1）如果 akk (k ) 0 ，则算法失效，停止计算；否则转（2）。
（2）对于 i=k=1，k=2，…，n 计算
2、 回代过程
2.1.2 列主元素 Gauss 消去法
1、 消元过程 对于 k=1，2，…，n-1 执行
（1）选行号 ik ，使
（2）交换
a(k
) kj
与
a(k) ik
j
（j=k，k+1，…，n）以及 b(k )k
（3）设 A 是非奇异矩阵的实对称矩阵，则有
cond
(
A)
2
1 n
其中 1 和 n 分别是矩阵 A 的模为最大和模为最小的特征值。
（4）设 A 是正交矩阵，则有 cond( A)2 1 2.3.2 关于病态线性方程组的求解问题
a.可以用下列方法判别线性方程组 Ax=b 是否病态：
（1）当 det A 相对很小或 A 的某些行（或列）近似线性相关是 2，方程组可能病态。
b.迭代矩阵： GJ D 1 LD
c.分量形式：
xi(k
1)
n
aij
j 1
ji
x
(k j
)
bi
aii
（ i1,2,,n;k1,2,）
d. Jacobi 迭代法收敛的充分条件：
（1） GJ 1 （2）如果方程组 Axb 的系数矩阵是主对角线按行（或按列）严格占优阵，则用 Jacobi 迭
代法求解必收敛。 2.4.3Gauss-Seidel 迭代法
（2）用列主元素 Gauss 消去法求解方程组时，若出现小列主元
a(k) ik k
《1，则方程
组可能病态。
（3）分别用 b 和 bb ( b《1)作方程组的右端向量，求解 Axb 和 A~x = bb ，
若 x 和 ~x 相差很大，则 Axb 是病态的。 当 A 的元素的数量级差别很大，且无一定规则时，方程组可能病态。
3
-1 - 4
-1 - 4 3 -1 - 4 3 -1 3 3 -1 3 8
L
3
-1 3
1 1 3
U
-1 - 4
8
由 Ly=b， Ux=y
10 得： y -10
52
x -89321 3 13 3
第 2 章 线性方程组的解法 --------学习小结
姓名 赵越 班级 机械 1504 学号 S20150171 一、 本章学习体会
通过两周的时间，我们进行了第 2 章—线性方程组的解法的学习。通过对这一章 的学习，我了解到了两种求解线性方程组的方法：直接方法和迭代法。掌握了这两种算 法的分类和各种类别计算方法的思路和算法。并且通过对这些算法的相互比较，得出了 其各自的优点和缺点，认识到了要根据具体的线性方程组的特点来选择合适的解法，这样 我们才能快速准确的得到方程组的解。然后还尝试去编译这些算法的 matlab 程序，学会 通过电脑编程来进行线性方程组的求解。
二、 本章知识梳理 2.1Gauss 消去法
Gauss 消去法是由消元和回代这两个过程组成的。
2主元素 Gauss 消去法
消
回
元
代
过
过
程
程
相关概念： 2.1.1 顺序 Gauss 消去法
1、 消元过程
对于 k=1,2，…，n-1 执行
消
回
元
代
过
3.Crout 分解法：如果 L 是下三角矩阵，U 是单位上三角阵，则称为矩阵 A 的 Crout（克劳
特）分解。
2.2.2 选主元的 Doolittle 分解法
1、定理 2.4 若矩阵 A Rnn 非奇异，则存在置换矩阵 Q，使得 QA 可作 Doolittle
分解，其中 L 是单位下三角矩阵，U 是上三角矩阵。
2.2.3 三角分解法解带状线性方程组 2.2.4 追赶法求解三对角线性方程组 1、设 n 元线性方程组 Ax=b 的系数矩阵 A 为非奇异的三对角矩阵
a1 b1
d2 a2 c2
A
cn1
dn an
这种方程组称为三对角线性方程组。
2.2.5 拟三对角线性方程组的求解方法
1、系数矩阵为如下的拟三角矩阵
敛。
三、 本章思考题
在求解线性方程组的时候，直接法和迭代法的区别是什么？各自的算法思想 是什么？适用的范围是什么？
答：迭代法就是一种不断的通过用旧的值来递推出新的值的过程，与迭代法 相对应的就是直接法，顾名思义，直接法就是直接对所求问题进行求解的方法， 一次性的快速解决问题。一般情况下，直接法是有线考虑的，但是遇到未知量数 量较多的复杂问题时，直接法就无法直接求解到答案，这就需要使用其他方法， 迭代法就可以很好的解决这种情况。同时由于计算机的发展，可以利用计算机运 算速度快的特点，结合迭代法的特点，很快的就可以求解出答案，比直接法要快 的多。
定理 2.18 如果 GS 1，则 SOR 方法收敛。 定理 2.19 SOR 方法收敛的必要条件是 0 2。 定理 2.20 如果方程组的系数矩阵 A 是主对角线按行（或按列）严格占优阵，则用 0 1的 SOR 方法求解必收敛。 定理 2.21 如果方程组的系数矩阵 A 是正定矩阵，则用 0 2的 SOR 方法求解必收
迭代矩阵
分量形式 收敛的充要条 件 迭代公式 迭代矩阵 分量形式 收敛的条件 迭代公式 迭代矩阵 分量形式
收敛的条件
R x b.定理 2.8 对任意的向量 d n ，迭代法 (k1)Gx(k1) d （ k0,1,）收敛的
充分必要条件是 (G)1。
2.4.2Jacobi 迭代法
a.迭代公式: x(k1) D 1 (LD)x(k) D 1b （ k 0,1,）
b.迭代公式: x(k1) (D L)-1Ux (k) (D L)(1) b （ k 0,1,）
b.迭代矩阵： GG （- D L）1U
c.分量形式：
x(k 1) i
i 1 j 1
aij
aii
x(k 1) j
n aij
j 11
aii
x
(k j
)
bi
aii
(i
1,2,...n; k
0,1,...)
b 与 (k) ik
所含的数值。
（3）对于 i=k+1，k+2，…，n 计算
2、 回代过程
2.2 直接三角分解法
2.2 直接三角分解法