k L L xk x * xk xk 1 x1 x0 1 L 1 L
证毕.
定理1指出, 只要构造的迭代函数满足
| ( x) | L 1
迭代法xk 1 ( xk )就收敛
数值分析
控制误差ε的方法：
(1) 先计算满足误差要求的迭代次数n，再迭代。由
3
解:本题迭代函数有两种构造形式
(1) (2)
x 2 x 3 1 1 ( x )
x
3
,迭代法发散.
x 1 2( x ), 可验证 2( x ) 1, x 0 ,1 2
迭代法收敛.
7.3 迭代法的速
Steffensen方法
简单迭代公式的加速 设 xk是根 x * 的某个近似值，用迭代公式校正 一次得
--------(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]上至少有一个根
定理
设序列 {xk }线性收敛于x*, k 0, ek x* xk 0, 且
ek 1 lim c k e k
*
(0 | c | 1)
则 {xk } 的Aitken序列 {xk }存在,且
x xk lim * 0 k x x k
即 比 {x } 更快收敛于x*. {xk } k
x * x7 = 0.090525
由定理1的(7)式出, L或| ( x)|在[a , b]上越小, 迭代法收敛就越快
迭代法收敛速度
设ek xk x *
定义1.
若存在实数p 1和c 0满足
ek 1 lim p k e k
c
--------(9)
则称迭代法p阶收敛,当p 1时称为线性收敛, p 1时 称为超线性收敛, p 2时称为平方收敛
3 2
(2) 如果将原方程化为等价方程
x3
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 已经收敛,故原方程的解为
Ln | xn | | x1 x0 | 1 L
可得
(1 L) ln | x1 x0 | n ln L
(2) 事后误差估计法。由于
L | xn | | xn xn 1 | 1 L
数值分析
对于预先给定的误差限 即要求| xk x*|
由(6)式,只要
简单迭代法的加速方案： x ˆn 1 ( xn ) ˆn 1 ) q '( x q ˆn 1 ˆn 1 xn ) xn 1 x (x 1 q 迭代次数大大减少，总的计算工作量减少， 但涉及导数值的计算不便于实际应用。
埃特金迭代法求方程的实根
L xk xk 1 1 L 1 L xk xk 1 --------(8) L
因此,当
迭代就可以终止, xk 可以作为方程的近似解
定义1：如果存在 x * 的某个邻域 R : x x * ，使迭代过程
xk 1 ( xk ) 对于任意初值 x0 R均收敛，则称迭代过程 xk 1 ( xk ) 在根 x * 邻近具有局部收敛性。
x
2e 因此采用迭代函数 x 1 ( x ) 10
x
取初值x0 0
x1 = 0.1000000 x2 = 0.0894829 x3 = 0.0906391 x4 = 0.0905126 x5 = 0.0905265 x6 = 0.0905250 x7 = 0.0905251
因此原方程的解为
简单迭代法加速方案的改进：
( xk 2 xk 1 ) 2 xk xk 2 xk 2 2 xk 1 xk Aitken加速方案: 2 ( x x ) x k 1 k k xk 2 2 xk 1 xk 避免了导数值的计算，但需要用两次迭代值进行计算。
L xk x * xk xk 1 1 L 2 L xk 1 xk 2 1 L
Lk x1 x0 1 L 由于L 1, lim( xk x*) 0
k
因此对任意初值x0 , 迭代法xk 1 ( xk )均收敛于x *
例1.
解:
用迭代法求解方程2 x x 1 0
3
(1) 将原方程化为等价方程
x 2x 1 如果取初值x0 0,由迭代法(3), 得
3
x0 0
x1 2 x 1 1
3 0
x2 2 x 1 3
3 1
x3 2 x 1 55

显然迭代法发散
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
xk 1 x * xk x *
p
即迭代法xk 1 ( xk )的收敛阶是p
定理3. 如果迭代法迭代函数 ( x)在根x * 附近满足：
p! ( p 1)! ( p) ( x *) , ( k ) p!

( p ) ( x*) ( p 1) ( x*)
2e x1 10
x0
0.1
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
--------(3) xk 1 ( xk ) (k 0,1,2 ,)

称(3)式为求解非线性方程(2)的简单迭代法
称 ( x )为迭代函数, 称xk 为第k步迭代值
如果存在一点x*, 使得迭代序列{ xk }满足
lim xk x *
k
--------(4)
则称迭代法(3)收敛,否则称为发散
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], 有
定理 2 若x*是 的不动点, 在x*的某邻域上存在 且连续, 并满足
* * 0 | ( x ) | 1, 则迭代过程
xk 1 ( xk ) 在x 的邻域是线性收敛的.
例2. 用迭代法求方程的近似解,精确到小数
点后6位
解:
e 10 x 2 0 x 由于e 0,
( p)
而
p!
xk 1 ( xk ) ( x*)
( p)

( p)
( x *) p ( xk x *) p!
xk 1 x * ( x *) ( x x *) p k
p!

( p 1) ( x*)
( p 1)!
( xk x *) p 1
迭代函数的构造有关
什么形式的迭代法
能够收敛呢?
x 1.0000
如果将(2)式表示为 y ( x) 与方程(2)同解 yx yx
y ( x)

yx
收敛
y ( x)
O x * x2
x1
y ( x)
( x)在x * 附近较平缓
yx yx
x0
O
x1
第7章 方程与方程组的迭代解法
§ 7.2 不动点迭代法及其收敛定理
一、迭代法原理
将非线性方程 f (x) = 0 化为一个同解方程
x ( x)
并且假设 ( x)为连续函数
--------(2)
任取一个初值x0 , 代入(2)的右端, 得 x1 ( x0 ) 继续 x2 ( x1 )
x
则2 10 x 0
x 0.2
x 0时,
0 e 1,
x
2 10 x 2
因此[0,0.2]为有根区间
本题迭代函数有两种构造形式
2e x 1 ( x) 10
x
x 2 ( x) ln(2 10 x)
0.2
e e ( x)| | 1 1 由于 10 10 10 | 2 ( x)| 5 2 10 x
显然, p越大,收敛速度也就越快
那么, 如何确定p , 从而确定收敛阶呢？
如果迭代函数 ( x )在精确解x * 处充分光滑, 即处处可导
将 ( x)在x * 作Taylor展开, 有
( x) ( x*) ( x*)( x x*)

( p 1 )