第4章解非线性方程-2

1、 4.4 非线性方程的牛顿法非线性方程的牛顿法 (Newton Method of Nonlinear Equations )内容提纲（内容提纲（Outline) 牛顿法及其几何意义牛顿法及其几何意义 收敛性及其收敛速度收敛性及其收敛速度 计算实例及其程序演示计算实例及其程序演示取取x0 0作为初始近似值作为初始近似值，将将 f (x)在在x0 0做做TaylorTaylor展开展开: :20000( )( )()()()()2!ff xf xfxxxxx0000( *)()()( *)f xf xfxxx000()*()f xxxfx1()()kkkkf xxxfx重复上述过程重复上述过程

2、0100()()fxxxfx作为第一次近似值作为第一次近似值一、牛顿法及其几何意义一、牛顿法及其几何意义Newton迭代公式迭代公式基本思路：基本思路：将非线性方程将非线性方程 f (x)=0 线性化线性化牛顿法的几何意义牛顿法的几何意义000:()()()Tangent line yf xfxxxxyx*x00100()()fxxxfxx 1x 21211()()fxxxfx牛顿法也称为切线法牛顿法也称为切线法, 迭代函数迭代函数( )( )( )f xxxfx（局部收敛性定理局部收敛性定理） 设设 f (x) C2a, b，若若 x* 为为 f (x) 在在a, b上的根上的根,且且 f

3、(x*) 0，则存在则存在 x* 的邻域的邻域 使得任取初始值使得任取初始值 ，Newton 法产生的序列法产生的序列 xk 收敛到收敛到 x*，且满足且满足( *)Ux0( *)xUx12|*|( *) |lim|*|2 |( *) |kkkxxfxxxfx至少平方收敛至少平方收敛二、牛顿法的收敛性与收敛速度二、牛顿法的收敛性与收敛速度定理定理4.4.1 2( *)( *)( *)01( *)fxf xxfx在在x*的附近的附近收敛收敛由由Taylor 展开：展开：2()0( *)()()(*)(*)2!kkkkkffxfxfxxxxx2()()*( *)()2()kkkkkkf xfxxx

4、xfxfx12*()( *)2()kkkkxxfxxfx 令令k ，由由 f (x*) 0，即可得结论。即可得结论。证明：证明：Newton法法实际上是一种特殊的迭代法实际上是一种特殊的迭代法( )( )( )f xxxfx迭代函数为：迭代函数为：思考题思考题1 若若 ，Newton法法是否仍收敛？是否仍收敛？( *)0fx设设 x* 是是 f 的的 m 重根，则令：重根，则令： 且且*( )()( )mf xxxq x( *)0q x2* 2*2( )( )( )( )( ) (1) ( )2 () ( )()( )( )() ( )f x fxxfxq x m mq xm xx q xxx

5、qxmq xxx q x1|( *)|11xm Answer1: 有局部收敛性有局部收敛性Answer2: 线性收敛线性收敛思考题思考题2当当x* 是是 f (x)=0的的m重根重根, 是否平方收敛？是否平方收敛？1*( )( )( )()()mmmfxq xq xxxxx*1*()()(1) ()() ()()()() ()kkkkkkkkkkkffmqqmqqxxxxxxxxxxxxxxxx*11*1|limlimkkkkkkmmxxxxNewton法的收敛性依赖于法的收敛性依赖于x0 的选取。的选取。 局部收敛定理对初始值局部收敛定理对初始值 x0 要求较高。要求较高。x*x0 x0 x

6、0 有根有根根唯一根唯一 (全局收敛性定理全局收敛性定理): 设设 f (x) C2a, b, 若若(1)f (a) f (b) 0；则由则由Newton法产生的序列法产生的序列 xk 单调地收敛到单调地收敛到f (x)=0 在在 a, b 的唯一根的唯一根x*,且收敛速度至少是二阶的且收敛速度至少是二阶的保证保证产生的序列产生的序列xk单调有界单调有界保证保证Newton迭迭代函数代函数将将a , b映射于自身映射于自身定理定理4.4.2 将将f (x* )在在 xk 处作处作TaylorTaylor展开展开*2( ) 0= ()()()()()2!kkkkkff xf xfxxxxx对迭代

7、公式两边取极限，得对迭代公式两边取极限，得*()()f xxxfx00001( )( )f xxxxfx又以以0)(, 0)(, 0)( 0 xfxfxf为例证明为例证明*2*211()() ()()2()()()2()kkkkkkkkkkkf xfxxxxfxfxfxxxxfx 说明数列说明数列 xk 有下界有下界*x1()()kkkkkf xxxxfx故故xk单调递减单调递减, 从而从而xk收敛收敛. .令令*limkkxx？定理定理4.4.3 (全局收敛性定理全局收敛性定理): 设设 f (x) C2a, b, 若若 (1) f (a) f (b) 0； (2) 在整个在整个a, b上上

8、 f (x) 0, f (x) 0 ； (3)( )( )|, |.( )( )f af bbabafaf b则对任何则对任何 , Newton 迭代格式产生的序列迭代格式产生的序列 都收敛于都收敛于f (x)=0 的根的根 x* .0 , xa bkx注注:定理的条件定理的条件(3) 保证了从保证了从 x*两侧任取两侧任取 x0 , 所得到所得到的数列的数列 xk 均在均在a , b内内.三、三、计算实例及其程序演示计算实例及其程序演示辅助工具辅助工具: : VC VC程序设计语言程序设计语言 MatlabMatlab数学软件数学软件 (1) (1) 选定初值选定初值x0 ,计算计算f (x

9、0) , f (x0) 计算步骤计算步骤(2) (2) 按公式按公式 迭代迭代 得新的近似值得新的近似值xk+1 1()()kkkkf xxxfx(3) (3) 对于给定的允许精度对于给定的允许精度 ，如果如果 则终止迭代，取则终止迭代，取 ; ;否则否则k=k+1，再转再转 步骤步骤(2)(2)计算计算*1kxx1|kkxx允许精度允许精度最大迭代次最大迭代次数数迭代信息迭代信息例例1 1：用用Newton法求方程法求方程 的根的根, 要求要求 20 xxe51| 10kkxx1ln(2)kkxx迭代格式一：迭代格式一：迭代格式二：迭代格式二：121kkxkkkxxexxe取初值取初值 x0

10、0.0,0.0,计算如下：计算如下：对迭代格式一对迭代格式一: : the iterative number is 27, the numerical solution is 0.442852706对迭代格式二对迭代格式二: the iterative number is 3, the numerical solution is 0.442854401解：解：例题例题2求函数求函数 的正实根的正实根精度要求：精度要求： 321019.6810.944f xxxx610从图形中我们可以从图形中我们可以看出：看出：在在x = 7和和 x = 8 之间有一单根；之间有一单根；在在x =1和和x =

11、2 之之间有一重根。间有一重根。用用MatlabMatlab画图，查看根的分布情形画图，查看根的分布情形初值初值x08.0 时,计算的是单根计算的是单根, The iterative number is 28,The numerical solution is 7.600001481初值初值x01.0 ,计算的是重根计算的是重根, The iterative number is 1356,The numerical solution is 1.198631981取初值取初值x08.0, ,用牛顿迭代公式计算如下：用牛顿迭代公式计算如下：取初值取初值x01.0, ,用牛顿迭代公式计算如下：用牛顿

12、迭代公式计算如下：小小 结结(1) 当当f (x)充分光滑且充分光滑且 x* 是是f (x) =0的单根时，牛的单根时，牛顿法在顿法在 x*的附近至少是平方收敛的。的附近至少是平方收敛的。(2) 当当f (x)充分光滑且充分光滑且 x* 是是f (x) =0的重根时，牛的重根时，牛顿法在顿法在 x*的附近是线性收敛的。的附近是线性收敛的。(3) Newton法在区间法在区间a , b上的收敛性依赖于初值上的收敛性依赖于初值x0 的选取。的选取。(4) Newton法的突出优点：收敛速度快法的突出优点：收敛速度快 缺点：需计算函数的导数。缺点：需计算函数的导数。四四 重根情形的重根情形的Newt

13、onNewton迭代法迭代法重根情形的重根情形的NewtonNewton迭代法是线性收敛的迭代法是线性收敛的, , 且有且有1( *)1xm 由此易知若迭代函数为：由此易知若迭代函数为：( )( )( )f xxxmfx则则NewtonNewton迭代格式迭代格式 为平方收敛为平方收敛. .1()()kkkkf xxxmfx但但 m 通常未知通常未知, ,故常用修改方法：故常用修改方法：( )( )( )f xu xfx令令若若x*为为f (x)的的m重根重根, 则则x*为为u (x) = 0的单根的单根, ,取取( )( )( )u xxxux则得则得: :12()()()()()kkkkk

14、kkf xfxxxfxf xfx此格式二阶收敛此格式二阶收敛, ,但要计算二阶导数但要计算二阶导数. .4.5 弦截法与抛物线法弦截法与抛物线法 一、一、 单点弦截法单点弦截法 固定一点固定一点 P0( x0 , f (x0), 用差商用差商 代替代替Newton公式中的公式中的 , 则得离散化的公式则得离散化的公式: 00()()kkf xf xxx()kfx100()()()()kkkkkf xxxxxf xf x称为单点弦截法称为单点弦截法, 是一种简单迭代法是一种简单迭代法. 几何意义几何意义: 依次用弦线代替曲线依次用弦线代替曲线, 用线性函数的零点作为用线性函数的零点作为f (x)

15、零点的近似值零点的近似值. 定理定理4.5.1 设设 f (x)在在a , b上满足：上满足： (1) f (a) f (b) 0; (2) 在在a , b上连续且不变号上连续且不变号; (3) 选取初始值选取初始值 , 使得使得 , 选选 定定a , b中的一个中的一个, 另一个为另一个为 . ( ),( )fxfx0 , xa b00(),()f xfx0 x1x则由迭代格式则由迭代格式 100()()()()kkkkkf xxxxxf xf x所产生的序列所产生的序列 xk 单调地收敛于单调地收敛于f (x)=0在在a , b上的唯一根上的唯一根 x*,且收敛速度是线性的且收敛速度是线性

16、的. 二、二、 双点弦截法双点弦截法 若若 用差商用差商 代替代替Newton公式中的公式中的 , 则得公式则得公式: 11()()kkkkf xf xxx()kfx111()()()()kkkkkkkf xxxxxf xf x称为双点弦截法称为双点弦截法. 注：注：双点弦截法与前面介绍的迭代法有明显区别双点弦截法与前面介绍的迭代法有明显区别, 前面所讲述前面所讲述迭代法计算迭代法计算 xk+1时只用到时只用到 xk , 故称为单步迭代故称为单步迭代; 而双点弦截法而双点弦截法计算计算 xk+1时时, 却同时用到前面两步的结果却同时用到前面两步的结果 xk 1和和 xk , 故称为多步故称为多

17、步迭代迭代.说明：说明：单点弦截是双点弦截的特殊情况单点弦截是双点弦截的特殊情况.几何解释：几何解释：xyx*xk 1xkxk+1Pk 1PkPk+1111(,(),(,()kkkkkkPxf xP xf x11()()kkkkf xf xxx为为 的斜率的斜率1kkP P直线方程为：直线方程为：11()()()()kkkkkkf xf xyf xxxxx定理定理4.5.2 (局部收敛定理局部收敛定理) 设设 f (x)=0, 如果：如果： (1) f (x)在根在根 x*的某个领域内有连续的二阶导数的某个领域内有连续的二阶导数, 且且(2) 任取任取 属于该领域属于该领域;则由双点弦截公式所

18、得序列则由双点弦截公式所得序列 收敛于根收敛于根 x*, 且收敛速度且收敛速度 ( )0fx01,xxkx151.6182P定理定理4.5.2 (全局性收敛定理全局性收敛定理) 设设 f (x) C2a , b, 且且 (1) f (a) f (b) 0； (2) 在整个在整个a, b上上 f (x) 0, f (x) 0 ； (3)( )( )|, |.( )( )f af bbabafaf b则则 由双点弦截公式所得序列由双点弦截公式所得序列 收敛于收敛于 f (x)=0 的唯一根的唯一根 x*. 01, , xxa bkx例例1：用用单点弦截和双点弦截求方程单点弦截和双点弦截求方程 在在

19、2,3内的特殊情况内的特殊情况.3( )250f xxx解解: (1) 单点弦截法单点弦截法2( )320,( )60,(2)10,(3)160fxxfxxff 取取 ， 单点弦截公式为：单点弦截公式为：013,2xx331332532215(3)(1,2,)221221kkkkkkkkkkkxxxxxxxkxxxx(2) 双点弦截法双点弦截法取取 ， 双点弦截公式为：双点弦截公式为：013,2xx3111331155(1,2,)22kkkkkkkkkx xxxxkxxxx三、弦截法与三、弦截法与Aitken迭代法的联系迭代法的联系 设设( )0( ).(),()( ()kkkkkf xxxy

20、xzyx 对于对于 在在 和和 两点处两点处使用弦截法使用弦截法, 则得则得( )( )0g xxx(, ()kkxg x(, ()kkyg y即为即为Aitken迭代公式迭代公式21 ()( ()2 ()kkkkkkkxxxxxxx 四、抛物线法四、抛物线法 若用过三点若用过三点 和和 的的抛物线抛物线2211(,(),(,()kkkkxf xxf x(,()kkxf x与与x 轴交点的横坐标作为轴交点的横坐标作为 xk+1 , 则得抛物线法或则得抛物线法或Mlller方方法法. 一条抛物线有两个实零点时一条抛物线有两个实零点时, 取与取与 xk 较近的那个零点较近的那个零点作为作为xk+1

21、 .12212121212121()()()()( )()()()()()()()()()()()kkkkkkkkkkkkkkkkkkkkkxxxxxxxxxf xf xxxxxxxxxxxxxf xxxxx4.5 非线性方程组的迭代算法非线性方程组的迭代算法一、不动点迭代格式一、不动点迭代格式(简单迭代格式简单迭代格式) 12121( )( )(,) ,( ) = ( ),( ),( ) )()TTnnkk= x xx0 +F xxxxxxxxx=x (0)(0)(0)012(,)Tn= xxxx取初值取初值 代入计算即可代入计算即可. 二、二、Newton迭代格式迭代格式111222121

22、2()0(,)0()0(,)0()()0(,)0nnnnnffxxxffxxxffxxx0 xxFxx( )( )( )1()( )()(),1,2,knkkiiijjjjfffxxinxxxx将非线性方程组线性化：将非线性方程组线性化：设设 为为 的第的第k 次近似解次近似解, 由由Taylor公公式得式得( )(, )kU*xx( ) 0 F x用线性方程组用线性方程组( )( )( )1()()()0,1,2,knkkiijjjjffxxinxxx即即( )( )( )()()()(*)kkk FxxxF x近似代替近似代替 , 用用(*)的解作为的解作为 的第的第k+1次近似次近似解解, 则得则得Newton迭代格式：迭代格式：( ) 0 F x( ) 0 F x(1)( )( )1( )()()(0,1,2,)k+kkkk xxFxF x这里这里111122221212()nnnnnnfffxxxfffxxxfffxx