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

1、7.4 -7.5 牛顿法及其推广,/* Newton Method */,一、牛顿迭代法的公式,二、牛顿迭代法的改进与推广,1,PPT学习交流,原理：将非线性方程线性化泰勒展开 /* Taylors expansion */,取 x0 x* ，将 f(x*) 在 x0 做一阶泰勒展开:, 在 x0 和 x*之间。,将 (x* x0)2看成高阶小量，则有：,一、牛顿迭代法的公式,2,PPT学习交流,线性 /* linear */,x0,只要 每一步迭代都有f ( xk ) 0， 而且 ，则 x*就是 f 的根。,3,PPT学习交流,牛顿迭代法的基本思想,将非线性方程 f(x)=0 的求根问题归结

2、为计算一系列线性方程的求根问题。,4,PPT学习交流,牛顿迭代法的计算步骤,(1)给出初始近似根 x0 及精度；,(3)若 ，转向(4)， 否则 ，转向(2);,(4)输出满足精度的根 x1 ，结束。,(2)计算,5,PPT学习交流,例,用牛顿迭代法求方程,在 x=0.5 附近的根。取,解,其牛顿迭代公式为,取初值 x0=0.5 ，迭代结果见下表,易见,故,6,PPT学习交流,k 0 1 2 3 xk 0.880000 0.884688 0.884675 0.884675,例 2 计算 的近似值, =10-6 x0=0.88,解：令 x=,问题转化为求f(x)=x2-0.78265=0 的正根

3、,由牛顿迭代公式,xk+1= xk-(xk)/(xk)= xk/2+0.78265/2xk,迭代结果,满足了精度要求,故,0.884675,7,PPT学习交流,设 f C2a, b，若 x* 为 f (x) 在a, b上的根，且 f (x*) 0，则存在 x* 的邻域,Newtons Method产生的序列 xk 收敛到x*，且满足,使得任取初值, Newtons Method 有 ，只要 就有 p 2。重根是线性收敛的。,8,PPT学习交流,证明： Newtons Method 事实上是一种特殊的不动点迭代，其中,收敛,则,9,PPT学习交流,由泰勒展开：,在单根 /*simple root

4、 */ 附近收敛快,10,PPT学习交流,注： Newtons Method 收敛性依赖于x0 的选取。,x*,x0,x0,x0,11,PPT学习交流,注 (1) 牛顿法要求初值充分接近根以保证局部收敛性。,(2)牛顿迭代法的主要优点是收敛较快，是平方收敛的缺点是公式中需要求 f(x) 的导数。若 f(x)比较复杂，则使用牛顿公式就大为不便。,12,PPT学习交流, 重根 /* multiple root */ 加速收敛法：,问题1: 若 ，Newtons Method 是否仍收敛？,设 x*是 f 的 n 重根，则：,因为 Newtons Method 事实上是一种特殊的不动点迭， 其中,二

5、、牛顿迭代法的改进与推广 /* improvement and generalization */,且,13,PPT学习交流,K1: 有局部收敛性，但重数 n 越高，收敛越慢。,则,问题2: 如何加速重根的收敛？,K2: 将求 f 的重根转化为求另一函数的单根。,?,令,则 f 的重根 = 的单根。,14,PPT学习交流, 下山法 /* Descent Method */ Newtons Method 局部微调：,原理：若由 xk 得到的 xk+1 不能使 | f | 减小，则在 xk 和 xk+1 之间找一个更好的点 ，使得,注： = 1 时就是Newtons Method 公式。 当 =

6、1 代入效果不好时，将 减半计算。 。,15,PPT学习交流, 弦截法 /* Secant Method */,Newtons Method 一步要计算 f 和 f ，相当于2个函数值，比较费时。现用 f 的值近似 f ，可少算一个函数值。,切线 /* tangent line */,割线 /* secant line */,切线斜率 割线斜率,需要 2 个初值 x0 和 x1 。,收敛比Newtons Method 慢，且对初值要求同样高。,16,PPT学习交流,弦截法与牛顿法相比较,相同之处：都是线性化方法,不同之处：牛顿法在计算xk+1时只用到前一步的值xk，故这种方法称为单点迭代法。,而弦截法在求xk+1时要用到前两步的值xk和xk-1，因此这种方法称为多点迭代法。,17,PPT学习交流,有关弦截法的收敛速度,与牛顿法相比，弦截法的收敛速度也是比较快的。可以证明，弦截法具有超线性收敛速度，收敛阶为,即,18,PPT学习交流,例,用弦截法求方程,在x=0.5附近的根。取,解,取x0=0.5，x1=0.6作为初始近似根，令,其弦截法迭代公式为,19,PPT学习交流,迭代结果见下表,易见,故,取初值