微分方程数值解
计算科学系 杨韧
椭圆型差分方程的迭代法
§ 3.8 椭圆型差分方程的迭代法
一、迭代法的基本理论
1、迭代公式
线性方程组 （ 3.45）
其中 A是 N阶非奇异矩阵,x,b均为 N维列向量。
将方程组改写为
的迭代公式 （ 3.47）
cGxx ??
?,1,0)()1( ???? ncGxx nn
bAx ?
椭圆型差分方程的迭代法
2、迭代的收敛性判断
定理 3.4 解方程组（ 3.45）的迭代格式（ 3.47）
对任意右端 c 及任意初始向量 X（ 0） 收敛的 充分必
要条件 为
推论 1 迭代格式（ 3.47）收敛的 充分条件 为
1m a x)( ?? i
i
G ??
1?G
椭圆型差分方程的迭代法
3、收敛速度
迭代公式
准确解满足
记解的误差向量
误差向量满足
?,1,0)()1( ???? ncGxx nn
cGxx ?? ??
?,1,0)()( ??? ? nxxe nn
?
?
? ???
初始误差向量—)0(
)()1(,1,0
e
nGee nn ?
椭圆型差分方程的迭代法
设迭代矩阵 G 有 N 个线性无关的特征向量 vi，分别
对应于特征值 λ i，且
由
得
N?????? ?21
?
?
?
N
i
ii vce
1
)0(
??
??
????
N
i
iii
N
i
ii vcGvcGee
11
)0()1(
??
??
?????
N
i
iii
N
i
iii vcGvcGee
1
2
1
)1()2(
椭圆型差分方程的迭代法
对于相当大的 n,有
则
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
??
??? ??
??
??
nn
n
n
n
n
N
i
i
n
ii
N
i
i
n
ii
nn
vcvcvc
vcGvcGee
1
22
1
2
111
11
1)1()(
?
?
?
?
?
??
?
11
1
1
)1(
111
)( vcevce nnnn ?? ????
)(1)(
)1(
G
e
e
n
i
n
i ????
?
椭圆型差分方程的迭代法
要求从第 n 步迭代到第（ n+p）步的误差减少为 e（ n）
的 10–q,即要求
)(1)2(21)1(1)( nppnpnpn eeee ??????? ????? ?
)(1)1( nn ee ???
pp
n
i
pn
i G
e
e ))((
1)(
)(
????
?
qpp G ????? 10))((
1
椭圆型差分方程的迭代法
两边去对数得
或
越小,越大，称
为迭代法的渐近收敛速度。
qGp ??? )(lg
)0)( l g ()(lg ????? GGqp
)(ln
10ln
G
qp
??
? 10
–q
0 x
pG ))((?
y
)(G? )(ln G??
)(ln)( GGR ???
椭圆型差分方程的迭代法
二,Jacobi 迭代和 Gauss-Seidel 迭代
方程组
A = D – L – R
bAx ?
?
?
?
?
?
?
?
?
?
?
?
nnn
n
aa
aa
A
?
??
?
1
111
?
?
?
?
?
?
?
?
?
?
?
?
?
nna
a
a
D
?
22
11
?
?
?
?
?
?
?
?
?
?
?
?
??
?
0
0
11
21
nnn
aa
a
L
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
0
0
1
112
nn
n
a
aa
R
?
??
?
椭圆型差分方程的迭代法
方程组写成
若, Jacobi 迭代格式 为
或
即
bxRLD ??? )(
bxRLDx ??? )(
),,2,1(0 Nia ii ???
bDxRLDx nn 1)(1)1( )( ??? ???
bxRLDx nn ???? )()1( )(
),,2,1(
1
1
)()1( Ni
a
b
xa
a
x
ii
i
N
ij
j
n
jij
ii
n
i ????? ?
?
?
?
椭圆型差分方程的迭代法
Gauss-Seidel 迭代法
或
即
迭代矩阵
bRxLxDx nnn ??? ?? )()1()1(
bLDRxLDx nn 1)(1)1( )()( ??? ????
),,2,1(
1
1
)(
1
1
)1()1(
Ni
a
b
xaxa
a
x
ii
j
N
ij
n
jij
i
j
n
jij
ii
n
i
??
?
?
?
?
?
?
?
?
?
??? ??
??
?
?
??
RLDG GS 1)( ??? )(1 RLDG J ?? ?
椭圆型差分方程的迭代法
三、椭圆型差分格式的 Jacobi 迭代和 Guass-Seidel 迭代
一般二阶线性椭圆型方程的五点差分格式
1,Jacobi 迭代格式（ 3.63）
2,Guass-Seidel 迭代格式 (3.64)
mlmlmlmlmlml ghUUUUU,
2
,01,41,3,12,11 ?????????? ????
)(1,2)( 1,4)( 1,3)(,12)(,11
0
)1(
,ml
n
ml
n
ml
n
ml
n
ml
n
ml ghUUUUU ?????????? ????
?
)(1,2)1( 1,4)( 1,3)1(,12)(,11
0
)1(
,ml
n
ml
n
ml
n
ml
n
ml
n
ml ghUUUUU ??????????
?
??
?
??
?
椭圆型差分方程的迭代法
3、收敛速度
考虑 Laplace方程的 Dirichlet条件问题
Jacobi 迭代矩阵的谱半径为
收敛速度为
? ?
??
?
?
?
???
?????
?
?
?
?
?
? ?
??
? ),(),(|
1,0|),(:),(0
2
2
2
2
yxyxfu
yxyxyx
y
u
x
u
)c o s ()( hG J ???
)c o s (ln)(ln)( hGGR JJ ??????
椭圆型差分方程的迭代法
由于
所以
Guass-Seidel 迭代矩阵的谱半径为
收敛速度为
)(21c o s 4
22
hOhh ?????
2
3
2
2
22
2
1lnc osln)(
22
3
22
2
2222
22
h
hhh
h
hGR
J
?
?
?
?
?
?
?
?
?
?
? ?
?
?
?
?
?
?
?
?
? ?
?
?
?
?
?
?
?
?
?
?
? ?
??????
?
? ? 2)()( JGS GG ???
22)(2)( hGRGR JGS ???
椭圆型差分方程的迭代法
例 1 利用五点差分格式近似 Laplcce方程的 Dirichlet问题
取步长 h=1，试用 Jacobi 迭代法求解,迭代误差限 ε =0.1。
?
?
?
?
?
?
?
?
?
???
???
????
?????
?
?
?
?
?
?
?
??
170100|
1700|
1000||
100,1700
10
0
170
2
2
2
2
xu
xu
yuu
yx
y
u
x
u
y
y
xx
椭圆型差分方程的迭代法
解 Jacobi 迭代法格式
dirichjac.m
lapjacobi
?
?
?
?
?
?
?
?
?
???
???
??
????
????
?
)17,,1,0(100,0
)16,,2,1(0
)9,,2,1;16,,2,1(
)(
4
1
10,0,
,17,0
)(
1,
)(
1,
)(
,1
)(
,1
)1(
,
?
?
??
lUU
mUU
ml
UUUUU
ll
mm
n
ml
n
ml
n
ml
n
ml
n
ml
运行结果 迭代次数 k = 89
迭代误差 err = 0.0992
椭圆型差分方程的迭代法
椭圆型差分方程的迭代法
椭圆型差分方程的迭代法
四、超松弛迭代法
1、逐次超松弛迭代法
方程组
当 时，逐次超松弛迭代格式为
（ 1）计算
(3.75.1)
ii
N
ij
n
jij
i
j
n
jiji
n
i axaxabx ??
?
?
??
?
?
??? ??
??
?
?
??
1
)(
1
1
)1()1(~
),,2,1(
1
Nibxa i
n
j
jij ????
?
0?iia
椭圆型差分方程的迭代法
（ 2）加权平均
(3.75.2)
或
即
矩阵形式
)~( )()1()()1( nininini xxxx ???? ??
)()1()1( )1(~ ninini xxx ????? ??
)()1( )()1(1)()1( bRxLxDxx nnnn ??????? ???
),,2,1(
)1(
1
)(
1
1
)1()()1(
Ni
abxaxaxx iii
N
ij
n
jij
i
j
n
jij
n
i
n
i
??
?
?
?
?
?
?
?
?
???????? ??
??
?
?
??
椭圆型差分方程的迭代法
记逐次超松弛迭代矩阵为
则 SOR迭代格式为
bDLDI
xRDILDIx nn
111
)(111)1(
)(
))1(()(
???
????
????
???????
bLD
xRDLDx nn
1
)(1)1(
)(
))1(()(
?
??
????
???????
?
? DD 1
?
? DD 1
?? DD 1
))1(()( 1 RDLDL ??????? ??
bLDxLx nn 1)()1( )( ?? ??? ???
椭圆型差分方程的迭代法
2、收敛性的判断
定理 3.5 SOR方法收敛的充分必要条件为
方程 的根
η 按模小于 1。
1)( ?? ?L
}))](())1d e t { [ ( (
}))1(()d e t { ()d e t (
1
1
?
?
?
???????????
???????????
LDLDRD
IRDLDIL
0)]}())1d e t { ( ( ????????? LDRD
????? 0)d e t ( IL
椭圆型差分方程的迭代法
定理 3.6 对所有 ω成立
证
即
故
1)( ???? ?L
)})1(()d e t { (d e t 1 RDLDL ??????? ??
?严格下三角 ?
严格上三角
)})1(()d e t { ( 111 RDILDI ??? ???????
N)1( ???
NN )1(21 ?????? ?
???? 1m a x 1)( ????? ?L
椭圆型差分方程的迭代法
由定理 3.5
SOR收敛的 必要条件 为, 若 A对称
正定,则 SOR收敛的 充分条件 为 。
为低超松弛因子,为超松弛因子,
, SOR是 G-S 迭代。
1)( ?? ?L
20 ???
1)(1 ?????? ?L
111 ??????
20 ???
1?? 1??
1??
椭圆型差分方程的迭代法
3、最佳松弛因子的确定
定义 使 的
称为最佳松弛因子。
)(m in)( ?
??
??? LL
opt
opt?
? ? )s i n (1
2
)(11
2
2 hG
J
opt ?
?
?
?
?
??
?
椭圆型差分方程的迭代法
例 2 利用五点差分格式近似 Laplcce方程的 Dirichlet问题
取步长 h=1，试用 Gauss-Seisel 迭代法最佳超松弛迭代法求
解,迭代误差限 ε =0.1。
?
?
?
?
?
?
?
?
?
???
???
????
?????
?
?
?
?
?
?
?
??
170100|
1700|
1000||
100,1700
10
0
170
2
2
2
2
xu
xu
yuu
yx
y
u
x
u
y
y
xx
椭圆型差分方程的迭代法
解
? ?
? ?
? ?
)(
,
)1(
1,
)(
1,
)1(
,1
)(
,1
)(
,
)(
,
)1(
,
)(
,
)(
,
)1(
,
)1(
,
)1(
1,
)(
1,
)1(
,1
)(
,1
)1(
,
4
4
1
~
)1(
~
4
1~
n
ml
n
ml
n
ml
n
ml
n
ml
n
ml
n
ml
n
ml
n
ml
n
ml
n
ml
n
ml
n
ml
n
ml
n
ml
n
ml
n
ml
UUUUUU
UUU
UUU
UUUUU
???????
???
???
????
?
??
?
??
?
??
?
??
?
??
?
?
?
??
椭圆型差分方程的迭代法
SOR 迭代法格式
?
?
?
?
?
?
?
?
?
?
?
???
???
??
?????
???
?
??
?
??
?
)17,,1,0(100,0
)16,,2,1(0
)9,,2,1;16,,2,1(
)4(
4
1
10,0,
,17,0
,
)1(
1,
)(
1,
)1(
,1
)(
,1,
,
)(
,
)1(
,
?
?
??
lUU
mUU
ml
UUUUUr
rUU
ll
mm
n
ml
n
ml
n
ml
n
ml
n
mlml
ml
n
ml
n
ml
椭圆型差分方程的迭代法
迭代按自然顺序
Dirichsor.m
lapsor.m
Jacobi Gauss-Seidel ω=1 SOR ω =1.5940
迭代次数 89 58 22
迭代误差 0.0987 0.0973 0.0816
l,m+1
l–1,m l,m l+1,m
l,m–1
椭圆型差分方程的迭代法
椭圆型差分方程的迭代法
上机作业 （ P.161）习题三 第 8题，要求,
（ 1） 用 Jacobi迭代法或 Guass-Seidel迭
代法编制程序；
（ 2）画解曲面图。