第2章 非线性方程的数值解法_shopo

1、1第二章 非线性方程的数值解法医学技术学院医学信息工程教研室赖小波 博士，副教授，硕士研究生导师第第2章章 非线性方程的数值解法非线性方程的数值解法 本章主要内容：本章主要内容：1 1、方程有根区间的确定、方程有根区间的确定2 2、二分法、迭代法、牛顿迭代法、弦截法求方程、二分法、迭代法、牛顿迭代法、弦截法求方程 基本原理与方法基本原理与方法（重点）（重点） 。3 3、迭代的构造及其收敛性判定、迭代的构造及其收敛性判定（重点）（重点）4 4、迭代过程的加速、迭代过程的加速5 5、非线性方程组的迭代解法、非线性方程组的迭代解法 工程实际与科学计算中都遇到大量求解非线工程实际与科学计算中都遇到大量

2、求解非线性方程的问题。设非线性方程性方程的问题。设非线性方程 f(x)=0 (2.1) (2.1)求数求数x* *, ,使使f (x*)00，的求根问题，其中，的求根问题，其中f(x)f(x)为非为非线性函数。线性函数。则称则称x x* *为方程（为方程（2.12.1）的根）的根, , 或称或称为函数为函数f(x)f(x)的零点的零点 常见的非线性方程有，代数方程（二次、常见的非线性方程有，代数方程（二次、三次等）、超越方程（三角方程，指数、对数三次等）、超越方程（三角方程，指数、对数方程等）。方程等）。2.1 2.1 引言引言 RTbVVap)(20)()(2RTbVVapVf本章将介绍求解

3、这种类型方程的近似解的数本章将介绍求解这种类型方程的近似解的数值方法值方法 在工程和科学技术领域中，经常会遇到求解在工程和科学技术领域中，经常会遇到求解 一元非线性方程的问题。一元非线性方程的问题。02736xxx0sin xex 前者是一个前者是一个6次代数方程，后者是一个超越方次代数方程，后者是一个超越方程。这些方程看似简单，但理论上已证明，对于次程。这些方程看似简单，但理论上已证明，对于次数大于等于数大于等于5的代数方程，一般不能用代数方法求的代数方程，一般不能用代数方法求其准确根。而在实际问题中，只要能获得满足一定其准确根。而在实际问题中，只要能获得满足一定精确度的近似根即可。所以研究

4、一元非线性方程近精确度的近似根即可。所以研究一元非线性方程近似根的数值解法，具有重要的现实意义。似根的数值解法，具有重要的现实意义。10 xxxyxy1lgxx1lg010 xxab( )yf x oxy 如果如果f(x)=0f(x)=0在区间在区间a,ba,b上仅有一个根，则称上仅有一个根，则称a,ba,b为方程的单根区间；为方程的单根区间； 如果如果f(x)=0f(x)=0在区间在区间a,ba,b有多个根，则称有多个根，则称a,ba,b为为方程的多根区间；方程的多根区间；求方程求方程2x2x5 55x5x2 21=01=0在实数范围内的根。在实数范围内的根。在实数范围内有三个实根在实数范围

5、内有三个实根3 3个有根区间缩小为个有根区间缩小为(0,1)、( (2,2,1)1)和和( (1,0)1,0)如果如果f(x)f(x)可以分解成可以分解成 , ,其中其中m m为正整为正整数且数且 , ,则称则称x x* *是是f(x)f(x)的的m m重零点重零点, ,或称方程或称方程f(x)=0f(x)=0的的m m重根。当重根。当m=1m=1时称时称x x* *为单根。为单根。)()()(*xgxxxfm0)(*xg0)(,0)()()(*)(*)1(*xfxfxfxfmm 方程的单根区间和多根区间统称为方程的有根区方程的单根区间和多根区间统称为方程的有根区间。为了研究方便，我们主要研究

6、方程在单根区间上间。为了研究方便，我们主要研究方程在单根区间上的求解方法。的求解方法。 若若f(x)f(x)存在存在m m阶导数阶导数, ,则是方程则是方程f(x)f(x)的的m m重根重根( (m1)m1) 当且仅当当且仅当02*)2510()(50202)(22234xxxxfxxxxf显然显然x=-5x=-5为其二重根为其二重根且且g(-5)0g(-5)0记笔记记笔记 当当f(x)f(x)不是不是x x的线性函数时，称对应的函数方程的线性函数时，称对应的函数方程为非线性方程。如果为非线性方程。如果f(x)f(x)是多项式函数，则称为代数是多项式函数，则称为代数方程，否则称为超越方程（三角

7、方程，指数、对数方方程，否则称为超越方程（三角方程，指数、对数方程等）。一般称程等）。一般称n n次多项式构成的方程次多项式构成的方程 )0(00111nnnnnaaxaxaxa为为n n次代数方程次代数方程, ,当当n n1 1时时, ,方程显然是非线性的方程显然是非线性的 一般稍微复杂的一般稍微复杂的3 3次以上的代数方程或超越方程次以上的代数方程或超越方程, ,很难甚至无法求得精确解。本章重点介绍常用的求很难甚至无法求得精确解。本章重点介绍常用的求解非线性方程的近似根的几种数值解法解非线性方程的近似根的几种数值解法 记笔记记笔记2.1.1 2.1.1 确定有根区间的方法确定有根区间的方法

8、v 为了确定根的初值，首先必须圈定根所在的范围，为了确定根的初值，首先必须圈定根所在的范围， 称为称为圈定根或根的隔离圈定根或根的隔离。v 在上述基础上，采取适当的数值方法确定具有一定在上述基础上，采取适当的数值方法确定具有一定 精度要求的初值。精度要求的初值。v 对于代数方程，其根的个数（实或复的）与其次数对于代数方程，其根的个数（实或复的）与其次数 相同。至于超越方程，其根可能是一个、几个或无相同。至于超越方程，其根可能是一个、几个或无 解，并没有什么固定的圈根方法解，并没有什么固定的圈根方法v 求方程根的问题，就几何上讲求方程根的问题，就几何上讲, ,是求曲线是求曲线 y=f (x) y

9、=f (x)与与 x x轴交点的横坐标。轴交点的横坐标。 由高等数学知识知由高等数学知识知, , 设设f (x)f (x)为区间为区间 a,ba,b上的单上的单值连续值连续, , 如果如果f (a)f (a)f (b)0 ,f (b)0 ,则则 a,ba,b中至少有一中至少有一点点使使f()=0, ,即方程的根即方程的根( (零点定理零点定理),),如果如果f(x)f(x)在在 a,ba,b上还是单调地递增或上还是单调地递增或递减递减，则仅有一个实根。，则仅有一个实根。记笔记记笔记n由此可大体确定根所在子区间，方法有：由此可大体确定根所在子区间，方法有：(1) (1) 画图法画图法(2) (2

10、) 逐步搜索法逐步搜索法y=f(x)abyx(1) (1) 画图法画图法 画出画出y=f(x)的略图，从而看出曲线与的略图，从而看出曲线与x x轴交点的轴交点的大致位置。大致位置。 例如例如 xlogx-1= 0 xlogx-1= 0可以改写为可以改写为logx=1/xlogx=1/x 画出对数曲线画出对数曲线y=logx,y=logx,与双曲线与双曲线y= 1/x,y= 1/x,它们交它们交 点的横坐标位于区间点的横坐标位于区间2,32,3内内 也可将也可将f (x) = 0分解为分解为 1 1(x)= (x)= 2 2(x)(x)的形式，的形式， 1 1(x)(x) 2 2 (x)(x)两

11、曲线交点的横坐标所在的子区间即为两曲线交点的横坐标所在的子区间即为含根区间含根区间。(1) (1) 画图法画图法xy1gxy023yxy0 xABa1b1a2b2(2) (2) 逐步搜索法逐步搜索法 对于给定的对于给定的f(x),设有根区间为设有根区间为 A,B,A,B,从从x x0 0=A=A出发出发, ,以步长以步长h=(B-A)/n(nh=(B-A)/n(n是正整数是正整数),),在在 A,BA,B内取定节内取定节点点: :x xi i=x=x0 0ih (i=0,1,2,ih (i=0,1,2,n),n),从左至右检查从左至右检查f(xi)的的符号符号, ,如发现如发现x xi i与端

12、点与端点x x0 0的函数值异号的函数值异号, ,则得到一个缩则得到一个缩小的有根子区间小的有根子区间x xi-1i-1,x,xi i。求初始近似根的逐步搜索算法：求初始近似根的逐步搜索算法： （设（设a,ba,b内有根）内有根）(1) x(1) x0 0a; a; (2) (2) 若若f(xf(x0 0 )f(x )f(x0 0 +h)0 +h)0则结束；否则做下步。则结束；否则做下步。(3) x(3) x0 0 x x0 0 +h +h，转，转(2) (2) （其中（其中h h为预选的步长）为预选的步长）例例2.1 2.1 方程方程f(x)=xf(x)=x3 3-x-1=0 -x-1=0

13、确定其有根区间确定其有根区间x xf(x)f(x)0 0.5 1.0 1.5 20 0.5 1.0 1.5 2 + + + +可以看出，在可以看出，在1.01.0,1.5,1.5内必有一根内必有一根解：用试凑的方法，不难发现解：用试凑的方法，不难发现 f(0)0f(0)0 在区间（在区间（0 0，2 2）内至少有一个实根）内至少有一个实根 设从设从x=0 x=0出发出发, ,取取h=0.5h=0.5为步长向右进行根的为步长向右进行根的 搜索搜索, ,列表如下列表如下v 用逐步搜索法进行实根隔离的关键是选取步长用逐步搜索法进行实根隔离的关键是选取步长h hv 要选择适当要选择适当h h ，使之既

14、能把根隔离开来，工作量，使之既能把根隔离开来，工作量 又不太大。又不太大。 v 为获取指定精度要求的初值为获取指定精度要求的初值, ,可在以上隔离根的可在以上隔离根的 基础上采用对分法继续缩小该含根子区间基础上采用对分法继续缩小该含根子区间 二分法可以看作是搜索法的一种改进。二分法可以看作是搜索法的一种改进。2.2 2.2 二分法二分法 二分法又称二分区间法二分法又称二分区间法, ,是求解方程是求解方程f(x)=0f(x)=0的近的近似根的一种常用的简单方法。似根的一种常用的简单方法。 设函数设函数f(x)f(x)在闭区间在闭区间 a,ba,b上连续上连续, ,且且f(f(a a)f()f(b

15、 b)0,)0,根据连续函数的性质可知根据连续函数的性质可知, , f f( (x x)= 0)= 0在在( (a,b)a,b)内必有实根内必有实根, ,称区间称区间 a,ba,b为有根区间。为明确为有根区间。为明确起见起见, ,假定方程假定方程f(x)=0f(x)=0在区间在区间 a,ba,b内有惟一实根内有惟一实根x x* *。 )(xfy x21bax 1b2112xba 2a3a 1a32xba 2b3b11,a b22,ab33,a b以此类推以此类推 二分法的基本思想是二分法的基本思想是: : 首先确定有根区间首先确定有根区间, ,将将区间二等分区间二等分, , 通过判断通过判断f

16、(x)f(x)的符号的符号, , 逐步将有根逐步将有根区间缩小区间缩小, , 直至有根区间足够地小直至有根区间足够地小, , 便可求出满便可求出满足精度要求的近似根。足精度要求的近似根。有根区间只能是下面三种情况之一有根区间只能是下面三种情况之一: :f(a)f(a)f(x)0,f(x)0,此时我们有此时我们有x x* *a,xa,x；f(x)f(x)f(b)0,f(b)0,此时我们有此时我们有x x* *x,bx,b；f(x)=0,f(x)=0,此时此时x x即为问题的精确解即为问题的精确解. . 可见可见, ,二分法就是逐步收缩有根区间，最后得出二分法就是逐步收缩有根区间，最后得出所求的根

17、。具体过程归纳如下所求的根。具体过程归纳如下 取有根区间取有根区间 a,ba,b之中点之中点, , 将它分为两半将它分为两半, ,分点分点 , ,这样就可缩小有根区间这样就可缩小有根区间20bax 对压缩了的有根区间对压缩了的有根区间 施行同样的手法施行同样的手法, , 即取中点即取中点 , ,将区间将区间 再分为两半再分为两半, ,然然 后再确定有根区间后再确定有根区间 , ,其长度是其长度是 的的 二分之一二分之一 如此反复下去如此反复下去, ,若不出现若不出现 , ,即可得出一即可得出一 系列有根区间序列：系列有根区间序列： 上述每个区间都是前一个区间的一半上述每个区间都是前一个区间的一

18、半, ,因此因此 的长度的长度11,ba2111bax11,ba22,ba11,ba0)(kxfkkbabababa,2211kkba ,)(21)(2111abababkkkkk 当当kk时趋于零时趋于零, ,这些区间最终收敛于一点这些区间最终收敛于一点x x* * 即为即为 所求的根所求的根 。11122kkkkkababab1*22kkkkababxx每次二分后每次二分后, ,取有根区间取有根区间 的中点的中点作为根的近似值，得到一个近似根的序列作为根的近似值，得到一个近似根的序列 该序列以根该序列以根x x* *为极限为极限 只要二分足够多次只要二分足够多次( (即即k k足够大足够大

19、),),便有便有这里这里为给定精度为给定精度, ,由于由于 , ,则则 kkba ,)(21kkkbax,210kxxxxkxx*kkbax,*当给定精度当给定精度0 0后后, ,要想要想 成立成立, ,只要只要取取k k满足满足 即可，亦即当即可，亦即当: : kxx*)(211abk12lglg)lg(abk时时, ,做到第做到第k+1k+1次二分次二分, ,计算得到的计算得到的 就是满就是满足精度要求的近似根足精度要求的近似根 。 在程序中通常用相邻的在程序中通常用相邻的 与与 的差的绝的差的绝对值或对值或 与与 的差的绝对值是否小于的差的绝对值是否小于来来决定二分区间的次数。决定二分区

20、间的次数。 kxkx1kxkakb2.2.1 2.2.1 实现二分法的基本步骤实现二分法的基本步骤 二分法是求方程近似根的方法中行之有效的最二分法是求方程近似根的方法中行之有效的最简单的方法，它的递推过程简单，便于计算机上实简单的方法，它的递推过程简单，便于计算机上实现，实现二分法的基本步骤如下。现，实现二分法的基本步骤如下。(1) (1) 输入有根区间的端点输入有根区间的端点 及预先给定的精及预先给定的精 度度 ；(2) (2) 计算计算 ；(3) (3) 若若 ，则，则 ；否则；否则 ；(4) (4) 若若 ，则输出方程满足精度要求的根，则输出方程满足精度要求的根 ， 计算结束；否则转计算

21、结束；否则转(2)(2)。ba,2/ )(bax0)()(xfafxb xa abx y n 开 始 输 入 a , b, (a+b)/2 x f(a) f(x )0 ? xb x a |b-a|0 输 出 x 结 束 y n 二分法算法实现二分法算法实现例2.2 求 在 的根解：因为 所以根存在32( )410f xxx1,2(1)5f (2)14fn有根区间11.0,2.01.52.37521.0,1.51.25-1.7968731.25,1.51.3750.1621141.25,1.3751.3125-0.8483951.3125,1.3751.34375-0.3509861.34375

22、,1.3751.359375 0.0964171.359375,1.3751.3671875 -0.0323681.359375,1.36718751.363281250.03215nx()nf x例例2.3 2.3 用二分法求方程用二分法求方程在在(1(1，2)2)内的根，取内的根，取02010)(3xxxf410#include #include #include #include #define f(x) (x#define f(x) (x* *x+10)x+10)* *x-20)x-20)#define eps 0.0001 /#define eps 0.0001 /* * 容许误差容

23、许误差 * */ /main()main() float a,b,y,x; float a,b,y,x; int k=0; int k=0; printf(a,b=); printf(a,b=); scanf(%f,%f ,&a,&b); scanf(%f,%f ,&a,&b); if(f(a) if(f(a)* *f(b)=0) /f(b)=0) /* * 判断区间内是否有实根判断区间内是否有实根 * */ / printf(Not root); return; printf(Not root); return; do do x=(a+b)/2; x=(a+b

24、)/2; k+; k+; if(f(a) if(f(a)* *f(x)0) /f(x)0) /* * 如果如果f(a)f(a)* *f(x)0,f(x)eps);/ while(fabs(b-a)eps);/* *判断精度要求判断精度要求* */ / x=(a+b)/2; / x=(a+b)/2; /* * 取小区间中点作为根的近似值取小区间中点作为根的近似值 * */ / printf(n The root is x=%f, k=%dn,x,k); printf(n The root is x=%f, k=%dn,x,k);程序运行结果：程序运行结果： a,b=1,2 The root is

25、 x=1.594574, k=14例例2.32.3 求方程求方程f(x)=xf(x)=x3 3-x-1=0 -x-1=0 在区间在区间1.01.0,1.5,1.5内的一内的一 个实根个实根, , 使误差不超过使误差不超过0.50.51010-2-2。P P1919例例2.42.4 证明方程证明方程 在区间在区间2, 32, 3内有一个根内有一个根 , , 使用二分法求误差不超过使用二分法求误差不超过0.50.51010-3 -3 的根要二的根要二 分多少次？分多少次？0523 xx且且f(x)f(x)在在2, 32, 3上连续上连续, ,故方程故方程f(x)=0f(x)=0在在2,32,3内至

26、少内至少有一个根。又有一个根。又 当时当时时，时， , ,故故f(x)f(x)在在2, 32, 3上是单调递增函数上是单调递增函数, ,从而从而f(x)f(x)在在2, 32, 3上有且仅有一根。上有且仅有一根。23)(2xxf3 , 2x0)( xf 给定误差限给定误差限 0.5 0.51010-3 -3 , ,使用二分法时使用二分法时52)(3xxxf016)3(, 01)2(ff证明证明: :令令 误差限为误差限为 只要取只要取k k满足满足 )(211*abxxkk311021)(21 abk即可，亦即即可，亦即 3102 k97.92110lg3gk所以需二分所以需二分1010次便可

27、达到要求。次便可达到要求。简单简单; 对对f (x) 要求不高要求不高(只要连续即可只要连续即可) .无法求复根及偶重根无法求复根及偶重根收敛慢收敛慢 用二分法求根，最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序，将a, b分为若干小区间，对每一个满足 f (ak)f (bk) 0 的区间调用二分法程序，可找出区间a, b内的多个根，且不必要求 f (a)f (b) 0 。优点优点缺点缺点2.3 2.3 迭代法迭代法 迭代法的基本思想是逐次逼近，即首先给出方迭代法的基本思想是逐次逼近，即首先给出方程的根的一个近似初始值，然后反复使用迭代公式程的根的一个近似初始值，然后反复使用迭代

28、公式校正这个初始值，使之逐步精确化，直到满足预先校正这个初始值，使之逐步精确化，直到满足预先给出的精度要求为止。给出的精度要求为止。2.3.1 2.3.1 迭代法原理迭代法原理 等价变换等价变换 f f(x) = 0 (2.3) (x) = 0 (2.3) f f(x)(x)的根的根 的根的根)(xx)(xx如果迭代序列收敛于如果迭代序列收敛于 , ,则当则当 连续时连续时, ,便是方便是方程程 的根。的根。0 x)(01xx1x)(12xx ,210nxxxx*x对预先给定的精度要求对预先给定的精度要求 ，只要某个，只要某个k 满足满足 即可结束计算并取即可结束计算并取 01kkxxkxx*

29、), 2 , 1 , 0()(1 kxxkk)(x0)(xf然后按式然后按式(2.3)(2.3)构造迭代公式构造迭代公式(2.4)在有根区间在有根区间a,ba,b上取一点上取一点 作为方程作为方程 根的初始近似根，代入式根的初始近似根，代入式(2.4)(2.4)右端，求得右端，求得 再把再把 作为预测值，进一步得到作为预测值，进一步得到 ，如，如此反复进行下去，得到一个近似根的序列此反复进行下去，得到一个近似根的序列0)(xf(2.4) (2.4) 称为求解非线称为求解非线性方程的简单迭代法性方程的简单迭代法例例2.5 2.5 用迭代法求方程用迭代法求方程 在在x=1.5x=1.5附近的一个根

30、附近的一个根解解 将方程改写成如下两种等价形式将方程改写成如下两种等价形式 013 xx1)(1)(3231xxxxxx相应地可得到两个迭代公式相应地可得到两个迭代公式1)(1)(321311kkkkkkxxxxxx如果取初始值如果取初始值 1.51.5，用上述两个迭代公，用上述两个迭代公式分别迭代，计算结果见式分别迭代，计算结果见P P2121 0 x例例2.6 已知方程已知方程 在在 上有一个根上有一个根324100 xx1 2 , 可以选取几种迭代格式呢？可以选取几种迭代格式呢？1)1)32410 xxxx 即即104)(23xxxx2)2)23410 xx 1321102xx 即即21

31、3)10(21)(xx3)3)即即2104xxx 12104xxx 21410)(xxx4)4)即即12104xx 21410)(xx如果由迭代格式如果由迭代格式 产生的序列产生的序列 收敛收敛, ,即即 nx)(1kkxx*limxxnn则称迭代法收敛。则称迭代法收敛。 可见，将求非线性方程可见，将求非线性方程f(x)=0f(x)=0的根的根, ,先化为等价形式先化为等价形式)(xx然后构造迭代公式然后构造迭代公式 )2 , 1 , 0()(1kxxkk如何判定这种方法如何判定这种方法是收敛的呢？是收敛的呢？等价形式的构等价形式的构造多种多样造多种多样2.3.3 2.3.3 迭代法收敛的条件

32、迭代法收敛的条件 对方程对方程f(x)=0f(x)=0可以构造不同的迭代公式可以构造不同的迭代公式, , 但但迭代公式迭代公式并非总是收敛。那么并非总是收敛。那么, ,当迭代函数当迭代函数 满足什么满足什么条件时，相应的迭代公式才收敛呢？即使迭代收条件时，相应的迭代公式才收敛呢？即使迭代收敛时，我们也不可能迭代很多次，而是迭代有限敛时，我们也不可能迭代很多次，而是迭代有限次后就停止，这就需要估计迭代值的误差，以便次后就停止，这就需要估计迭代值的误差，以便适时终止迭代适时终止迭代 ),2, 1 ,0()(1kxxkk)(x定理定理2.12.1 设函数设函数 在在a,b上具有连续的一阶导上具有连续

33、的一阶导 数数, 且满足且满足 （1）对所有的对所有的xa,b 有有 a,b （2）存在存在 0 L 1 ,使所有的使所有的xa,b有有 L则方程则方程 在在a,b上的解上的解 存在且唯一存在且唯一，对任意的对任意的 a ,b ，迭代过程迭代过程均收敛于均收敛于 。并有误差估计式并有误差估计式 )(x)(x)(x)(xx*x0 x)(1kkxx*x1*1kkkxxLLxx01*1xxLLxxkk 10)(xx 开 始 输 入 x0,N 1 kk+ 1 k x1 x0 输 出 近 似 根 x1 |x1- x0|? 输 出 迭 代 失 败 标 志 结 束 n k0c0），），使使)(1kkxx)(

34、xx*xkkxxe*ceepkkk1lim则称序列则称序列 是是 p p 阶收敛的阶收敛的, ,c c称渐近误差常数。特别称渐近误差常数。特别地地, ,p p=1=1时称为线性收敛时称为线性收敛, ,p p=2=2时称为平方收敛。时称为平方收敛。1 1 p p 2 2时称为超线性收敛。时称为超线性收敛。 kx 数数p p的大小反映了迭代法收敛的速度的快的大小反映了迭代法收敛的速度的快慢，慢，p p愈大，则收敛的速度愈快，故迭代法的愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。收敛阶是对迭代法收敛速度的一种度量。ceepkkk1lim定理定理2.32.3 设迭代过程设迭代

35、过程 , 若若 在所求根在所求根 的邻域连续且的邻域连续且 则迭代过程在则迭代过程在 邻域是邻域是p p阶收敛的阶收敛的。)(1kkxx)()(xp*x0)(, 0)()()(*)(*) 1(* xxxxpp*x例例2.2.1010 已知迭代公式已知迭代公式 收敛于收敛于 证明该迭代公式平方收敛。证明该迭代公式平方收敛。21132kkkxxx3*3x根据定理根据定理2.32.3可知，迭代公式平方收敛。可知，迭代公式平方收敛。032336)(0)(33* xx，为了使迭代过程收敛或提高收敛的速度为了使迭代过程收敛或提高收敛的速度, , 可设法可设法 提高初值的精度以减少迭代的次数提高初值的精度以

36、减少迭代的次数 提高收敛的阶数提高收敛的阶数 p p将将 代入代入，3*3x2132)(xxx436)(232)(xxxx ，证证: : 迭代公式相应的迭代函数为迭代公式相应的迭代函数为2.4 2.4 牛顿迭代法牛顿迭代法 用迭代法可逐步精确方程用迭代法可逐步精确方程 根的近似值根的近似值，但必须要找到，但必须要找到 的等价方程的等价方程 , ,如果如果 选得不合适选得不合适, ,不仅影响收敛速度不仅影响收敛速度, ,而且有可能造成迭代而且有可能造成迭代格式发散。我们希望找到一种迭代方法格式发散。我们希望找到一种迭代方法, ,既结构简单既结构简单, ,收敛速度快收敛速度快, ,又不存在发散的问

37、题。这就是牛顿迭代又不存在发散的问题。这就是牛顿迭代法法0)(xf0)(xf)(xx)(x2.4.1 2.4.1 牛顿迭代法的基本思想牛顿迭代法的基本思想(1)(1)原理：将非线性方程原理：将非线性方程 f f(x) = 0(x) = 0 逐步线性化而形成迭代公式逐步线性化而形成迭代公式. . 对于方程对于方程 ,设其近似根为设其近似根为 , 函数函数f(x)f(x)可在可在 附近作泰勒展开附近作泰勒展开 0)(xfkx 2)(21)()()(kkkkkxxxfxxxfxfxf 设设 的根的根 , ,则有则有 , ,即即 0)(xf0)(*xf0)()(*kkkxxxfxf)()(*kkkxf

38、xfxxkx忽略高次项忽略高次项, ,用其线性部分作为函数用其线性部分作为函数f(x)f(x)的近似，的近似， )()()(kkkxxxfxfxf*x将右端取为将右端取为 , ,即即 是比是比 更接近于更接近于 的近似值的近似值 1kx1kxkx*x)()(1kkkkxfxfxx)2,1 ,0(k这就是著名的牛顿迭代公式这就是著名的牛顿迭代公式2.4.2 2.4.2 牛顿迭代法的几何解释牛顿迭代法的几何解释 方程方程f f( (x x)=0)=0的根的根x x* *是曲线是曲线y y= =f f( (x x) )与与x x轴交点的横坐轴交点的横坐标标, ,设设x xk k是根是根x x* *的

39、某个近似值的某个近似值, ,过曲线过曲线y y= =f f( (x x) )的横坐标为的横坐标为x xk k的点的点Pk=(xk,f(xk)引切线交引切线交x x轴于轴于x xk+1 k+1 , ,并将其作为并将其作为x x* *牛顿迭代法如下牛顿迭代法如下图所示图所示x*xyxkPky=f(x)xk+1xk+2Pk+1Pk+2新的近似值新的近似值, ,重复上述过程重复上述过程, ,可见一次次用切线方程可见一次次用切线方程来求解方程来求解方程f(x)=0f(x)=0的根的根, ,所以亦称为牛顿切线法。所以亦称为牛顿切线法。2.4.3 2.4.3 实现牛顿迭代法的基本步骤实现牛顿迭代法的基本步骤

40、 实现牛顿迭代法的基本步骤如下：实现牛顿迭代法的基本步骤如下： (1) (1) 给出初始近似根给出初始近似根 及精度及精度 ； (2) (2) 计算计算 ； (3) (3) 若若 ，转向，转向(4)(4)；否则；否则 ，转向，转向(2)(2)； (4) (4) 输出满足精度的根输出满足精度的根 ，结束。，结束。 0 x)()(0001xfxfxx01xx10 xx 1x例例2.11 2.11 用牛顿迭代法求方程用牛顿迭代法求方程 在在1.01.0附近的实根，设初值附近的实根，设初值 ，精度要求，精度要求 为为 。 当当 时，时， 有有 。0654323xxx00001. 06543)(23xx

41、xxf589)( 2xxxf0 . 10 x#include #include #define eps 0.00001 /* 容许误差容许误差 */float f(float x) /* 定义函数定义函数f(x) */ return(-3*x+4)*x-5)*x+6; float f1(float x) /* 定义函数定义函数f(x)的导数的导数 */ return (-9*x+8)*x-5; main() float x0,x1; int k=0; printf(x1=); scanf(%f,&x1); do x0=x1; /* 准备下一次迭代的初值准备下一次迭代的初值 */ x1=

42、x0-f(x0)/f1(x0); /* 牛顿迭代牛顿迭代 */ k+; /* 统计迭代次数统计迭代次数 */ while(fabs(x1-x0)eps); /*满足精度满足精度,输出近似根输出近似根*/ printf(x=%f,k=%dn,x1,k);程序运行结果：程序运行结果：x=1.265328K=4x1=1 定理定理2.4 2.4 设设 是方程是方程 的单根的单根, , 且且f f( (x x) )在在 的某邻域内有连续的二阶导数的某邻域内有连续的二阶导数, , 则牛则牛顿法在顿法在 附近局部收敛附近局部收敛, , 且至少二阶收敛且至少二阶收敛, , 有有 *x0)(xf*x2.4.2.

43、4.4 4 牛顿迭代法的收敛性牛顿迭代法的收敛性*x)(2)(limlim*2*1*1xfxfxxxxeekkkkkk 牛顿迭代法对初值牛顿迭代法对初值x x0 0的选取要求比较高。的选取要求比较高。 X X0 0 必必须充分靠近须充分靠近x x* *才能保证局部收敛。才能保证局部收敛。定理定理2.5 2.5 如果在有根区间如果在有根区间a,ba,b上上连续且不变号，在连续且不变号，在a,ba,b上取初始近似根上取初始近似根x x0 0满足，满足，则牛顿迭代法产生的迭代序列单调收敛于方程则牛顿迭代法产生的迭代序列单调收敛于方程f(x)=0f(x)=0在该区间上的唯一解。在该区间上的唯一解。证明

44、证明 （ 略略 ）)(, 0)(, 0)()(xfxfbfaf 0)()(00 xfxfyx10 x0X*0 x0X*x2 不满足迭代条件时，可能导致迭代值远离根的不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况情况而找不到根或死循环的情况2.4.2.4.4 4 牛顿迭代法的收敛性牛顿迭代法的收敛性例例2.12.12 2 用用求求 x x= =e e-x-x的根的根, ,=10=10-4-4解：因解：因 f f ( (x xk k)= )= x x e ex x 1 , 1 , f f ( (x xk k)=e)=ex x ( ( x x+1)+1)建立迭代公式建立迭代公式

45、nxnnnxxnnnxexxxeexxxnnn 1)1 (11取取x x0 0=0.5,=0.5,逐次计算得逐次计算得 x x1 1=0.57102, =0.57102, x x2 2=0.56716=0.56716， x x3 3=0.56714=0.567142.5 2.5 弦截法弦截法 研究目的：在牛顿法基础上，构造既有较研究目的：在牛顿法基础上，构造既有较高的收敛速度，又不需计算导数的迭代公式。高的收敛速度，又不需计算导数的迭代公式。思想：用差商思想：用差商11)()(kkkkxxxfxf)(kxf 代替导数代替导数弦截迭代公式弦截迭代公式 , 2 , 1),()()()(111 kx

46、xxfxfxfxxkkkkkkkx0 x1需要需要2 2个初值个初值 x x0 0 和和 x x1 1。x22.5.2.5.1 1 弦截法几何意义弦截法几何意义弦截法也称割线法弦截法也称割线法, ,其几何意义是用过曲线上两其几何意义是用过曲线上两点点 、 的割线来代替曲线的割线来代替曲线, ,用割线用割线与与x x轴交点的横座标作为方程的近似根轴交点的横座标作为方程的近似根)(,(000 xfxP)(,(111xfxP2.5.2 2.5.2 实现弦截法的基本步骤实现弦截法的基本步骤实现弦截法的基本步骤如下实现弦截法的基本步骤如下: :(1) (1) 选择迭代初值选择迭代初值 及精度及精度 ；(

47、2) (2) 计算计算 ；(3) (3) 若若 ，转向，转向(4)(4)；否则；否则 ， ， 转向转向(2)(2)；(4) (4) 输出满足精度的根输出满足精度的根 ，结束。，结束。10,xx)()()()(0101112xxxfxfxfxx12xx10 xx 21xx 2x例例2.13 2.13 用弦截法求方程用弦截法求方程在区间在区间 内的实根，取内的实根，取 。0123 xx5 . 1 ,4 . 1510#include #include #include #include #define eps 0.00001 /#define eps 0.00001 /* * 容许误差容许误差 *

48、*/ /#define N 100 /#define N 100 /* * 最大迭代次数最大迭代次数N N * */ /float f(float x) /float f(float x) /* * 定义函数定义函数f(x) f(x) * */ / float y; float y; y=(x-1) y=(x-1)* *x x* *x-1;x-1; return(y); return(y); main()main() float x0,x1,x2; float x0,x1,x2; int i; int i; printf(input x0,x1=); printf(input x0,x1=);

49、 scanf(%f,%f,&x0,&x1); scanf(%f,%f,&x0,&x1); for(i=1;i=N;i+) for(i=1;i=N;i+) x2=x1-(f(x1) x2=x1-(f(x1)* *(x1-x0)/(f(x1)-f(x0); (x1-x0)/(f(x1)-f(x0); / /* * 弦截法迭代公式弦截法迭代公式 * */ / if(fabs(x2-x1)eps | fabs(f(x2)eps) if(fabs(x2-x1)eps | fabs(f(x2)eps) / /* *满足精度要求输出近似根并退出满足精度要求输出近似根并退出*

50、*/ / printf(nRoot of equation is:%8.6fn,x2); printf(nRoot of equation is:%8.6fn,x2); return; return; x0=x1; / x0=x1; /* * 准备下一次迭代的初值准备下一次迭代的初值 * */ / x1=x2; x1=x2; printf(nAfter %d repeat, no solved.n,N); printf(nAfter %d repeat, no solved.n,N); / /* * 输出无解信息输出无解信息 * */ / 程序运行结果：程序运行结果：input x1,x2=1

51、.4,1.5input x1,x2=1.4,1.5Root of equation is: Root of equation is: 1.4655711.465571 弦截法与牛顿迭代法都是线性化方法，但两弦截法与牛顿迭代法都是线性化方法，但两者有本质的区别：者有本质的区别： 牛顿迭代法与一般迭代法在计算牛顿迭代法与一般迭代法在计算 时只用到前一步时只用到前一步的值的值 ，故称之为单点迭代法；而弦截法在求，故称之为单点迭代法；而弦截法在求 时要时要用到前两步的结果用到前两步的结果 和和 ，使用这种方法必须给出两，使用这种方法必须给出两个初始近似根个初始近似根 ，这种方法称为多点迭代法。，这种方

52、法称为多点迭代法。 另外，弦截法比牛顿迭代法收敛速度较慢，但它的计另外，弦截法比牛顿迭代法收敛速度较慢，但它的计算量比牛顿迭代法小。算量比牛顿迭代法小。 kx1kx1kxkx10,xx1kx 可以证明，弦截法具有超线性收敛，收敛的阶约可以证明，弦截法具有超线性收敛，收敛的阶约为为1.6181.618，它与前面介绍的一般迭代法一样都是线性化，它与前面介绍的一般迭代法一样都是线性化方法，但也有区别。即一般迭代法在计算方法，但也有区别。即一般迭代法在计算 时只用到时只用到前一步的值前一步的值 ，故称之为单点迭代法；而弦截法在求，故称之为单点迭代法；而弦截法在求 时要用到前两步的结果时要用到前两步的结

53、果 和和 ，使用这种方，使用这种方法必须给出两个初始近似根法必须给出两个初始近似根 ，这种方法称为多，这种方法称为多点迭代法。点迭代法。 1kx1kx1kxkx10,xxkx例例2.12 2.12 用弦截法求方程用弦截法求方程 在初始值在初始值 邻近的一个根。要求邻近的一个根。要求xex5 . 00 x0001. 01kkxx解：取解：取 , , , , 令令5 . 00 x6.01xxexxf)()()()()(1111kkxxkkxkkkxxeexxexxxkkk 计算结果如下：计算结果如下： 易见取近似根易见取近似根 则可满足精度要求。则可满足精度要求。56714. 04x利用弦截迭代公

54、式利用弦截迭代公式补充补充 非线性方程组的数值解法非线性方程组的数值解法 二阶非线性方程组：二阶非线性方程组：0),(0),(21yxyxff方法：通过消元化为含有一个未知量的方程求方法：通过消元化为含有一个未知量的方程求 根问题，然后用牛顿法求解根问题，然后用牛顿法求解0) 13() 1(),(05),(2221xyxyxyxfyxf例：求解下列非方程组例：求解下列非方程组NewtonNewton法解方程组例法解方程组例由由 得得y=(3x+1)/(x+1) y=(3x+1)/(x+1) 将代入得将代入得f(x)=xf(x)=x2 2+(3x+1)+(3x+1)2 2/ (x+1)/ (x+

55、1)2 2-5=0 -5=0 化简得化简得f(x)=4xf(x)=4x4 4+ 2x+ 2x3 3 +5x+5x2 2-4x-4=0 -4x-4=0 然后用牛顿迭代法求出然后用牛顿迭代法求出x x的近似值作为的近似值作为x x* *, , 并将并将x x* *代代入或后，再用牛顿迭代法求出入或后，再用牛顿迭代法求出y y的近似值作为的近似值作为y y* * 即可。即可。0) 13() 1(),(05),(2221xyxyxyxfyxf例例2.12 2.12 求求 052),(032),(22yxyxvyxyx 在在( (x x0 0,y,y0 0)=(-1,2)=(-1,2)附近解附近解方法：

56、通过消元化为含有一个未知量的方程求方法：通过消元化为含有一个未知量的方程求根问题，然后用牛顿法求解根问题，然后用牛顿法求解解：由得解：由得x=3-2yx=3-2y并代入整理得：并代入整理得： 2 2（3-23-2y)y)2 2 +y+y2 2 5=05=0 9y 9y2 2 -24y+13=0y+13=0 f(y)= 9y f(y)= 9y2 2 24y+13 f24y+13 f (y)=18y(y)=18y 24 , 1 , 0,24181324921kyyyyykkkkky 0.74x 1.52例例2.12.13 3 求求 0sin2),(0cos2),(xyyxvyxyxkkkkkkyyyyyyyyyfyyyfyyyxvyxsin)cos21cos(212)cos21sin(2sin21)cos21cos(2)(0)cos21sin(2)(0)cos21sin(2),(2,cos2111）代入（）得由（ 非线性方程的解通常叫做方程的根非线性方程的解