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
L xk x * xk xk 1 1 L 2 L xk 1 xk 2 1 L
第6章 方程与方程组的迭代解法
§ 6.2 不动点迭代法及其收敛定理
一、迭代法原理
将非线性方程 f (x) = 0 化为一个同解方程
x ( x)
并且假设 ( x)为连续函数
--------(2)
任取一个初值 x0 , 代入(2)的右端, 得 x1 ( x0 ) 继续 x2 ( x1 )
例2. 用迭代法求方程的近似解,精确到小数
点后6位
解:
e 10x 2 0 x 由于e 0,
x
则2 10x 0
x 0 .2
x 0时,
0 e 1,
x
2 10 x 2
3 2
显然迭代法发散 (2) 如果将原方程化为等价方程
x1 2
仍取初值
x0 0
x1 3
x2
3
x1 1 3 1.7937 0.9644 2 2
x0 1 3 1 2 2
0.7937
同样的方程 不同的迭代格式 有不同的结果
依此类推,得 x2 = 0.9644 x3 = 0.9940 x4 = 0.9990 x5 = 0.9998 x6 = 1.0000 x7 = 1.0000 已经收敛,故原方程的解为
x1
x3 x * x2
x0
发散
y ( x)
O
x2
x1
x0 x *
( x)在x * 附近较陡峭
O
x3 x1 x * x0 x2
迭代过程的收敛性 定理1. 设迭代函数 ( x )在[a, b]上连续, 且满足 (1) 当x [a, b]时, a ( x ) b;
(2) 存在一正数L, 满足0 L 1, 且x [a, b], 有
迭代函数的构造有关
什么形式的迭代法
能够收敛呢?
x 1.0000
如果将(2)式表示为 y ( x ) 与方程(2)同解 yx y x
y ( x)

yx
收敛
y ( x)
O x * x2
x1
y ( x)
( x)在x * 附近较平缓
yx yx
x0
O
(局部收敛性)
--------(6) --------(7)
证:
设f ( x) x ( x),
则f ( x)在[a , b]上连续可导
由条件(1) f ( a) a ( a) 0
f (b) b (b) 0
由根的存在定理,
方程f ( x) 0在[a, b]上至少有一个根

--------(3) xk 1 ( xk ) (k 0,1,2 ,)
称(3)式为求解非线性方程(2)的简单迭代法
称 ( x)为迭代函数, 称xk 为第k步迭代值
如果存在一点x*, 使得迭代序列{ xk }满足
lim xk x *
k
--------(4)
则称迭代法(3)收敛,否则称为发散
Lk x1 x0 1 L 由于L 1, lim( xk x *) 0 k
因此对任意初值 x0 , 迭代法xk 1 ( xk )均收敛于x *
L Lk xk x * xk xk 1 x1 x0 1 L 1 L
证毕.
定理1指出, 只要构造的迭代函数满足 | ( x) | L 1
| ( x )| L
--------(5)
则1o. 方程x ( x)在[a, b] 内有唯一解x *
2o.对于任意初值x0 [a, b], 迭代法xk 1 ( xk )均收敛于x *
3o .
4o .
L xk x * xk xk 1 1 L Lk xk x * x1 x0 1 L
由微分中值定理
xk 1 x * ( xk ) ( x*) ( )(xk x*)
xk 1 xk ( xk ) ( xk 1 ) ( )(xk xk 1 )
由于| ( x)| L
xk 1 xk
L xk xk 1
xk 1 ( xk ) 对于任意初值 x0 R均收敛，则称迭代过程 xk 1 ( xk ) 在根 x * 邻近具有局部收敛性。
定理 2 若x*是 的不动点, 在x*的某邻域上存在 且连续, 并满足
* * 0 | ( x ) | 1, 则迭代过程
xk 1 ( xk ) 在x 的邻域是线性收敛的.
迭代法xk 1 ( xk )就收敛
|xk x*| 对于预先给定的误差限 即要求
由(6)式,只要
L xk xk 1 1 L 1 L xk xk 1 --------(8) L
因此,当

迭代就可以终止, xk可以作为方程的近似解
定义1：如果存在 x * 的某个邻域 R : x x由 | ( x )|
f ( x) 1 ( x) 0
则f ( x)在[a, b]上单调递增 ,
f ( x) 0在[a, b]上仅有一个根
所以 1 . 方程x ( x)在[a, b] 内有唯一解 x*
o
2o. 对于迭代法 xk 1 ( xk ),
例1. 解:
用迭代法求解方程 2x x 1 0
3
(1) 将原方程化为等价方程
x 2x 1
3
如果取初值 x0 0,由迭代法 (3), 得
x0 0
x1 2 x 1 1
3 0
x2 2 x 1 3
3 1
x3 2 x 1 55

x3