第三章 迭代法s3 Newton迭代法.ppt

文档介绍：第三章迭代法
第三节 Newton迭代法
Newton迭代
基本思想:
将非线性方程线性化
设 xk 是 f (x)=0 的近似根, 将 f (x) 在 xk Taylor 展开:
, 在 xk 和 x 之间.
x
y
x*
xk
xk+1
条件: f’(x)  0
Newton迭代
Newton 法可以看作下面的不动点迭代:
其中
’(x*) = 0
Newton 法至少二阶局部收敛
定理
设 f(x) 在其零点 x* 的某个邻域内二阶连续可导且 f’(x)  0,则存在 x* 的某个邻域 N(x*) =[x*-, x* +], 使得对 x0 N(x*),Newton 法产生的序列以不低于二阶的收敛速度收敛到 x* 。(局部收敛定理)
Newton迭代法发散的例子
举例(一)
例: 设计一个二阶收敛算法计算(a > 0)。
解:转化为求 x2-a = 0 的正根
Newton 迭代:
二阶收敛
练****设计一个局部收敛的迭代算法只用加、减、乘法计算倒数1/a。
重根情形
设 x* 是 f(x) 的 m(m2) 重根,Newton法是否收敛?
Taylor 展式
Newton 迭代:
线性收敛。
且重数 m 越高,收敛越慢。
Taylor 展式
Taylor 展式
提高收敛阶
提高收敛速度
但 m 通常无法预先知道!
法一:取
二阶收敛
法二:将求 f(x) 的重根转化为求另一个函数的单根。
构造针对(x) 的具有二阶收敛的 Newton 迭代:
令,则 x* 是(x) 的单重根。