6.09级7.5-2牛顿修正.ppt

* 5.2 Newton法收敛定理 §5 牛顿迭代法 定理6和定理7都要求满足 初值选取较困难. 在实际应用中可以放宽对初值的要求,即有以下的非局部收敛定理. 注 ② 证Newton序列是单调序列,且是有界序列,因此有极限； ① 证f(x)=0在[a,b]上 有唯一解x*； 分析 分以下几步证明: 需要证明为什么Newton序列单调二阶收敛于 的唯一解x*. 定理中 x0容易选取， 只要满足 即可. ③ 证明Newton序列的极限值就是f(x)=0的唯一解x*， 最后由定理10得Newton序列二阶收敛于唯一解x*. 在[a,b]上 定理11 （Newton法非局部收敛定理） 且满足： 在[a,b]上不变号； 则对 满足 Newton序列单调二阶收敛于 在[a,b]上的唯一解x*. 在[a,b]上不取零， 证明 ① 先证f(x)=0有唯一解. ② 证Newton序列单调,有界,从而有极限. 考虑由牛顿法得到的x1的特性, 因为f(x)连续, 所以f(x)=0在[a,b]上至少有一个 解,设为x*. 又因为f (x)连续, 则f (x)在[a,b]上 恒正或恒负, 从而f(x)在[a,b]上 严格单调上升或下降, f(x)=0在[a,b] 上最多只有一个解. 因此f(x)=0在[a,b] 内有唯一解x*. (考虑x1与x0、x*的大小关系, 进一步讨论f (x1)的符号.) 另外, 比较以上两式,并考虑到 f(x0)与 同号,得x1介于x0与x* 不变号. 首先由 f (x1)与 f (x0) 同号 (否则 f(x)=0不是有唯一解)， 同时可得 同理由 得由牛顿法得到的x2 必介于x1与 x*之间，且 f (x2)与f (x1)同号， ，由此得到的牛顿序列 之间， (若 则 若 则 )且 则有 满足 xk+1介于xk与x*之间, 从而 且 又单调、有界序列必有极限， 设极限为 并有界, 是单调序列 ③ 证 对 两边取 时的极限,得 由于 从而 又由f(x)=0在[a,b] 上只有唯一解x*. 得 即 最后,由定理7知{xk}二阶收敛于x*. # 例4 用Newton法求解 解 首先可以判断解在(0,1)内. 在(0,1)上 (恒正) (不变号) 则Newton迭代序列单调二阶收敛到 在(0,1)内的唯一根 , Newton迭代的计算结果如下表 表4-2 优点 收敛速度快 . 缺点 1. 需要每次计算导数值 f (x)，如果函数f (x)比较复杂， 使用牛顿公式不方便 . 2. 对初值x0要求苛刻. 5.3 Newton切线法的修正算法 1.简化牛顿切线法 思想方法 用常数c 代替牛顿切线法中的 f (xk) 简化牛顿切线法公式 至少是线性收敛， 收敛性 当取c = f (xk)时，是二阶收敛. 在初始值x0，取c = f (x0) , c的选取方法 在xk附近的一些点上 可取c = f (xk) . 这样即保证了计算简单又使收敛较快，在某些点上 接近平方收敛. 2.Newton下山法(修正的Newton法) 用牛顿切线法求方程x 3-x-1= 0在x=1.5附近的一个根 . 解 取迭代初值x0=1.5，用牛顿公式 计算结果如表4-3所示 . 1.5 1.34783 1.32520 1.32472 1.32472 0 1 2 3 4 表4-3 其中x3=1.32472 的每一位数字都是有效数字. 例5 如果改用 x0=0.6作为初值，迭代一次得x1=17.9, 这个结果反而比x0 更偏离了所求的根 x*. 为了防止迭代发散，对迭代过程附加一基本 要求,即保证函数值单调下降 ，满足这项要求的算 法称下山法. (1) 下山序列的定义 若视|f(x)|为f(x)在x点的高度,则 是山谷最低点. 定义 若序列 满足 ，称 是f(x)的一个 下山序列. 下山序列的极限点,不一定是f(x)＝0的解. 方程f(x)＝0的解 满足： ，称 是|f(x)| 的最小点. 注 (2) 收敛的牛顿序列除去有限点外一定是下山序列 因为 中值定理 (3) 下山法 引理1 则一定存在 成立 分析 该式子实际上是两个函数值的比较, 即是点x与邻近点 的函数值, 而点x与点 只差 且含有 f(x)的导数 由已知考虑用导数的定义, 时,形如: 的导数定义. 证明 由导数的定义 得 即 引理1 则一定存在 成立 于是由极限的概念, 只要 有 存在 于是由极限的概念, 只要 有 从而 则 # 即 存在 牛顿下山法的定义 是f(x)在 点的下山方向.在牛顿 其中 称为下山因子. 说明 (1)当 时, 牛顿下山法为标准的 牛顿法； 当 时, 此时 不收敛于 因此为保证收敛性, tk 不能太小. (2)下山