《数值分析7-4,5(牛顿法,弦截法)》由会员分享，可在线阅读，更多相关《数值分析7-4,5(牛顿法,弦截法)（22页珍藏版）》请在金锄头文库上搜索。
1、7.4 -7.5 牛顿法及其推广/* Newton Method */一、牛顿迭代法的公式二、牛顿迭代法的改进与推广原理：将非线性方程线性化泰勒展开 /* Taylors expansion */取 x0 x* ，将 f(x*) 在 x0 做一阶泰勒展开: 在 x0 和 x*之间。将 (x* x0)2看成高阶小量，则有：一、牛顿迭代法的公式线性 /* linear */xyx* x0只要 每一步迭代都 有f ( xk ) 0， 而且 ，则 x*就是 f 的根。牛顿迭代法的基本思想将非线性方程 f(x)=0 的求根问题归结为计算一系列线性方程的求根问题。牛顿迭代法的计算步骤(1)给出初始近似根
2、x0 及精度；(3)若 ，转向(4)，否则 ，转向(2);(4)输出满足精度的根 x1 ，结束。(2)计算例用牛顿迭代法求方程 在 x=0.5 附近的根。取解其牛顿迭代公式为取初值 x0=0.5 ，迭代结果见下表易见故k 0 1 2 3 xk 0.5 0.57102 0.56716 0.56714k 0 1 2 3xk 0.880000 0.884688 0.884675 0.884675例 2 计算 的近似值, =10-6 x0=0.88解：令 x=问题转化为求f(x)=x2-0.78265=0 的正根由牛顿迭代公式xk+1= xk-(xk)/(xk)= xk/2+0.78265/2xk 迭
3、代结果满足了精度要求,故0.884675设 f C2a, b，若 x* 为 f (x) 在a, b上的根 ，且 f (x*) 0，则存在 x* 的邻域定理（局部收敛性）Newtons Method产生的序列 xk 收敛到 x*，且满足使得任取初值 Newtons Method 有 ，只要就有 p 2。重根是线性收敛的。证明： Newtons Method 事实上是一种特 殊的不动点迭代，其中收敛则由泰勒展开：在单根 /*simple root */ 附近收敛快只要 f (x*) 0，则令 可得结论。注：注： Newtons Method 收敛性依赖于x0 的 选取。x*x0x0x0注 (1)
4、牛顿法要求初值充分接近根以保 证局部收敛性。(2)牛顿迭代法的主要优点是收敛较快， 是平方收敛的缺点是公式中需要求 f(x) 的导数。若 f(x)比较复杂，则使用牛顿 公式就大为不便。 重根 /* multiple root */ 加速收敛法： 问题1: 若 ，Newtons Method 是否仍收敛？设 x*是 f 的 n 重根，则：因为 Newtons Method 事实上是一种特殊 的不动点迭，其中二、牛顿迭代法的改进与推广 /* improvement and generalization */且K1: 有局部收敛性，但重数 n 越高，收敛 越慢。则问题2: 如何加速重根的收敛？K2:
5、 将求 f 的重根转化为求另一函数的单根 。?令 则 f 的重根 = 的单根。 下山法 /* Descent Method */ Newtons Method 局部微调 ：原理：若由 xk 得到的 xk+1 不能使 | f | 减小，则在 xk 和 xk+1 之间找一个更好的点 ，使得 xkxk+1注：注： = 1 时就是Newtons Method 公式。当 = 1 代入效果不好时，将 减半计算。 。 弦截法 /* Secant Method */ Newtons Method 一步要计算 f 和 f ，相 当于2个函数值，比较费时。现用 f 的值近 似 f ，可少算一个函数值。x0x1切线
6、 /* tangent line */割线 /* secant line */切线斜率 割线斜率需要 2 个初值 x0 和 x1 。收敛比Newtons Method 慢，且对初 值要求同样高。弦截法与牛顿法相比较相同之处：都是线性化方法不同之处：牛顿法在计算xk+1时只用到前 一步的值xk，故这种方法称为单点迭代法 。而弦截法在求xk+1时要用到前两步的值xk 和xk-1，因此这种方法称为多点迭代法。有关弦截法的收敛速度与牛顿法相比，弦截法的收敛速度也是 比较快的。可以证明，弦截法具有超线 性收敛速度，收敛阶为即例用弦截法求方程 在x=0.5附近的根。取 解取x0=0.5，x1=0.6作为初始近似 根，令其弦截法迭代公式为迭代结果见下表k 0 1 2 3 4 xk 0.5 0.6 0.56754 0.56715 0.56714易见 故取初值 x0=0.5 ，牛顿迭代结果见下表k 0 1 2 3 xk 0.5 0.57102 0.56716 0.56714抛物线法本质：将非线性方程转化为一元二次方程的求解。有两种转化方法！作业：习题 7，12，13
