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

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 的求根问题归结的求根问题归结为计算一系列线性方程的求根问题。为计算一系列线性方程的求根问题。 牛顿迭代法的计算步骤牛顿迭代法的计算步骤(1)(1)给出初始近似根给出初始近似根 x0 及精度及精度；)()(0001xfxfxx (3)(3)若若 ，转向，转向(4)(4)， 否

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

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

5、的邻域的邻域*)(xB *)(0 xBx *)(2*)()*(*lim21xfxfxxxxkkk 定理定理（局部收敛性局部收敛性）Newtons Method产生的序列产生的序列 xk 收敛到收敛到x*，且满足，且满足使得任取初值使得任取初值 Newtons Method 有有 ，只要，只要 就有就有 p 2。重根是线性收敛的。重根是线性收敛的。*)(2*)(|lim21xfxfeekkk 0*)( xf证明：证明： Newtons Method 事实上是一种特事实上是一种特殊的不动点迭代，其中殊的不动点迭代，其中)()()(xfxfxxg 10*)(*)(*)(*)(2xfxfxfxg收敛收

6、敛则则 由泰勒展开：由泰勒展开：2)*(!2)()*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(! 2)()()(*kkkkkkxxxffxfxfxx 1 kx)(2)()*(*21kkkkxffxxxx 在单根在单根 /*simple root */ 附近收敛快附近收敛快只要只要 f (x*) 0，则令，则令 可得结论。可得结论。 kNewtons Method 收敛性依赖于收敛性依赖于x0 的的选取选取x*x0 x0 x0注注 (1) (1) 牛顿法要求初值充分接近根以保牛顿法要求初值充分接近根以保证局部收敛性。证局部收敛性。(2)(2)牛顿迭代法的主要优点是收敛较快，牛

7、顿迭代法的主要优点是收敛较快，是平方收敛的缺点是公式中需要求是平方收敛的缺点是公式中需要求 f(x) 的导数。若的导数。若 f(x)比较复杂，则使用牛顿比较复杂，则使用牛顿公式就大为不便。公式就大为不便。 重根重根 /* multiple root */ 加速收敛法：加速收敛法：问题问题1: 若若 ，Newtons Method 是否仍收敛？是否仍收敛？0*)( xf设设 x*是是 f 的的 n 重根，则：重根，则：因为因为 Newtons Method 事实上是一种特殊事实上是一种特殊的不动点迭的不动点迭，其中其中)()()(xfxfxxg 二、牛顿迭代法的改进与推广二、牛顿迭代法的改进与推

8、广/* improvement and generalization */)(*)()(xqxxxfn 0*)( xq且且 22*)(*)(*)(*)(1|*)(|xfxfxfxfxg111 nK1: 有局部收敛性，但重数有局部收敛性，但重数 n 越高，收敛越高，收敛越慢。越慢。则则问题问题2: 如何加速重根的收敛？如何加速重根的收敛？K2: 将求将求 f 的重根转化为求另一函数的单根。的重根转化为求另一函数的单根。?令令)()()(xfxfx 则则 f 的重根的重根 = = 的单根。的单根。 下山法下山法 /* Descent Method */ Newtons Method 局部微调：局部

9、微调：原理：原理：若由若由 xk 得到的得到的 xk+1 不能使不能使 | f | 减小，减小，则在则在 xk 和和 xk+1 之间找一个更好的点之间找一个更好的点 ，使，使得得 1 kx)()(1kkxfxf xkxk+1,)1(1kkxx 1, 0 )()()1()()(1kkkkkkkkxfxfxxxfxfxx = 1 时就是时就是Newtons Method 公式。公式。 当当 = 1 代入效果不好时，将代入效果不好时，将 减半计算。减半计算。 。 弦截法弦截法 /* Secant Method */ Newtons Method 一步要计算一步要计算 f 和和 f ，相，相当于当于2

10、个函数值，比较费时。现用个函数值，比较费时。现用 f 的值近的值近似似 f ，可少算一个函数值。，可少算一个函数值。x0 x1切线切线/* tangent line */割线割线/* secant line */切线斜率切线斜率 割线斜率割线斜率11)()()( kkkkkxxxfxfxf)()()(111 kkkkkkkxfxfxxxfxx需要需要 2 个初值个初值 x0 和和 x1 。收敛比收敛比Newtons Method 慢，且对初慢，且对初值要求同样高。值要求同样高。弦截法与牛顿法相比较弦截法与牛顿法相比较相同之处：相同之处：都是线性化方法都是线性化方法不同之处：不同之处：牛顿法在计

11、算牛顿法在计算x xk+1k+1时只用到前时只用到前一步的值一步的值x xk k，故这种方法称为，故这种方法称为单点迭代法单点迭代法。而弦截法在求而弦截法在求x xk+1k+1时要用到前两步的值时要用到前两步的值x xk k和和x xk-1k-1，因此这种方法称为，因此这种方法称为多点迭代法多点迭代法。有关弦截法的收敛速度有关弦截法的收敛速度与牛顿法相比，弦截法的收敛速度也是与牛顿法相比，弦截法的收敛速度也是比较快的。可以证明，弦截法具有超线比较快的。可以证明，弦截法具有超线性收敛速度，收敛阶为性收敛速度，收敛阶为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易见易见故故