第六章 逐次逼近法
6.3 非线性方程的迭代法§
6.3 非线性方程的迭代法§
方程是在科学研究中不可缺少的工具
方程求解是科学计算中一个重要的研究对象
几百年前就已经找到
了代数方程中二次至
五次方程的求解公式
但是 ,对于更高次数
的代数方程目前仍
无有效的精确解法
对于无规律的非代数方程的求解也无精确解法
因此 ,研究非线性方程的数值解法成为必然
0)( =xf设非线性方程 --------(1)
0*)(*, =xfx 使得如果存在一点
的根或零点为方程则称 )1(*x
上只有一个根 ，在区间如果方程 ],[)1( ba
为单根区间则称 ],[ ba
上有多个根 ，在区间如果方程 ],[)1( ba
为多根区间则称 ],[ ba
本节主要研究单根区间上的求解方法
一 、 简单迭代法 (基本迭代法 )
--------(2)
将非线性方程 (1)化为一个同解方程
)( xx j=
为连续函数并且假设 )( xj
得的右端代入任取一个初值 ,)2(,0x
)( 01 xx j=
)( 12 xx j=
)(1 kk xx j=+
继续
KKK
--------(3)),2,1,0( L=k
称 (3)式为求解非线性方程 (2)的 简单迭代法
步迭代值为第称为迭代函数称 kxx k,)(j
满足使得迭代序列如果存在一点 ∞0}{*, kxx
*lim xxk
k
=
∞→
则称迭代法 (3)收敛 ,否则称为发散
--------(4)
012* xxxxO
)( xy j=
xy =
0231 * xxxxxO
)( xy j=
xy =
如果将 (2)式表示为 )( xy j= xy =??? 与方程 (2)同解
收敛
附近较平缓在 *)( xxj
例 1. 012 3 =?? xx用迭代法求解方程
解 :
12 3 ?= xx
(1) 将原方程化为等价方程
得由迭代法如果取初值 ),3(,00 =x
*012 xxxxO
)( xy j= xy =
2013 * xxxxxO
)( xy j=
xy =
发散
附近较陡峭在 *)( xxj
12 301 ?= xx 1?=
12 312 ?= xx 3?=
12 323 ?= xx 55?=
00 =x
KKK
显然迭代法发散
3
2
1+= xx
(2) 如果将原方程化为等价方程
00 =x
3 01
2
1+= xx
仍取初值
3
2
1= 7937.0≈
3 12
2
1+= xx 3
2
7937.1= 9644.0≈
x2 = 0.9644
x3 = 0.9940
x4 = 0.9990
x5 = 0.9998
x6 = 1.0000
x7 = 1.0000
依此类推 ,得
已经收敛 ,故原方程的解为
0000.1=x
同样的方程
不同的迭代格式
有不同的结果
什么形式的迭代法
能够收敛呢 ?
迭代函数的构造有关
定理 1. 且满足上连续在设迭代函数 ,],[)( baxj
;)(,],[)1( bxabax ≤≤∈ j时当
有且满足存在一正数 ],,[,10,)2( baxLL ∈?<<
Lx ≤′ |)(|j
*],[)(.1 xbaxxo 内有唯一解在方程则 j=
*)(],,[.2 10 xxxbax kko 均收敛于迭代法对于任意初值 j=∈ +
11*.3 ???≤? kkk
o xx
L
Lxx
011*.4 xxL
Lxx k
k
o ?
?≤?
--------(5)
--------(6)
--------(7)
(局部收敛性 )
证 :
由条件 (1)
),()( xxxf j?=设
)()( aaaf j?= 0≤
)()( bbbf j?= 0≥
上连续可导在则 ],[)( baxf
由根的存在定理 , 上至少有一个根在方程 ],[0)( baxf =
1|)(| <≤′ Lxj由
)(1)( xxf j ′?=′ 0>
,],[)( 上单调递增在则 baxf 上仅有一个根在 ],[0)( baxf =
*],[)(.1 xbaxxo 内有唯一解在方程所以 j=
),(.2 1 kko xx j=+对于迭代法
*1 xxk ?+ *)()( xxk jj ?= *))(( xxk ?′= xj
由微分中值定理
kk xx ?+ 1 )()( 1??= kk xx jj ))(( 1??′= kk xxxj
*1 xxk ?+ *xxL k ?≤
kk xx ?+1 1??≤ kk xxL
)(* 11 kkk xxxxL ???= ++
)(* 11 kkk xxLxxL ?+?≤ ++
kkk xxL
Lxx ?
?≤? ++ 11 1*
Lx ≤′ |)(|j由于
11* ???≤? kkk xxL
Lxx
21
2
1 ?? ??≤ kk xxL
L
KKK
011 xxL
Lk ?
?≤
,1<L由于 *)(lim xxkk ?∞→ 0=
*)(, 10 xxxx kk 均收敛于迭代法因此对任意初值 j=+
11* ???≤? kkk xxL
Lxx
011 xxL
Lk ?
?≤ 证毕 .
定理 1指出 ,
1|)(| <≤′ Lxj
e<?? ? 11 kk xxLL
由 (6)式 ,只要
因此 ,当 eL Lxx kk ?<? ? 11 e≈
迭代就可以终止 , 可以作为方程的近似解kx
只要构造的迭代函数满足
就收敛迭代法 )(1 kk xx j=+
e对于预先给定的误差限 e<? |*| xxk即要求
此时虽收敛但不
一定是唯一根
--------(8)
例 2. 用迭代法求方程的近似解 ,精确到小数点后 6位
0210 =?+ xe x
解 :
本题迭代函数有两种构造形式
10
2)(
1
xe
xx ?== j )102ln()(2 xxx ?== j
|)(| 1 xj ′ 10
xe
= |)(| 2 xj ′ x102 10?=
,0>xe由于 0102 >? x则 2.0<x
110
2.0
<< e
10
2)(
1
xe
xx ?== j因此采用迭代函数
,0时<x ,10 << xe 2102 >? x
为有根区间因此 ]2.0,0[
5≥由于
00 =x取初值
10
2 0
1
xe
x ?= 1.0=
d1 = 0.1000000
d2 = -0.0105171
d3 = 0.1156e-002
d4 = -0.1265e-003
d5 = 0.1390e-004
d6 = -0.1500e-005
d7 = 0.1000e-006
由于 |d7| =0.1000e-006<1e-6
因此原方程的解为 x7 = 0.090525≈*x
x1 = 0.1000000
x2 = 0.0894829
x3 = 0.0906391
x4 = 0.0905126
x5 = 0.0905265
x6 = 0.0905250
x7 = 0.0905251
由定理 1的 (7)式出 ,
,],[|)(| 上越小在或 baxL j ′
*xxe kk ?=设
迭代法收敛就越快
定义 1. 满足和若存在实数 01 >≥ cp
p
k
k
k e
e 1lim +
∞→ c=
时称为平方收敛称为超线性收敛
时时称为线性收敛当阶收敛则称迭代法
2,
1,1,
=
>=
p
ppp
收敛速度也就越快越大显然 ,, p
--------(9)
从而确定收敛阶呢 ？如何确定那么 ,, p 不可能直接确定
即处处可导处充分光滑在精确解如果迭代函数 ,*)( xxj
有展开作在将 ,*)( Taylorxxj
L+?′′+?′+= 2*)(!2 *)(*)*)((*)()( xxxxxxxx jjjj
L+?+??+ ?
?
p
p
p
p
xxp xxxp x *)(! *)(*)()!1( *)(
)(
1
)1( jj
0*)()1( == ? xpjL=′′=′ *)(*)( xx jj如果 0*)()( ≠xpj而
+= *)()( xx jj L+? p
p
xxp x *)(! *)(
)(j
定理 2.
)(1 kk xx j=+ L+?+= pk
p
xxp xx *)(! *)(*)(
)(j
j
p
k
p
xxp x *)(! *)(
)(
?= j*1 xxk ?+
p
k
k
xx
xx
*
*1
?
?+ L+?
++=
+
*)()!1( *)(! *)(
)1()(
xxp xp x k
pp jj
pxx kk 的收敛阶是即迭代法 )(1 j=+
附近满足 ：在根如果迭代法迭代函数 *)( xxj
阶导数切连续 ；存在 px)()1( j
,0*)()1( == ? xpjL=′′=′ *)(*)()2( xx jj 0*)()( ≠xpj而
pxx kk 的收敛阶是则迭代法 )(1 j=+
L+?++ +
+
1
)1(
*)()!1( *)( pk
p
xxp xj
)(,! *)(
)(
∞→→ kp x
pj
例 3. 证明迭代法重根的是方程设 ,)2(0)(* ≥= mxfx
)(
)(
1
k
k
kk xf
xfxx
′?=+
为线性收敛
证明 : 故重根的是方程因为 ,0)(* mxfx =
)(*)()( xgxxxf m?= 2,0*)( ≥≠ mxg且
所以 )(xf ′ )(*)()(*)( 1 xgxxxgxxm mm ′?+?= ?
)(*)()(*)(
)(*)(
1
k
m
kk
m
k
k
m
k
k xgxxxgxxm
xgxxx
′?+?
??=
?)(
)(
1
k
k
kk xf
xfxx
′?=+
)(*)()(
)(*)(
kkk
kk
k xgxxxmg
xgxxx
′?+
??=
*1 xxk ?+ ))(*)()( )(1*)((
kkk
k
k xgxxxmg
xgxx
′?+??=
*
*lim 1
xx
xx
k
k
k ?
?+
∞→ ))(*)()(
)(1(lim
kkk
k
k xgxxxmg
xg
′?+?= ∞→ m
11 ?=
011,2 >?≥ mm 时
重根是线性收敛的该迭代法对 )2(≥m
例 4. 证明迭代法且设 ,0)(,0)( ≠′= afaf
)(
)(
1
k
k
kk xf
xfxx
′?=+ 至少是平方收敛的
由定义 1
注意例 4与例 3的迭代法是相同的 ,两例有何区别 ?
证明 : 令 )( )()( xf xfxx ′?=j
)(xj′则 2
2
)]([
)()()]([1
xf
xfxfxf
′
′′?′?=
2)]([
)()(
xf
xfxf
′
′′?=
0)( =′ aj所以
由 定理 2 该迭代法至少是平方收敛的
二 、 Newton迭代法
如果将非线性方程 0)( =xf
)()( xfxkxx ?= 0)( ≠xk且
令 )()()( xfxkxx ?=j
)()()()(1)( xfxkxfxkx ′?′?=′j
,0)(* 的根为设 =xfx 则收敛速度越快附近越小在 ,*|)(| xxj′
化为等价方程
如果 0*)( ≠′ xf
*)(*)(*)(*)(1 xfxkxfxk ′?′? 0=
0*)( =′ xj令
*)(
1*)(
xfxk ′=
即
则
于是取 )(1)( xfxk ′=
)(
)()(
xf
xfxx
′?=j )(
)(
xf
xfxx
′?=
--------(10)
--------(11)
式构造迭代法由取初值 )11(,0x
)(
)(
1
k
k
kk xf
xfxx
′?=+ ),2,1,0( L=k --------(12)
(12)式称为 Newton迭代法
参见例 4 ， 可知 ,0*)( ≠′ xf只要
Newton迭代法至少平方收敛
局部收敛性
例 5. 用 Newton迭代法求方程的根 :
0133 =+? xx
解 : 13)( 3 +?= xxxf设
33)( 2 ?=′ xxf
由 Newton迭代法
)(
)(
1
k
k
kk xf
xfxx
′?=+
得取初值 ,5.00 =x
x0 =0.5;
x1 =0.3333333333
x2 =0.3472222222
x3 =0.3472963532
x4 =0.347296355333
13
2
3
?
+??=
k
kk
k x
xxx
迭代四次 精度达 10-8
1+kx
*x
)( xfy =
kx
Newtonddf.m
)(
)(
1
k
k
kk xf
xfxx
′?=+Newton迭代法
需要求每个迭代点处的导数 )( kxf ′ 复杂 ！
得中的近似替代用 ,)(0 kk xxfx ′
)(
)(
0
1 xf
xfxx k
kk ′?=+
--------(12)
--------(13)
这种格式称为 简化 Newton迭代法 精度稍低
)( kxf ′如果用数值导数代替
1
1 )()()(
?
?
?
?≈′
kk
kk
k xx
xfxfxf
三 、 Newton迭代法的变形
则 Newton迭代法变为
)()()( )( 1
1
1 ?
?
+ ???= kk
kk
k
kk xxxfxf
xfxx --------(14)
这种格式称为 弦截法 收敛阶约为 1.618
1+kx
1
1 )()(,
?
?
?
?=
kk
kk
AB xx
xfxfKAB的斜率为如图
1
1 )()(tan
?
?
?
?=
kk
kk
xx
xfxfa
*x
)( xfy =
1?kx
kx
A
B
a)(
)()(
)(
1
1
1 ?
?
+ ???= kk
kk
k
kk xxxfxf
xfxx
)(cot kk xfx ??= a
)(cot kxf?a
几何意义
例 6. 用简化 Newton法和弦截法解例 (5)中方程的根 ，
0133 =+? xx
解 : 13)( 3 +?= xxxf设 33)( 2 ?=′ xxf
由简化 Newton法
)(
)(
0
1 xf
xfxx k
kk ′?=+ 33
13
2
0
3
?
+??=
x
xxx kk
k
并和 Newton 迭代法比较
由弦截法
)()()( )( 1
1
1 ?
?
+ ???= kk
kk
k
kk xxxfxf
xfxx
Newtonddf.m
x0=0.5
x1= 0.3333333333
x2 = 0.3497942387
x3 = 0.3468683325
x4 = 0.3473702799
x5 = 0.3472836048
x6 = 0.3472985550
x7 = 0.3472959759
x8 = 0.3472964208
x9 = 0.3472963440
x10 = 0.3472963572
x11 = 0.3472963553
x0=0.5;
x1=0.4;
x2 = 0.3430962343
x3 = 0.3473897274
x4 = 0.3472965093
x5 = 0.3472963553
x6 = 0.3472963553
简化 Newton法 由弦截法
要达到精度 10-8
简化 Newton法迭代 11次
弦截法迭代 5次
Newton迭代法 迭代 4次
无论前面哪种迭代法 ：
Newton迭代法 简化 Newton法 弦截法
0)arctan()( == xxf 0=x精确解为
Newton迭代法 )1(arctan 21 kkkk xxxx +??=+
10 =x取初值
x0 = 2
x1 = -3.54
x2 = 13.95
x3 = -279.34
x4 = 122017
是否收敛均与初值的位置有关
如
20 =x若取初值
x0 =1
x1 = -0.5708
x2 = 0.1169
x3 = -0.0011
x4 = 7.9631e-010
x5 = 0
收敛 发散
|)(||)(|: 1 kk xfxf <+入要求如果在构造迭代法时加
建立迭代法因此考虑引入一因子 ,l
)(
)(
1
k
k
kk xf
xfxx
′?=+ l
使得选择一个在迭代时 ,, l
|)(||)(| 1 kk xfxf <+
--------(15)
这种方法称为 Newton下山法 ， 称为下山因子l
的选取方式l 的顺序，，，，按 L32 2121211=l
成立为止直到 |)(||)(| 1 kk xfxf <+
例 7. 99.0,
3)( 0
3
?=?= xxxxf 取初值求解方程
5
1 10||
?
? ≤? nn xx
解 : 1.先用 Newton迭代法 1)( 2 ?=′ xxf
)(
)(
1
k
k
kk xf
xfxx
′?=+ )1(3
3
2
3
?
??=
k
kk
k x
xxx
)1(3
3
2
0
0
3
0
01 ?
??=
x
xxxx 50598.32?=
)1(3
3
2
1
1
3
1
12 ?
??=
x
xxxx 69118.21?=
15689.15=
x4 = 9.70724
x5 = 6.54091
x6 = 4.46497
x7 = 3.13384
x8 = 2.32607
x9 = 1.90230
x10= 1.75248
x11= 1.73240
x12= 1.73205
x13= 1.73205)1(3
3
2
2
2
3
2
23 ?
??=
x
xxxx
迭代 13
次才达
到精度
要求
Newtonddf.m
2.用 Newton下山 法 ,结果如下
k=0 x0 =-0.99 fx0 =0.666567
k = 1 x1 =32.505829 f(x) = 11416.4
w =0.5 x1 =15.757915 f(x) = 1288.5
w =0.25 x1 =7.383958 f(x) =126.8
w =0.125 x1 =3.196979 f(x) =7.69
w = 0.0625 x1 =1.103489 f(x)=-0.655
k = 2 x2 = 4.115071 f(x) =19.1
w = 0.5 x2 = 2.60928 f(x)=3.31
w =0.25 x2 =1.85638 f(x)=0.27
k = 3 x3 =1.74352 f(x)=0.023
k = 4 x4 = 1.73216 f(x)=0.00024
k = 5 x5 = 1.73205 f(x)=0.00000
k = 6 x6 = 1.73205 f(x)=0.000000
)( kk xfxk 下山因子
的根0)arctan()( == xxf考虑方程
fc4.m和 dfc4.m
Newtonddf.m
实验 ：
四 、 多根区间上的逐次逼近法
上根的情形在区间方程 ],[0)( baxf =
有唯一根
有多根 所有根均为单根
有重根
用迭代法求解
的多个根均为单根在区间 ],[0)(.1 baxf =
,],[0)( 个单根上有在设 mbaxf = 个小区间分成将 nba ],[
],[,],,[],,[ 12110 nn bbbbbb ?L
然后在每个区间上判断是否有根
nibf i ,,2,1,0)( L=的值 ，计算
1,,2,1,0,0)()(0)( 1 ?=<= + nibfbfbf iii L是否成立或判断
若成立
就是一个根ib 中至少有一个根],[ 1+ii bb
统计根的个数
,个如果根的个数正好是 m 则所有的有根区间均为单根区间
,个如果根的个数小于 m 则继续对分区间 ,并重新判断
直到找到所有根的所在区间
然后在每个有根区间进行求根
,],[ 为单根区间假设区间 dc
)(210 dcx +=取其中点
,0)( 0 =xf若 中的根就是 ],[0 dcx
,0)()( 0 <? xfcf若 ,],[ 0 为有根区间则 xc 011 , xdcc ==令
,0)()( 0 <? dfxf若 ,],[ 0 为有根区间则 dx ddxc == 101 ,令
长度只有一半就缩小为于是有根区间 ],,[],[ 11 dcdc
),(21],[ 11111 dcxdc +=的中点继续取
可得一系列的小区间和中点
],[,],,[],,[],,[ 221100 nn dcdcdcdc L
nxxxx ,,,, 210 L
小区间
中点
显然每个小区间都有单根
)( nn cd ? )(21 cdn ?=
|| 1?? nn xx )(21 1 cdn ?= +
可得任意要求的精度确定适当的 ,n
)(21 nnn dcx += L,2,1,0=n
搜索法 — 二分法
例 8. 的三个根求方程 0769.4179.381.11 23 =?+? xxx
解 : 769.4179.381.11)( 23 ?+?= xxxxf设
769.41)0( ?=f由于 1.236)10( ≈f
可知方程的解在区间 [0,10]内
将区间 [0,10]等分成三等份
[0,3.33]
[3.33,6.67]
[6.67,10]
769.41)0( ?=f
24.1)33.3( ≈f
87.19)67.6( ≈f
1.236)10( ≈f
[0,3.33]内至少有一个根
[5,6.67]
[3.33,5]
32.0)5( ?≈f
87.19)67.6( ≈f
将 [3.33,6.67]再分成两个区间
24.1)33.3( ≈f
[5,6.67]内至少有一个根
[3.33,5]内至少有一个根
[0,3.33] [5,6.67][3.33,5]
因此找到了三个有单根的区间
769.41)0( ?=f 24.1)33.3( ≈f 87.19)67.6( ≈f32.0)5( ?≈f
39.3)66.1( ?≈f 52.0)17.4( ?≈f 36.5)84.5( ≈f
10.21 ≈x 90.32 ≈x 1.53 ≈x依此类推结果为
对分
0===== L
有重根在区间 ],[0)(.2 baxf =
2*,],[0)( ≥= mxmbaxf 重根有在区间
)(*)()( xgxxxf m?=因此可令 0*)( ≠xg且
*)(xf ′*)( xf *)()1( xf m ?*)(xf ′′故有
0*)()( ≠xf m且
由例 3.
)(
)(
1
k
k
kk xf
xfxx
′?=+对于 Newton迭代法 趋于零
,0)( ≠′ kxf即使 Newton迭代法 也只是线性收敛
此时 Newton迭代法 可能不收敛
)(
)()(
xf
xfmxx
′?=j考察函数 处的导数在 *x
0*)( =′ xf由于 处的导数在所以不能直接求 *)( xxj
而应该用定义求导
h
xhxf hxfmhx
h
xhx *)*(
)*(*
*)()*( ?+′
+?+
=?+ jj
)*(
)*(1
hxf
hxf
h
m
+′
+?=
)(*)()!1(*)(*)(
)(*)(!*)(*)(
1
)(
1
1)(
mm
m
mm
m
hOxfmhxfhxf
hOxfmhxfhxf
h
m
+?++′′+′
+++′+
?= ?
+
L
L
Tailor展开
)(*)()!1(
)(*)(!
1
)(
1
1)(
mm
m
mm
m
hOxfmh
hOxfmh
h
m
+?
+
?= ?
+
))(1(1 hOmhhm +?= )(hO= )0(0 →→ h
0*)( =′ xj所以
由 定理 2， 迭代法 )( )(1
k
k
kk xf
xfmxx
′?=+
至少是二阶收敛
