§ 4,解线性方程组的迭代法
迭代法概述
雅可比 (Jacobi)迭代法
高斯 — 塞德尔（ Gauss-Seidel)迭代法
松弛法
迭代法的收敛条件
误差估计一,迭代法概述迭代法的基本思想是构造一串收敛到解的序列，即建立一种从已有近似解计算新的近似解的规则。由不同的计算规则得到不同的迭代法，本章介绍单步定常线性迭代法。
直接法比较适用于中小型方程组。对高阶方程组，既使系数矩阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序复杂等不足,
迭代法则能保持矩阵的稀疏性，具有计算简单，编制程序容易的优点，并在许多情况下收敛较快。故能有效地解一些高阶方程组。
1
( 0 )
( 1 ) ( )
( ) ( )
( ) (,,)
,
( k= 0,1,2,)
{}
T
ij n n n
n
n
kk
kk
Ax b
A a b b b
x M x g
M n g R
xR
x M x g
x k x
Ax b
对线性方程组其中 非奇异矩阵，
构造其形如的同解方程组，其中 为 阶方阵,。
任取初始向量 代入迭代公式产生向量序列,当 充分大时，以 作为方程组 的近似解，这就是求解线
M
性方程组的单步定常线性迭代法。 称为迭代矩阵。
()
()
()
()
()
(
{ }
l im 0
{}
l im
{ }
l im
k n n
k
k
k
k
k
n k n
i
k
x R x R
xx
xx
xx
R x R x
x
,设 为 中 的 向 量 序 列,,如 果其 中 为 向 量 范 数,则 称 序 列 收 敛 于,记 为
,中 的 向 量 序 列 收 敛 于 中 的 向 量 当 且 仅 当定 义定 理
)
( ) ( ) ( ) ( )
1 2 1 2
( 1,2,,)
(,,,),(,,,)
k
i
k k k k T T
nn
x i n
x x x x x x x x
其 中 。
( ) ( )
( ) ( ) ( )
1
()
{ } l im 0
1
0 m a x
l im = 0 ( 1,2,,)
l im
kk
k
k k k
i i j j
jn
k
ii
k
k
x x x x
in
x x x x x x
x x i n
x
证,由 定 义,收 敛 于 即而 对 任 意,有由 极 限 存 在 准 则 得即
()
( 1,2,,)
k
ii
x i n
()
()
()
()
( ) ( )
()
{ }
l i m 0
{}
l i m
{ } ( ) ( 1,2,),(
{}
k
k
k
k
k
k
kk
ij ij
k
A n A n
AA
AA
AA
A a k A a n
AA
定 义,设 为 阶 方 阵 序 列,为 阶 方 阵,如 果其 中 为 矩 阵 范 数,则 称 序 列 收 敛 于 矩 阵,记 为定 理,设 ) 均 为 阶 方 阵,
则 矩 阵 序 列 收 敛 于 矩 阵 的 充
()
l i m (,1,2,,)
k
ij ij
k
a a i j n
要 条 件 为证 明 略 。
( 1 ) ( ) ( )
( 1 ) ( )
{ }
,
l im l im [ ]
k k k
kk
kk
x Mx g x
x
x x Mx g Mx g
x Ax b
定 理 表 明,向 量 序 列 和 矩 阵 序 列 的 收 敛 可 以 归 结 为对 应 分 量 或 对 应 元 素 序 列 的 收 敛 。
若 按 产 生 的 向 量 序 列 收 敛 于 向量 则 有即 是 方 程 组 的 解 。
二,雅可比 (Jacobi)迭代法
1 1 1 1 2 2 1 n 1
2 1 1 2 2 2 2 n 2
n 1 1 n 1 2 n n
n
n
nn
a x a x a x b
a x a x a x b
a x a x a x b
0 ( 1,2,,),ii ina若 系 数 矩 阵 非 奇 异 即 则 有
13 112 1
1 2 3
11 11 11 11
23 221 2
2 1 3
22 22 22 22
12
n 1 2
0 -
0
n
n
n
n
nn
nn nn
aaab
x x x x
a a a a
aaab
x x x x
a a a a
aa
x x x
aa
3
3
1 12 2 13 3 1
1
2 21 1 23 3 2
2
n1
0
nn
nn nn
nn
nn
n
ab
x
aa
gx b x b x b x
gx b x b x b x
x
1 2 2 3 3
,(,,1,2,,),( 1,2,,),
nn
n
ij
i
ij i
ii ii
a b
b i j i j n g i n
aa
gb x b x b x
其 中
12 13 1 1 1 1
21 23 2 1 2 2
1 2 3 1
( 0 ) ( 1 ) 1 0 ( 1 )
( 2 ) ( )
( 1 )
0
0
0
,
{}
nn
nn
n n n nn n
k
k
b b b b g
b b b b g
Bg
b b b b g
x B x g
x x x B x g x
xx
x B x
（ ） （ ）
若记则方程组可简记为选初值向量 代入,代入
，如此继续下去，就产生一个向量序列满足
()
( 0,1,2,)
k
gk
J ac ob i
此过程所给出的迭代法称为 迭代法，又称简单迭代法。
矩阵简化记法
1
1
1
100
010
001
0
0
0
21
221
112
21
221
112
bb
bb
bb
bb
bb
bb
nn
n
n
nn
n
n
B
AD I -
aaa
aaa
aaa
a
a
a
I
nn
1
nnn2n1
2n2221
1n1211
1
1
22
1
11
1
12
1 1 1 2 2 2
(,,,)
(,,,)
T
T
n
n n n
g g gg
bDb a b a b a
同样收敛与解
1
*
**
n 0 1 2
{ }
B g
nn
k
J a c o b i B gxx
xx
xx
（ ） （ ）
（）
迭代,，，
若收敛,则
* 1 * 1
*
( )
I B x g D A x D b
A x b
即故如果序列收敛,则收敛到解,B 称迭代矩阵,
1 2 3
1 2 3
1 2 3
1 2 3
2 1 3
3 1 2
1 0 2 7 2
1 0 2 8 3
5 4 2
1
0 2 7 2
10
1
0 2 8 3
10
1
0 4 2
5
x x x
J a c o b i x x x
x x x
x x x
x x x
x x x
例,用 迭 代 法 求 解解,原 方 程 可 变 形 为
0 1 2
0 0,1 0,2
1 0 2 0,1 0 0,2
0,2 0,2
11
1 0 1 0
0
1 1 0
11
1 0 1 0
1
7 2 8 3 4 2 7,2 8,3 8,4
1
1
11
55
1
00 51
T
T
B
g
＝
＝
1 ( 7,2,8,3,8,4 ) Tg D b
1
1
00
10
1 0 0 1 0 1 2 0 0,1 0,2
1
0 1 0 0 0 1 1 0 2 0,1 0 0,2
10
0 0 1 1 1 5 0,2 0,2 0
1
00
5
B I D A
( 0 )
( 0 )
( 2 ) ( 1 )
( 9 )
( 0,0,0 ),
( 7,2,8,3,8,4 )
( 9,7 1,1 0,7 0,1 1,5 )
( 1 0,9 9 9 4,1 1,9 9 9 4,1 2,9 9 9 2 )
( 1 1,1 2,1 3 ),
T
T
T
T
x
B x g
x B x g
x
x
(1)
取 代 入 迭 代 式,得
x
精 确 解 为
Jacobi迭代法的计算过程如下：
( 0 ) ( 0 ) ( 0 ) ( 0 )
1 1 2
( 0 )
1
( 0 )
( 0 )
1,( ),(,,),,(,,,),
,.
2,1.
3,1,2,,( ) /
4.,,5
5.,1,( 1,2,,),3
ij n n
n
i i ij j ii
j
ji
ii
A a b b b n x x x x
N
k
i n x b a x a
x x x
k N k k x x i n
输入 维数最大容许迭代次数置对若 输出 停机；否则转 。
若 置 转 ；
否则，输出失败信息，停机。
( ) ( 1
,
kk
M x x
）
评价：公式简单，每迭代一次只需计算一次矩阵和向量的乘法，不改变 的稀疏性，需两组工作单元，存 。
三,高斯 — 塞德尔（ Gauss-Seidel)迭代法
( 1 ) ( )
( 1 ) ( ) ( ) ( )
1 12 2 13 3 1
1
( 1 ) ( ) ( )
22
()
11 23 3 2
2
( 0,1,2,)
kk
k k k k
nn
k k k
n
k
n
x B x g k
gx b x b x b x
gx b b x bx x
迭 代 公 式 用 方 程 组 表 示 为
( 1 )
1
( ) ( ) ( )
1 2,1
( ) (
1
1
2
)
kk
n n n n n
n
kk
kk
n
J ac obi
xx
gx b b xx bx
因 此,在 迭 代 法 的 计 算 过 程 中,需 同 时 保 留 两 个近 似 解 向 量 和 。 若 把 迭 代 公 式 改 写 成
( 1 ) ( ) ( ) ( )
1 12 2 13 3 1
1
( 1 ) ( ) ( )
2 21 23 3 2
(1
2
( 1 )
1
)
( 1 )
1 2
1
k k k k
nn
kk k
k
k
nn
k
n n n
x
gx b x b x b x
gx b b
x
b x x
xb
,1
( 0 )
( 1 ) ( 1 )
)
2
(
1
,{ },
kk
nnn
n
k
n
xx
J ac obi
gb xbx
这 样,在 整 个 计 算 过 程 中,只 需 用 个 单 元 存 储 近 似解 分 量 。 而 且 通 常 认 为,近 似 解 可 能 比 老 近 似 解 更 接近 精 确 解,因 此,可 望 这 种 迭 代 会 更 有 效 。
选 取 初 始 向 量 用 上 式 迭 代 产 生 近 似 解 序 列这 种 方 法 叫 。
,与 相 比,只 需 一 组 工评 价 作 单 元 存 放 近 似 解迭 代 法
。
Gau ss - S e id e l
( 1 ) ( )
12 1
2,21
12
( 1 ) ( )
1
( 1 ) 1 ( ) 1
00
00
U
0
0
( )
) 1,( )
( )
()
kk
n
n
nn
kk
kk
L x U x g
L
I L x U x g
I L I L
x I L U x I L g
bb
bb
bb
(k+1)
用矩阵表示为 x
其中,
移项可得因为de t( 故 存在，上式可改写为
1 2 1 3 1
21 2 3 2
3 1 3 2
1
1 2 1
11
1 1 1
( 1 ) 1 (
0 0 0 0
0 0
0 00
,
()
( )
n
n
nn
n n n n
kk
A
a a a
a aa
LUaa
a
a a a
L D L U D U
I L D D D L D D L
x I L U x
如果用矩阵 来表示，记则由
)1
( 1 ) 1 ( ) 1
1
()
( ) ( )
( )
kk
I L g
x D L Ux D L b
M D L U Gau ss Se i de l
式中矩阵 为 迭代法的迭代矩阵。
1 2 3
1 2 3
1 2 3
( 0 )
1 ( 0 ) ( 0 )
1 2 3 1
1 ( 1 ) ( 0 )
2 1 3 2
1
3
10 2 72
10 2 83
5 42
( 0,0,0),
11
( 2 ) 72 7.2 00 0
10 10
11
( 2 ) ( 7.2 00 0 83 ) 9.0 20 0
10 10
T
x x x
Gau ss Se i de l x x x
x x x
x
x x x b
x x x b
x
（）
（）
（）
例：用 迭代法求解解：仍取 代入迭代式，得
( 1 ) ( 1 )
1 2 3
( 5 )
11
( ) 7.2 00 0 9.0 20 0 42 ) 11,64 40
55
( 10,99 89,11,99 93,12,99 96 )
( 11,12,13 ),
T
x x b
x
x
（
如此继续下去，
精确解为
( 1 ) ( 12
11
2
22
2
3
( 2 )
2
)
( 2 )
1
( 2 )
1 3
23
( 1 )
3
11
( ) 9,0 2 2 1 1,6 4 4 0 7 2
1 0 1 0
11
( 2 ) ( 2 1 1,6 4 4 0 8 3 )
1 0 1 0
11
( ) 4 2
5
2
)
5
B
xb
xb
A
xA
x xB Ax
x
b C
xx
（ ）
（ ）
（ ）
（
G au se se ide l
J ac ob i
G au se se ide l J ac ob i
G au se se ide l
J ac ob i J ac ob i
G au se se ide l
J ac ob i
上例计算结果表明,迭代法比 迭代法效果好。事实上，对有些问题 迭代法确实比迭代法收敛得快，但也有 迭代比 迭代收敛得慢，甚至还有迭代收敛,迭代发散的情形。
评价：与 相比，只需一组工作单元存放近似解。
四,松弛法
( 1 ) ( ) ( 1 )
12
1
( 1 ) ( ) ( )
11
1
( 1 ) ( ) ( )
11
(,,,),
1
( ) (
T k k k
n
in
k k k
i ij j ij j i i
j j i
in
k k k
i ij j ij j i
j j iii
G auss Se ide l
x x x x x x x
G auss Se ide l
x b x b x g x
b a x a x x
a
迭代法加速:
记 其中 由迭代公式得到。于是有
()
( 1 ) ( )
1,2,,)
k
kk
in
x G auss Se ide l k
x
x x x
可以把 看作 迭代的修正项，即第 次近似解 以此项修正后得到新的近似解
( 1 ) ( )
( 1 )
1
( 1 ) ( )
11
( 1 ) ( )
(
kk
kk
i i i
in
k k k
i i ij j ij j
j j i
ii
x
x x x
x x x
x b a x a x
a
i
松弛法是将 乘上一个参数因子 作为修正项而得到新的近似解，具体公式为即
1,2,,)
11
1
n
A x b
G auss
Se ide l
按上式计算 的近似解序列的方法称为松弛法，
称为松弛因子。当 时称为低松弛； 是迭代； 时称为超松弛法。
( 1 ) ( ) ( ) ( ) ( )
1 1 12 2 13 3 1
1
( 1 ) ( ) ( ) ( )
2 2 3 2
2
23
( 1 ) ( )
1
( 1 )
1
1 +
1
21
()
1
1
1
+
k k k k k
nn
k k k k
nn
kkk
n n n
k
gx x b x b x b x
gbx x x b x
b
xx
x
b x
( 1 )
2
(1
1
)
,21
,0
n n n
n
ij
i
k
ii
i
k
j
i
n
gbb
a
x
b
a
x
a
其 中,
( 1 ) ( )
( ) 1 ( 1 ) 1 ( ) 1 ( )
( ) 1 ( 1 ) 1 ( ) 1
1 1 1 1
( 1 ) 1
( )
( 1 )
) 1,( )
(
kk
k k k k
k k k
k
x x x
x D L x D Ux D b x
x D L x D Ux D b
I D L I D L D L
x DD D
－
松弛法迭代公式的矩阵表示：
因为det ( 故（ ） 与 存在，
有
1 1 1 ( ) 1
1 1 1 1 ( ) 1
1
) [ ( 1 ) ] (
) ( ) [ ( 1 ) ] ( )
( ) [ ( 1 ) ]
,
k
k
L D U x DD
D L D b D L D U x D L b
M D L D U
松弛法的迭代矩阵为松弛因子的选取对收敛速度影响极大 但目前尚无可供实用的计算最佳松弛因子的方法。通常是根据系数矩阵的性质及实际经验，通过试算来确定松弛因子。
( 0 )
12
1 2 3
23
1
( 1 ) ( 1 ) ( )
11
1,4,( 1,1,1 ),
21
2 0
2 1,8
( 1 ) ( )
T
in
k k k k
i i i ij j ij j
j j iii
x
xx
x x x
xx
x x b a x a x
a
例,取 用 超 松 弛 法 解 方 程 组解,由
( 1 ) ( ) ( )
1 1 2
( 1 ) ( ) ( 1 ) ( )
2 2 1 3
( 1 ) ( ) ( 1 )
3 3 2
( 0 )
( 9 )
0,4 0,7 ( 1 )
0,4 0,7 ( ) ( 0,1,2,)
0,4 0,7 ( 1,8 )
( 1,1,1 )
( 1,2 0 0,1,3 9 9 6,1,6 0 0 1 ) ( 1,2,1,4,1,6 )
k k k
k k k k
k k k
T
TT
x x x
x x x x k
x x x
x
xx
将 代 入 上 式 开 始 迭 代,
精 确 解迭代矩阵
Jacobi迭代法
Gauss-Seidel迭代法
松弛法
1( ) [ ( 1 ) ]M D L D U
1( ) M D L U
1 B I D A
12 13 1
21 23 2
31 32
1
1 2 1
11
22
0 0 0 0
0 0
0 00
n
n
nn
n n n n
nn
A
a a a
a aa
aaLU
a
a a a
D
a
a
a
，
，
如 果 用 矩 阵 来 表 示,记五,迭代法的收敛条件
1
12
12
( 1,2,,)
( ) m a x { }
(,,,)
(,,,) ( 1,2,),( ) [ (
i
i
in
n
k
k k k k
n
A n i n A
A
A
A A A A
kA
A
迭 代 法 的 收 敛 与 迭 代 矩 阵 的 特 征 值 有 关 。
定 义,设 为 阶 方 阵,为 的 特征 值,称 特 征 值 的 最 大 值 为 矩 阵 的 谱 半 径,记 为称 为 。
由 特 征 值 的 定 义 知,矩 阵 的 谱 是因 而矩 阵 的 谱
)]
k
A
1.矩阵的谱半径
,,
,( )
:,
,
( ),
,,,
ii
i i i i i i
ii
i
An
AA
Au
u u Au A u
uA
AA
An
设 为 任 意 阶 方 阵 为 任 意 由 向 量 范 数 诱 导出 的 矩 阵 范 数 则证 对 的 任 一 特 征 值 及 相 应 的 特 征 向 量 都 有因 为 为 非 零 向 量 于 是 有由 的 任 意 性 即 得 证 毕设 为 任 意 阶 方 阵 则 对 任定意 正 数 存理定 理 在 一 种矩 阵
2
,( )
,,
( ) ( )
AA
n
A A A A A
范 数 使 得证 明 略 。
对 任 意 阶 方 阵 一 般 不 存 在 矩 阵 范 数 使 得
。 但 若 为 对 称 矩 阵,则 有 。
l im 0
l im 0 ( )
0 ( ) [ ( ) ]
l im [ ( ) ] 0 ( ) 1
k
k
k
k
k k k
k
k
A
A A A
A A A
AA
证,若由 矩 阵 收 敛 的 定 义 知 又 因由 极 限 存 在 的 准 则,有 ＝ 所 以必 要 性
。
l im 0 ( ) 1kkA n A A,设 为 阶 方 阵,则 的 充 要 条 件 为定 理 。
1 ( )
( ) 1 0,
2
1 ( )
( ) 1
2
,l im l im 0 l im 0,
kk
k k k
k k k
A
A
A
AA
A A A A A
若,取 由 上 一 定 理知,存 在 一 种 矩 阵 范 数,得而充使分 性
2、迭代法的收敛条件
( 0 )
( 1 ) ( )
()
* ( ) * *
**
( ) *
( 0,1,2,)
{ } ( ) 1,
:,,l im
kk
k
k
k
k
xg
x M x g k
xM
n x x x x
x M x g
xx
,对 任 意 初 始 向 量 和 常 数 项,由 迭 代 格 式产 生 的 向 量 序 列 收 敛 的 充 要 条 件 是证 设 存 在 维 向 量 使 得,则 满 足由 迭 代必 要 性公 式 有定 理
( 1 ) *
( 1 ) * 2 ( 2 ) * ( 0 ) *
( 0 ) * ( ) *
( 0 )
( ) ( ) ( )
l im ( ) l im ( ) 0
,l im 0
( ) 1,
k
k k k
kk
kk
k
k
M x g M x g
M x x M x x M x x
M x x x x
x n M
M?
于 是 有因 为 为 任 意 维 向 量 因 此 上 式 成 立 必 须由 上 一 定 理
* * *
( ) * ( 1 ) * ( 0 ) *
( 0 )
( ) *
,( ) 1,1,
de t ( ) 0,,
,,
l i m 0
( ) ( )
,,
l i m ( ) l i m
k
k
k k k
k
kk
MM
I M n g I M x g
x x M x g
M
x x M x x M x x
x
xx
若 则 不 是 的 特 征 值 因 而 有于 是 对 任 意 维 向 量 方 程 组有 唯 一 解 记 为 即并 且又 因 为所 以 对 任 意 初充 分 性始 向 量 都 有
( 0 ) *
( 1 ) ( ) ( )
( ) = 0
{ },
k
k k k
M x x
x M x g x
即 由 迭 代 公 式 产 生 的 向 量 序 列 收 敛
12
12
1
0 2
,,,
d e t( ) [ ( ) ]
d e t( ) 1
d e t( ) (
2
) ( 1 )
n
n
n
M
MM
M
M D L D U
松 弛 法 收 敛 的 必 要 条 件 是 。
证,设 松 弛 法 的 迭 代 矩 阵 由 特 征 值 。
因 为由 定 理,松 弛 法 收 敛 必 有为论又 因推
( 0 )
( 1 ) ( )
()
1,
( 0,1,2
1
,)
{ },
kk
k
x g M
x M x g k
x
对 任 意 初 始 向 量 和 右 端 项,若 由 迭推 代格 式产 生 的 向 列论量 序 收 敛迭 代 法 收 敛 与 否 只 决 定 于 迭 代 矩 阵 的,与
。 对 同 一 方 程 组,由 于 不 同 的 迭 代 法 迭 代矩 阵 不 同,可 能 出 现 有 的 方 法 收初 始 向敛,有谱 半的 方量 及 右 端 项法 发 散无径关的 情 形 。
1
1 1 2 2
1 1 2 2
1
( )
( 1 ) ( 1 )
d e t( ) ( 1 ) 1 0 2
nn
n
nn
n
DL
a a a
D U a a a
M
。
1 2 3
1 2 3
1 2 3
2 2 1
2
2 2 3
x x x
x x x
x x x
例,对 方 程 组讨 论 Jacobi 迭 代 法 与 Gauss-Seidel 迭 代 法 的 收 敛 性 。
1 2 2 1 0 0
1 1 1 0 1 0
2 2 1 0 0 1
0 0 0 0 2 2
1 0 0 0 0 1
2 2 0
1
0 0 0
AD
LU
求 迭 代 矩 阵 判 别 其 谱 半 径 是 否 小解,于 。
J a c o b i 迭 代 法 的 迭 代 矩 阵 为
1
0 2 2
1 0 1
2 2 0
B I D A
3
1 2 3
22
1 1 0
22
0,( ) 0 1,
Ja c obi
IB
B
其 特 征 方 程 为因 此 有 于 是所 以 迭 代 法 收 敛 。
1
1
2
1 2 3
1 0 0 1 0 0
1 1 0 ( ) 1 1 0
2 2 1 0 2 1
1 0 0 0 2 2 0 2 2
( ) 1 1 0 0 0 1 0 2 3
0 2 1 0 0 0 0 0 2
22
0 2 3 ( 2) 0
0 0 2
0,2,( ) 2 1,
D L D L
M D L U
IM
M
特 征 方 程特 征 值 为 故 所 以 迭 代 发 散 。
1G a u s s - S e i d e l ( ),M D L U迭 代,由
0 2
1
12
1,
1,1
B
M
上例说明了 确实只是松弛法收敛的必要条件，而非充要条件，因为Gau ss- Sei del
迭代记为 的情形。
判断定理虽然给出了判别迭代收敛的充要条件，但要求逆矩阵和特征值。推论 与 仅分别给出了收敛的充分与必要条件，许多情形下不能起作用。如上例，两个方法均有由推论 无法判别收敛性。
对一些特殊的系数矩阵可给出几个常用的判别收敛条件
1
11 12
11 22
22
( ) ( 1,2,,)
,
0
1 1 0
1 1
n
ij ii ij
j
ji
n A a a a i n
iA
iA
A
AA
A A A A
A
A
严弱对 角 占定 义,若 阶 方 阵 满 足且 至 少 有 一 个 值,使 上 式 中 不 等 号 严 格 成 立,则 称 为
。 若 对 所 有,上 式 不 等 号 均 严 格 成 立,则 称为 。
定 义,如 果 矩 阵 不 能 通 过 行 的 互 换 和 相 应 的 列 互 换 成为 形 式 其 中,为 方 阵,则格 对 角 占 优 阵称 为 。
例,
约优 阵不 可
13
2 1 0
0 0 1 1
0 1 2 0 1 1
PI T
P A P
,
1.
Jac obi G a uss - S e i de l
2,0 1,
3.
02
10 1 2 2 1 0
1 10 2 1 2 1
1 1 5 0 1 2
Ax b
A
A
A
AB
A
设 有 线 性 方 程 组 下 列 结 论 成 立 （ ）
若 为 严 格 对 角 占 优 阵 或 不 可 约 弱 对 角 占 优 阵,则迭 代 法 和 迭 代 法 均 收 敛 。
若 为 严 格 对 角 占 优 阵,则 松 弛 法 收 敛 。
若 为 对 称 正 定 阵,则 松 弛 法 收 敛 的 充 要 条 件 为
。
收 敛 充上 两 例 中,
为分 条 件严 格 对 角
B
占 优 阵,故 Jacobi 与 Gauss-Seidel 迭代 均 收 敛 。 为 非 严 格 对 角 占 优 阵,但 为 对 称 正 定阵,=1.4 故 松 弛 法 收 敛 。
-1
11
1
22
11
,1
22
11
1
22
3 ( 0 2)
1
11
0
22
11
- 0
22
11
0
22
Ax b A
AA
A
B I D A
例,讨论用三种迭代法求解的收敛性。
解：因 为对称且其各阶主子式皆大于零，故 为对称正定矩阵。由判别条件,G aus s-S eid el迭 代法与松弛法均收敛。 不是弱对角占优阵，故不能用条件 判断。
Jacobi 迭代法的迭代矩阵为
3
2
1 2 3
11
22
1 1 3 1
2 2 4 4
11
22
1
( ) ( 1 ) 0
2
1
,1,( ) 1
2
IB
B
Jaco b i
其特征方程得 因而迭代法不收敛。
3 10
,
94
10 10
00
33
,
9 15
00
42
30 15
( ),( )
22
Ax b A
J ac obi Gaus s Se i de l
BM
BM
改变方程组中方程的次序，即将系数矩阵作行交换，会改变迭代法的收敛性。
例：
与 迭代的迭代矩阵分别为谱半径分别是 。均不收敛。
''
'
' ' '
,
3 1 0 9 4
9 4 3 1 0
A x b
A x b
AA
A A x b
J a c o b i G a u ss S e id e l
若交换方程的次序，得 的同解方程组为严格对角占优阵，因而对方程组 用与 迭代求解均收敛。
六,误差估计
( 1 ) ( )
( ) *
( ) * ( 1 ) ( 0 )
1*
*1
( ) * ( 1 ) * ( 0 ) *
,1,
,
1
( ) 1,0,
)
)
( ) ( )
kk
k
k
k
k k k
x Mx g M
xx
M
x x x x
M
M M I M
I M x Mx g x
x I M g
x x M x x M x x
( 先 验定 理,设 有 迭 代 格 式 若收 敛 于 则 有 误 差 估 计 式证,因 故 于 是
( 存 在,方 程 组 有 唯 一 解,
且 ( 有估
。 从 而计 ）
( 0 ) 1
1 ( 0 )
1 ( 0 ) 1
[ ) ]
) [ ) ]
) [ ]
k
k
k
M x I M g
M I M I M x g
M I M x x
（ ）
(
((
(
( ) * 1 ( 0 ) 1
1
11
11
1
1
( ) *
)
) )
) )
) )
)
1
)
1
1
k
k
k
k
x x M I M x x
I M I M I
I M I M I M
I M I M I M
I M I M
IM
M
M
xx
（）
取范数 (
又因为 ( (
((
取范数 ( (
(
移项得 (
代入得
( 1 ) ( 0 )
xx
M
。
( ) * ( 1 ) ( 0 )
( 1 ) ( 0 )
1
:
( 1 )
ln
ln
k
k
M
x x x x
M
M
xx
k
M
k
根 据 事 先 给 定 的 精 度,可 估 计 出 迭由 误 差 估 计数式代 的 次
( 0 ) ( 1 )
4 ( 1 ) ( 0 )
0 0,1 0,2 0 7,2
0,1 0 0,2,0,8,3
0,2 0,2 0 0 8,4
1 0,0,4,8,4
1 2,9 3 2,1 3
M x x
M x x
k
－
例,若则 有即 需 要 迭 代 次 才 能 满 足 精 度 。
( 1 ) ( )
( ) *
( ) * ( ) ( 1 )
( ) * ( 1 ) * ( 1 ) 1
1 ( 1 ) ( 1 ) 1 ( 1 ) ( )
( ) * 1 (
,1,
,
1
( ) [ ) ]
) [ ] ) ( )
)
kk
k
k k k
k k k
k k k k
kk
x Mx g M
xx
M
x x x x
M
x x M x x M x I M g
M I M x Mx g M I M x x
x x M I M x
,设 有 迭 代 格 式 若收 敛 于 则 有 误 差 估 计 式证,因
（ 事 后 估 计 ）
((
(
定 理
(
1 ) ( )
( ) ( 1 )
( ) ( 1 )
1
1
.
k
kk
kk
Mx
x
M
xx
M
x?
当 不 太 接 近 时,可 用 作 为 停 机 准 则 。
迭代法概述
雅可比 (Jacobi)迭代法
高斯 — 塞德尔（ Gauss-Seidel)迭代法
松弛法
迭代法的收敛条件
误差估计一,迭代法概述迭代法的基本思想是构造一串收敛到解的序列，即建立一种从已有近似解计算新的近似解的规则。由不同的计算规则得到不同的迭代法，本章介绍单步定常线性迭代法。
直接法比较适用于中小型方程组。对高阶方程组，既使系数矩阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序复杂等不足,
迭代法则能保持矩阵的稀疏性，具有计算简单，编制程序容易的优点，并在许多情况下收敛较快。故能有效地解一些高阶方程组。
1
( 0 )
( 1 ) ( )
( ) ( )
( ) (,,)
,
( k= 0,1,2,)
{}
T
ij n n n
n
n
kk
kk
Ax b
A a b b b
x M x g
M n g R
xR
x M x g
x k x
Ax b
对线性方程组其中 非奇异矩阵，
构造其形如的同解方程组，其中 为 阶方阵,。
任取初始向量 代入迭代公式产生向量序列,当 充分大时，以 作为方程组 的近似解，这就是求解线
M
性方程组的单步定常线性迭代法。 称为迭代矩阵。
()
()
()
()
()
(
{ }
l im 0
{}
l im
{ }
l im
k n n
k
k
k
k
k
n k n
i
k
x R x R
xx
xx
xx
R x R x
x
,设 为 中 的 向 量 序 列,,如 果其 中 为 向 量 范 数,则 称 序 列 收 敛 于,记 为
,中 的 向 量 序 列 收 敛 于 中 的 向 量 当 且 仅 当定 义定 理
)
( ) ( ) ( ) ( )
1 2 1 2
( 1,2,,)
(,,,),(,,,)
k
i
k k k k T T
nn
x i n
x x x x x x x x
其 中 。
( ) ( )
( ) ( ) ( )
1
()
{ } l im 0
1
0 m a x
l im = 0 ( 1,2,,)
l im
kk
k
k k k
i i j j
jn
k
ii
k
k
x x x x
in
x x x x x x
x x i n
x
证,由 定 义,收 敛 于 即而 对 任 意,有由 极 限 存 在 准 则 得即
()
( 1,2,,)
k
ii
x i n
()
()
()
()
( ) ( )
()
{ }
l i m 0
{}
l i m
{ } ( ) ( 1,2,),(
{}
k
k
k
k
k
k
kk
ij ij
k
A n A n
AA
AA
AA
A a k A a n
AA
定 义,设 为 阶 方 阵 序 列,为 阶 方 阵,如 果其 中 为 矩 阵 范 数,则 称 序 列 收 敛 于 矩 阵,记 为定 理,设 ) 均 为 阶 方 阵,
则 矩 阵 序 列 收 敛 于 矩 阵 的 充
()
l i m (,1,2,,)
k
ij ij
k
a a i j n
要 条 件 为证 明 略 。
( 1 ) ( ) ( )
( 1 ) ( )
{ }
,
l im l im [ ]
k k k
kk
kk
x Mx g x
x
x x Mx g Mx g
x Ax b
定 理 表 明,向 量 序 列 和 矩 阵 序 列 的 收 敛 可 以 归 结 为对 应 分 量 或 对 应 元 素 序 列 的 收 敛 。
若 按 产 生 的 向 量 序 列 收 敛 于 向量 则 有即 是 方 程 组 的 解 。
二,雅可比 (Jacobi)迭代法
1 1 1 1 2 2 1 n 1
2 1 1 2 2 2 2 n 2
n 1 1 n 1 2 n n
n
n
nn
a x a x a x b
a x a x a x b
a x a x a x b
0 ( 1,2,,),ii ina若 系 数 矩 阵 非 奇 异 即 则 有
13 112 1
1 2 3
11 11 11 11
23 221 2
2 1 3
22 22 22 22
12
n 1 2
0 -
0
n
n
n
n
nn
nn nn
aaab
x x x x
a a a a
aaab
x x x x
a a a a
aa
x x x
aa
3
3
1 12 2 13 3 1
1
2 21 1 23 3 2
2
n1
0
nn
nn nn
nn
nn
n
ab
x
aa
gx b x b x b x
gx b x b x b x
x
1 2 2 3 3
,(,,1,2,,),( 1,2,,),
nn
n
ij
i
ij i
ii ii
a b
b i j i j n g i n
aa
gb x b x b x
其 中
12 13 1 1 1 1
21 23 2 1 2 2
1 2 3 1
( 0 ) ( 1 ) 1 0 ( 1 )
( 2 ) ( )
( 1 )
0
0
0
,
{}
nn
nn
n n n nn n
k
k
b b b b g
b b b b g
Bg
b b b b g
x B x g
x x x B x g x
xx
x B x
（ ） （ ）
若记则方程组可简记为选初值向量 代入,代入
，如此继续下去，就产生一个向量序列满足
()
( 0,1,2,)
k
gk
J ac ob i
此过程所给出的迭代法称为 迭代法，又称简单迭代法。
矩阵简化记法
1
1
1
100
010
001
0
0
0
21
221
112
21
221
112
bb
bb
bb
bb
bb
bb
nn
n
n
nn
n
n
B
AD I -
aaa
aaa
aaa
a
a
a
I
nn
1
nnn2n1
2n2221
1n1211
1
1
22
1
11
1
12
1 1 1 2 2 2
(,,,)
(,,,)
T
T
n
n n n
g g gg
bDb a b a b a
同样收敛与解
1
*
**
n 0 1 2
{ }
B g
nn
k
J a c o b i B gxx
xx
xx
（ ） （ ）
（）
迭代,，，
若收敛,则
* 1 * 1
*
( )
I B x g D A x D b
A x b
即故如果序列收敛,则收敛到解,B 称迭代矩阵,
1 2 3
1 2 3
1 2 3
1 2 3
2 1 3
3 1 2
1 0 2 7 2
1 0 2 8 3
5 4 2
1
0 2 7 2
10
1
0 2 8 3
10
1
0 4 2
5
x x x
J a c o b i x x x
x x x
x x x
x x x
x x x
例,用 迭 代 法 求 解解,原 方 程 可 变 形 为
0 1 2
0 0,1 0,2
1 0 2 0,1 0 0,2
0,2 0,2
11
1 0 1 0
0
1 1 0
11
1 0 1 0
1
7 2 8 3 4 2 7,2 8,3 8,4
1
1
11
55
1
00 51
T
T
B
g
＝
＝
1 ( 7,2,8,3,8,4 ) Tg D b
1
1
00
10
1 0 0 1 0 1 2 0 0,1 0,2
1
0 1 0 0 0 1 1 0 2 0,1 0 0,2
10
0 0 1 1 1 5 0,2 0,2 0
1
00
5
B I D A
( 0 )
( 0 )
( 2 ) ( 1 )
( 9 )
( 0,0,0 ),
( 7,2,8,3,8,4 )
( 9,7 1,1 0,7 0,1 1,5 )
( 1 0,9 9 9 4,1 1,9 9 9 4,1 2,9 9 9 2 )
( 1 1,1 2,1 3 ),
T
T
T
T
x
B x g
x B x g
x
x
(1)
取 代 入 迭 代 式,得
x
精 确 解 为
Jacobi迭代法的计算过程如下：
( 0 ) ( 0 ) ( 0 ) ( 0 )
1 1 2
( 0 )
1
( 0 )
( 0 )
1,( ),(,,),,(,,,),
,.
2,1.
3,1,2,,( ) /
4.,,5
5.,1,( 1,2,,),3
ij n n
n
i i ij j ii
j
ji
ii
A a b b b n x x x x
N
k
i n x b a x a
x x x
k N k k x x i n
输入 维数最大容许迭代次数置对若 输出 停机；否则转 。
若 置 转 ；
否则，输出失败信息，停机。
( ) ( 1
,
kk
M x x
）
评价：公式简单，每迭代一次只需计算一次矩阵和向量的乘法，不改变 的稀疏性，需两组工作单元，存 。
三,高斯 — 塞德尔（ Gauss-Seidel)迭代法
( 1 ) ( )
( 1 ) ( ) ( ) ( )
1 12 2 13 3 1
1
( 1 ) ( ) ( )
22
()
11 23 3 2
2
( 0,1,2,)
kk
k k k k
nn
k k k
n
k
n
x B x g k
gx b x b x b x
gx b b x bx x
迭 代 公 式 用 方 程 组 表 示 为
( 1 )
1
( ) ( ) ( )
1 2,1
( ) (
1
1
2
)
kk
n n n n n
n
kk
kk
n
J ac obi
xx
gx b b xx bx
因 此,在 迭 代 法 的 计 算 过 程 中,需 同 时 保 留 两 个近 似 解 向 量 和 。 若 把 迭 代 公 式 改 写 成
( 1 ) ( ) ( ) ( )
1 12 2 13 3 1
1
( 1 ) ( ) ( )
2 21 23 3 2
(1
2
( 1 )
1
)
( 1 )
1 2
1
k k k k
nn
kk k
k
k
nn
k
n n n
x
gx b x b x b x
gx b b
x
b x x
xb
,1
( 0 )
( 1 ) ( 1 )
)
2
(
1
,{ },
kk
nnn
n
k
n
xx
J ac obi
gb xbx
这 样,在 整 个 计 算 过 程 中,只 需 用 个 单 元 存 储 近 似解 分 量 。 而 且 通 常 认 为,近 似 解 可 能 比 老 近 似 解 更 接近 精 确 解,因 此,可 望 这 种 迭 代 会 更 有 效 。
选 取 初 始 向 量 用 上 式 迭 代 产 生 近 似 解 序 列这 种 方 法 叫 。
,与 相 比,只 需 一 组 工评 价 作 单 元 存 放 近 似 解迭 代 法
。
Gau ss - S e id e l
( 1 ) ( )
12 1
2,21
12
( 1 ) ( )
1
( 1 ) 1 ( ) 1
00
00
U
0
0
( )
) 1,( )
( )
()
kk
n
n
nn
kk
kk
L x U x g
L
I L x U x g
I L I L
x I L U x I L g
bb
bb
bb
(k+1)
用矩阵表示为 x
其中,
移项可得因为de t( 故 存在，上式可改写为
1 2 1 3 1
21 2 3 2
3 1 3 2
1
1 2 1
11
1 1 1
( 1 ) 1 (
0 0 0 0
0 0
0 00
,
()
( )
n
n
nn
n n n n
kk
A
a a a
a aa
LUaa
a
a a a
L D L U D U
I L D D D L D D L
x I L U x
如果用矩阵 来表示，记则由
)1
( 1 ) 1 ( ) 1
1
()
( ) ( )
( )
kk
I L g
x D L Ux D L b
M D L U Gau ss Se i de l
式中矩阵 为 迭代法的迭代矩阵。
1 2 3
1 2 3
1 2 3
( 0 )
1 ( 0 ) ( 0 )
1 2 3 1
1 ( 1 ) ( 0 )
2 1 3 2
1
3
10 2 72
10 2 83
5 42
( 0,0,0),
11
( 2 ) 72 7.2 00 0
10 10
11
( 2 ) ( 7.2 00 0 83 ) 9.0 20 0
10 10
T
x x x
Gau ss Se i de l x x x
x x x
x
x x x b
x x x b
x
（）
（）
（）
例：用 迭代法求解解：仍取 代入迭代式，得
( 1 ) ( 1 )
1 2 3
( 5 )
11
( ) 7.2 00 0 9.0 20 0 42 ) 11,64 40
55
( 10,99 89,11,99 93,12,99 96 )
( 11,12,13 ),
T
x x b
x
x
（
如此继续下去，
精确解为
( 1 ) ( 12
11
2
22
2
3
( 2 )
2
)
( 2 )
1
( 2 )
1 3
23
( 1 )
3
11
( ) 9,0 2 2 1 1,6 4 4 0 7 2
1 0 1 0
11
( 2 ) ( 2 1 1,6 4 4 0 8 3 )
1 0 1 0
11
( ) 4 2
5
2
)
5
B
xb
xb
A
xA
x xB Ax
x
b C
xx
（ ）
（ ）
（ ）
（
G au se se ide l
J ac ob i
G au se se ide l J ac ob i
G au se se ide l
J ac ob i J ac ob i
G au se se ide l
J ac ob i
上例计算结果表明,迭代法比 迭代法效果好。事实上，对有些问题 迭代法确实比迭代法收敛得快，但也有 迭代比 迭代收敛得慢，甚至还有迭代收敛,迭代发散的情形。
评价：与 相比，只需一组工作单元存放近似解。
四,松弛法
( 1 ) ( ) ( 1 )
12
1
( 1 ) ( ) ( )
11
1
( 1 ) ( ) ( )
11
(,,,),
1
( ) (
T k k k
n
in
k k k
i ij j ij j i i
j j i
in
k k k
i ij j ij j i
j j iii
G auss Se ide l
x x x x x x x
G auss Se ide l
x b x b x g x
b a x a x x
a
迭代法加速:
记 其中 由迭代公式得到。于是有
()
( 1 ) ( )
1,2,,)
k
kk
in
x G auss Se ide l k
x
x x x
可以把 看作 迭代的修正项，即第 次近似解 以此项修正后得到新的近似解
( 1 ) ( )
( 1 )
1
( 1 ) ( )
11
( 1 ) ( )
(
kk
kk
i i i
in
k k k
i i ij j ij j
j j i
ii
x
x x x
x x x
x b a x a x
a
i
松弛法是将 乘上一个参数因子 作为修正项而得到新的近似解，具体公式为即
1,2,,)
11
1
n
A x b
G auss
Se ide l
按上式计算 的近似解序列的方法称为松弛法，
称为松弛因子。当 时称为低松弛； 是迭代； 时称为超松弛法。
( 1 ) ( ) ( ) ( ) ( )
1 1 12 2 13 3 1
1
( 1 ) ( ) ( ) ( )
2 2 3 2
2
23
( 1 ) ( )
1
( 1 )
1
1 +
1
21
()
1
1
1
+
k k k k k
nn
k k k k
nn
kkk
n n n
k
gx x b x b x b x
gbx x x b x
b
xx
x
b x
( 1 )
2
(1
1
)
,21
,0
n n n
n
ij
i
k
ii
i
k
j
i
n
gbb
a
x
b
a
x
a
其 中,
( 1 ) ( )
( ) 1 ( 1 ) 1 ( ) 1 ( )
( ) 1 ( 1 ) 1 ( ) 1
1 1 1 1
( 1 ) 1
( )
( 1 )
) 1,( )
(
kk
k k k k
k k k
k
x x x
x D L x D Ux D b x
x D L x D Ux D b
I D L I D L D L
x DD D
－
松弛法迭代公式的矩阵表示：
因为det ( 故（ ） 与 存在，
有
1 1 1 ( ) 1
1 1 1 1 ( ) 1
1
) [ ( 1 ) ] (
) ( ) [ ( 1 ) ] ( )
( ) [ ( 1 ) ]
,
k
k
L D U x DD
D L D b D L D U x D L b
M D L D U
松弛法的迭代矩阵为松弛因子的选取对收敛速度影响极大 但目前尚无可供实用的计算最佳松弛因子的方法。通常是根据系数矩阵的性质及实际经验，通过试算来确定松弛因子。
( 0 )
12
1 2 3
23
1
( 1 ) ( 1 ) ( )
11
1,4,( 1,1,1 ),
21
2 0
2 1,8
( 1 ) ( )
T
in
k k k k
i i i ij j ij j
j j iii
x
xx
x x x
xx
x x b a x a x
a
例,取 用 超 松 弛 法 解 方 程 组解,由
( 1 ) ( ) ( )
1 1 2
( 1 ) ( ) ( 1 ) ( )
2 2 1 3
( 1 ) ( ) ( 1 )
3 3 2
( 0 )
( 9 )
0,4 0,7 ( 1 )
0,4 0,7 ( ) ( 0,1,2,)
0,4 0,7 ( 1,8 )
( 1,1,1 )
( 1,2 0 0,1,3 9 9 6,1,6 0 0 1 ) ( 1,2,1,4,1,6 )
k k k
k k k k
k k k
T
TT
x x x
x x x x k
x x x
x
xx
将 代 入 上 式 开 始 迭 代,
精 确 解迭代矩阵
Jacobi迭代法
Gauss-Seidel迭代法
松弛法
1( ) [ ( 1 ) ]M D L D U
1( ) M D L U
1 B I D A
12 13 1
21 23 2
31 32
1
1 2 1
11
22
0 0 0 0
0 0
0 00
n
n
nn
n n n n
nn
A
a a a
a aa
aaLU
a
a a a
D
a
a
a
，
，
如 果 用 矩 阵 来 表 示,记五,迭代法的收敛条件
1
12
12
( 1,2,,)
( ) m a x { }
(,,,)
(,,,) ( 1,2,),( ) [ (
i
i
in
n
k
k k k k
n
A n i n A
A
A
A A A A
kA
A
迭 代 法 的 收 敛 与 迭 代 矩 阵 的 特 征 值 有 关 。
定 义,设 为 阶 方 阵,为 的 特征 值,称 特 征 值 的 最 大 值 为 矩 阵 的 谱 半 径,记 为称 为 。
由 特 征 值 的 定 义 知,矩 阵 的 谱 是因 而矩 阵 的 谱
)]
k
A
1.矩阵的谱半径
,,
,( )
:,
,
( ),
,,,
ii
i i i i i i
ii
i
An
AA
Au
u u Au A u
uA
AA
An
设 为 任 意 阶 方 阵 为 任 意 由 向 量 范 数 诱 导出 的 矩 阵 范 数 则证 对 的 任 一 特 征 值 及 相 应 的 特 征 向 量 都 有因 为 为 非 零 向 量 于 是 有由 的 任 意 性 即 得 证 毕设 为 任 意 阶 方 阵 则 对 任定意 正 数 存理定 理 在 一 种矩 阵
2
,( )
,,
( ) ( )
AA
n
A A A A A
范 数 使 得证 明 略 。
对 任 意 阶 方 阵 一 般 不 存 在 矩 阵 范 数 使 得
。 但 若 为 对 称 矩 阵,则 有 。
l im 0
l im 0 ( )
0 ( ) [ ( ) ]
l im [ ( ) ] 0 ( ) 1
k
k
k
k
k k k
k
k
A
A A A
A A A
AA
证,若由 矩 阵 收 敛 的 定 义 知 又 因由 极 限 存 在 的 准 则,有 ＝ 所 以必 要 性
。
l im 0 ( ) 1kkA n A A,设 为 阶 方 阵,则 的 充 要 条 件 为定 理 。
1 ( )
( ) 1 0,
2
1 ( )
( ) 1
2
,l im l im 0 l im 0,
kk
k k k
k k k
A
A
A
AA
A A A A A
若,取 由 上 一 定 理知,存 在 一 种 矩 阵 范 数,得而充使分 性
2、迭代法的收敛条件
( 0 )
( 1 ) ( )
()
* ( ) * *
**
( ) *
( 0,1,2,)
{ } ( ) 1,
:,,l im
kk
k
k
k
k
xg
x M x g k
xM
n x x x x
x M x g
xx
,对 任 意 初 始 向 量 和 常 数 项,由 迭 代 格 式产 生 的 向 量 序 列 收 敛 的 充 要 条 件 是证 设 存 在 维 向 量 使 得,则 满 足由 迭 代必 要 性公 式 有定 理
( 1 ) *
( 1 ) * 2 ( 2 ) * ( 0 ) *
( 0 ) * ( ) *
( 0 )
( ) ( ) ( )
l im ( ) l im ( ) 0
,l im 0
( ) 1,
k
k k k
kk
kk
k
k
M x g M x g
M x x M x x M x x
M x x x x
x n M
M?
于 是 有因 为 为 任 意 维 向 量 因 此 上 式 成 立 必 须由 上 一 定 理
* * *
( ) * ( 1 ) * ( 0 ) *
( 0 )
( ) *
,( ) 1,1,
de t ( ) 0,,
,,
l i m 0
( ) ( )
,,
l i m ( ) l i m
k
k
k k k
k
kk
MM
I M n g I M x g
x x M x g
M
x x M x x M x x
x
xx
若 则 不 是 的 特 征 值 因 而 有于 是 对 任 意 维 向 量 方 程 组有 唯 一 解 记 为 即并 且又 因 为所 以 对 任 意 初充 分 性始 向 量 都 有
( 0 ) *
( 1 ) ( ) ( )
( ) = 0
{ },
k
k k k
M x x
x M x g x
即 由 迭 代 公 式 产 生 的 向 量 序 列 收 敛
12
12
1
0 2
,,,
d e t( ) [ ( ) ]
d e t( ) 1
d e t( ) (
2
) ( 1 )
n
n
n
M
MM
M
M D L D U
松 弛 法 收 敛 的 必 要 条 件 是 。
证,设 松 弛 法 的 迭 代 矩 阵 由 特 征 值 。
因 为由 定 理,松 弛 法 收 敛 必 有为论又 因推
( 0 )
( 1 ) ( )
()
1,
( 0,1,2
1
,)
{ },
kk
k
x g M
x M x g k
x
对 任 意 初 始 向 量 和 右 端 项,若 由 迭推 代格 式产 生 的 向 列论量 序 收 敛迭 代 法 收 敛 与 否 只 决 定 于 迭 代 矩 阵 的,与
。 对 同 一 方 程 组,由 于 不 同 的 迭 代 法 迭 代矩 阵 不 同,可 能 出 现 有 的 方 法 收初 始 向敛,有谱 半的 方量 及 右 端 项法 发 散无径关的 情 形 。
1
1 1 2 2
1 1 2 2
1
( )
( 1 ) ( 1 )
d e t( ) ( 1 ) 1 0 2
nn
n
nn
n
DL
a a a
D U a a a
M
。
1 2 3
1 2 3
1 2 3
2 2 1
2
2 2 3
x x x
x x x
x x x
例,对 方 程 组讨 论 Jacobi 迭 代 法 与 Gauss-Seidel 迭 代 法 的 收 敛 性 。
1 2 2 1 0 0
1 1 1 0 1 0
2 2 1 0 0 1
0 0 0 0 2 2
1 0 0 0 0 1
2 2 0
1
0 0 0
AD
LU
求 迭 代 矩 阵 判 别 其 谱 半 径 是 否 小解,于 。
J a c o b i 迭 代 法 的 迭 代 矩 阵 为
1
0 2 2
1 0 1
2 2 0
B I D A
3
1 2 3
22
1 1 0
22
0,( ) 0 1,
Ja c obi
IB
B
其 特 征 方 程 为因 此 有 于 是所 以 迭 代 法 收 敛 。
1
1
2
1 2 3
1 0 0 1 0 0
1 1 0 ( ) 1 1 0
2 2 1 0 2 1
1 0 0 0 2 2 0 2 2
( ) 1 1 0 0 0 1 0 2 3
0 2 1 0 0 0 0 0 2
22
0 2 3 ( 2) 0
0 0 2
0,2,( ) 2 1,
D L D L
M D L U
IM
M
特 征 方 程特 征 值 为 故 所 以 迭 代 发 散 。
1G a u s s - S e i d e l ( ),M D L U迭 代,由
0 2
1
12
1,
1,1
B
M
上例说明了 确实只是松弛法收敛的必要条件，而非充要条件，因为Gau ss- Sei del
迭代记为 的情形。
判断定理虽然给出了判别迭代收敛的充要条件，但要求逆矩阵和特征值。推论 与 仅分别给出了收敛的充分与必要条件，许多情形下不能起作用。如上例，两个方法均有由推论 无法判别收敛性。
对一些特殊的系数矩阵可给出几个常用的判别收敛条件
1
11 12
11 22
22
( ) ( 1,2,,)
,
0
1 1 0
1 1
n
ij ii ij
j
ji
n A a a a i n
iA
iA
A
AA
A A A A
A
A
严弱对 角 占定 义,若 阶 方 阵 满 足且 至 少 有 一 个 值,使 上 式 中 不 等 号 严 格 成 立,则 称 为
。 若 对 所 有,上 式 不 等 号 均 严 格 成 立,则 称为 。
定 义,如 果 矩 阵 不 能 通 过 行 的 互 换 和 相 应 的 列 互 换 成为 形 式 其 中,为 方 阵,则格 对 角 占 优 阵称 为 。
例,
约优 阵不 可
13
2 1 0
0 0 1 1
0 1 2 0 1 1
PI T
P A P
,
1.
Jac obi G a uss - S e i de l
2,0 1,
3.
02
10 1 2 2 1 0
1 10 2 1 2 1
1 1 5 0 1 2
Ax b
A
A
A
AB
A
设 有 线 性 方 程 组 下 列 结 论 成 立 （ ）
若 为 严 格 对 角 占 优 阵 或 不 可 约 弱 对 角 占 优 阵,则迭 代 法 和 迭 代 法 均 收 敛 。
若 为 严 格 对 角 占 优 阵,则 松 弛 法 收 敛 。
若 为 对 称 正 定 阵,则 松 弛 法 收 敛 的 充 要 条 件 为
。
收 敛 充上 两 例 中,
为分 条 件严 格 对 角
B
占 优 阵,故 Jacobi 与 Gauss-Seidel 迭代 均 收 敛 。 为 非 严 格 对 角 占 优 阵,但 为 对 称 正 定阵,=1.4 故 松 弛 法 收 敛 。
-1
11
1
22
11
,1
22
11
1
22
3 ( 0 2)
1
11
0
22
11
- 0
22
11
0
22
Ax b A
AA
A
B I D A
例,讨论用三种迭代法求解的收敛性。
解：因 为对称且其各阶主子式皆大于零，故 为对称正定矩阵。由判别条件,G aus s-S eid el迭 代法与松弛法均收敛。 不是弱对角占优阵，故不能用条件 判断。
Jacobi 迭代法的迭代矩阵为
3
2
1 2 3
11
22
1 1 3 1
2 2 4 4
11
22
1
( ) ( 1 ) 0
2
1
,1,( ) 1
2
IB
B
Jaco b i
其特征方程得 因而迭代法不收敛。
3 10
,
94
10 10
00
33
,
9 15
00
42
30 15
( ),( )
22
Ax b A
J ac obi Gaus s Se i de l
BM
BM
改变方程组中方程的次序，即将系数矩阵作行交换，会改变迭代法的收敛性。
例：
与 迭代的迭代矩阵分别为谱半径分别是 。均不收敛。
''
'
' ' '
,
3 1 0 9 4
9 4 3 1 0
A x b
A x b
AA
A A x b
J a c o b i G a u ss S e id e l
若交换方程的次序，得 的同解方程组为严格对角占优阵，因而对方程组 用与 迭代求解均收敛。
六,误差估计
( 1 ) ( )
( ) *
( ) * ( 1 ) ( 0 )
1*
*1
( ) * ( 1 ) * ( 0 ) *
,1,
,
1
( ) 1,0,
)
)
( ) ( )
kk
k
k
k
k k k
x Mx g M
xx
M
x x x x
M
M M I M
I M x Mx g x
x I M g
x x M x x M x x
( 先 验定 理,设 有 迭 代 格 式 若收 敛 于 则 有 误 差 估 计 式证,因 故 于 是
( 存 在,方 程 组 有 唯 一 解,
且 ( 有估
。 从 而计 ）
( 0 ) 1
1 ( 0 )
1 ( 0 ) 1
[ ) ]
) [ ) ]
) [ ]
k
k
k
M x I M g
M I M I M x g
M I M x x
（ ）
(
((
(
( ) * 1 ( 0 ) 1
1
11
11
1
1
( ) *
)
) )
) )
) )
)
1
)
1
1
k
k
k
k
x x M I M x x
I M I M I
I M I M I M
I M I M I M
I M I M
IM
M
M
xx
（）
取范数 (
又因为 ( (
((
取范数 ( (
(
移项得 (
代入得
( 1 ) ( 0 )
xx
M
。
( ) * ( 1 ) ( 0 )
( 1 ) ( 0 )
1
:
( 1 )
ln
ln
k
k
M
x x x x
M
M
xx
k
M
k
根 据 事 先 给 定 的 精 度,可 估 计 出 迭由 误 差 估 计数式代 的 次
( 0 ) ( 1 )
4 ( 1 ) ( 0 )
0 0,1 0,2 0 7,2
0,1 0 0,2,0,8,3
0,2 0,2 0 0 8,4
1 0,0,4,8,4
1 2,9 3 2,1 3
M x x
M x x
k
－
例,若则 有即 需 要 迭 代 次 才 能 满 足 精 度 。
( 1 ) ( )
( ) *
( ) * ( ) ( 1 )
( ) * ( 1 ) * ( 1 ) 1
1 ( 1 ) ( 1 ) 1 ( 1 ) ( )
( ) * 1 (
,1,
,
1
( ) [ ) ]
) [ ] ) ( )
)
kk
k
k k k
k k k
k k k k
kk
x Mx g M
xx
M
x x x x
M
x x M x x M x I M g
M I M x Mx g M I M x x
x x M I M x
,设 有 迭 代 格 式 若收 敛 于 则 有 误 差 估 计 式证,因
（ 事 后 估 计 ）
((
(
定 理
(
1 ) ( )
( ) ( 1 )
( ) ( 1 )
1
1
.
k
kk
kk
Mx
x
M
xx
M
x?
当 不 太 接 近 时,可 用 作 为 停 机 准 则 。
