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