取初值x0 0
2 e x0 x1 10
d1 = d2 = d3 = d4 = d5 = d6 = d7 =
0 .1
0.1000000 -0.0105171 0.1156e-002 -0.1265e-003 0.1390e-004 -0.1500e-005 0.1000e-006
x1 = 0.1000000 x2 = 0.0894829 x3 = 0.0906391 x4 = 0.0905126 x5 = 0.0905265 x6 = 0.0905250 x7 = 0.0905251
i 2 ,3 , , n
7.2 迭代法的基本理论
Ax b
不动点迭代法
将非线性方程f(x)=0化为一个同解方程
x ( x)
--------(1)
设 ( x)为连续函数,若x满足f (x ) 0, 则x 也满足x x , 反之亦然,称x 是函数 x 的一个不动点，于是求f(x )的零点 问题等价转化为求不动点的问题。
华长生制作
( p ) ( x*)
p!
( x x*) p
18
xk 1 ( xk ) ( x*)
( p ) ( x*)
p!
( xk x*) p
( p) ( p 1) ( x *) ( x*) p xk 1 x * ( xk x*) ( xk x*) p 1 p! ( p 1)!
p 1时称为超线性收敛, p 2时称为平方收敛
华长生制作
16
上式表明，当k 时，ek 1是ek的p阶无穷小量
阶数p越大，收敛越快
如果在[a,b]或x的邻域有 '( x* ) 0, 则
* 对 x0 x ，必有 xk x*,k=1,2,…，而且
ek 1 xk 1 x ( xk ) ( x ) (k )ek
x*的一个闭邻域 [ x* , x* ], 在其上 ' ( x) L 1, 并且有 ( x) x* ( x) ( x ) L x x* ,
即对一切x [ x* , x* ]，有 x [ x* , x* ]。 从而对任意x0 [ x* , x* ], 迭代法收敛。
11
因此,当
迭代就可以终止, xk可以作为方程的近似解
华长生制作
例2. 用迭代法求方程的近似解,精确到小数点后6位
e x 10x 2 0
解:
由于e x 0,
则2 10x 0
x 0 .2
x 0时, 0 e x 1, 2 10 x 2
因此[0,0.2]为有根区间
p阶导数连续,则迭代法p阶收敛的充要条件是
( x*) x, ( x*)
( p 1) ( x*) 0,
( p ) ( x*) 0
19
且有
华长生制作
lim
ek 1 1 p x 0 k e p p! k
9
L xk x * xk xk 1 1 L
L2 xk 1 xk 2 1 L

Lk x1 x0 1 L
由于L 1,
lim( xk x *) 0
k
因此对任意初值 x0 , 迭代法xk 1 ( xk )均收敛于x *
L Lk xk x * xk何确定 p, 从而确定收敛阶呢？ 不可能直接确定
如果迭代函数 ( x)在精确解x * 处充分光滑,即处处可导 将( x)在x * 作Taylor 展开, 有
( x ) ( x *) ( x *)( x x *)

( x *)
2!
( x x *)2
不动点迭代法的一般理论
定理1. 设迭代函数 ( x)在[a, b]上连续, 且满足
(1) 当x [a , b]时, a ( x) b; (2) 存在一正数 L, 满足0 L 1, 且x [a, b],有
| ( x )| L
则 1o. x ( x)在[a, b] 内有唯一解x*,即有唯一不动点
由于|d7| =0.1000e-006<1e-6
因此原方程的解为
华长生制作
x * x7 = 0.090525
13
局部收敛性和收敛阶
一般讨论[a,b]上的全局收敛性比较困难，可转向讨 论在 x 附近的收敛性。
x 定义 若存在 的不动点 的一个闭邻 域 N (x ) [x , x ] 0 ，对任意的 x N x ，由x
由于| ( x)| L
xk 1 xk L xk xk 1
xk 1 x * L xk x * L xk 1 x * ( xk 1 xk )
L xk 1 x * L ( xk 1 xk )
xk 1
华长生制作
L x* xk 1 xk 1 L
华长生制作
证毕.
10
L1 定理1指出, 只要构造的迭代函数满足 | ( x)|
迭代法xk 1 ( xk )就收敛, L或| ( x)|在[a , b]上越小,
迭代法收敛就越快。
对于预先给定的误差限 即要求|xk x*|
由(3)式,只要
L xk xk 1 1 L 1 L xk xk 1 L
2o.对于任意初值 x0 [a, b],迭代法xk 1 ( xk )均收敛于x *
L 3 . xk x * xk xk 1 1 L k L 4 o. xk x * x1 x0 1 L
o
华长生制作
(局部收敛性)
--------(3)
7
证:
设f ( x) x ( x), 则f ( x)在[a , b]上连续可导
华长生制作 4
x0 0
3 x1 2 x0 1 1
3 x2 2 x1 1 3
3 x3 2 x2 1 55

显然迭代法发散
(2) 如果将原方程化为等价方程
x3
华长生制作
x1 2
5
仍取初值
x0 0
x1
3
x2 3
x0 1 1 3 0.7937 2 2 x1 1 3 1.7937 0.9644 2 2
本题迭代函数有两种构造形式
2 ex x 2 ( x) ln( 2 10x) x 1 ( x) 10 10 ex e0.2 5 ( x)| ( x)| 1 |2 由于 |1 2 10 x 10 10 2 ex x 1 ( x) 因此采用迭代函数 12 华长生制作 10
任取一个初值x0 , 代入(1)式的右端, 得 x1 ( x0 ) x2 ( x1 )
继续
xk 1 ( xk )
( k 0 ,1,2 ,) --------(2)
2
称(2)式为求解非线性方程(1)的不动点迭代法
华长生制作
称( x)为迭代函数 , 称xk为第k步迭代值
依此类推,得 x2 = 0.9644
x3 = 0.9940 x4 = 0.9990 x5 = 0.9998 x6 = 1.0000 x7 = 1.0000
同样的方程 不同的迭代格式 有不同的结果 迭代函数的构造有关
什么形式的迭代法 能够收敛呢?
6
已经收敛,故原方程的解为
华长生制作
x 1.0000
( p 1) ( x*)
( p 1)!
( x x*) p 1
( p ) ( x*)
p!
( x x*) p
如果 ( x*) ( x*) ( p 1) ( x*) 0
而 ( p ) ( x*) 0
( x) ( x*)
上述定理称为局部收敛定理，它给出了局部收敛的一个
充分条件。
华长生制作 15
下面讨论迭代法的阶，它是度量一种迭代法收 敛快慢的标志。
设ek xk x
定义1.
若存在实数 p 1和c 0满足 ek 1 lim p c k ek 则称迭代法(或序列 xk ) p阶收敛,当p 1时称为线性收敛,
所以 1o. 方程x ( x)在[a, b] 内有唯一解 x*
华长生制作 8
2o. 对于迭代法 xk 1 ( xk ),
由微分中值定理
xk 1 x * ( xk ) ( x*) ( )(xk x*) xk 1 xk ( xk ) ( xk 1 ) ( )(xk xk 1 )
如果存在一点 x*, 使得迭代序列 { xk } 0 满足
lim xk x *
k
则称迭代法收敛,否则称为发散 如果将(1)式表示为
yx

yx y ( x)
yx
y ( x) y ( x)
收敛
O x * x2
华长生制作
x1
x0
O
x1
x3 x * x2
x0
f (a) a (a) 0 f (b) b (b) 0
由条件(1)
由根的存在定理, 方程f ( x) 0在[a, b]上至少有一个根
由
| ( x)| L1 f ( x) 1 ( x) 0
则f ( x)在[a, b]上单调递增 , f ( x) 0在[a, b]上仅有一个根
* * '
其中在 k与 x*之间。于是
ek 1 lim lim ' ( k ) ' ( x* ) 0。 k e k k