例4. 设f (a) 0,且f (a) 0,证明迭代法
xk 1
xk
f (xk ) f (xk )
至少是平方收敛的
注意例4与例3的迭代法是相同的,两例有何区别?
x0 0
x1 2 x03 1 1 x2 2 x13 1 3
x3 2 x23 1 55
显然迭代法发散
(2) 如果将原方程化为等价方程
x3 x1 2
仍取初值 x0 0
x1 3
x0 1 2
3 1 2
0.7937
x2 3
x1 1 3
2
1.7937 0.9644
2
依此类推,得 x2 = 0.9644 x3 = 0.9940
f
( xn 2!
)
(
x
xn
)2
f ( x) f ( xn ) f '( xn )( x xn ) ——Taylor展开线性化
f(x)=0 近似于 f(xn)+ f′(xn)(x-xn)=0 (1)
从(1)解出x, 记为xn+1 ,则
xn1 xn
f ( xn ) f ( xn )
(n 0,1,...)
f '' ( x*) 2 f '(x*)
c
证：将f(x)在 xn 处作2阶Taylor展开,并将解x*代入
0
f ( x*)
f ( xn )
f' ( xn )( x* xn
)
f
"(n
2!
)
(
x
*
xn
)2
x*
xn
f ( xn f' ( xn
) )
f"(n
2 f' ( xn
) )
(
x
*
xn
)2
xn1
x n1
x n
f ( xn ) f '( xn )
Newton迭代法又称切线法.
4. Newton迭代法收敛定理
定理 设 f(x*)=0, f '( x*) 0 ,且在 x* 的邻域
上 f ''存在, 连续, 则可得
（1）Newton迭代公式在单根情况下至少2阶收敛;
lim （2） n
( xn1 x*) (xn x*)2
(2) 存在一正数L,满足0 L 1,且x [a, b], 有
|(x)| L
--------(5)
则1o. 方程x ( x)在[a, b]内有唯一解x *
2o.对于任意初值x0 [a, b], 迭代法xk1 ( xk )均收敛于x *
3o.
xk
x*
L 1 L
xk xk1
4o.
xk
x*
Lk 1 L
(1) x 2 x3 1 1( x ) ,迭代法发散.
(2)
x3
x 1 2
2( x ),可验证2( x )
1,x 0,1
迭代法收敛.
Newton 迭代法
1. Newton迭代公式建立
将f(x)在点xn作Taylor展开:
f (x)
f ( xn )
f '( xn )( x xn )
由于|( x)| L
xk 1 xk L xk xk1
xk1 xk L xk xk 1
xk1 x * L xk x * L xk1 x * (xk1 xk )
L xk1 x * L(xk1 xk )
xk 1
x
*
1
L L
xk 1 xk
xk
x
*
L 1L
xk xk 1
称(3)式为求解非线性方程(2)的简单迭代法
称 ( x)为迭代函数, 称xk为第k步迭代值
如果存在一点x*, 使得迭代序列{ xk }满足
lim
k
xk
x*
--------(4)
则称迭代法(3)收敛,否则称为发散
例1. 用迭代法求解方程 2x3 x 1 0
解: (1) 将原方程化为等价方程
x 2x3 1 如果取初值 x0 0,由迭代法(3), 得
且g(x*) 0, m 2
所以 f ( x) m(x x*)m1 g(x) (x x*)m g(x)
xk 1 xk
f (xk ) f (xk )
xk
m( xk
( xk x*)m g( xk ) x*)m1 g( xk ) ( xk x*)m g( xk )
xk
( xk x*)g(xk ) mg ( xk ) (xk x*)g(xk
y (x)
O x * x2
x1
(
x0
x
)在x
*
O
x1
附近较平缓
y (x)
yx
x3 x * x2 x0
yx
发散
y (x)
O x2
x1 x0 x *
O
x3 x1 x * x0 x2
(x)在x * 附近较陡峭
迭代过程的收敛性 定理1. 设迭代函数( x)在[a, b]上连续, 且满足
(1) 当x [a, b]时, a ( x) b;
0 ex 1, 2 10x 2
因此[0,0.2]为有根区间
本题迭代函数有两种构造形式
x
1(x)
2 ex 10
x 2(x) ln(2 10x)
由于|1( x)|
ex 10
e0.2 10
1
|2 ( x)|
2
10 10x
5
因此采用迭代函数
x
1(x)
2 ex 10
取初值
x0
x1
0
则f (x)在[a,b]上单调递增 , f (x) 0在[a,b]上仅有一个根
所以 1o. 方程x (x)在[a,b]内有唯一解 x *
2o. 对于迭代法 xk 1 ( xk ),
由微分中值定理
xk 1 x * (xk ) (x*) ( )( xk x*)
xk 1 xk (xk ) (xk 1 ) ( )( xk xk 1 )
x4 = 0.9990
同样的方程
不同的迭代格式
有不同的结果
x5 = 0.9998 x6 = 1.0000
迭代函数的构造有关
x7 = 1.0000 已经收敛,故原方程的解为
x 1.0000
什么形式的迭代法
能够收敛呢?
如果将(2)式表示为 yx
yx
y (x)
与方程(2)同解
yx
y (x)
收敛
2
e 10
x0
0.1
x1 = 0.1000000 x2 = 0.0894829 x3 = 0.0906391 x4 = 0.0905126 x5 = 0.0905265 x6 = 0.0905250 x7 = 0.0905251
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
)(x p!
*)
(
xk
x*) p
xk 1
x
*
(
p)( x*) p!
(
xk
x*) p
(
(
p1)
p
( x*) 1)!
(
xk
x*) p1
xk 1 x * xk x * p
(
p ) ( x*) p!
(
(
p1)
p
( x*) 1)!
(
xk
x*)
( p)(x*) ,(k )
p!
即迭代法 xk 1 (xk )的收敛阶是 p
定理2
若x*是的不动点, 在x*的某邻域上存在 且连续, 并满足 0 | (x*) | 1, 则迭代过程 xk1 (xk ) 在x*的邻域是线性收敛的.
例2. 用迭代法求方程的近似解,精确到小数 点后6位
ex 10x 2 0 解: 由于ex 0,
则2 10x 0 x 0.2
x 0时,
( xn
) )
(
x
*
xn
)2
注意到ξn 在xn 及x*之间,及 lim xn x* ,故 n
xn1 x*
f"(n )
f"( x* )
xn x* 2 2 f' ( xn ) 2 f' ( x* )
0(二阶收敛)若 f "(x*) 0
0(大于二阶收敛)若 f "(x*) 0
所以，Newton法至少二阶收敛.
由于|d7| =0.1000e-006<1e-6
因此原方程的解为 x* x7 = 0.090525
迭代法收敛速度
由定理1的(7)式出,
L或|(x)|在[a,b]上越小, 迭代法收敛就越快
设ek xk x *
定义1.
若存在实数p 1和c 0满足
c lim
k
ek 1 ekp
--------(9)
)
xk 1
x
*
( xk
x*)( 1
mg (xk
)
g(xk ) (xk x*)g(xk
) )
lim xk 1 x * k xk x *
lim(1
g(xk )
)
k mg ( xk ) ( xk x*)g( xk )
1 1 m
m 2时,1 1 0 m
由定义1
该迭代法对 m( 2)重根是线性收敛的
则称迭代法p阶收敛,当p 1时称为线性收敛, p 1时