第4章解非线性方程-2ppt课件

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

2、f xfxxx000()*()f xxxfx1()()kkkkf xxxfx重复上述过程重复上述过程 0100()()fxxxfx作为第一次近似值作为第一次近似值一、牛顿法及其几何意义一、牛顿法及其几何意义Newton迭代公式迭代公式基本思路：将非线性方程基本思路：将非线性方程 f (x)=0 f (x)=0 线性线性化化牛顿法的几何意义牛顿法的几何意义000:()()()Tangent line yf xfxxxxyx*x00100()()fxxxfxx 1x 21211()()fxxxfx牛顿法也称为切线法牛顿法也称为切线法, 迭代函数迭代函数( )( )( )f xxxfx（局部收敛性定

3、理）（局部收敛性定理） 设设 f (x)C2a, b，假设，假设 x* 为为 f (x) 在在a, b上的根上的根,且且 f (x*) 0，则存在，则存在 x* 的邻域的邻域 使得任取初使得任取初始值始值 ，Newton 法产生的序列法产生的序列 xk 收敛到收敛到 x*，且，且满足满足( *)Ux0( *)xUx12|*|( *) |lim|*|2 |( *) |kkkxxfxxxfx至少平方收敛至少平方收敛二、牛顿法的收敛性与收敛速度二、牛顿法的收敛性与收敛速度定理定理4.4.1 2( *)( *)( *)01( *)fxf xxfx在在x*的附近收敛的附近收敛由由Taylor Taylo

4、r 展开：展开：2()0( *)()()(*)(*)2!kkkkkffxfxfxxxxx2()()*( *)()2()kkkkkkf xfxxxxfxfx12*()( *)2()kkkkxxfxxfx 令令k ，由，由 f (x*) 0，即可得结论。即可得结论。证明：证明：NewtonNewton法实际上是一种特殊的迭代法法实际上是一种特殊的迭代法( )( )( )f xxxfx迭代函数为：迭代函数为：思考题思考题1 假设假设 ，NewtonNewton法是否仍收敛？法是否仍收敛？( *)0fx设设 x* 是是 f 的的 m 重根，则令：重根，则令： 且且*( )()( )mf xxxq x(

5、 *)0q x2* 2*2( )( )( )( )( ) (1) ( )2 () ( )()( )( )() ( )f x fxxfxq x m mq xm xx q xxxqxmq xxx q x1|( *)|11xm Answer1: 有局部收敛性有局部收敛性Answer2: 线性收敛线性收敛思考题思考题2当当x* 是是 f (x)=0的的m重根重根, 是否平方收敛？是否平方收敛？1*( )( )( )()()mmmfxq xq xxxxx*1*()()(1) ()() ()()()() ()kkkkkkkkkkkffmqqmqqxxxxxxxxxxxxxxxx*11*1|limlimkk

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

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

8、假设假设 (1) f (a) f (b) 0； (2) 在整个在整个a, b上上 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程序设计语言程序设计语言 Matlab Ma

9、tlab数学软件数学软件 (1) (1) 选定初值选定初值x0 ,x0 ,计算计算f (x0) , f (x0) , f f (x0) (x0) 计算步骤计算步骤(2) (2) 按公式按公式 迭代迭代 得新的近似值得新的近似值xk+1 xk+1 1()()kkkkf xxxfx(3) (3) 对于给定的允许精度对于给定的允许精度，假如，假如 则终止迭代，取则终止迭代，取 ; ;否则否则k=k+1k=k+1，再转，再转 步骤步骤(2)(2)计算计算*1kxx1|kkxx允许精度允许精度最大迭代次最大迭代次数数迭代信息迭代信息例例1 1：用：用NewtonNewton法求方程法求方程 的根的根,

10、, 要求要求 20 xxe51| 10kkxx1ln(2)kkxx迭代格式一：迭代格式一：迭代格式二：迭代格式二：121kkxkkkxxexxe取初值取初值 x0 x00.0,0.0,计算如下：计算如下：对迭代格式一对迭代格式一: the iterative number is 27, : the iterative number is 27, the numerical solution is 0.442852706the numerical solution is 0.442852706对迭代格式二对迭代格式二: the iterative number is 3, : the itera

11、tive number is 3, the numerical solution is 0.442854401the numerical solution is 0.442854401解：解：例题例题2求函数求函数 的正实根的正实根精度要求：精度要求： 321019.6810.944f xxxx610从图形中我们可以从图形中我们可以看出：看出：在在x = 7x = 7和和 x = 8 x = 8 之间有一单根；之间有一单根；在在x =1x =1和和x = 2 x = 2 之之间有一重根。间有一重根。用用MatlabMatlab画图，查看根的分布情形画图，查看根的分布情形初值初值x08.0 时时

12、,计算的是单根计算的是单根, The iterative number is 28,The numerical solution is 7.600001481初值初值x01.0 ,计算的是重根计算的是重根, The iterative number is 1356,The numerical solution is 1.198631981取初值取初值x0 x08.0,8.0,用牛顿迭代公式计算如下：用牛顿迭代公式计算如下：取初值取初值x0 x01.0,1.0,用牛顿迭代公式计算如下：用牛顿迭代公式计算如下：小小 结结(1) 当当f (x)充分光滑且充分光滑且 x* 是是f (x) =0的单根时

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

14、的, , 且有且有1( *)1xm 由此易知若迭代函数为：由此易知若迭代函数为：( )( )( )f xxxmfx则则NewtonNewton迭代格式迭代格式 为平方收敛为平方收敛. .1()()kkkkf xxxmfx但但 m m 通常未知通常未知, ,故常用修改方法：故常用修改方法：( )( )( )f xu xfx令令若若x x* *为为f (x)f (x)的的m m重根重根, , 则则x x* *为为u (x) = 0u (x) = 0的单根的单根, ,取取( )( )( )u xxxu x则得则得: :12()()()()()kkkkkkkf xfxxxfxf xfx此格式二阶收敛此

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

16、 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*,且收敛速度是线性的且收敛速度是线性的. 二、二、 双点弦截法双点弦截法 假设假设 用差

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

18、单点弦截是双点弦截的特殊情况.几何解释：几何解释：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) 任取任取 属于该领域属于该领域;则由双点弦截公式所得序列则由双点弦截公式所得序列 收敛于根收敛于根 x

19、*, 且收敛速度且收敛速度 ( )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：用单点弦截和双点弦截求方程：用单点弦截和双点弦截求方程 在在2,3内的特殊情况内的特殊情况.3( )250

20、f 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 xxxyxzyx 对于对于 在在 和和 两点处两

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

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

23、(,)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这里这