2004-11-22 1
第七章非线性方程求根
§7.0 简介
§7.1 二分法（对分法）
§7.2 迭代法的基本理论
§7.3 迭代的加速收敛方法
§7.4 Newton迭代法
§7.5弦割法和抛物线法
2004-11-22 2
§7.0简介一、问题求解非线性方程f(x)=0 ！
如多项式方程：
0)(
01
1
1
=++++=
axaxaxaxp
n
n
n
nn
L
困难：方程的解难以用公式表达。
需要一定精度的近似解！
2004-11-22 3
二、概念方程的解称为方程的根或称为的零点。若其中
m为正整数，满足，则显然这时称为的m重零点，或称为的m重根。
() 0=xf
*
x
( ) 0=xf
( )xf
() ( ) ()xgxxxf
m
*
=
( )xg
( ) 0≠xg ( ) 0
*
=xf
*
x
()xf
*
x
( ) 0=xf
定理：若有m阶连续导数，则是的m重零点的充要条件为：
( )xf
*
x
( )xf
0)(,0)()()(
*)(*)1(**
≠===
′
=
xfxfxfxf
mm
L
2004-11-22 4
概念（续）
证明：必要性设是的m重零点，则且
*
x
()xf
)()()(
*
xgxxxf
m
=
( ) 0
*
≠xg
[]
∑
=
=
k
i
ik
i
mi
k
k
xgxxcxf
0
)(
)(
*)(
)()()(
∑
=
+=
k
i
imimi
k
xgxximmmc
0
)(*
)())(1()1( L
0)(!
)())(1()1()(
*
0
*)(***)(
≠=
+=
∑
=
xgm
xgxximmmcxf
m
i
imimi
m
k
L
mk =
当时
10?≤≤ mk
0)())(1()1()(
0
*)(***)(
=?+=
∑
=
k
i
imimi
k
k
xgxximmmcxf L
当时
2004-11-22 5
概念（续）
充分性：
m
m
m
m
xx
m
xxxf
xx
m
xf
xxxfxfxf
)(
!
))((
)(
)!1(
)(
))(()()(
*
**
1*
*)1(
***
+
+?
++?
′
+=
θ
L
由Taylor公式得
10 <<θ
))((
!
1
)(
**)(
xxxf
m
xg
m
+= θ
)()()(
*
xgxxxf
m
=
0)(
!
1
)(
*)(*
≠= xf
m
xg
m
其中。令则有且
( ) 0
*
=xf
0)(,0)(,,0)(
*)(*)1(*
≠==
′
xfxfxf
mm
L
*
x
设使得，
*
x
)(xf
根据定义为的m重零点。
证毕
2004-11-22 6
三、根的隔离方程可能有多个实根，我们只能逐个求出来。
定义：设在区间[a,b]上方程有一个根，则称该区间为方程的一个有根区间。若在区间[a,b]上方程只有一个根，则称把方程的根隔离出来了。
Remark：若能把有根区间不断缩小，则可以得出根的近似值。
基于函数f(x)的连续性质，常用的根的隔离的方法有：函数作图法与试算法。
要找出方程的所有的根，要进行“根的搜索”。
返回
2004-11-22 7
§7.1二分法（对分法）
一、算法设在[a,b]上连续，f(a)f(b)<0且在[a,b]内f(x)=0
仅有一个实根。二分法的基本思想是：逐步将有根区间分半，通过判别函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求出满足给定精度的根的近似值。
)(xf
*
x
*
x
具体算法：
)(
2
1
111
bax +=
)(
1
xf
记[a,b]为[a
1
,b
1
]。将区间[a
1
,b
1
]分半，计算中点以及函数值。
1
*
xx =
若则。
0)(
1
=xf
2004-11-22 8
二分法（对分法）（续）
1212
,xbaa ==
否则，若有，则，令
],[
11
*
xax ∈0)()(
11
<afxf
或，则，令
0)()(
11
<bfxf
],[
11
*
bxx ∈
1212
,bbxa ==
再计算中点的函数值。],[
22
ba
2
22
2
ba
x
+
=
)(
2
xf
)(
2
1
)(
2
1
1122
ababab?=?=?
新的有根区间的长度],[
22
ba
],[
33
ba )(
2
1
)(
2
1
2
2233
ababab?=?=?
新的有根区间的长度令。
2323
,xbaa ==
2323
,bbxa ==
令
，或则，
0)()(
22
<bfxf
若则。否则则，
2
*
xx =0)(
2
=xf 0)()(
22
<afxf ],[
22
*
xax ∈
],[
22
*
bxx ∈
2004-11-22 9
二分法（对分法）（续）
如此对分下去则得到一系列的有根区间
LL ],[],[],[
2211 kk
bababa
)(
2
1
)(
2
1
1
11
ababab
k
kkkk
==?=?
L
且
L,2,1),(
2
1
)(
2
1
*
=?=?≤? kababxx
k
kkk
由及
2
kk
k
ba
x
+
=
当对分过程无限继续下去，则有根区间必收敛到一点，即
*
lim xx
k
k
=
∞→
2004-11-22 10
二分法（对分法）（续）
二、误差估计定理：给定方程f(x)=0，设f(x)在区间[a,b]上连续，且f(a)f(b)<0，则由二分法产生的序列
{x
k
}收敛于方程的根x
*
，且具有误差估计
),2,1()(
2
1
*
L=?≤? kabxx
k
k
2004-11-22 11
二分法（对分法）（续）
三、收敛准则
1.事先误差估计：
ε<?≤? )(
2
1
*
abxx
k
k利用误差估计定理，令得
2ln
ln)ln( ε
>
ab
k
从而得到对分次数k，取x
k
作为根得近似值x
*
。
2.事后误差估计：
给定ε，每步检查，或若成立，则取，否则继续对分。
k
xx ≈
*
ε<?≤?
)(
2
1
1
abxx
k
kk
ε<)(
k
xf
Remark：二分法的优点是方法及相应的程序均简单，
且对f(x)性质要求不高，只要连续即可。但二分法不能用于求复数根和偶数重根。
返回
2004-11-22 12
§7.2迭代法的基本理论一、不动点迭代法令方程,将其变成一个等价的方程,
构造,
0)( =xf
)(xx Φ=
L,1,0),(
1
=Φ=
+
kxx
kk
}{
k
x
称为迭代序列，
)(xΦ
称为迭代函数,
)(
1 kk
xx Φ=
+
称为迭代格式或迭代过程（迭代式），
)lim()(limlim
1 k
k
k
k
k
k
xxx
∞→∞→
+
∞→
Φ=Φ=
且当连续时，有或。
)(xΦ
即
)(
**
xx Φ= 0)(
*
=xf
即序列的极限为的根。
}{
k
x
*
x
0)( =xf
2004-11-22 13
不动点迭代法（续）
也称为不动点迭代法（也称简单迭代法或逐次逼近法）。
L,1,0),(
1
=Φ=
+
kxx
kk
求的零点就等价转化为求φ的不动点。
)(xf
由于的根满足，反之亦然。
0)( =xf
)(
**
xx Φ=
*
x
也称为的不动点。即映射关系φ将映射到本身。
*
x）（xΦ
*
x
*
x
Remark：可以通过不同的途径将f(x)=0化为
x=φ(x)的形式。
问题：如何选取合适的迭代函数φ(x)？
迭代函数φ(x)应满足什么条件，序列{x
k
}收敛？
怎样加速序列{x
k
}的收敛？
2004-11-22 14
二、不动点迭代法的一般理论定理1.（不动点定理）已知，满足
，且
)(xx Φ=
)(xΦ
),(],[)( baCbaCx
′
∩∈Φ
],[)( baxx在Φ=
*
x
1,上有唯一的不动点则
bxabax ≤Φ≤∈ )(],,[有
2,对任意
Lxbax ≤Φ
′
∈ )(),(有
1.存在常数0<L<1,使对任意
01
*
1
*
1
,
1
xx
L
L
xxxx
L
L
xx
k
kkkk
≤
≤?
}{
k
x3,有误差估计
*
x
L2,1,0),(),,(
110
=Φ=∈
++
kxxbax
kk
}{
k
x
2.对任意产生的序列必收敛到φ的不动点
2004-11-22 15
不动点迭代法的一般理论（续）
证明：
1.由于上连续，作辅助函数
],[)( bax在Φ
,)()( xxx?=?ψ
0)()(,0)()(],[)( ≤?=≥?=∈ bbbaaabaCx?ψ?ψψ且，则故由连续函数的介值定理，至少存在即存在φ的不动点
****
)(,0)(],[ xxxbax ==∈?ψ即使
*
x
又设
,1)(
),,()(],[,)(
*
2
*
1
<≤Φ
′
∈Φ∈Φ
Lx
baCxbaxxx
且
。注意有两个不动点
))(()()(
*
2
*
1
*
2
*
1
*
2
*
1
xxxxxx?Φ
′
=Φ?Φ=? ξ
00))(1(
*
2
*
1
*
2
*
1
=?=?Φ
′
xxxx，得ξ
,
*
2
*
1
xx =
)(xΦ
故由微分中值定理即有唯一的不动点。
2004-11-22 16
不动点迭代法的一般理论（续）
2.因
*
1
*
1
*
1
*
)()()( xxLxxxxxx
kkkk
≤?Φ
′
=Φ?Φ=?
ξ
*
1
xx
k
与
其中ξ介于之间，故有
LL 2,1,
*
0
*
1
*
=?≤≤?≤?
kxxLxxLxx
k
kk
因
。即],[,lim,0lim,1
0
**
baxxxxxL
k
k
k
k
∈?==?<
∞→∞→
2004-11-22 17
不动点迭代法的一般理论（续）
3.由
L,2,1),,(),(,
))(()()(
11
111
=?∈?≤
Φ
′
Φ?Φ=?
+
kbaxxxxL
xxxxxx
kkkk
kkkkkk
ξ
ξ
－－
＝
*
1
**
1
*
1
)()( xxxxxxxxxx
kkkkkk
≥=?
+++
**
1
xxLxx
kk
≤?
+
由结论2有故**
1
*
1
)1( xxLxxxxxx
kkkkk
≥≥?
++
即
11
*
11
1
+
≤?
≤?
kkkkk
xx
L
L
xx
L
xx
0121
2
*
11
xx
L
L
xx
L
L
xx
k
kkk
≤≤?
≤?
L
证毕
2004-11-22 18
不动点迭代法的一般理论（续）
Remark1：若φ(x)为定义在区间[a,b]上的函数，
且，均有φ(x)∈ [a,b]，则称φ(x)为区间[a,b]
自身上的一个映射。若φ(x)为区间[a,b]自身上的一个映射，且
],[ bax∈?
],[,,10
21
baxxL ∈?<<?
2121
)()( xxLxx?≤?φφ
则称φ(x)为区间[a,b]上的一个压缩映射，L为Lipschitz常数。关于压缩映射有如下结论：
（1）若φ(x)为区间[a,b]上的压缩映射，则称φ(x)必为区间[a,b]上的连续函数。
（2）若φ(x)为区间[a,b]自身上的映射，φ(x)∈C[a,b]
且，则φ(x)必是区间[a,b]上的一个压缩映射。1)( <≤
′
Lxφ
2004-11-22 19
不动点迭代法的一般理论（续）
Remark2：不动点定理还可以叙述为：若φ(x)为定义在区间[a,b]上的压缩映射，则φ(x)在区间[a,b]上存在唯一的不动点。
Remark3：不动点定理的两个误差估计式实际上给出了迭代收敛的两个准则：事后误差估计与事先误差估计（利用估计式预先求出迭代次数k）。
Remark4：由不动点定理知，若L≈1，则{x
k
}必然收敛较慢；若L<<1，则收敛速度快。
Remark5：不动点定理给出的是区间[a,b]上的收敛性，
称之为全局收敛性。（判定困难）
2004-11-22 20
三、局部收敛性及收敛阶
1,局部收敛性
（1）定义：若存在φ的不动点的闭邻域使对任意产生的迭
)0](,[)(
***
>+?= δδδ xxxN
L,2,1,0),(),(
1
*
0
=Φ=∈
+
kxxxNx
kk
迭代
*
x
代序列均收敛于，则称求的迭代法在附近局部收敛。
}{
k
x
*
x
*
x
L,2,1,0),(
1
=Φ=
+
kxx
kk
*
x
（2）局部收敛性的判别定理2.设为φ（x）的不动点，在的
*
x )(xΦ
′
*
x
某个邻域连续，且，则迭代式收敛。
1)( <≤Φ
′
Lx
2004-11-22 21
局部收敛性及收敛阶（续）
证明：
因连续，故存在使得，，
)(xΦ
′
)0](,[)(
***
>+?= δδδ xxxN
1)( <≤Φ
′
Lx )(
*
xNx∈
将前述定理1中的[a,b]取为迭代法收敛。
)(
*
0
xNx ∈
],[
**
δδ +? xx
则对任意
)(
*
xNx∈
故即对一切有。
δ<?≤Φ?Φ=?Φ
***
)()()( xxLxxxx
δδ +<Φ<?
**
)( xxx
Remark1：可以证明，若在根的邻域中，则可以以邻域内任何一点为初始值，用迭代过程产生的序列就一定不会收敛于。事实上，
*
x
1)( >Φ
′
x
0
x
*
x
*
0
*
1
*
1
*
1
*
))(()()( xxxxxxxxxx
kkkk
>?>?Φ
′
=Φ?Φ=?
ξ
Remark2：当不取在的邻域为内时可能不收敛。0
x
*
x
证毕
2004-11-22 22
局部收敛性及收敛阶（续）
2.收敛速度收敛速度是接近收敛的过程中迭代误差的下降速度。
（1）p阶收敛的定义设收敛于，令迭代误差
，如果存在实数及非零正常数C使得
）（
kk
xx Φ=
+1
*
)( xxx的根Φ=
*
xxe
kk
=
C
e
e
p
k
k
k
=
+
∞→
1
lim
（称为渐近误差常数）
1≥p
则称该迭代过程以及该迭代式是p阶收敛的。
若0<C<1,p=1称为线性收敛；p>1称为超线性收敛；
p＝2称为平方收敛（二次收敛）。p 越大，收敛速度越快；反之，p越小，收敛速度就越慢。
2004-11-22 23
局部收敛性及收敛阶（续）
（2）收敛速度的判别设迭代法满足全局收敛或局部收敛的条件，则。
）（
kk
xx Φ=
+1
*
lim xx
k
k
=
∞→
再设在[a,b]或x
*
的邻域中，
。0)( ≠
′
xφ
若取，必有
),2,1(,
*
L=≠ kxx
k
*
0
xx ≠
从而有
kkkk
exxxxe )()()(
**
11
ξφφφ
′
=?=?=
++
其中ξ介于x
k
与x
*
之间。
当时，由的连续性得，
∞→k
)(xφ
′ 0)(lim
*
1
≠
′
=
+
∞→
x
e
e
k
k
k
φ
故这种情况下迭代是线性收敛的。这启发我们，要得到超收敛的方法，迭代式必须满足。
0)(
*
=
′
xφ
2004-11-22 24
局部收敛性及收敛阶（续）
定理：迭代式的迭代函数的高阶导数（p>1）在不动点的邻域里连续，则迭代式为p
阶收敛的充要条件是
),1,0(),(
1
L=Φ=
+
kxx
kk
)( p
Φ
*
x
0)(,0)()()(,)(
*)(*)1(****
≠Φ=Φ=Φ
′′
=Φ
′
=Φ
xxxxxx
pp
L
)1)(1(0)(
!
1
lim
**)(
1
可证收敛要求<Φ
′
=≠Φ=
+
∞→
xpx
pe
e
p
p
k
k
k
且有证明：
充分性.对p>1，由于即满足在邻域具有局部收敛性的条件，故迭代式收敛。
0
*
=Φ
′
）（x
)(
1 kk
xx Φ=
+
*
x
2004-11-22 25
局部收敛性及收敛阶（续）
由
p
k
pp
k
p
kk
xx
p
xxx
p
xxxxx
))((
!
1
))((
)!1(
1
))(()()(
*)(1**)1(
***
Φ+?Φ
+
+?Φ
′
+Φ=Φ
ξ
L
之间，故与介于
*
xx
k
ξ
p
k
p
kk
xx
p
xxx )(
!
)(
)(
*
)(
*
1
Φ
+=Φ=
+
ξ
即为p阶收敛
0)(
!
1
lim
*)(1
≠Φ=
+
∞→
x
pe
e
p
p
k
k
k
)(
1 kk
xx Φ=
+
)(
!
1
)(
lim
*)(
*
*
1
x
pxx
xx
p
p
k
k
k
Φ=
+
∞←
－
故当p＝1时，
))(()()(
**
xxxx
kk
Φ
′
+Φ=Φ ξ
1)(lim
*
*
*
1
<Φ
′
=
+
∞→
x
xx
xx
k
k
k
即
2004-11-22 26
局部收敛性及收敛阶（续）
必要性：设迭代式为p 阶收敛，由收敛定义有也即。由邻域的连续性知。
*
lim xx
k
k
=
∞→
*
)(lim xx
k
k
=Φ
∞→
*
)( xx在Φ )(
**
xx Φ=
下面证明：0)(,0)()()(
*)(*)1(**
≠Φ=Φ==Φ
′′
=Φ
′
xxxx
pp
L
用反证法，假定设有正整数使
0
p
0)()()(
*)1(**
0
=Φ==Φ
′′
=Φ
′
xxx
p
L 0)(
*)(
0
≠Φ x
p
pp ≠
0
0
0
)(
!
)(
)(
*
0
)(
* p
k
p
k
xx
p
xx?
Φ
+=Φ
ξ
0)(
!
1
lim
*)(
0
1
0
0
≠=
+
∞→
x
p
e
e
p
p
k
k
k
Φ
则即显然
+∞==?≤=
∞←∞→
++
000
1
lim0lim1,
1
0
11
pp
k
k
k
k
pp
k
p
k
k
p
k
k
e
epp
ee
e
e
e
得时，由当
2004-11-22 27
局部收敛性及收敛阶（续）
)0lim(
0
1
>=
+
∞→
C
e
e
p
k
k
k
即，这也与为p阶收敛矛盾。
0
1
limlimlim
00
11
=?=
∞→
+
∞→
+
∞→
pp
k
k
p
k
k
k
p
k
k
k
ee
e
e
e
}{
k
x
0
1
lim0lim1
0
0
==+≥
∞→∞→
pp
k
k
k
k
e
epp得由当即不存在。这与为p 阶收敛矛盾。
}{
k
x
p
k
k
k
e
e
1
lim
+
∞→
证毕
2004-11-22 28
局部收敛性及收敛阶（续）
（3）收敛速度的实例设有两个迭代序列和，且为线性收敛，
为平方收敛，且有
{ }
k
x { }
k
x
~
{ }
k
x { }
k
x
~
)1
~~
,0
~
(
~
~
~
),10(
0
2
11
limlim
<>=<<=
+
∞→
+
∞→
eccc
e
e
cc
e
e
k
k
k
k
k
k
0
1
1
2
1
ececece
k
kkk
+
+
≈≈≈≈ L
1
1
2
0
)12(
4
1
2
2
1
~~~~~~~~
+
+
+
≈≈≈≈
k
k
ececcece
kkk
L
则若
75.0
~
,1
~
00
==== ccee
，欲使误差小于10
－8
，则对于线性收敛的，由可得，
因此大约需要65次迭代。
{}
k
x
81
10)75.0(
+
≤
k
03.64
75.0lg
8
1 ≈
≥+k
2004-11-22 29
局部收敛性及收敛阶（续）
{ }
k
x
~
而对于平方收敛的，由可得，因此大约需要7次迭代。
8)12(
10)75.0(
1
≤
+k
02.61,03.651
75.0lg
8
2
1
≥+≈+
≥
+
k
k
结论：平方收敛的序列收敛速度要比线性收敛的序列大的多。
Remark:本节的方法是以求解非线性方程的实根来讨论的，但类似的结果完全可以推广到求方程的复数根的情形。
返回
2004-11-22 30
第三节迭代的加速收敛方法一、用两个迭代值的组合方法由得，取和，则
)(xx?= xxx θ?θ?=? )()1(
0≠θ 1≠θ
])([
1
1
xxx θ?
θ
=
L,2,1,0],)([
1
)(
1
=?
+=
+
k
xxxx
kkkk
θ
θ
,......2,1,0],)([
1
1
1
=?
=
+
kxx
kk
k
x
θ?
θ
迭代公式为或在上式中θ取不同的值或表达式时，就可以得到不同的迭代法。选取特殊的θ，有可能使得迭代加速。
当时，有
1?=θ
,.........2,1,0],)([
2
1
1
=+=
+
k
xxx
kkk
2004-11-22 31
用两个迭代值的组合方法（续）
对原迭代收敛，在邻域内，
改造后的迭代
)(
1 kk
xx?=
+
x
*
1)(' <≤ Lx?
)(
1 kk
xx ψ=
+
))('1(
2
1
)(' xx?ψ +=
若，即。故当L
越大时，相对于越小，这样可以加快收敛。
2
1
)('0,0)('1 <<<≤?<? xxL ψ?
2
1
)(' <xψ
)(' xψ )(' x?
但对可能有
,1)('0 <≤< Lx?
)1(
2
1
)(' Lx +≤ψ
)(')(' xx?ψ >
通常取，则
)('
*
x?θ =
从而新的迭代格式收敛速度变慢了。
)](')([
)('1
1
)(
*
*
xxx
x
x
ψ?
=
0)](')('[
)('1
1
)('
**
*
*
=?
= xx
x
x
ψ
2004-11-22 32
用两个迭代值的组合方法（续）
0)('1,0)('
**
=≠ xx ψ?时，
)(
1 kk
xx ψ=
+
当即至少为二阶收敛的。
])([
)('1
)('
)()(
*
*
xx
x
x
xx?
+=?
ψ
迭代式还可以变形为从而得加速迭代公式：
))((
1
)(
1 kkkk
xx
C
C
xx?
+=
+
L,2,1,0
][
1
)(
111
1
=
+=
=
+++
+
k
xx
C
C
xx
xx
kkkk
kk
实际中，常取θ为的近似值C。
)('
*
x?
2004-11-22 33
用两个迭代值的组合方法（续）
Remark1：该迭代法对原迭代式的各近似值在根x
*
的两侧往复地趋于x
*
时较为有效。在这种情况下，不但能加快新序列的收敛，还能有效地防止死循环的出现。
Remark2：若序列{x
k
}单调趋于x
*
时，上式不能起到加速收敛的作用。
)('
*
x?
Remark3：该方法的缺点是需估计的近似值。
2004-11-22 34
二．使用三个迭代值的组合方法设方程为，的某个预测值为校正两次
)(xx?=
*
x
,
0
x
。)(),(
1201
xxxx ==
由于ζ
1
在与之间
ζ
2
在与之间。
在邻域中，消去导数信息，即
))(('
*
01
*
1
xxxx?=? ζ?
0
x
*
x
))(('
*
12
*
2
xxxx?=? ζ?
1
x
*
x
*
x
即
*
1
*
0
*
2
*
1
xx
xx
xx
xx
≈
*
2020
*
1
2
1
)(2 xxxxxxxx +?≈?
012
2
01
0
210
2
120
*
2
)(
2 xxx
xx
x
xxx
xxx
x
+?
=
+?
≈
因此可以得下述Aitken方法：
2004-11-22 35
使用三个迭代值的组合方法（续）
给出，校正，再校正
)(
1 kk
xx?=
+
)(
12 ++
=
kk
xx?
0
x
kkk
kk
xxx
xx
+?
)(2))((
))((
2
=
+ kk
xx
1
或
kkk
kk
kk
xxx
xx
xx
+?
=
++
+
+
12
2
1
1
2
)(
改进k=0,1,2,….
上式称为Aitken加速收敛方法。
若记,k=0,1,2,…..,上式也可以写成。
),(
kk
xy?= )(
kk
yz?=
=
+?
=
==
+
L2.1.0.
2
)(
)()(
2
1
k
xyz
xy
xx
yzxy
kkk
kk
kk
kkkk
，
该式也称为Steffensen迭代法。
2004-11-22 36
使用三个迭代值的组合方法（续）
对于Aitken(或Steffensen)迭代，有以下定理：
定理：设函数有不动点，且在的邻域内具有二阶连续导数，若且则
Steffensen迭代式为二阶收敛，而且其极限为。
)(x?
*
x
*
x
Ax =)('
*
,0,1 ≠≠ AA
*
x
证明设Aitken或Steffensen迭代式为
k=0,1,2,…
)(=
+
xx
k
ψ
1
])([)]())(([
][
)(2))((
][
)(
22
xxxx
xx
x
xxx
xx
xx
)(
=
+?
)(
=
ψ
则
2004-11-22 37
使用三个迭代值的组合方法（续）
(1)验证,与有相同的不动点
)(x? )(xψ
若则
)(
**
xx ψ=
0])(2))(()][([])([
*****2**
=+=? xxxxxxxψ?
])([)]())(([
])([
lim)]([lim
2
**
xxxx
xx
xx
xxxx
=?
→→
ψ
即。注意
)(
**
xx?= ),(
**
xx?=,1)('
*
≠x?
]1)('[)](')('))(('[
]1)('][)([2
lim
*
=
→
xxxx
xxx
xx
)1)('()(')('*))(('
)1)(')()((2
****
***
=
xxxx
xxx
0
1)('
))((
2
)1)('()1)(')(('
)1)(')()((
2
*
**
***
***
=
=
=
x
xx
xxx
xxx
2004-11-22 38
使用三个迭代值的组合方法（续）
即.注意的连续性，知,从而说明与具有相同的不动点。
*
)(lim
*
xx
xx
=
→
ψ )(xψ
**
)( xx =ψ
)(xx?= )(xx ψ=
(2)验证Steffensen迭代为二阶收敛由有二阶连续导数，且为的不动点，有
)(x?
*
x
)(x?
2*"**'*
))((
2
1
))(()()( xxxxxxx?+?+= ζ
])[()(
2***
xxOxxAx?+?+=
1.
)()()(
**
xxxxxx=
)(])[()(
*2**
xxxxOxxA+?=
])[())(1(
2**
xxOxxA?+=
2004-11-22 39
使用三个迭代值的组合方法（续）
2.
]))()([())()()(1()())((
2**
xxOxxAxx+=?
22**
2**
)])(()([
)])(()()[1(
xxOxxAO
xxOxxAA
+?+
+=
])[()()1(
2**
xxOxxAA?+=
2004-11-22 40
使用三个迭代值的组合方法（续）
])([)]())(([
])([
2
*
kkkk
kk
k
xxxx
xx
xx
=
**
1
)( xxxx
kk
=?
+
ψ
故
])[())(1()()1(
))(()()1(
2***
3*2*2
*
xxOxxAxxAA
xxOxxA
xx
kkk
kk
k
+
+
=
])[()()1(
))(()()1(
2**2
3*2*2
*
xxOxxA
xxOxxA
xx
kk
kk
k
+
+
=
))((
))(()()1(
))((
2*
2**2
3*
xxO
xxOxxA
xxO
k
kk
k
=
+
=
0
)(
lim
2*
*
1
0
≠=
+
→
C
xx
xx
k
k
k
即Steffensen迭代二阶收敛证毕
2004-11-22 41
使用三个迭代值的组合方法（续）
kkk
kk
kk
xxx
xx
xx
+?
=
++
+
+
12
2
1
1
2
)(
称为Aitken加速迭代格式，此时可以证明比收敛快。只有当由不动点迭代，
产生，得到的公式才称为Steffensen公式。
}{
k
x }{
k
x
)(
1 kk
xx?=
+
}{
k
x )(
12 ++
=
kk
xx?
Remark2：严格讲，
返回
Remark1：当在的邻域中，则
1)('0 << x?
.1)('0
*
<< x?
)(
1 kk
xx?=
+
*
x
但Steffensen迭代不仅能加速收敛，而且也能将发散的迭代改进为收敛的迭代。
不收敛。
1)(' >x?
.1)('
*
>x?
)(
1 kk
xx?=
+
线性收敛。当在的邻域中
*
x时，则
Remark3：Steffensen加速技术一般不对高阶收敛的迭代法进行加速，因为此时效果不明显。
2004-11-22 42
第四节Newton 迭代法一．标准牛顿迭代法及其收敛阶
1．标准牛顿法(Newton-Raphson公式)
L+?+?+=
2
)(
!2
)("
))((')()(
k
k
kkk
xx
xf
xxxfxfxf
)(xf 0)( =xf
0))((')( =?+
kkk
xxxfxf
取前两项近似代替得近似的线性方程设是的一个近似根。
0)( =xf
k
x
设,令解为得上式
0)( =xf 1+k
x
),2,1,0(,
)('
)(
1
L=?=
+
k
xf
xf
xx
k
k
kk
)('
)(
xf
xf
xx?=
0)( =xf
显然是的同解方程。
0)( =xf
称为的Newton迭代法，对应的方程
2004-11-22 43
标准牛顿法（续）
由知是处的切线与轴交点的横坐标，
)('
)(
1
k
k
kk
xf
xf
xx?=
+
1+k
x ))(,(
kk
xfx
)(xfy =
)('
)(
k
k
k
xf
xx
xfy
=
x
故Newton法的几何意义是逐次用切线代替曲线，
求切线与横坐标轴的交点。
Newton法亦称为切线法。
Newton法示意图见下页。
2004-11-22 44
标准牛顿法（续）
y
x
0
x
n
x
n+1
x
n+2
x
*
y=f(x)
Newton法示意图
2004-11-22 45
2.局部收敛性与收敛的阶由及
)('
)(
)(
xf
xf
xx?=?
)}(")()]({[
)]([
1
1)('
2
2
xfxfxf
xf
x?
′
′
=?
再根据在内连续,知
)(" xf
),(
**
δδ +? xx
,0)(' ≠xf
)('),( xx
0
)]([
)(")(
)(',)(
2*
**
***
=
′
==
xf
xfxf
xxx
在内连续，且
),(
**
δδ +? xx
证明：
定理：设为的根，在开区间内，
连续，则Newton迭代式对至少为二阶收敛.
*
x
0)( =xf ),(
**
δδ +? xx
)(" xf,0)(' ≠xf
],[
**
0
δδ +?∈ xxx
证毕
*
x
Remark：只有当初值选的充分靠近时，才能保证序列收敛。
故由迭代局部收敛的充分条件知，Newton迭代法局部收敛，且至少为2阶收敛。
2004-11-22 46
3.非局部收敛性定理：设有且，（二阶导数存在）
且满足，
0)( =xf ],[)(
2
baCxf ∈
0)()( <bfaf（1）
（2）（不变号）
],[.0)(",0)(' baxxfxf ∈?≠≠
)("),(' xfxf
取使
],,[
0
bax ∈,0)(")(
00
>xfxf
*
x
则（1）在内有唯一的根
],[ ba
0)( =xf
)(2
)(
)(
lim
*
*
2*
*
1
xf
xf
xx
xx
k
k
k
′
′′
=
+
∞→
（2）由Newton迭代式产生的序列收敛于,且
*
x}{
k
x
2004-11-22 47
非局部收敛性（续）
证明：
（1）由在上连续，且知在内至少有一根，由（即不变号），知在内有唯一的根，且保证了该根为单根。
)(xf
],[ ba
0)()( <bfaf 0)( =xf
],[ ba
0)(' ≠xf
)(xf
0)( =xf
],[ ba
,0)(' ≠xf
（2）条件（1）和有四种情况。
仅就的情况证明。
0)( ≠
′′
xf
0)(",0)(,0)( >>< xfbfaf
由中值定理，存在使得
),( ba∈ζ
0
)()(
)(' >
=
ab
afbf
f ζ
由于在上不变号，因而在上总大于零，
)(' xf)(' xf ],[ ba],[ ba
即对，由，知在上单调增。又由可知。
],[ ba].,[ bax∈ 0)(' >xf0)(' >xf )(xf
0)(")(
00
>xfxf 0)(
0
>xf
2004-11-22 48
非局部收敛性（续）
解
0))(("
2
1
))((')()(
2
0
*
00
*
00
*
=?+?+= xxfxxxfxfxf ζ
又由知0)(
0
>xf
,
*
0
xx >
而得
0
0
0
01
)('
)(
x
xf
xf
xx <?=
<
<
01
0
*
xx
xx
即
0)(
)('
)("
2
1
)('
)(
2
0
*
0
0
0
0
0
*
<=+? xx
xf
f
xf
xf
xx
ζ
而另一方面，将在作Taylor展开，
)(xf
0
x
2
00000
))(("
!2
1
))((')()( xxfxxxfxfxf?+?+= ζ
其中在与之间，
0
ζ
0
xx
2
0
*
00
*
00
))(("
2
1
))((')( xxfxxxfxf=?+ ζ
变形
2004-11-22 49
非局部收敛性（续）
故
0]
)('
)(
[
0
0
0
*
1
*
<=?
xf
xf
xxxx
于是
01
*
xxx <<
一般地，设类似可得
,
*
k
xx <
0)( >
k
xf
k
k
k
kk
x
xf
xf
xx <?=
+
)('
)(
1
0)(
)('
)("
2
1
2*
<=
k
k
k
xx
xf
f ζ
)(
)(
]
)(
)(
[
*
**
1
*
k
k
k
k
k
kk
xf
xf
xx
xf
xf
xxxx
′
+?=
′
=?
+
且
)2.1.0(
1
*
L=<<
+
kxxx
kk
即有由此知为单调下降序列，且有下界，故必有极限
*
x
x
}{
k
x
2004-11-22 50
非局部收敛性（续）
从而得，再由在内有唯一根，
则必有
0)( =xf 0)( =xf ],[ ba
*
xx =
)('
)(
1
k
k
kk
xf
xf
xx?=
+
对两端同时取极限从而知
*
lim xx
k
k
=
∞→
且由
)('
)("
2
1
)()(
2*
*
1
2*
1
*
k
k
k
k
k
k
xf
f
xx
xx
xx
xx ζ
=
=
++
)(
)(
2
1
)(
lim
*
*
2*
*
1
xf
xf
xx
xx
k
k
k
′
′′
=
+
∞→
得这表明了Newton迭代的二阶收敛性。
证毕
2004-11-22 51
非局部收敛性（续）
更一般的非局部收敛定理如下：
定理：设在上连续，且
)(" xf ],[ ba
则对，Newton迭代序列收敛于方程在内的唯一实根。
],[ ba
*
x
0)( =xf
],[
0
bax ∈?
}{
k
x
，ab
af
af
≤
)('
)(
.
)('
)(
ab
bf
bf
≤（3）
0)("0)(' ≠≠ xfxf
（2）
0)()( <bfaf
（1）
Remark：该定理的实质是指，当取x
0
=a或x
0
=b时，
能保证x
1
仍然在区间[a,b]中。
2004-11-22 52
二.重根情形的牛顿迭代法
Remark：标准牛顿迭代法仅适用于单根的情形。
设为的重根在的某邻域内有
m 阶连续导数，这时
*
x
0)( =xf
),2( ≥m
)(xf
*
x
0)()(')(
*)1(**
====
xfxfxf
m
L
0)(
*)(
≠xf
m
将在处展开，有：)(xf
*
x
m
m
m
m
xx
m
f
xx
m
xf
xfxf )(
!
)(
)(
)!1(
)(
)()(
*
1
)(
)1(*
*)1(
*
+?
++=
ξ
L
1*
2
)(
2*
*)1(
*
)(
)!1(
)(
)(
)!2(
)(
)(')('
+?
++=
m
m
m
m
xx
m
f
xx
m
xf
xfxf
ξ
L
2004-11-22 53
重根情形的牛顿迭代法（续）
其中介于与之间.
2*3
)(
3*
*)1(
*
)(
)!2(
)(
)(
)!3(
)(
)(")("
+?
++=
m
mm
xx
m
f
xx
m
xf
xfxf
ξ
L
321
ξξξ，，
*
x
x
)('
)(
)(
xf
xf
xx?=?
由Newton迭代函数得
]
)(
)!1(
)(
)(
!
)(
[lim)(lim)(
1*
2
)(
*
1
)(
*
**
→→
==
m
m
m
m
xxxx
xx
m
f
xx
m
f
x
xx
ξ
ξ
*
2
)(
1
)(*
]
)(
)()(
[lim
*
x
mf
fxx
x
m
m
xx
=
=
→
ξ
ξ
2004-11-22 54
重根情形的牛顿迭代法（续）
2
*
))((
)()(
lim)(lim)(
**
xf
xfxf
xx
xxxx
′
′′
=
′
=
′
→→
2
2
)(
3
)(
1
)(
)]([
)()()1(
lim
*
ξ
ξξ
m
mm
xx
fm
ffm?
=
→
m
1
1?=
由于，故对于m重根（m>2），Newton迭代法仍收敛，但只有线性收敛速度。
1)(0
*
<
′
< x?
若取，从以上分析可知，，
由此得到平方收敛的方法：
)(
)(
)(
xf
xf
mxx
′
=?
0)(
*
=
′
x?
)(
)(
1
k
k
kk
xf
xf
mxx
′
=
+ L,2,1,0=k
该方法称为改进的Newton法。但实际上该式使用比较困难，因为事先很难知道根的重数m。
*
x
2004-11-22 55
重根情形的牛顿迭代法（续）
′
′′
′
=
′
=
2
))((
)()(
)(
)(
)(
)(
)(
xf
xfxf
xf
xf
x
x
x
xx
μ
μ
一种修改法是令则若是的重零点，
),(
)(
)(
xf
xf
x
′
=μ
*
x
则是的单重零点，取迭代函数
)(xμ
*
x
)(xf m
即
)()())((
)()(
)(
2
xfxfxf
xfxf
xx
′′
′
′
=?
则是二阶收敛的。缺点是需要计算，计算量稍大。
[] )()()(
)()(
2
1
kkk
kk
kk
xfxfxf
xfxf
xx
′′
′
′
=
+
),(
k
xf
′′
2004-11-22 56
三,Newton下山法由Newton迭代法的收敛定理知，Newton迭代法对初值x
0
的要求是很苛刻的。在实际应用中往往难以给出较好的初值x
0
。下面我们给出一种降低对初值要求的修正的Newton法。
方程的解是的最小值点，即
0)( =xf
*
x
)(xf
)()(0
min
*
xfxf
x
==
若我们视为在处的高度，则是山谷的最低点。
)(xf)(xf
x
*
x
若序列满足则称是的一个下山序列。求下山序列的算法称为下山法。
}{
k
x,)()(
1 kk
xfxf <
+
}{
k
x
)(xf
2004-11-22 57
Newton下山法（续）
Newton下山法即是要求迭代后，得到一个以0为下界的严格单调减序列，这样当时，
可得
})({
k
xf
∞→k
,0)(
1
→
+k
xf
1
*
+
≈
k
xx
2*
1
*
)(
)(2
)(
k
k
k
k
xx
xf
f
xx?
′
′′
=
+
η
因为
))(()()(
*
11
*
1
xxfxfxf
kkk
′
=?
+++
ξ
)(2
)()(
))((
1
*
111
k
kk
kkk
xf
ff
xxfx
′
′′′
=?
′
=
+
+++
ηξ
ξ
2*
)(
k
xx?
2
)(
)(
)(2
)()(
′′
′′′
=
k
k
k
kk
f
xf
xf
ff
ξ
ηξ
有
2004-11-22 58
Newton下山法（续）
∞→k
若为的单根，则当时，
)(xf
*
x
[]
0
)(
)(
2
1
)(
)(
2
*
2
1
≠
′
′′
→
+
＊
xf
xf
xf
xf
k
k
))(()(
2
1 kk
xfOxf =
+
即
k
)()(
1 kk
xfxf <
+于是当充分大时，。
结论：收敛的牛顿序列除去有限个点后一定为下山序列。但下山序列的一个极限点不一定是方程的根。
2004-11-22 59
Newton下山法（续）
引理：若，且则存在使得当时， ，
[ ]baCxf,)(
2
∈,0)( ≡xf
,0>δ
δ<< t0
)()
)(
)(
( xf
xf
xf
txf <
′
[ ]bax,∈
证明：将在处展开,得
′
)(
)(
xf
xf
txf
x
)()(
)(
)(
)(
)(
)(
2
tOxf
xf
xf
txf
xf
xf
txf +
′
′
=
′
0
lim
→t
0
)(
)(
)(
)(
)(
)(
)(
)(
=
′
′
′
′
xf
xf
t
xf
xf
xf
txf
xf
xf
txf
所以
2004-11-22 60
Newton下山法（续）
故
),,0(,01 δδ ∈?>>? t
)(
2
1
)(
)(
)(
)(
)(
)(
)(
)(
(
xf
xf
xf
t
xf
xf
xf
txf
xf
xf
txf
′
≤
′
′
′
′
)(
2
1
)()1()
)(
)(
( xftxft
xf
xf
txf ≤
′
）（10 <<< δt即由
≥
′
)()1()
)(
)(
( xft
xf
xf
txf )()1()
)(
)(
( xft
xf
xf
txf
′
得
)()()
2
1(
)(
)(
( xfxf
t
xf
xf
txf <?≤
′
证毕
2004-11-22 61
Newton下山法（续）
0>
k
t
)(
)(
1
xf
xf
txx
k
kkk
′
=
+
,....1,0,)()(
1
=<
+
kxfxf
kk
Remark：该引理表明，是f(x)在x点的下山方向。可以选择适当的，使满足
)(
)(
xf
xf
′
在Newton迭代法中引进下山因子
]( 1,0∈
k
t
将迭代格式修改为
)(
)(
1
k
k
kkk
xf
xf
txx
′
=
+
,...1,0=k
则有为保证是的一个收敛的下山序列，则不能太小；为保证牛顿法的高阶收敛性，
我们希望k充分大时，，即成为标准牛顿迭代法。
,)()(
1 kk
xfxf <
+
}{
k
x
)(xf
k
t
1=
k
t
下山因子的一种常用取法是取自集合。
k
t
,...
4
1
,
2
1
,1
2004-11-22 62
Newton下山法（续）
这种将下山法和牛顿迭代法结合起来使用的方法称为牛顿下山法。其计算步骤如下：
Step1.选取初始。
0
x
Step2.取下山因子。
1=t
Step3.计算及。
)(
)(
1
k
k
kk
xf
xf
txx
′
=
+
)(
1+k
xf
Step4.判断？
)()(
1 kk
xfxf <
+
)()(
1 kk
xfxf <
+
（1）若成立，则有两种情况：
当时，终止迭代，取；
xkk
xx ε<?
+1
*
x
1+
≈
k
x
2004-11-22 63
Newton下山法（续）
)()(
1 kk
xfxf ≥
+
（2）若，也有两种情况：
xkk
xx ε≥?
+1
当时，增加1，即把称为新的，
转Step2继续迭代。
k 1+k
x
k
x
当，且时，将缩小一半，转
Step3继续迭代；
t
t ε>
fk
xf ε≥
+
)(
1
t
当，且时，终止迭代，取；
否则，取（δ为一适当增量），转Step2继续迭代。
t
t ε≤
fk
xf ε<
+
)(
1 1
*
+
≈
k
xx
kk
xx →+
+
δ
1
Remark：上述步骤中，，分别表示根的允许误差和残量精度要求，为下山因子下界。
x
ε
f
ε
t
ε
2004-11-22 64
Newton下山法（续）
Remark1：由数值试验可知，用Newton下山法求解方程的根，需要一定的经验。当函数形状复杂时，Newton下山法可能收敛很慢。只有当x
k
充分接近x
*
时，才具有二阶收敛速度。
Remark2：对形状复杂的函数使用Newton法和
Newton下山法时，程序中应该加上是否为零的判断，以排除不能进行迭代的可能。
)(
k
xf
′
0)( =
′
k
xf
Remark3：Newton法是一种特定的不动点迭代法，因此它可以用于求方程f(x)=0的复根。
返回
2004-11-22 65
第五节弦割法和抛物线法弦割法、抛物线法使用更多的已知信息来构造迭代函数，使得达到超线性收敛。
设是=0的一组近似根，使用它们及其函数值构造插值多项式，并适当选取=0的一个根做为的新的根。从而确立了一个代过程，记迭代函数为，则
L
21
,,
kkk
xxx
)(xf
)(),...(),(
1 rkkk
xfxfxf
)(xp
r
)(xp
r
0)( =xf
1+k
x
rk
x
(?
=
+1k
x
,,,,
21
L
xxx
kkk
)
rk
x
当和，分别称为弦割法与抛物线法。
1=r 2=r
2004-11-22 66
一.弦割法及其收敛性
1.迭代格式：
设为的近似根，对应的函数值为
1
,
kk
xx
0)( =xf
，用近似代替，得近似方程。令其根为，
则有1+k
x
)(
)()(
)(
1
1
=
kk
kk
k
k
xx
xfxf
xf
x
,...1,0=k
)(
)()(
)()(
1
1
1 k
kk
kk
k
xx
xx
xfxf
xfxp?
+=
),(),(
1?kk
xfxf
)(
1
xp
)(xf
0)(
1
=xp 1+k
x
2004-11-22 67
弦割法的迭代格式（续）
用弦AB代替，用弦AB与x轴交点C的横坐标作为的新的近似根。再用弦AC与X轴交点的横坐标作为的新的近似根。
)(xf
1+k
x
0)( =xf1+k
x
0)( =xf
弦割法求要用到开始必须先给出。
1+k
x,,
1?kk
xx
10
,xx
此迭代过程为弦割法，又称为拟牛顿法。弦割法求的过程，相当于过A、B两点作直线,
用来描述
=
k
k
xx
xfy )(
1
1
)()(
kk
kk
xx
xfxf
)(
1
xp
0=
1+k
x
2004-11-22 68
2.局部收敛性设在的某邻域内连续，
则存在的一个邻域,
当时，弦割法产生的序列收敛于，且收敛阶为。
)(,0)(,0)(
*
xfxfxf
′′
≠
′
=
*
x
*
x
[ ]δδ
δ
+?=
***
,)( xxxN
）（0>δ
)(,
*
10
xNxx
δ
∈
}{
k
x
*
x
618.1
定理：
为了证明该局部收敛性定理，先证明如下引理：
引理：设，在的某个邻域内连续且，又设，且互异，记，则有其中由弦割法产生，介于和之间。
0)(
*
=xf
*
x
[ ]δδ
δ
+?=
***
,)( xxxN
)(xf
′′ 0)( ≠
′
xf
)(,
*
1
xNxx
kk δ
∈
*
1
,,xxx
kk?
*
xxe
kk
=
kk
k
k
k
ee
f
f
e
11
)(2
)(
+
′
′′
=
ξ
η
1+k
x
kk
ξη,
},,min{
*
1
xxx
kk?
},,max{
*
1
xxx
kk?
2004-11-22 69
局部收敛性（续）－引理的证明记过的直线方程为，则可看作是以为节点的插值多项式。因此
))(,()),(,(
11 kkkk
xfxxfx
)(
1
xp )(
1
xp
kk
xx,
1?
之间。与在
kkkk
xxxxxxfxpxf
111
),)()((
2
1
)()(
′′
=? ηη
注意到f(x
*
)=0，得
kkkkkk
eefxxxxfxp
1
*
1
**
1
)(
2
1
))()((
2
1
)(
′′
=
′′
= ηη
另一方面，由于是的根，故
1+k
x
0)(
1
=xp
11
1
1
1
*
111
*
1
*
1
)(
)()(
))(()()()(
++
++
′
=
=?
′
=?=
kkk
kk
kk
kk
efe
xx
xfxf
xxpxpxpxp ξξ
其中ξ介于x
*
与x
k+1
之间，ξ
k
介于x
k
与x
k-1
之间。联立上面两式，得
kk
k
k
k
ee
f
f
e
11
)(2
)(
+
′
′′
=
ξ
η
η
k
介于和、之间。
*
x
1?k
x
k
x
ξ
k
，η
k
均在x
k-1
,x
k
和x
*
所介定的范围内，当x
k-1
,x
k
∈N
δ
(x
*
)
时，有ξ
k
，η
k
∈ N
δ
(x
*
)。
证毕
2004-11-22 70
局部收敛性（续）－定理的证明第一步，证明存在x
*
的某邻域N
δ
(x
*
)=[x
*
-δ,x
*
+δ]，
x
0
,x
1
∈ N
δ
(x
*
)时，由弦割法生成的{x
k
}都属于N
δ
(x
*
)。
由于在x
*
的某邻域内连续，且，
故?ε>0，及相应的邻域N
ε
(x
*
)=[x
*
-ε,x
*
+ ε ]，?x∈
N
ε
(x
*
)时，。令
)(),( xfxf
′′′
0)(
*
≠
′
xf
0)( ≠
′
xf
′
′′
=
∈
∈
)(2
)(
min
max
)(
)(
*
*
xf
xf
M
xNx
xNx
ε
ε
ε
则，利用引理有
)(,
*
10
xNxx
ε
∈?
102
eeMe
ε
≤
今取δ>0，要求δ<ε，δM
δ
<1，则当?x
0
,x
1
∈ N
δ
(x
*
)?
N
ε
(x
*
)时，有。再次利用引理可得，
，即x
2
∈ N
δ
(x
*
)。
δδ <<
10
,ee
δδδδδ
δδ
<=≤ MMe
2
2004-11-22 71
局部收敛性（续）－定理的证明一般地，若x
k-1
,x
k
∈ N
δ
(x
*
)，利用引理可得
，即得x
k＋1
∈ N
δ
(x
*
)。
δδδ
δδ
<≤≤
+
MeeMe
kkk 11
第二步，证明{x
k
}的收敛性。由引理及递推关系，当
k≥1时，
02
2
121
)()( eMeMeMeeMe
k
kkkkk
δδδ
δδδδ
≤≤≤≤≤
L
因δM
δ
<1，故k→∞时，e
k
→0，即{x
k
}收敛于x
*
。
第三步，分析收敛阶。令，显然有M
*
≤M
ε
。又由于{x
k
}的收敛性，当k充分大时，引理可写成
))(2/()(
***
xfxfM
′′′
=
kkk
eeMe
1
*
1?+
≈
再引入，显然有d
k
≤d<1。对引理种的式子两边同乘以M
*
，得。
δ
δ
MdeMd
kk
==，
*
11?+
≈
kkk
ddd
2004-11-22 72
局部收敛性（续）－定理的证明设，则{m
k
}满足差分方程
m
k+1
=m
k
+m
k-1
,k=1,2,…
L,2,1,0,== kdd
k
m
k
初始条件m
0
，m
1
由迭代初值决定。由d
0
≤d,d
1
≤ d，
知上面的差分方程的初始条件是m
0
≥1，m
1
≥1。上面差分方程式的特征方程为：
λ
2
－λ－1＝0
解得特征根为
λ 618.0)51(
2
1
,618.1)51(
2
1
21
≈?=≈+= λ
因而m
k
可表示为
kk
k
m
2211
λαλα +=
α
1
，α
2
可由m
0
≥1，m
1
≥1来确定，最终得到：
21
110
2
21
021
21
021
1
,0
||
λλ
λ
α
λλ
λ
λλ
λ
α
=>
+
=
=
mmmmmm
2004-11-22 73
局部收敛性（续）－定理的证明证毕因，且α
1
≠0，故当k充分大时，有
21
λλ >
k
k
m
11
λα≈
1
11111
1
,
+
+
≈=≈=
+
k
k
k
k
dddddd
m
k
m
k
λαλα
1
1
1
≈
+
λ
k
k
d
d
()
1
1
*
1
*
≈
+
λ
k
k
eM
eM
c
xf
xf
M
e
e
k
k
=
+
′
′′
=≈
618.0
*
*
1
*1
)(2
)(
)(
1
1
λ
λ
这说明弦割法为p＝0.618阶的迭代法。
Remark：与Newton法相比，弦割法不必计算，
作为代价，其收敛阶比Newton法低，并且需要两个初始值x
0
,x
1
。
)(
k
xf
′
故或故有
2004-11-22 74
3.非局部收敛性关于弦割法的非局部收敛定理，类似于牛顿法。
定理：设在上连续，且
)(xf
′′
],[ ba
（1）
0)()( <bfaf
（2 ）对一切
0)(,0)(],,[ ≠
′′
≠
′
∈ xfxfbax
（3）
ab
bf
bf
ab
af
af
≤
′
≤
′
)(
)(
,
)(
)(
则对任意的初始值，弦割法产生的迭代序列收敛于，且是在内唯一的零点。
],[,
10
baxx ∈
}{
k
x
*
x
*
x
f
],[ ba
2004-11-22 75
4.对于弦割法的修正弦割法与第二节中的Steffensen迭代法有密切的关系。
设的等价方程为对在使用弦割法，
求出的值记为，则
0)( =xf
)),(()(),(),(
kkkkk
xyzxyxx ====
,0)()( =?= xxxg?
))(,(),(,(
kkkk
ygyxgx
1+k
x
1+k
x
=?
=
kkk
kk
k
k
xyx
ygxg
xg
x )(
)()(
)(
)(
))(())((
)(
kk
kkkk
kk
xy
xxyy
xx
kkk
kk
k
xyz
xy
x
+?
=
2
)(
2
kkk
kk
k
xxx
xx
x
+?
=
)(2)((
))((
2
这就是Steffensen迭代法。
2004-11-22 76
修正的弦割法（续）
牛顿法和弦割法的另一种修改方式为：对于给定的令，则与等价。对如此特定的应用Steffensen迭代，有
,0)( =xf )()( xfxx +=?
0)( =xf )(xx?=
)(x?
+
=Ψ
Ψ=
+
)())((
)(
)(
)(
2
1
xfxfxf
xf
xx
xx
kk
该迭代式也称为Steffensen迭代，它也可看作是对
Newton法和弦割法的一种修改。这一迭代公式既不要计算Newton法中的导数，也不需弦割法中的两个初值，它是一种单点迭代法。
)(
k
xf
′
2004-11-22 77
修正的弦割法（续）
当在附近满足连续的条件时，则修正的弦割法在附近是平方收敛的。该迭代法也称为Steffensen迭代法。
)(xf
*
x )(,0)( xfxf
′′
≠
′
*
x
)()(
kkkk
xfxxy +==?
)()( xfxx +=?
事实上令，则有
))(()()(
kkkkkkk
xfxfyyfyyz ++=+==?
代入Steffensen迭代格式
kkk
kk
kk
xyz
xy
xx
+?
=
+
2
)(
2
1
=
+?+
=
+
kkkk
k
kk
xyxfxf
xf
xx
))((
)(
2
1
)())((
)(
2
kkk
k
xfxfxf
xf
+
即即修正的Newton迭代法。
2004-11-22 78
二.抛物线法（Müller法）
用的三个近似根所确定的抛物线代替，
求方程近似根的方法，称为抛抛物线，又称Müller法。
)(xf0)( =xf
基本思想为：
(1)以的三个近似根及它们的函数值构造牛顿插值多项式(或拉格朗日多项式) 。
)( xf 0=
kkk
xxx,,
12
)(
2
xp
(2)用代替，则有两个零点。
)(
2
xp
)(xf
)(
2
xp
(3)设在中，最接近于，从而希望所求得的根比较接近的一个作为，在这种要求下，舍去一个根。即以中与较接近的零点作为，
从面构造一个迭代过程。
xxx
kkk
,,
12
k
x
*
x
k
x
1+k
x0)(
2
=xp
k
x
1+k
x
2004-11-22 79
1.抛物线法的迭代格式设的根为，它的三个近似值分别是，
按Lagrange插值公式有：
0)( =xf
*
x
kkk
xxx,,
12
)(
))((
))((
2
212
1
=
k
kkkk
kk
xf
xxxx
xxxx
)(
2
xp
)(
))((
))((
1
121
2
+
k
kkkk
kk
xf
xxxx
xxxx
)(
))((
))((
12
12
k
kkkk
kk
xf
xxxx
xxxx
+
2004-11-22 80
抛物线法的迭代格式（续）
将之写为的形式
cbxax ++
2
引入新变量
1?
=
kk
k
xx
xx
λ
21
1
3
=
kk
kk
xx
xx
λ
+=1
3
δ
21
2
3
=
kk
kk
xx
xx
λ
=
++?=
+?=
3
33
2
31
2
32
3331
2
32
)(
))(()()(
)()()(
δ
δλδλ
λδλλ
k
kkk
kkk
xfc
xfxfxfb
xfxfxfa
)(
1
)(
2
3
2
cbap ++= λλ
δ
λ
λ
可表达成的二次函数
)(
2
xp
则其中
2004-11-22 81
抛物线法的迭代格式（续）
的零点为
)(
1
)(
2
3
2
cbap ++= λλ
δ
λ
)
4
)4()(
(
2
1
2
4
2
222
acbb
acbb
aa
acbb
=
±?
=
m
λ
acbb
c
4
2
2
±
=
1?
=
kk
k
xx
xx
λ
由知取模较小的，得到的与较为接近，即上式中取分母大的零点取为，
λ
1+k
x
k
x
4
λ
acbbsignb
c
4)(
2
2
4
+
=λ
即从而
)(
141?+
+=
kkkk
xxxx λ
2004-11-22 82
抛物线法的迭代格式（续）
抛物线法的计算步骤如下：
(1)计算；，
33
δλ
(2)计算;,,cba
(3)计算；
4
λ
(4)计算；
1+k
x
(5)用分别代替，用分别代替，以便进行下一步迭代。
11
,,
+? kkk
xxx
kkk
xxx,,
12
)(),(),(
11 +? kkk
xfxfxf
)(),(),(
12 kkk
xfxfxf
（6）在计算中，若，则，
否则就重复执行(1)-(5)。
ελ <?
)
14 kk
xx（
1
*
+
≈
k
xx
2004-11-22 83
2.抛物线法的局部收敛定理定理：设在的某邻域内连续，
则存在的一个邻域,
)(,0)(,0)(
**
xfxfxf
′′′
≠
′
=
*
x
],[)(
***
δδ
δ
+?= xxxN
）（0>δ
*
x
时，由抛物线法产生的序列收敛于，且其中为方程的根。
)(,,
*
210
xNxxx
δ
∈?
}{
k
x
*
x
lim
∞→k
=
+
p
k
k
xx
xx
*
*
1
2
1
*
*
)(6
)(
′
′′′
p
xf
xf
839.1=p
0)1(
23
=++? λλλ
2004-11-22 84
Remark
1.抛物线法对初值的选取范围较Newton法和弦割法的宽；
此外，弦割法在重根时有可能不收敛，而抛物线法仍然收敛，但收敛速度可能很慢。因此，抛物线法是一个比较有效的求根方法。其缺点是每迭代一步所需的计算量比弦割法的大。抛物线法也可用于求方程的复根。
2.抛物线法比弦割法收敛快，但比Newton法收敛慢。
3.由于三次以上的多项式方程的根一般已不好计算，因此一般不用三次以上的插值多项式来构造求根方法。
返回
第七章非线性方程求根
§7.0 简介
§7.1 二分法（对分法）
§7.2 迭代法的基本理论
§7.3 迭代的加速收敛方法
§7.4 Newton迭代法
§7.5弦割法和抛物线法
2004-11-22 2
§7.0简介一、问题求解非线性方程f(x)=0 ！
如多项式方程：
0)(
01
1
1
=++++=
axaxaxaxp
n
n
n
nn
L
困难：方程的解难以用公式表达。
需要一定精度的近似解！
2004-11-22 3
二、概念方程的解称为方程的根或称为的零点。若其中
m为正整数，满足，则显然这时称为的m重零点，或称为的m重根。
() 0=xf
*
x
( ) 0=xf
( )xf
() ( ) ()xgxxxf
m
*
=
( )xg
( ) 0≠xg ( ) 0
*
=xf
*
x
()xf
*
x
( ) 0=xf
定理：若有m阶连续导数，则是的m重零点的充要条件为：
( )xf
*
x
( )xf
0)(,0)()()(
*)(*)1(**
≠===
′
=
xfxfxfxf
mm
L
2004-11-22 4
概念（续）
证明：必要性设是的m重零点，则且
*
x
()xf
)()()(
*
xgxxxf
m
=
( ) 0
*
≠xg
[]
∑
=
=
k
i
ik
i
mi
k
k
xgxxcxf
0
)(
)(
*)(
)()()(
∑
=
+=
k
i
imimi
k
xgxximmmc
0
)(*
)())(1()1( L
0)(!
)())(1()1()(
*
0
*)(***)(
≠=
+=
∑
=
xgm
xgxximmmcxf
m
i
imimi
m
k
L
mk =
当时
10?≤≤ mk
0)())(1()1()(
0
*)(***)(
=?+=
∑
=
k
i
imimi
k
k
xgxximmmcxf L
当时
2004-11-22 5
概念（续）
充分性：
m
m
m
m
xx
m
xxxf
xx
m
xf
xxxfxfxf
)(
!
))((
)(
)!1(
)(
))(()()(
*
**
1*
*)1(
***
+
+?
++?
′
+=
θ
L
由Taylor公式得
10 <<θ
))((
!
1
)(
**)(
xxxf
m
xg
m
+= θ
)()()(
*
xgxxxf
m
=
0)(
!
1
)(
*)(*
≠= xf
m
xg
m
其中。令则有且
( ) 0
*
=xf
0)(,0)(,,0)(
*)(*)1(*
≠==
′
xfxfxf
mm
L
*
x
设使得，
*
x
)(xf
根据定义为的m重零点。
证毕
2004-11-22 6
三、根的隔离方程可能有多个实根，我们只能逐个求出来。
定义：设在区间[a,b]上方程有一个根，则称该区间为方程的一个有根区间。若在区间[a,b]上方程只有一个根，则称把方程的根隔离出来了。
Remark：若能把有根区间不断缩小，则可以得出根的近似值。
基于函数f(x)的连续性质，常用的根的隔离的方法有：函数作图法与试算法。
要找出方程的所有的根，要进行“根的搜索”。
返回
2004-11-22 7
§7.1二分法（对分法）
一、算法设在[a,b]上连续，f(a)f(b)<0且在[a,b]内f(x)=0
仅有一个实根。二分法的基本思想是：逐步将有根区间分半，通过判别函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求出满足给定精度的根的近似值。
)(xf
*
x
*
x
具体算法：
)(
2
1
111
bax +=
)(
1
xf
记[a,b]为[a
1
,b
1
]。将区间[a
1
,b
1
]分半，计算中点以及函数值。
1
*
xx =
若则。
0)(
1
=xf
2004-11-22 8
二分法（对分法）（续）
1212
,xbaa ==
否则，若有，则，令
],[
11
*
xax ∈0)()(
11
<afxf
或，则，令
0)()(
11
<bfxf
],[
11
*
bxx ∈
1212
,bbxa ==
再计算中点的函数值。],[
22
ba
2
22
2
ba
x
+
=
)(
2
xf
)(
2
1
)(
2
1
1122
ababab?=?=?
新的有根区间的长度],[
22
ba
],[
33
ba )(
2
1
)(
2
1
2
2233
ababab?=?=?
新的有根区间的长度令。
2323
,xbaa ==
2323
,bbxa ==
令
，或则，
0)()(
22
<bfxf
若则。否则则，
2
*
xx =0)(
2
=xf 0)()(
22
<afxf ],[
22
*
xax ∈
],[
22
*
bxx ∈
2004-11-22 9
二分法（对分法）（续）
如此对分下去则得到一系列的有根区间
LL ],[],[],[
2211 kk
bababa
)(
2
1
)(
2
1
1
11
ababab
k
kkkk
==?=?
L
且
L,2,1),(
2
1
)(
2
1
*
=?=?≤? kababxx
k
kkk
由及
2
kk
k
ba
x
+
=
当对分过程无限继续下去，则有根区间必收敛到一点，即
*
lim xx
k
k
=
∞→
2004-11-22 10
二分法（对分法）（续）
二、误差估计定理：给定方程f(x)=0，设f(x)在区间[a,b]上连续，且f(a)f(b)<0，则由二分法产生的序列
{x
k
}收敛于方程的根x
*
，且具有误差估计
),2,1()(
2
1
*
L=?≤? kabxx
k
k
2004-11-22 11
二分法（对分法）（续）
三、收敛准则
1.事先误差估计：
ε<?≤? )(
2
1
*
abxx
k
k利用误差估计定理，令得
2ln
ln)ln( ε
>
ab
k
从而得到对分次数k，取x
k
作为根得近似值x
*
。
2.事后误差估计：
给定ε，每步检查，或若成立，则取，否则继续对分。
k
xx ≈
*
ε<?≤?
)(
2
1
1
abxx
k
kk
ε<)(
k
xf
Remark：二分法的优点是方法及相应的程序均简单，
且对f(x)性质要求不高，只要连续即可。但二分法不能用于求复数根和偶数重根。
返回
2004-11-22 12
§7.2迭代法的基本理论一、不动点迭代法令方程,将其变成一个等价的方程,
构造,
0)( =xf
)(xx Φ=
L,1,0),(
1
=Φ=
+
kxx
kk
}{
k
x
称为迭代序列，
)(xΦ
称为迭代函数,
)(
1 kk
xx Φ=
+
称为迭代格式或迭代过程（迭代式），
)lim()(limlim
1 k
k
k
k
k
k
xxx
∞→∞→
+
∞→
Φ=Φ=
且当连续时，有或。
)(xΦ
即
)(
**
xx Φ= 0)(
*
=xf
即序列的极限为的根。
}{
k
x
*
x
0)( =xf
2004-11-22 13
不动点迭代法（续）
也称为不动点迭代法（也称简单迭代法或逐次逼近法）。
L,1,0),(
1
=Φ=
+
kxx
kk
求的零点就等价转化为求φ的不动点。
)(xf
由于的根满足，反之亦然。
0)( =xf
)(
**
xx Φ=
*
x
也称为的不动点。即映射关系φ将映射到本身。
*
x）（xΦ
*
x
*
x
Remark：可以通过不同的途径将f(x)=0化为
x=φ(x)的形式。
问题：如何选取合适的迭代函数φ(x)？
迭代函数φ(x)应满足什么条件，序列{x
k
}收敛？
怎样加速序列{x
k
}的收敛？
2004-11-22 14
二、不动点迭代法的一般理论定理1.（不动点定理）已知，满足
，且
)(xx Φ=
)(xΦ
),(],[)( baCbaCx
′
∩∈Φ
],[)( baxx在Φ=
*
x
1,上有唯一的不动点则
bxabax ≤Φ≤∈ )(],,[有
2,对任意
Lxbax ≤Φ
′
∈ )(),(有
1.存在常数0<L<1,使对任意
01
*
1
*
1
,
1
xx
L
L
xxxx
L
L
xx
k
kkkk
≤
≤?
}{
k
x3,有误差估计
*
x
L2,1,0),(),,(
110
=Φ=∈
++
kxxbax
kk
}{
k
x
2.对任意产生的序列必收敛到φ的不动点
2004-11-22 15
不动点迭代法的一般理论（续）
证明：
1.由于上连续，作辅助函数
],[)( bax在Φ
,)()( xxx?=?ψ
0)()(,0)()(],[)( ≤?=≥?=∈ bbbaaabaCx?ψ?ψψ且，则故由连续函数的介值定理，至少存在即存在φ的不动点
****
)(,0)(],[ xxxbax ==∈?ψ即使
*
x
又设
,1)(
),,()(],[,)(
*
2
*
1
<≤Φ
′
∈Φ∈Φ
Lx
baCxbaxxx
且
。注意有两个不动点
))(()()(
*
2
*
1
*
2
*
1
*
2
*
1
xxxxxx?Φ
′
=Φ?Φ=? ξ
00))(1(
*
2
*
1
*
2
*
1
=?=?Φ
′
xxxx，得ξ
,
*
2
*
1
xx =
)(xΦ
故由微分中值定理即有唯一的不动点。
2004-11-22 16
不动点迭代法的一般理论（续）
2.因
*
1
*
1
*
1
*
)()()( xxLxxxxxx
kkkk
≤?Φ
′
=Φ?Φ=?
ξ
*
1
xx
k
与
其中ξ介于之间，故有
LL 2,1,
*
0
*
1
*
=?≤≤?≤?
kxxLxxLxx
k
kk
因
。即],[,lim,0lim,1
0
**
baxxxxxL
k
k
k
k
∈?==?<
∞→∞→
2004-11-22 17
不动点迭代法的一般理论（续）
3.由
L,2,1),,(),(,
))(()()(
11
111
=?∈?≤
Φ
′
Φ?Φ=?
+
kbaxxxxL
xxxxxx
kkkk
kkkkkk
ξ
ξ
－－
＝
*
1
**
1
*
1
)()( xxxxxxxxxx
kkkkkk
≥=?
+++
**
1
xxLxx
kk
≤?
+
由结论2有故**
1
*
1
)1( xxLxxxxxx
kkkkk
≥≥?
++
即
11
*
11
1
+
≤?
≤?
kkkkk
xx
L
L
xx
L
xx
0121
2
*
11
xx
L
L
xx
L
L
xx
k
kkk
≤≤?
≤?
L
证毕
2004-11-22 18
不动点迭代法的一般理论（续）
Remark1：若φ(x)为定义在区间[a,b]上的函数，
且，均有φ(x)∈ [a,b]，则称φ(x)为区间[a,b]
自身上的一个映射。若φ(x)为区间[a,b]自身上的一个映射，且
],[ bax∈?
],[,,10
21
baxxL ∈?<<?
2121
)()( xxLxx?≤?φφ
则称φ(x)为区间[a,b]上的一个压缩映射，L为Lipschitz常数。关于压缩映射有如下结论：
（1）若φ(x)为区间[a,b]上的压缩映射，则称φ(x)必为区间[a,b]上的连续函数。
（2）若φ(x)为区间[a,b]自身上的映射，φ(x)∈C[a,b]
且，则φ(x)必是区间[a,b]上的一个压缩映射。1)( <≤
′
Lxφ
2004-11-22 19
不动点迭代法的一般理论（续）
Remark2：不动点定理还可以叙述为：若φ(x)为定义在区间[a,b]上的压缩映射，则φ(x)在区间[a,b]上存在唯一的不动点。
Remark3：不动点定理的两个误差估计式实际上给出了迭代收敛的两个准则：事后误差估计与事先误差估计（利用估计式预先求出迭代次数k）。
Remark4：由不动点定理知，若L≈1，则{x
k
}必然收敛较慢；若L<<1，则收敛速度快。
Remark5：不动点定理给出的是区间[a,b]上的收敛性，
称之为全局收敛性。（判定困难）
2004-11-22 20
三、局部收敛性及收敛阶
1,局部收敛性
（1）定义：若存在φ的不动点的闭邻域使对任意产生的迭
)0](,[)(
***
>+?= δδδ xxxN
L,2,1,0),(),(
1
*
0
=Φ=∈
+
kxxxNx
kk
迭代
*
x
代序列均收敛于，则称求的迭代法在附近局部收敛。
}{
k
x
*
x
*
x
L,2,1,0),(
1
=Φ=
+
kxx
kk
*
x
（2）局部收敛性的判别定理2.设为φ（x）的不动点，在的
*
x )(xΦ
′
*
x
某个邻域连续，且，则迭代式收敛。
1)( <≤Φ
′
Lx
2004-11-22 21
局部收敛性及收敛阶（续）
证明：
因连续，故存在使得，，
)(xΦ
′
)0](,[)(
***
>+?= δδδ xxxN
1)( <≤Φ
′
Lx )(
*
xNx∈
将前述定理1中的[a,b]取为迭代法收敛。
)(
*
0
xNx ∈
],[
**
δδ +? xx
则对任意
)(
*
xNx∈
故即对一切有。
δ<?≤Φ?Φ=?Φ
***
)()()( xxLxxxx
δδ +<Φ<?
**
)( xxx
Remark1：可以证明，若在根的邻域中，则可以以邻域内任何一点为初始值，用迭代过程产生的序列就一定不会收敛于。事实上，
*
x
1)( >Φ
′
x
0
x
*
x
*
0
*
1
*
1
*
1
*
))(()()( xxxxxxxxxx
kkkk
>?>?Φ
′
=Φ?Φ=?
ξ
Remark2：当不取在的邻域为内时可能不收敛。0
x
*
x
证毕
2004-11-22 22
局部收敛性及收敛阶（续）
2.收敛速度收敛速度是接近收敛的过程中迭代误差的下降速度。
（1）p阶收敛的定义设收敛于，令迭代误差
，如果存在实数及非零正常数C使得
）（
kk
xx Φ=
+1
*
)( xxx的根Φ=
*
xxe
kk
=
C
e
e
p
k
k
k
=
+
∞→
1
lim
（称为渐近误差常数）
1≥p
则称该迭代过程以及该迭代式是p阶收敛的。
若0<C<1,p=1称为线性收敛；p>1称为超线性收敛；
p＝2称为平方收敛（二次收敛）。p 越大，收敛速度越快；反之，p越小，收敛速度就越慢。
2004-11-22 23
局部收敛性及收敛阶（续）
（2）收敛速度的判别设迭代法满足全局收敛或局部收敛的条件，则。
）（
kk
xx Φ=
+1
*
lim xx
k
k
=
∞→
再设在[a,b]或x
*
的邻域中，
。0)( ≠
′
xφ
若取，必有
),2,1(,
*
L=≠ kxx
k
*
0
xx ≠
从而有
kkkk
exxxxe )()()(
**
11
ξφφφ
′
=?=?=
++
其中ξ介于x
k
与x
*
之间。
当时，由的连续性得，
∞→k
)(xφ
′ 0)(lim
*
1
≠
′
=
+
∞→
x
e
e
k
k
k
φ
故这种情况下迭代是线性收敛的。这启发我们，要得到超收敛的方法，迭代式必须满足。
0)(
*
=
′
xφ
2004-11-22 24
局部收敛性及收敛阶（续）
定理：迭代式的迭代函数的高阶导数（p>1）在不动点的邻域里连续，则迭代式为p
阶收敛的充要条件是
),1,0(),(
1
L=Φ=
+
kxx
kk
)( p
Φ
*
x
0)(,0)()()(,)(
*)(*)1(****
≠Φ=Φ=Φ
′′
=Φ
′
=Φ
xxxxxx
pp
L
)1)(1(0)(
!
1
lim
**)(
1
可证收敛要求<Φ
′
=≠Φ=
+
∞→
xpx
pe
e
p
p
k
k
k
且有证明：
充分性.对p>1，由于即满足在邻域具有局部收敛性的条件，故迭代式收敛。
0
*
=Φ
′
）（x
)(
1 kk
xx Φ=
+
*
x
2004-11-22 25
局部收敛性及收敛阶（续）
由
p
k
pp
k
p
kk
xx
p
xxx
p
xxxxx
))((
!
1
))((
)!1(
1
))(()()(
*)(1**)1(
***
Φ+?Φ
+
+?Φ
′
+Φ=Φ
ξ
L
之间，故与介于
*
xx
k
ξ
p
k
p
kk
xx
p
xxx )(
!
)(
)(
*
)(
*
1
Φ
+=Φ=
+
ξ
即为p阶收敛
0)(
!
1
lim
*)(1
≠Φ=
+
∞→
x
pe
e
p
p
k
k
k
)(
1 kk
xx Φ=
+
)(
!
1
)(
lim
*)(
*
*
1
x
pxx
xx
p
p
k
k
k
Φ=
+
∞←
－
故当p＝1时，
))(()()(
**
xxxx
kk
Φ
′
+Φ=Φ ξ
1)(lim
*
*
*
1
<Φ
′
=
+
∞→
x
xx
xx
k
k
k
即
2004-11-22 26
局部收敛性及收敛阶（续）
必要性：设迭代式为p 阶收敛，由收敛定义有也即。由邻域的连续性知。
*
lim xx
k
k
=
∞→
*
)(lim xx
k
k
=Φ
∞→
*
)( xx在Φ )(
**
xx Φ=
下面证明：0)(,0)()()(
*)(*)1(**
≠Φ=Φ==Φ
′′
=Φ
′
xxxx
pp
L
用反证法，假定设有正整数使
0
p
0)()()(
*)1(**
0
=Φ==Φ
′′
=Φ
′
xxx
p
L 0)(
*)(
0
≠Φ x
p
pp ≠
0
0
0
)(
!
)(
)(
*
0
)(
* p
k
p
k
xx
p
xx?
Φ
+=Φ
ξ
0)(
!
1
lim
*)(
0
1
0
0
≠=
+
∞→
x
p
e
e
p
p
k
k
k
Φ
则即显然
+∞==?≤=
∞←∞→
++
000
1
lim0lim1,
1
0
11
pp
k
k
k
k
pp
k
p
k
k
p
k
k
e
epp
ee
e
e
e
得时，由当
2004-11-22 27
局部收敛性及收敛阶（续）
)0lim(
0
1
>=
+
∞→
C
e
e
p
k
k
k
即，这也与为p阶收敛矛盾。
0
1
limlimlim
00
11
=?=
∞→
+
∞→
+
∞→
pp
k
k
p
k
k
k
p
k
k
k
ee
e
e
e
}{
k
x
0
1
lim0lim1
0
0
==+≥
∞→∞→
pp
k
k
k
k
e
epp得由当即不存在。这与为p 阶收敛矛盾。
}{
k
x
p
k
k
k
e
e
1
lim
+
∞→
证毕
2004-11-22 28
局部收敛性及收敛阶（续）
（3）收敛速度的实例设有两个迭代序列和，且为线性收敛，
为平方收敛，且有
{ }
k
x { }
k
x
~
{ }
k
x { }
k
x
~
)1
~~
,0
~
(
~
~
~
),10(
0
2
11
limlim
<>=<<=
+
∞→
+
∞→
eccc
e
e
cc
e
e
k
k
k
k
k
k
0
1
1
2
1
ececece
k
kkk
+
+
≈≈≈≈ L
1
1
2
0
)12(
4
1
2
2
1
~~~~~~~~
+
+
+
≈≈≈≈
k
k
ececcece
kkk
L
则若
75.0
~
,1
~
00
==== ccee
，欲使误差小于10
－8
，则对于线性收敛的，由可得，
因此大约需要65次迭代。
{}
k
x
81
10)75.0(
+
≤
k
03.64
75.0lg
8
1 ≈
≥+k
2004-11-22 29
局部收敛性及收敛阶（续）
{ }
k
x
~
而对于平方收敛的，由可得，因此大约需要7次迭代。
8)12(
10)75.0(
1
≤
+k
02.61,03.651
75.0lg
8
2
1
≥+≈+
≥
+
k
k
结论：平方收敛的序列收敛速度要比线性收敛的序列大的多。
Remark:本节的方法是以求解非线性方程的实根来讨论的，但类似的结果完全可以推广到求方程的复数根的情形。
返回
2004-11-22 30
第三节迭代的加速收敛方法一、用两个迭代值的组合方法由得，取和，则
)(xx?= xxx θ?θ?=? )()1(
0≠θ 1≠θ
])([
1
1
xxx θ?
θ
=
L,2,1,0],)([
1
)(
1
=?
+=
+
k
xxxx
kkkk
θ
θ
,......2,1,0],)([
1
1
1
=?
=
+
kxx
kk
k
x
θ?
θ
迭代公式为或在上式中θ取不同的值或表达式时，就可以得到不同的迭代法。选取特殊的θ，有可能使得迭代加速。
当时，有
1?=θ
,.........2,1,0],)([
2
1
1
=+=
+
k
xxx
kkk
2004-11-22 31
用两个迭代值的组合方法（续）
对原迭代收敛，在邻域内，
改造后的迭代
)(
1 kk
xx?=
+
x
*
1)(' <≤ Lx?
)(
1 kk
xx ψ=
+
))('1(
2
1
)(' xx?ψ +=
若，即。故当L
越大时，相对于越小，这样可以加快收敛。
2
1
)('0,0)('1 <<<≤?<? xxL ψ?
2
1
)(' <xψ
)(' xψ )(' x?
但对可能有
,1)('0 <≤< Lx?
)1(
2
1
)(' Lx +≤ψ
)(')(' xx?ψ >
通常取，则
)('
*
x?θ =
从而新的迭代格式收敛速度变慢了。
)](')([
)('1
1
)(
*
*
xxx
x
x
ψ?
=
0)](')('[
)('1
1
)('
**
*
*
=?
= xx
x
x
ψ
2004-11-22 32
用两个迭代值的组合方法（续）
0)('1,0)('
**
=≠ xx ψ?时，
)(
1 kk
xx ψ=
+
当即至少为二阶收敛的。
])([
)('1
)('
)()(
*
*
xx
x
x
xx?
+=?
ψ
迭代式还可以变形为从而得加速迭代公式：
))((
1
)(
1 kkkk
xx
C
C
xx?
+=
+
L,2,1,0
][
1
)(
111
1
=
+=
=
+++
+
k
xx
C
C
xx
xx
kkkk
kk
实际中，常取θ为的近似值C。
)('
*
x?
2004-11-22 33
用两个迭代值的组合方法（续）
Remark1：该迭代法对原迭代式的各近似值在根x
*
的两侧往复地趋于x
*
时较为有效。在这种情况下，不但能加快新序列的收敛，还能有效地防止死循环的出现。
Remark2：若序列{x
k
}单调趋于x
*
时，上式不能起到加速收敛的作用。
)('
*
x?
Remark3：该方法的缺点是需估计的近似值。
2004-11-22 34
二．使用三个迭代值的组合方法设方程为，的某个预测值为校正两次
)(xx?=
*
x
,
0
x
。)(),(
1201
xxxx ==
由于ζ
1
在与之间
ζ
2
在与之间。
在邻域中，消去导数信息，即
))(('
*
01
*
1
xxxx?=? ζ?
0
x
*
x
))(('
*
12
*
2
xxxx?=? ζ?
1
x
*
x
*
x
即
*
1
*
0
*
2
*
1
xx
xx
xx
xx
≈
*
2020
*
1
2
1
)(2 xxxxxxxx +?≈?
012
2
01
0
210
2
120
*
2
)(
2 xxx
xx
x
xxx
xxx
x
+?
=
+?
≈
因此可以得下述Aitken方法：
2004-11-22 35
使用三个迭代值的组合方法（续）
给出，校正，再校正
)(
1 kk
xx?=
+
)(
12 ++
=
kk
xx?
0
x
kkk
kk
xxx
xx
+?
)(2))((
))((
2
=
+ kk
xx
1
或
kkk
kk
kk
xxx
xx
xx
+?
=
++
+
+
12
2
1
1
2
)(
改进k=0,1,2,….
上式称为Aitken加速收敛方法。
若记,k=0,1,2,…..,上式也可以写成。
),(
kk
xy?= )(
kk
yz?=
=
+?
=
==
+
L2.1.0.
2
)(
)()(
2
1
k
xyz
xy
xx
yzxy
kkk
kk
kk
kkkk
，
该式也称为Steffensen迭代法。
2004-11-22 36
使用三个迭代值的组合方法（续）
对于Aitken(或Steffensen)迭代，有以下定理：
定理：设函数有不动点，且在的邻域内具有二阶连续导数，若且则
Steffensen迭代式为二阶收敛，而且其极限为。
)(x?
*
x
*
x
Ax =)('
*
,0,1 ≠≠ AA
*
x
证明设Aitken或Steffensen迭代式为
k=0,1,2,…
)(=
+
xx
k
ψ
1
])([)]())(([
][
)(2))((
][
)(
22
xxxx
xx
x
xxx
xx
xx
)(
=
+?
)(
=
ψ
则
2004-11-22 37
使用三个迭代值的组合方法（续）
(1)验证,与有相同的不动点
)(x? )(xψ
若则
)(
**
xx ψ=
0])(2))(()][([])([
*****2**
=+=? xxxxxxxψ?
])([)]())(([
])([
lim)]([lim
2
**
xxxx
xx
xx
xxxx
=?
→→
ψ
即。注意
)(
**
xx?= ),(
**
xx?=,1)('
*
≠x?
]1)('[)](')('))(('[
]1)('][)([2
lim
*
=
→
xxxx
xxx
xx
)1)('()(')('*))(('
)1)(')()((2
****
***
=
xxxx
xxx
0
1)('
))((
2
)1)('()1)(')(('
)1)(')()((
2
*
**
***
***
=
=
=
x
xx
xxx
xxx
2004-11-22 38
使用三个迭代值的组合方法（续）
即.注意的连续性，知,从而说明与具有相同的不动点。
*
)(lim
*
xx
xx
=
→
ψ )(xψ
**
)( xx =ψ
)(xx?= )(xx ψ=
(2)验证Steffensen迭代为二阶收敛由有二阶连续导数，且为的不动点，有
)(x?
*
x
)(x?
2*"**'*
))((
2
1
))(()()( xxxxxxx?+?+= ζ
])[()(
2***
xxOxxAx?+?+=
1.
)()()(
**
xxxxxx=
)(])[()(
*2**
xxxxOxxA+?=
])[())(1(
2**
xxOxxA?+=
2004-11-22 39
使用三个迭代值的组合方法（续）
2.
]))()([())()()(1()())((
2**
xxOxxAxx+=?
22**
2**
)])(()([
)])(()()[1(
xxOxxAO
xxOxxAA
+?+
+=
])[()()1(
2**
xxOxxAA?+=
2004-11-22 40
使用三个迭代值的组合方法（续）
])([)]())(([
])([
2
*
kkkk
kk
k
xxxx
xx
xx
=
**
1
)( xxxx
kk
=?
+
ψ
故
])[())(1()()1(
))(()()1(
2***
3*2*2
*
xxOxxAxxAA
xxOxxA
xx
kkk
kk
k
+
+
=
])[()()1(
))(()()1(
2**2
3*2*2
*
xxOxxA
xxOxxA
xx
kk
kk
k
+
+
=
))((
))(()()1(
))((
2*
2**2
3*
xxO
xxOxxA
xxO
k
kk
k
=
+
=
0
)(
lim
2*
*
1
0
≠=
+
→
C
xx
xx
k
k
k
即Steffensen迭代二阶收敛证毕
2004-11-22 41
使用三个迭代值的组合方法（续）
kkk
kk
kk
xxx
xx
xx
+?
=
++
+
+
12
2
1
1
2
)(
称为Aitken加速迭代格式，此时可以证明比收敛快。只有当由不动点迭代，
产生，得到的公式才称为Steffensen公式。
}{
k
x }{
k
x
)(
1 kk
xx?=
+
}{
k
x )(
12 ++
=
kk
xx?
Remark2：严格讲，
返回
Remark1：当在的邻域中，则
1)('0 << x?
.1)('0
*
<< x?
)(
1 kk
xx?=
+
*
x
但Steffensen迭代不仅能加速收敛，而且也能将发散的迭代改进为收敛的迭代。
不收敛。
1)(' >x?
.1)('
*
>x?
)(
1 kk
xx?=
+
线性收敛。当在的邻域中
*
x时，则
Remark3：Steffensen加速技术一般不对高阶收敛的迭代法进行加速，因为此时效果不明显。
2004-11-22 42
第四节Newton 迭代法一．标准牛顿迭代法及其收敛阶
1．标准牛顿法(Newton-Raphson公式)
L+?+?+=
2
)(
!2
)("
))((')()(
k
k
kkk
xx
xf
xxxfxfxf
)(xf 0)( =xf
0))((')( =?+
kkk
xxxfxf
取前两项近似代替得近似的线性方程设是的一个近似根。
0)( =xf
k
x
设,令解为得上式
0)( =xf 1+k
x
),2,1,0(,
)('
)(
1
L=?=
+
k
xf
xf
xx
k
k
kk
)('
)(
xf
xf
xx?=
0)( =xf
显然是的同解方程。
0)( =xf
称为的Newton迭代法，对应的方程
2004-11-22 43
标准牛顿法（续）
由知是处的切线与轴交点的横坐标，
)('
)(
1
k
k
kk
xf
xf
xx?=
+
1+k
x ))(,(
kk
xfx
)(xfy =
)('
)(
k
k
k
xf
xx
xfy
=
x
故Newton法的几何意义是逐次用切线代替曲线，
求切线与横坐标轴的交点。
Newton法亦称为切线法。
Newton法示意图见下页。
2004-11-22 44
标准牛顿法（续）
y
x
0
x
n
x
n+1
x
n+2
x
*
y=f(x)
Newton法示意图
2004-11-22 45
2.局部收敛性与收敛的阶由及
)('
)(
)(
xf
xf
xx?=?
)}(")()]({[
)]([
1
1)('
2
2
xfxfxf
xf
x?
′
′
=?
再根据在内连续,知
)(" xf
),(
**
δδ +? xx
,0)(' ≠xf
)('),( xx
0
)]([
)(")(
)(',)(
2*
**
***
=
′
==
xf
xfxf
xxx
在内连续，且
),(
**
δδ +? xx
证明：
定理：设为的根，在开区间内，
连续，则Newton迭代式对至少为二阶收敛.
*
x
0)( =xf ),(
**
δδ +? xx
)(" xf,0)(' ≠xf
],[
**
0
δδ +?∈ xxx
证毕
*
x
Remark：只有当初值选的充分靠近时，才能保证序列收敛。
故由迭代局部收敛的充分条件知，Newton迭代法局部收敛，且至少为2阶收敛。
2004-11-22 46
3.非局部收敛性定理：设有且，（二阶导数存在）
且满足，
0)( =xf ],[)(
2
baCxf ∈
0)()( <bfaf（1）
（2）（不变号）
],[.0)(",0)(' baxxfxf ∈?≠≠
)("),(' xfxf
取使
],,[
0
bax ∈,0)(")(
00
>xfxf
*
x
则（1）在内有唯一的根
],[ ba
0)( =xf
)(2
)(
)(
lim
*
*
2*
*
1
xf
xf
xx
xx
k
k
k
′
′′
=
+
∞→
（2）由Newton迭代式产生的序列收敛于,且
*
x}{
k
x
2004-11-22 47
非局部收敛性（续）
证明：
（1）由在上连续，且知在内至少有一根，由（即不变号），知在内有唯一的根，且保证了该根为单根。
)(xf
],[ ba
0)()( <bfaf 0)( =xf
],[ ba
0)(' ≠xf
)(xf
0)( =xf
],[ ba
,0)(' ≠xf
（2）条件（1）和有四种情况。
仅就的情况证明。
0)( ≠
′′
xf
0)(",0)(,0)( >>< xfbfaf
由中值定理，存在使得
),( ba∈ζ
0
)()(
)(' >
=
ab
afbf
f ζ
由于在上不变号，因而在上总大于零，
)(' xf)(' xf ],[ ba],[ ba
即对，由，知在上单调增。又由可知。
],[ ba].,[ bax∈ 0)(' >xf0)(' >xf )(xf
0)(")(
00
>xfxf 0)(
0
>xf
2004-11-22 48
非局部收敛性（续）
解
0))(("
2
1
))((')()(
2
0
*
00
*
00
*
=?+?+= xxfxxxfxfxf ζ
又由知0)(
0
>xf
,
*
0
xx >
而得
0
0
0
01
)('
)(
x
xf
xf
xx <?=
<
<
01
0
*
xx
xx
即
0)(
)('
)("
2
1
)('
)(
2
0
*
0
0
0
0
0
*
<=+? xx
xf
f
xf
xf
xx
ζ
而另一方面，将在作Taylor展开，
)(xf
0
x
2
00000
))(("
!2
1
))((')()( xxfxxxfxfxf?+?+= ζ
其中在与之间，
0
ζ
0
xx
2
0
*
00
*
00
))(("
2
1
))((')( xxfxxxfxf=?+ ζ
变形
2004-11-22 49
非局部收敛性（续）
故
0]
)('
)(
[
0
0
0
*
1
*
<=?
xf
xf
xxxx
于是
01
*
xxx <<
一般地，设类似可得
,
*
k
xx <
0)( >
k
xf
k
k
k
kk
x
xf
xf
xx <?=
+
)('
)(
1
0)(
)('
)("
2
1
2*
<=
k
k
k
xx
xf
f ζ
)(
)(
]
)(
)(
[
*
**
1
*
k
k
k
k
k
kk
xf
xf
xx
xf
xf
xxxx
′
+?=
′
=?
+
且
)2.1.0(
1
*
L=<<
+
kxxx
kk
即有由此知为单调下降序列，且有下界，故必有极限
*
x
x
}{
k
x
2004-11-22 50
非局部收敛性（续）
从而得，再由在内有唯一根，
则必有
0)( =xf 0)( =xf ],[ ba
*
xx =
)('
)(
1
k
k
kk
xf
xf
xx?=
+
对两端同时取极限从而知
*
lim xx
k
k
=
∞→
且由
)('
)("
2
1
)()(
2*
*
1
2*
1
*
k
k
k
k
k
k
xf
f
xx
xx
xx
xx ζ
=
=
++
)(
)(
2
1
)(
lim
*
*
2*
*
1
xf
xf
xx
xx
k
k
k
′
′′
=
+
∞→
得这表明了Newton迭代的二阶收敛性。
证毕
2004-11-22 51
非局部收敛性（续）
更一般的非局部收敛定理如下：
定理：设在上连续，且
)(" xf ],[ ba
则对，Newton迭代序列收敛于方程在内的唯一实根。
],[ ba
*
x
0)( =xf
],[
0
bax ∈?
}{
k
x
，ab
af
af
≤
)('
)(
.
)('
)(
ab
bf
bf
≤（3）
0)("0)(' ≠≠ xfxf
（2）
0)()( <bfaf
（1）
Remark：该定理的实质是指，当取x
0
=a或x
0
=b时，
能保证x
1
仍然在区间[a,b]中。
2004-11-22 52
二.重根情形的牛顿迭代法
Remark：标准牛顿迭代法仅适用于单根的情形。
设为的重根在的某邻域内有
m 阶连续导数，这时
*
x
0)( =xf
),2( ≥m
)(xf
*
x
0)()(')(
*)1(**
====
xfxfxf
m
L
0)(
*)(
≠xf
m
将在处展开，有：)(xf
*
x
m
m
m
m
xx
m
f
xx
m
xf
xfxf )(
!
)(
)(
)!1(
)(
)()(
*
1
)(
)1(*
*)1(
*
+?
++=
ξ
L
1*
2
)(
2*
*)1(
*
)(
)!1(
)(
)(
)!2(
)(
)(')('
+?
++=
m
m
m
m
xx
m
f
xx
m
xf
xfxf
ξ
L
2004-11-22 53
重根情形的牛顿迭代法（续）
其中介于与之间.
2*3
)(
3*
*)1(
*
)(
)!2(
)(
)(
)!3(
)(
)(")("
+?
++=
m
mm
xx
m
f
xx
m
xf
xfxf
ξ
L
321
ξξξ，，
*
x
x
)('
)(
)(
xf
xf
xx?=?
由Newton迭代函数得
]
)(
)!1(
)(
)(
!
)(
[lim)(lim)(
1*
2
)(
*
1
)(
*
**
→→
==
m
m
m
m
xxxx
xx
m
f
xx
m
f
x
xx
ξ
ξ
*
2
)(
1
)(*
]
)(
)()(
[lim
*
x
mf
fxx
x
m
m
xx
=
=
→
ξ
ξ
2004-11-22 54
重根情形的牛顿迭代法（续）
2
*
))((
)()(
lim)(lim)(
**
xf
xfxf
xx
xxxx
′
′′
=
′
=
′
→→
2
2
)(
3
)(
1
)(
)]([
)()()1(
lim
*
ξ
ξξ
m
mm
xx
fm
ffm?
=
→
m
1
1?=
由于，故对于m重根（m>2），Newton迭代法仍收敛，但只有线性收敛速度。
1)(0
*
<
′
< x?
若取，从以上分析可知，，
由此得到平方收敛的方法：
)(
)(
)(
xf
xf
mxx
′
=?
0)(
*
=
′
x?
)(
)(
1
k
k
kk
xf
xf
mxx
′
=
+ L,2,1,0=k
该方法称为改进的Newton法。但实际上该式使用比较困难，因为事先很难知道根的重数m。
*
x
2004-11-22 55
重根情形的牛顿迭代法（续）
′
′′
′
=
′
=
2
))((
)()(
)(
)(
)(
)(
)(
xf
xfxf
xf
xf
x
x
x
xx
μ
μ
一种修改法是令则若是的重零点，
),(
)(
)(
xf
xf
x
′
=μ
*
x
则是的单重零点，取迭代函数
)(xμ
*
x
)(xf m
即
)()())((
)()(
)(
2
xfxfxf
xfxf
xx
′′
′
′
=?
则是二阶收敛的。缺点是需要计算，计算量稍大。
[] )()()(
)()(
2
1
kkk
kk
kk
xfxfxf
xfxf
xx
′′
′
′
=
+
),(
k
xf
′′
2004-11-22 56
三,Newton下山法由Newton迭代法的收敛定理知，Newton迭代法对初值x
0
的要求是很苛刻的。在实际应用中往往难以给出较好的初值x
0
。下面我们给出一种降低对初值要求的修正的Newton法。
方程的解是的最小值点，即
0)( =xf
*
x
)(xf
)()(0
min
*
xfxf
x
==
若我们视为在处的高度，则是山谷的最低点。
)(xf)(xf
x
*
x
若序列满足则称是的一个下山序列。求下山序列的算法称为下山法。
}{
k
x,)()(
1 kk
xfxf <
+
}{
k
x
)(xf
2004-11-22 57
Newton下山法（续）
Newton下山法即是要求迭代后，得到一个以0为下界的严格单调减序列，这样当时，
可得
})({
k
xf
∞→k
,0)(
1
→
+k
xf
1
*
+
≈
k
xx
2*
1
*
)(
)(2
)(
k
k
k
k
xx
xf
f
xx?
′
′′
=
+
η
因为
))(()()(
*
11
*
1
xxfxfxf
kkk
′
=?
+++
ξ
)(2
)()(
))((
1
*
111
k
kk
kkk
xf
ff
xxfx
′
′′′
=?
′
=
+
+++
ηξ
ξ
2*
)(
k
xx?
2
)(
)(
)(2
)()(
′′
′′′
=
k
k
k
kk
f
xf
xf
ff
ξ
ηξ
有
2004-11-22 58
Newton下山法（续）
∞→k
若为的单根，则当时，
)(xf
*
x
[]
0
)(
)(
2
1
)(
)(
2
*
2
1
≠
′
′′
→
+
＊
xf
xf
xf
xf
k
k
))(()(
2
1 kk
xfOxf =
+
即
k
)()(
1 kk
xfxf <
+于是当充分大时，。
结论：收敛的牛顿序列除去有限个点后一定为下山序列。但下山序列的一个极限点不一定是方程的根。
2004-11-22 59
Newton下山法（续）
引理：若，且则存在使得当时， ，
[ ]baCxf,)(
2
∈,0)( ≡xf
,0>δ
δ<< t0
)()
)(
)(
( xf
xf
xf
txf <
′
[ ]bax,∈
证明：将在处展开,得
′
)(
)(
xf
xf
txf
x
)()(
)(
)(
)(
)(
)(
2
tOxf
xf
xf
txf
xf
xf
txf +
′
′
=
′
0
lim
→t
0
)(
)(
)(
)(
)(
)(
)(
)(
=
′
′
′
′
xf
xf
t
xf
xf
xf
txf
xf
xf
txf
所以
2004-11-22 60
Newton下山法（续）
故
),,0(,01 δδ ∈?>>? t
)(
2
1
)(
)(
)(
)(
)(
)(
)(
)(
(
xf
xf
xf
t
xf
xf
xf
txf
xf
xf
txf
′
≤
′
′
′
′
)(
2
1
)()1()
)(
)(
( xftxft
xf
xf
txf ≤
′
）（10 <<< δt即由
≥
′
)()1()
)(
)(
( xft
xf
xf
txf )()1()
)(
)(
( xft
xf
xf
txf
′
得
)()()
2
1(
)(
)(
( xfxf
t
xf
xf
txf <?≤
′
证毕
2004-11-22 61
Newton下山法（续）
0>
k
t
)(
)(
1
xf
xf
txx
k
kkk
′
=
+
,....1,0,)()(
1
=<
+
kxfxf
kk
Remark：该引理表明，是f(x)在x点的下山方向。可以选择适当的，使满足
)(
)(
xf
xf
′
在Newton迭代法中引进下山因子
]( 1,0∈
k
t
将迭代格式修改为
)(
)(
1
k
k
kkk
xf
xf
txx
′
=
+
,...1,0=k
则有为保证是的一个收敛的下山序列，则不能太小；为保证牛顿法的高阶收敛性，
我们希望k充分大时，，即成为标准牛顿迭代法。
,)()(
1 kk
xfxf <
+
}{
k
x
)(xf
k
t
1=
k
t
下山因子的一种常用取法是取自集合。
k
t
,...
4
1
,
2
1
,1
2004-11-22 62
Newton下山法（续）
这种将下山法和牛顿迭代法结合起来使用的方法称为牛顿下山法。其计算步骤如下：
Step1.选取初始。
0
x
Step2.取下山因子。
1=t
Step3.计算及。
)(
)(
1
k
k
kk
xf
xf
txx
′
=
+
)(
1+k
xf
Step4.判断？
)()(
1 kk
xfxf <
+
)()(
1 kk
xfxf <
+
（1）若成立，则有两种情况：
当时，终止迭代，取；
xkk
xx ε<?
+1
*
x
1+
≈
k
x
2004-11-22 63
Newton下山法（续）
)()(
1 kk
xfxf ≥
+
（2）若，也有两种情况：
xkk
xx ε≥?
+1
当时，增加1，即把称为新的，
转Step2继续迭代。
k 1+k
x
k
x
当，且时，将缩小一半，转
Step3继续迭代；
t
t ε>
fk
xf ε≥
+
)(
1
t
当，且时，终止迭代，取；
否则，取（δ为一适当增量），转Step2继续迭代。
t
t ε≤
fk
xf ε<
+
)(
1 1
*
+
≈
k
xx
kk
xx →+
+
δ
1
Remark：上述步骤中，，分别表示根的允许误差和残量精度要求，为下山因子下界。
x
ε
f
ε
t
ε
2004-11-22 64
Newton下山法（续）
Remark1：由数值试验可知，用Newton下山法求解方程的根，需要一定的经验。当函数形状复杂时，Newton下山法可能收敛很慢。只有当x
k
充分接近x
*
时，才具有二阶收敛速度。
Remark2：对形状复杂的函数使用Newton法和
Newton下山法时，程序中应该加上是否为零的判断，以排除不能进行迭代的可能。
)(
k
xf
′
0)( =
′
k
xf
Remark3：Newton法是一种特定的不动点迭代法，因此它可以用于求方程f(x)=0的复根。
返回
2004-11-22 65
第五节弦割法和抛物线法弦割法、抛物线法使用更多的已知信息来构造迭代函数，使得达到超线性收敛。
设是=0的一组近似根，使用它们及其函数值构造插值多项式，并适当选取=0的一个根做为的新的根。从而确立了一个代过程，记迭代函数为，则
L
21
,,
kkk
xxx
)(xf
)(),...(),(
1 rkkk
xfxfxf
)(xp
r
)(xp
r
0)( =xf
1+k
x
rk
x
(?
=
+1k
x
,,,,
21
L
xxx
kkk
)
rk
x
当和，分别称为弦割法与抛物线法。
1=r 2=r
2004-11-22 66
一.弦割法及其收敛性
1.迭代格式：
设为的近似根，对应的函数值为
1
,
kk
xx
0)( =xf
，用近似代替，得近似方程。令其根为，
则有1+k
x
)(
)()(
)(
1
1
=
kk
kk
k
k
xx
xfxf
xf
x
,...1,0=k
)(
)()(
)()(
1
1
1 k
kk
kk
k
xx
xx
xfxf
xfxp?
+=
),(),(
1?kk
xfxf
)(
1
xp
)(xf
0)(
1
=xp 1+k
x
2004-11-22 67
弦割法的迭代格式（续）
用弦AB代替，用弦AB与x轴交点C的横坐标作为的新的近似根。再用弦AC与X轴交点的横坐标作为的新的近似根。
)(xf
1+k
x
0)( =xf1+k
x
0)( =xf
弦割法求要用到开始必须先给出。
1+k
x,,
1?kk
xx
10
,xx
此迭代过程为弦割法，又称为拟牛顿法。弦割法求的过程，相当于过A、B两点作直线,
用来描述
=
k
k
xx
xfy )(
1
1
)()(
kk
kk
xx
xfxf
)(
1
xp
0=
1+k
x
2004-11-22 68
2.局部收敛性设在的某邻域内连续，
则存在的一个邻域,
当时，弦割法产生的序列收敛于，且收敛阶为。
)(,0)(,0)(
*
xfxfxf
′′
≠
′
=
*
x
*
x
[ ]δδ
δ
+?=
***
,)( xxxN
）（0>δ
)(,
*
10
xNxx
δ
∈
}{
k
x
*
x
618.1
定理：
为了证明该局部收敛性定理，先证明如下引理：
引理：设，在的某个邻域内连续且，又设，且互异，记，则有其中由弦割法产生，介于和之间。
0)(
*
=xf
*
x
[ ]δδ
δ
+?=
***
,)( xxxN
)(xf
′′ 0)( ≠
′
xf
)(,
*
1
xNxx
kk δ
∈
*
1
,,xxx
kk?
*
xxe
kk
=
kk
k
k
k
ee
f
f
e
11
)(2
)(
+
′
′′
=
ξ
η
1+k
x
kk
ξη,
},,min{
*
1
xxx
kk?
},,max{
*
1
xxx
kk?
2004-11-22 69
局部收敛性（续）－引理的证明记过的直线方程为，则可看作是以为节点的插值多项式。因此
))(,()),(,(
11 kkkk
xfxxfx
)(
1
xp )(
1
xp
kk
xx,
1?
之间。与在
kkkk
xxxxxxfxpxf
111
),)()((
2
1
)()(
′′
=? ηη
注意到f(x
*
)=0，得
kkkkkk
eefxxxxfxp
1
*
1
**
1
)(
2
1
))()((
2
1
)(
′′
=
′′
= ηη
另一方面，由于是的根，故
1+k
x
0)(
1
=xp
11
1
1
1
*
111
*
1
*
1
)(
)()(
))(()()()(
++
++
′
=
=?
′
=?=
kkk
kk
kk
kk
efe
xx
xfxf
xxpxpxpxp ξξ
其中ξ介于x
*
与x
k+1
之间，ξ
k
介于x
k
与x
k-1
之间。联立上面两式，得
kk
k
k
k
ee
f
f
e
11
)(2
)(
+
′
′′
=
ξ
η
η
k
介于和、之间。
*
x
1?k
x
k
x
ξ
k
，η
k
均在x
k-1
,x
k
和x
*
所介定的范围内，当x
k-1
,x
k
∈N
δ
(x
*
)
时，有ξ
k
，η
k
∈ N
δ
(x
*
)。
证毕
2004-11-22 70
局部收敛性（续）－定理的证明第一步，证明存在x
*
的某邻域N
δ
(x
*
)=[x
*
-δ,x
*
+δ]，
x
0
,x
1
∈ N
δ
(x
*
)时，由弦割法生成的{x
k
}都属于N
δ
(x
*
)。
由于在x
*
的某邻域内连续，且，
故?ε>0，及相应的邻域N
ε
(x
*
)=[x
*
-ε,x
*
+ ε ]，?x∈
N
ε
(x
*
)时，。令
)(),( xfxf
′′′
0)(
*
≠
′
xf
0)( ≠
′
xf
′
′′
=
∈
∈
)(2
)(
min
max
)(
)(
*
*
xf
xf
M
xNx
xNx
ε
ε
ε
则，利用引理有
)(,
*
10
xNxx
ε
∈?
102
eeMe
ε
≤
今取δ>0，要求δ<ε，δM
δ
<1，则当?x
0
,x
1
∈ N
δ
(x
*
)?
N
ε
(x
*
)时，有。再次利用引理可得，
，即x
2
∈ N
δ
(x
*
)。
δδ <<
10
,ee
δδδδδ
δδ
<=≤ MMe
2
2004-11-22 71
局部收敛性（续）－定理的证明一般地，若x
k-1
,x
k
∈ N
δ
(x
*
)，利用引理可得
，即得x
k＋1
∈ N
δ
(x
*
)。
δδδ
δδ
<≤≤
+
MeeMe
kkk 11
第二步，证明{x
k
}的收敛性。由引理及递推关系，当
k≥1时，
02
2
121
)()( eMeMeMeeMe
k
kkkkk
δδδ
δδδδ
≤≤≤≤≤
L
因δM
δ
<1，故k→∞时，e
k
→0，即{x
k
}收敛于x
*
。
第三步，分析收敛阶。令，显然有M
*
≤M
ε
。又由于{x
k
}的收敛性，当k充分大时，引理可写成
))(2/()(
***
xfxfM
′′′
=
kkk
eeMe
1
*
1?+
≈
再引入，显然有d
k
≤d<1。对引理种的式子两边同乘以M
*
，得。
δ
δ
MdeMd
kk
==，
*
11?+
≈
kkk
ddd
2004-11-22 72
局部收敛性（续）－定理的证明设，则{m
k
}满足差分方程
m
k+1
=m
k
+m
k-1
,k=1,2,…
L,2,1,0,== kdd
k
m
k
初始条件m
0
，m
1
由迭代初值决定。由d
0
≤d,d
1
≤ d，
知上面的差分方程的初始条件是m
0
≥1，m
1
≥1。上面差分方程式的特征方程为：
λ
2
－λ－1＝0
解得特征根为
λ 618.0)51(
2
1
,618.1)51(
2
1
21
≈?=≈+= λ
因而m
k
可表示为
kk
k
m
2211
λαλα +=
α
1
，α
2
可由m
0
≥1，m
1
≥1来确定，最终得到：
21
110
2
21
021
21
021
1
,0
||
λλ
λ
α
λλ
λ
λλ
λ
α
=>
+
=
=
mmmmmm
2004-11-22 73
局部收敛性（续）－定理的证明证毕因，且α
1
≠0，故当k充分大时，有
21
λλ >
k
k
m
11
λα≈
1
11111
1
,
+
+
≈=≈=
+
k
k
k
k
dddddd
m
k
m
k
λαλα
1
1
1
≈
+
λ
k
k
d
d
()
1
1
*
1
*
≈
+
λ
k
k
eM
eM
c
xf
xf
M
e
e
k
k
=
+
′
′′
=≈
618.0
*
*
1
*1
)(2
)(
)(
1
1
λ
λ
这说明弦割法为p＝0.618阶的迭代法。
Remark：与Newton法相比，弦割法不必计算，
作为代价，其收敛阶比Newton法低，并且需要两个初始值x
0
,x
1
。
)(
k
xf
′
故或故有
2004-11-22 74
3.非局部收敛性关于弦割法的非局部收敛定理，类似于牛顿法。
定理：设在上连续，且
)(xf
′′
],[ ba
（1）
0)()( <bfaf
（2 ）对一切
0)(,0)(],,[ ≠
′′
≠
′
∈ xfxfbax
（3）
ab
bf
bf
ab
af
af
≤
′
≤
′
)(
)(
,
)(
)(
则对任意的初始值，弦割法产生的迭代序列收敛于，且是在内唯一的零点。
],[,
10
baxx ∈
}{
k
x
*
x
*
x
f
],[ ba
2004-11-22 75
4.对于弦割法的修正弦割法与第二节中的Steffensen迭代法有密切的关系。
设的等价方程为对在使用弦割法，
求出的值记为，则
0)( =xf
)),(()(),(),(
kkkkk
xyzxyxx ====
,0)()( =?= xxxg?
))(,(),(,(
kkkk
ygyxgx
1+k
x
1+k
x
=?
=
kkk
kk
k
k
xyx
ygxg
xg
x )(
)()(
)(
)(
))(())((
)(
kk
kkkk
kk
xy
xxyy
xx
kkk
kk
k
xyz
xy
x
+?
=
2
)(
2
kkk
kk
k
xxx
xx
x
+?
=
)(2)((
))((
2
这就是Steffensen迭代法。
2004-11-22 76
修正的弦割法（续）
牛顿法和弦割法的另一种修改方式为：对于给定的令，则与等价。对如此特定的应用Steffensen迭代，有
,0)( =xf )()( xfxx +=?
0)( =xf )(xx?=
)(x?
+
=Ψ
Ψ=
+
)())((
)(
)(
)(
2
1
xfxfxf
xf
xx
xx
kk
该迭代式也称为Steffensen迭代，它也可看作是对
Newton法和弦割法的一种修改。这一迭代公式既不要计算Newton法中的导数，也不需弦割法中的两个初值，它是一种单点迭代法。
)(
k
xf
′
2004-11-22 77
修正的弦割法（续）
当在附近满足连续的条件时，则修正的弦割法在附近是平方收敛的。该迭代法也称为Steffensen迭代法。
)(xf
*
x )(,0)( xfxf
′′
≠
′
*
x
)()(
kkkk
xfxxy +==?
)()( xfxx +=?
事实上令，则有
))(()()(
kkkkkkk
xfxfyyfyyz ++=+==?
代入Steffensen迭代格式
kkk
kk
kk
xyz
xy
xx
+?
=
+
2
)(
2
1
=
+?+
=
+
kkkk
k
kk
xyxfxf
xf
xx
))((
)(
2
1
)())((
)(
2
kkk
k
xfxfxf
xf
+
即即修正的Newton迭代法。
2004-11-22 78
二.抛物线法（Müller法）
用的三个近似根所确定的抛物线代替，
求方程近似根的方法，称为抛抛物线，又称Müller法。
)(xf0)( =xf
基本思想为：
(1)以的三个近似根及它们的函数值构造牛顿插值多项式(或拉格朗日多项式) 。
)( xf 0=
kkk
xxx,,
12
)(
2
xp
(2)用代替，则有两个零点。
)(
2
xp
)(xf
)(
2
xp
(3)设在中，最接近于，从而希望所求得的根比较接近的一个作为，在这种要求下，舍去一个根。即以中与较接近的零点作为，
从面构造一个迭代过程。
xxx
kkk
,,
12
k
x
*
x
k
x
1+k
x0)(
2
=xp
k
x
1+k
x
2004-11-22 79
1.抛物线法的迭代格式设的根为，它的三个近似值分别是，
按Lagrange插值公式有：
0)( =xf
*
x
kkk
xxx,,
12
)(
))((
))((
2
212
1
=
k
kkkk
kk
xf
xxxx
xxxx
)(
2
xp
)(
))((
))((
1
121
2
+
k
kkkk
kk
xf
xxxx
xxxx
)(
))((
))((
12
12
k
kkkk
kk
xf
xxxx
xxxx
+
2004-11-22 80
抛物线法的迭代格式（续）
将之写为的形式
cbxax ++
2
引入新变量
1?
=
kk
k
xx
xx
λ
21
1
3
=
kk
kk
xx
xx
λ
+=1
3
δ
21
2
3
=
kk
kk
xx
xx
λ
=
++?=
+?=
3
33
2
31
2
32
3331
2
32
)(
))(()()(
)()()(
δ
δλδλ
λδλλ
k
kkk
kkk
xfc
xfxfxfb
xfxfxfa
)(
1
)(
2
3
2
cbap ++= λλ
δ
λ
λ
可表达成的二次函数
)(
2
xp
则其中
2004-11-22 81
抛物线法的迭代格式（续）
的零点为
)(
1
)(
2
3
2
cbap ++= λλ
δ
λ
)
4
)4()(
(
2
1
2
4
2
222
acbb
acbb
aa
acbb
=
±?
=
m
λ
acbb
c
4
2
2
±
=
1?
=
kk
k
xx
xx
λ
由知取模较小的，得到的与较为接近，即上式中取分母大的零点取为，
λ
1+k
x
k
x
4
λ
acbbsignb
c
4)(
2
2
4
+
=λ
即从而
)(
141?+
+=
kkkk
xxxx λ
2004-11-22 82
抛物线法的迭代格式（续）
抛物线法的计算步骤如下：
(1)计算；，
33
δλ
(2)计算;,,cba
(3)计算；
4
λ
(4)计算；
1+k
x
(5)用分别代替，用分别代替，以便进行下一步迭代。
11
,,
+? kkk
xxx
kkk
xxx,,
12
)(),(),(
11 +? kkk
xfxfxf
)(),(),(
12 kkk
xfxfxf
（6）在计算中，若，则，
否则就重复执行(1)-(5)。
ελ <?
)
14 kk
xx（
1
*
+
≈
k
xx
2004-11-22 83
2.抛物线法的局部收敛定理定理：设在的某邻域内连续，
则存在的一个邻域,
)(,0)(,0)(
**
xfxfxf
′′′
≠
′
=
*
x
],[)(
***
δδ
δ
+?= xxxN
）（0>δ
*
x
时，由抛物线法产生的序列收敛于，且其中为方程的根。
)(,,
*
210
xNxxx
δ
∈?
}{
k
x
*
x
lim
∞→k
=
+
p
k
k
xx
xx
*
*
1
2
1
*
*
)(6
)(
′
′′′
p
xf
xf
839.1=p
0)1(
23
=++? λλλ
2004-11-22 84
Remark
1.抛物线法对初值的选取范围较Newton法和弦割法的宽；
此外，弦割法在重根时有可能不收敛，而抛物线法仍然收敛，但收敛速度可能很慢。因此，抛物线法是一个比较有效的求根方法。其缺点是每迭代一步所需的计算量比弦割法的大。抛物线法也可用于求方程的复根。
2.抛物线法比弦割法收敛快，但比Newton法收敛慢。
3.由于三次以上的多项式方程的根一般已不好计算，因此一般不用三次以上的插值多项式来构造求根方法。
返回
