第五章 迭代法51迭代过程的收敛性 迭代加速.ppt

文档介绍：第五章方程求根的迭代法
迭代法的思想
压缩映像原理
局部收敛性
收敛性的阶
第一节迭代过程的收敛性
非线性方程的根
求 f (x) = 0 的根
代数方程: f (x) = a0 + a1x + . . . + anxn
超越方程: f (x) 含超越函数,如 sin(x), ex, lnx 等
实根与复根
根的重数
f (x) = ( x – x*)m · g(x) 且 g(x*)  0, 则 x* 为 f (x) 的 m 重根
有根区间:[a, b] 上存在 f (x) = 0 的一个实根
在有根的前提下求出方程的近似根。
研究内容:
(x) 的不动点x*
迭代法的思想
f (x) = 0
x = (x) 称为迭代函数
等价变换
基本思想
从一个给定的初值 x0 出发,计算 x1 = (x0), x2 = (x1), …
若收敛,即存在 x* 使得,则由的连续性和可得 x* = (x*),即 x* 是的不动点,也就是 f (x) 的零点。
具体做法:
不动点迭代
f (x) 的零点x*
几何含义:
求曲线 y = (x) 与直线 y = x 的交点
xk+1 = (xk)
x
y
y = x
x
y
y = x
x
y
y = x
x
y
y = x
x*
x*
x*
x*
y= (x)
y= (x)
y= (x)
y=(x)
x0
p0
x1
p1
x0
p0
x1
p1

x0
p0
x1
p1

x0
p0
x1
p1

x2

例 x3x1 = 0, [1,2], 取 x0=
迭代公式1:
迭代公式2:
计算结果:
公式1:
公式2:
怎么判断迭代公式收敛或发散呢?
精确解x* =
...
压缩映像原理

设(x)C[a, b] 且一阶导数连续,若
(2)  0  L < 1,使得| ’(x) |  L 对 x[a, b] 成立
则函数 f (x) = x - (x) 在[a, b] 中有唯一的零点 x*。
(压缩映像原理,不动点原理)
x* 称为(x) 的不动点
(x*) = x*
(1) a (x)  b 对一切 x[a, b] 都成立
简证:
f(a) = a - (a) 0 , f(b) = b - (b)  0
f(x) 在[a, b] 上有零点。
唯一性:反证法,假设存在 x*, y*[a, b] 使得
x* = (x*)
y* = (y*)
矛盾!
封闭性
压缩性
收敛性分析

设(x)C[a, b] 且一阶导数连续,若
(2)  0  L < 1,使得| ’(x) |  L 对 x[a, b] 成立
(1) a (x)  b 对一切 x[a, b] 都成立
则有
(a) 对任意 x0[a, b],由 xk+1 = (xk) 产生的迭代序列
均收敛到(x) 在[a, b] 中的唯一不动点 x*。
(b) 有如下的误差估计
可用| x k+1-xk | 来
控制收敛精度,
L 越小收敛越快.
后验估计:
先验估计:
证: (a) 由压缩映像定理可知,不动点 x* 存在且唯一。
(b)
又
全局收敛与局部收敛
定理的条件保证了不动点迭代的全局收敛性。
即迭代的收敛性与初始点的选取无关。
这种在 x* 的邻域内具有的收敛性称为局部收敛性。
定理中的条件| ’(x) |  L < 1 可以适当放宽
(2’) ’(x) 在 x* 的某个邻域内连续,且| ’(x*) | <1
由’(x) 的连续性及| ’(x*) | <1 即可推出:
若(x)的一阶导数连续, 且满足条件(2’), 则一定存在 x* 的某个邻域 N(x*) =[x*-, x* +], 使得对
 x N(x*)都有| ’(x) |  L < 1, 则由x0 N(x*) 开始的迭代都收敛。
具有局部收敛性的迭代计算上不一定收敛,它是否收敛还要看初值是否取的恰当;
而不具有局部收敛性的迭代对任何初值都不可能收敛。

例用不同方法求 x23 = 0的根, 取 x0=2.
迭代公式1:
迭代公式2:
迭代公式3:
迭代公式4:
计算结果:
怎么判断收敛的迭代公式的速度快慢呢?
精确值: