1.2,牛顿法,弦截法ppt课件

1、7.4 -7.5 牛顿法及其推广 /* Newton Method */一、牛顿迭代法的公式一、牛顿迭代法的公式二、牛顿迭代法的改进与推广二、牛顿迭代法的改进与推广原理：将非线性方程线性化原理：将非线性方程线性化泰勒展开泰勒展开 /* Taylors expansion */取取 x0 x* ，将，将 f(x*) 在在 x0 做一阶泰勒展开做一阶泰勒展开:20000)*(! 2)()*)()(*)(xxfxxxfxfxf 在在 x0 和和 x*之间。之间。将将 (x* x0)2看成高阶小量，则有：看成高阶小量，则有：一、牛顿迭代法的公式一、牛顿迭代法的公式)*)()(*)(0000 xxxfx

2、fxf )()(*000 xfxfxx 线性线性 /* linear */xyx*x0)()(1kkkkxfxfxx 只要只要 每一步迭代都每一步迭代都有有f ( xk ) 0， 而而且且 ，那么那么 x*就是就是 f 的根。的根。*limxxkk 牛顿迭代法的基本思想牛顿迭代法的基本思想将非线性方程将非线性方程 f(x)=0 f(x)=0 的求根问题归的求根问题归结为计算一系列线性方程的求根问题。结为计算一系列线性方程的求根问题。 牛顿迭代法的计算步骤牛顿迭代法的计算步骤(1)(1)给出初始近似根给出初始近似根 x0 x0 及精度及精度；)()(0001xfxfxx (3)(3)假设假设 ，

3、转向，转向(4)(4)， 否则否则 ，转向，转向(2);(2); 01xx10 xx (4)(4)输出满足精度的根输出满足精度的根 x1 x1 ，完毕。，完毕。(2)(2)计算计算例例 00002. 023xx用牛顿迭代法求方程用牛顿迭代法求方程01 xxe在在 x=0.5 x=0.5 附近的根。取附近的根。取解解其牛顿迭代公式为其牛顿迭代公式为kxkkkxexxxk 11取初值取初值 x0=0.5 x0=0.5 ，迭代结果见下表，迭代结果见下表易见易见故故567. 03 xxk 0 1 2 3xk 0.5 0.57102 0.56716 0.5671400005. 0 k 0 1 2 3 x

4、k 0.880000 0.884688 0.884675 0.884675例例 2 2 计算计算 的近似值的近似值, , =10-6 =10-6 x0=0.88x0=0.880.782650.78265解：令解：令 x= x=问题转化为求问题转化为求f(x)=x2-0.78265=0 f(x)=x2-0.78265=0 的正根的正根由牛顿迭代公式由牛顿迭代公式xk+1= xk-(xk)/(xk)= xk/2+0.78265/2xk迭代结果迭代结果满足了精度要求满足了精度要求,故故0.782650.884675设设 f C2a, b，假设，假设 x* 为为 f (x) 在在a, b上的上的根，且

5、根，且 f (x*) 0，则存在，则存在 x* 的邻域的邻域*)(xB *)(0 xBx *)(2*)()*(*lim21xfxfxxxxkkk 定理定理（局部收敛性）（局部收敛性）Newtons Method产生的序列产生的序列 xk 收敛到收敛到x*，且满足，且满足使得任取初值使得任取初值 Newton Newtons Method s Method 有有 ，只要，只要 就有就有 p p 2 2。重根是线性收敛的。重根是线性收敛的。*)(2*)(|lim21xfxfeekkk 0*)( xf证明：证明： Newton Newtons Method s Method 事实上是一种特事实上是一

6、种特殊的不动点迭代，其中殊的不动点迭代，其中)()()(xfxfxxg 10*)(*)(*)(*)(2xfxfxfxg局部收敛局部收敛那那么么 由泰勒展开：由泰勒展开：2)*(!2)()*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(! 2)()()(*kkkkkkxxxffxfxfxx 1 kx)(2)()*(*21kkkkxffxxxx 在单根在单根 /*simple root */ 附近收敛附近收敛快快只要只要 f (x*) 0，则令，则令 可得结论。可得结论。 kx*x0 x0 x0注注 (1) (1) 牛顿法要求初值充分接近根以保牛顿法要求初值充分接近根以保证局部收敛

7、性。证局部收敛性。(2)(2)牛顿迭代法的主要优点是收敛较快，牛顿迭代法的主要优点是收敛较快，是平方收敛的缺点是公式中需要求是平方收敛的缺点是公式中需要求 f(x) f(x) 的导数。假设的导数。假设 f(x) f(x)比较复杂，则使用牛比较复杂，则使用牛顿公式就大为不便。顿公式就大为不便。 重根重根 / /* * multiple root multiple root * */ / 加速收敛法：加速收敛法：问题问题1: 假设假设 ，Newtons Method 是否仍收敛？是否仍收敛？0*)( xf设设 x*是是 f 的的 n 重根，那么：重根，那么：因为因为 Newtons Method

8、事实上是一种特殊事实上是一种特殊的不动点迭，的不动点迭，其中其中)()()(xfxfxxg 二、牛顿迭代法的改进与推广二、牛顿迭代法的改进与推广/* improvement and generalization */)(*)()(xqxxxfn 0*)( xq且且 22*)(*)(*)(*)(1|*)(|xfxfxfxfxg111 nK1: 有局部收敛性，但重数有局部收敛性，但重数 n 越高，收敛越高，收敛越慢。越慢。那么那么问题问题2: 如何加速重根的收敛？如何加速重根的收敛？K2: 将求将求 f 的重根转化为求另一函数的单根。的重根转化为求另一函数的单根。?令令)()()(xfxfx 那么

9、那么 f f 的重根的重根 = = 的单根。的单根。 下山法下山法 / /* * Descent Method Descent Method * */ / Newton Newtons Method s Method 局部微调：局部微调：原理：若由原理：若由 xk xk 得到的得到的 xk+1 xk+1 不能使不能使 | f | | f | 减小，则在减小，则在 xk xk 和和 xk+1 xk+1 之间找一个更好的之间找一个更好的点点 ，使得，使得 1 kx)()(1kkxfxf xkxk+1,)1(1kkxx 1, 0 )()()1()()(1kkkkkkkkxfxfxxxfxfxx 弦截

10、法弦截法 / /* * Secant Method Secant Method * */ / Newtons Method 一步要计算一步要计算 f 和和 f ，相当于，相当于2个函数值，比较费时。现用个函数值，比较费时。现用 f 的值近似的值近似 f ，可少算一个函数值。可少算一个函数值。x0 x1切线切线/* tangent line */割线割线/* secant line */切线斜率切线斜率 割线斜率割线斜率11)()()( kkkkkxxxfxfxf)()()(111 kkkkkkkxfxfxxxfxx需要需要 2 个初值个初值 x0 和和 x1 。收敛比收敛比Newtons Me

11、thod 慢，且对初慢，且对初值要求同样高。值要求同样高。弦截法与牛顿法相比较弦截法与牛顿法相比较相同之处：都是线性化方法相同之处：都是线性化方法不同之处：牛顿法在计算不同之处：牛顿法在计算xk+1xk+1时只用到前时只用到前一步的值一步的值xkxk，故这种方法称为单点迭代法。，故这种方法称为单点迭代法。而弦截法在求而弦截法在求xk+1xk+1时要用到前两步的值时要用到前两步的值xkxk和和xk-1xk-1，因此这种方法称为多点迭代，因此这种方法称为多点迭代法。法。有关弦截法的收敛速度有关弦截法的收敛速度与牛顿法相比，弦截法的收敛速度也是与牛顿法相比，弦截法的收敛速度也是比较快的。可以证明，弦

12、截法具有超线比较快的。可以证明，弦截法具有超线性收敛速度，收敛阶为性收敛速度，收敛阶为618. 1)51(21 p即即)( , 0|618. 11 kcxxxxkk例例用弦截法求方程用弦截法求方程01 xxe在在x=0.5附近的根。取附近的根。取解解取取x0=0.5，x1=0.6作为初始近似作为初始近似根，令根，令0)( xexxf其弦截法迭代公式为其弦截法迭代公式为)()(1111 kkxxkkxkkkxxeexxexxxkkk00005. 0 迭代结果见下表迭代结果见下表k 0 1 2 3 4 xk 0.5 0.6 0.56754 0.56715 0.56714 00001. 034xx易见