第六章 逐次逼近法
6.5 迭代法的加速§
6.5 迭代法的加速§
无论是解线性方程组的 Jacobi迭代法和 G— S迭代法
还是解非线性方程 Newton系列迭代法
都涉及到收敛速度问题
如何加快迭代法的速度呢 ？
也涉及到初值的选取问题
如何改善迭代法的适用范围呢 ？
i
ii
n
ij
k
jij
ii
i
j
k
jij
ii
k
i baxaaxaax
111
1
)(
1
1
)1()1( +??= ∑∑
+=
?
=
++
一 、 线性方程组迭代法的加速
考虑解线性方程组的 Gauss-Seidel迭代法
∑∑
+=
?
=
+ ??=
n
ij
k
jij
ii
i
j
k
jij
ii
i
ii
xaaxaaba
1
)(
1
1
)1( 111
)()(
1
1
)1( 111 k
i
n
ij
k
jij
ii
i
j
k
jij
ii
i
ii
xxaaxaaba +??= ∑∑
=
?
=
+
)(1 )(
1
1
)1()( ∑∑
=
?
=
+ ??+=
n
ij
k
jij
i
j
k
jiji
ii
k
i xaxabax
------(1)
令 )()1()( kikiki xxr ?= +
)(1 )(
1
1
)1( ∑∑
=
?
=
+ ??=
n
ij
k
jij
i
j
k
jiji
ii
xaxaba
的改变量次迭代时为第 xkr ki 1)( +
)()()1( k
i
k
i
k
i rxx +=
+因此
得前加一个因子在改变量 ),20(,)( << wwkir
)()()1( k
i
k
i
k
i rxx w+=
+
)( )(
1
1
)1()( ∑∑
=
?
=
+ ??+=
n
ij
k
jij
i
j
k
jiji
ii
k
i xaxabax
w
------(2)
得在上式中合并 ,)( kix
)()1(
1
)(
1
1
)1()()1( ∑∑
+=
?
=
++ ??+?=
n
ij
k
jij
i
j
k
jiji
ii
k
i
k
i xaxabaxx
ww
LL ,2,1,0,,2,1 == kni ------(3)
上式称为 逐次超松弛法 (SOR迭代法 ), 称为松弛因子w
G
k
G
k fxBx +=+ )()1(
bLDUxLD k 1)(1 )()( ?? ?+?=
bUxxLD kk +=? + )()1()(
由 G-S迭代法的矩阵形式
------(4)
)()1()( kkk xxr ?= +
)()()1( kkk rxx w+=+
bUxLxDx kkk ++= ++ )()1()1(
bDUxDLxDx kkk 1)(1)1(1)1( ??+?+ ++=
bDUxDLxDxx kkkk 1)(1)1(1)()( ??+? +++?=
bDUxDLxDx kkk 1)(1)1(1)( ??+? +++?=
)()1( 1)(1)1(1)( bDUxDLxDx kkk ??+? +++?= ww
------(5)
的改变量次迭代时第 xk 1+
w前加上因子在 )( kr
)()1( )()1()()1( bUxLxDxDx kkkk +++?= ++ ww
bxUDxLD kk wwww ++?=? + )()1( ))1(()(
bLDxUDLDx kk 1)(1)1( )())1(()( ??+ ?++??= wwwww ----(6)
上式为逐次超松弛法 (SOR迭代法 )的矩阵形式
))1(()( 1 UDLDB wwww +??= ?
bLDf 1)( ??= www
令
ww fxBx
kk +=+ )()1( ----(7)
法的迭代矩阵为 SORBw
,1时当 =w SOR法化为
bLDUxLDx kk 1)(1)1( )()( ??+ ?+?= G-S迭代法
G-S法为 SOR法的特例 , SOR法为 G-S法的加速
例 1. 用 G-S法和 SOR法求下列方程组的解 , 45.1=w取
??
?
?
?
??
?
?
?
??
??
??
321
242
124
??
?
?
?
??
?
?
?
3
2
1
x
x
x
??
?
?
?
??
?
?
?
?=
3
2
0
要求精度 1e-6
解 : (1)G-S迭代法
GB ULD
1)( ??=
1
321
042
004 ?
??
?
?
?
??
?
?
?
??
?=
??
?
?
?
??
?
?
?
000
200
120
??
?
?
?
??
?
?
?
=
5.03/10
625.025.00
25.05.00
f bLD 1)( ??=
1
321
042
004 ?
??
?
?
?
??
?
?
?
??
?= ???
?
?
??
?
?
?
?
3
2
0
??
?
?
?
??
?
?
?
?=
3/2
5.0
0
)',0,0()0( ０取初值 =x gauss_seidel.m
[x,k]=gauss_seidel(a,b,[1,1,1]',1e-6)
1 1 1
0.7500000 0.3750000 1.5000000
0.5625000 0.5312500 1.5416667
0.6510417 0.5963542 1.6145833
0.7018229 0.6582031 1.6727431
……………………………………….
0.9999933 0.9999923 1.9999926
0.9999943 0.9999935 1.9999937
0.9999952 0.9999944 1.9999946
k = 71
x=
0.999995
0.999994
1.999995
满足精度的解
迭代次数为 71次
(1)SOR迭代法
1 1 1
0.6375000 0.0121875 1.3199063
0.2004270 0.3717572 1.3122805
0.6550335 0.5340119 1.6922848
0.7058468 0.7733401 1.7771932
………………………………………..
0.9999990 0.9999976 1.9999991
0.9999984 0.9999993 1.9999989
0.9999998 0.9999994 1.9999998
0.9999996 0.9999998 1.9999997
k = 24
x=
1.000000
1.000000
2.000000
满足精度的解
迭代次数为 24次
bLDxUDLDx kk 1)(1)1( )())1(()( ??+ ?++??= wwwww
sor.m
SOR法的收敛速度比 G-S法要快得多,w选取适当的
SOR法都收敛吗 ？
1.SOR迭代法收敛的充要条件是
对于 SOR迭代法 (7),有如下结论
1)( <wr B ----(8)
|1|)( ?≥ wr wB由于 (此结论的证明较复杂 ), 因此有
法收敛的必要条件是即 SOR20,1|1|.2 <<<? ww
,,20,.3 )0(xA 对任意初值且为对称正定矩阵若矩阵 << w
法均收敛SOR
收敛对任意初值为对称正定矩阵若矩阵 )0(,.4 xSGA ?
另外 ,松弛因子的选取是很困难的 ,一般采用试算进行
二 、 非线性方程迭代法的加速
对于迭代法 )(1 kk xx j=+
)(1 kkkk xxxx j+?=?+
kkk xxr ?= +1
kkkk rxx w+=+1 ))(( kkkk xxx jw +?+=
)()1(1 kkkkk xxx jww +?=+
)( kk xx j+?=
上式的迭代函数 )()1()( xxx wjwy +?=
)()1()( xx jwwy ′+?=′ 0=
令 迭代改变量
kw加入因子
即 的加权平均 与 )( kk xx j
求导并令
----(9)
)(1
1
xjw ′?=
)(1
1
k
k xjw ′?=
)()1(1 kkkkk xxx jww +?=+
得
因此有 松弛迭代法 :
--------(10)
??
?
从后面的例子可以看出 ,加速效果是明显的
甚至一些不收敛的迭代法经过松弛加速后也能收敛
),( kxj′要计算松弛法的每一步迭代都 不方便
*,)( xxx 的精确解为假设方程 j= 0x初值为
)( 01 xx j= )( 12 xx j=
22 ** xxxx ?+= )(*)( 12 xxx jj ?+=
)*)(( 12 xxx ?′+= xj 中值定理
)*()()( 1
01
01
2 xxxx
xxx ?
?
?+≈ jj
差商近似代替导数
)*(* 1
01
12
2 xxxx
xxxx ?
?
?+≈
即
得解出 *,x
012
2
12
2 2
)(*
xxx
xxxx
+?
??≈
于是可以得到迭代格式 :
)( 01 xx j= )( 12 xx j=其中
)()1( kk xx j=
)( )1()2( kk xx j=
kkk
kk
kk xxx
xxxx
+?
??=
+ )1()2(
2)1()2(
)2(
1 2
)(
L,2,1,0=k
??
?
-------(11)
上组公式称为 Altken公式或 Altken加速
将 (11)式综合后可得一个解析式表示的迭代法 :
kkk
kk
kk xxx
xxxx
+?
??=
+ )(2))((
)]())(([))(( 2
1 jjj
jjjjj ----(12)
上式称为 Steffensen迭代法
Altken公式与 Steffensen公式是等价的
加速效果也是很明显的
例 2中将比较不同加速方法
例 2. 对迭代格式 3 1
3
1
+=
+
k
k
xx
进行加速解方程组 0133 =+? xx
6
0 10,5.0
?= 精确到初值 x
解 :
x0 = 0.5
x1 = 0.375
x2 = 0.3509115
x3 = 0.3477369
x4 = 0.3473496
x5 = 0.3473028
x6 = 0.3472971
x7 = 0.3472964
3
13
1
+=
+
k
k
xx
(1)直接使用迭代格式
迭代 7次 ,得到满足精度的解
347296.0=x
(2)对迭代格式进行松弛加速
21
1
k
k x?=w
)1(3
13
2
23
k
kk
x
xx
?
+?=
3
1)( 3 += xxj 2)( xx =′j
)()1(1 kkkkk xxx jww +?=+
x0 = 0.5
x1 = 0.3333333
x2 = 0.3472222
x3 = 0.3472964
x4 = 0.3472964
迭代 4次 ,得到满足精度的解
347296.0=x
(3)对迭代格式进行 Altken加速 (11)式
3
13)1( += k
k
xx
x0 = 0.5
x1 = 0.3451613
x2 = 0.3472961
x3 = 0.3472964
迭代 3次 ,得到满足精度的解
347296.0=x
从以上 3种结果可见 ,迭代法加速技术效果比较明显
5.1)4( 0 =x如果将初值改为
3
13
1
+=
+
k
k
xx迭代格式 显然不收敛
3
1)( 3)1()2( += k
k
xx
kkk
kk
kk xxx
xxxx
+?
??=
+ )1()2(
2)1()2(
)2(
1 2
)(
x0 = 1.5
x1 = 1.5350706
x2 = 1.5321124
x3 = 1.5320889
x4 = 1.5320889
迭代 4次 ,得到满足精度的解
532089.1=x
对迭代格式进行松弛加速 x = 1.5x = 1.5333333
x = 1.5320906
x = 1.5320889
x = 1.5320889
迭代 4次 ,得到满足精度的解
532089.1=x
对迭代格式进行 Altken加速
可见加速技术可能将不收敛的迭代法加速为收敛
希望同学们好好复习
争取考出水平 , 考出好成绩 !
