数值分析7-4,5(牛顿法,弦截法).ppt

7 4 7 5牛顿法及其推广 NewtonMethod 一 牛顿迭代法的公式 二 牛顿迭代法的改进与推广 原理 将非线性方程线性化 泰勒展开 Taylor sexpansion 取x0 x 将f x 在x0做一阶泰勒展开 在x0和x 之间 将 x x0 2看成高阶小量 则有 一 牛顿迭代法的公式 线性 linear x0 只要每一步迭代都有f xk 0 而且 则x 就是f的根 牛顿迭代法的基本思想 将非线性方程f x 0的求根问题归结为计算一系列线性方程的求根问题 牛顿迭代法的计算步骤 1 给出初始近似根x0及精度 3 若 转向 4 否则 转向 2 4 输出满足精度的根x1 结束 2 计算 例 用牛顿迭代法求方程 在x 0 5附近的根 取 解 其牛顿迭代公式为 取初值x0 0 5 迭代结果见下表 易见 故 k0123xk0 8800000 8846880 8846750 884675 例2计算的近似值 10 6x0 0 88 解 令x 问题转化为求f x x2 0 78265 0的正根 由牛顿迭代公式 xk 1 xk xk xk xk 2 0 78265 2xk 迭代结果 满足了精度要求 故 0 884675 设f C2 a b 若x 为f x 在 a b 上的根 且f x 0 则存在x 的邻域 Newton sMethod产生的序列 xk 收敛到x 且满足 使得任取初值 Newton sMethod有 只要就有p 2 重根是线性收敛的 证明 Newton sMethod事实上是一种特殊的不动点迭代 其中 收敛 则 由泰勒展开 在单根 simpleroot 附近收敛快 注 Newton sMethod收敛性依赖于x0的选取 x x0 x0 x0 注 1 牛顿法要求初值充分接近根以保证局部收敛性 2 牛顿迭代法的主要优点是收敛较快 是平方收敛的缺点是公式中需要求f x 的导数 若f x 比较复杂 则使用牛顿公式就大为不便 重根 multipleroot 加速收敛法 问题1 若 Newton sMethod是否仍收敛 设x 是f的n重根 则 因为Newton sMethod事实上是一种特殊的不动点迭 其中 二 牛顿迭代法的改进与推广 improvementandgeneralization 且 K1 有局部收敛性 但重数n越高 收敛越慢 则 问题2 如何加速重根的收敛 K2 将求f的重根转化为求另一函数的单根 令 则f的重根 的单根 下山法 DescentMethod Newton sMethod局部微调 原理 若由xk得到的xk 1不能使 f 减小 则在xk和xk 1之间找一个更好的点 使得 注 1时就是Newton sMethod公式 当 1代入效果不好时 将 减半计算 弦截法 SecantMethod Newton sMethod一步要计算f和f 相当于2个函数值 比较费时 现用f的值近似f 可少算一个函数值 切线 tangentline 割线 secantline 切线斜率 割线斜率 需要2个初值x0和x1 收敛比Newton sMethod慢 且对初值要求同样高 弦截法与牛顿法相比较 相同之处 都是线性化方法 不同之处 牛顿法在计算xk 1时只用到前一步的值xk 故这种方法称为单点迭代法 而弦截法在求xk 1时要用到前两步的值xk和xk 1 因此这种方法称为多点迭代法 有关弦截法的收敛速度 与牛顿法相比 弦截法的收敛速度也是比较快的 可以证明 弦截法具有超线性收敛速度 收敛阶为 即 例 用弦截法求方程 在x 0 5附近的根 取 解 取x0 0 5 x1 0 6作为初始近似根 令 其弦截法迭代公式为