第4章非线性方程数值解法

1、 第四章第四章非线性方程数值解法非线性方程数值解法目目 录录v4.1 基本问题v4.2 二分法v4.3 迭代法v4.4 Newton迭代法v4.5 迭代的加速方法v4.6 多点迭代法v4.7 数值实验及程序东北林业大学理学院东北林业大学理学院24.1 4.1 基本问题基本问题v本章研究求解单变量非线性方程的各种数值解法：本章研究求解单变量非线性方程的各种数值解法：二分法；二分法； 单点迭代法；单点迭代法；多点迭代法；迭代法的收敛性。多点迭代法；迭代法的收敛性。东北林业大学理学院东北林业大学理学院3( )0( ) , .f xxRf xC a b本章讨论单变量非线性方程： 的求根问题，其中，v对

2、非线性方程求根大致分三个步骤：对非线性方程求根大致分三个步骤：判断根的存在性及个数；根的隔离；根的精确化。4.2 4.2 二分法二分法东北林业大学理学院东北林业大学理学院4v二分法二分法：是一个把含根区间不断缩短，使含根区间中点成为一个满足误差要求的近似解的方法二分法的计算步骤二分法的计算步骤东北林业大学理学院东北林业大学理学院5注注：二分法要求：二分法要求：函数连续函数连续 且且 两端点函数值异号两端点函数值异号。( )0, f xa b计算非线性方程：在区间上的根。(), (2aba bxxf x0001、取中点=, 点的函数值);0110(,;f xf aa xb bf xf ba a

3、b xa b0101112、若)与)同号，则令 = , = ; 若)与)同号，则令 = , = ; 新的有根区间变为, ,*lim2kkkkka ba ba babx113、如此反复，可得一系列有根区间： 方程的根：。东北林业大学理学院东北林业大学理学院6*1*1220,2(ln()ln )/ln2, kkkkkkbabaxxxxbakba由于: ，对任意给定的要使 只需令： 即： 其中表示取整。优点优点：计算简单，收敛性可保证，函数要求低。：计算简单，收敛性可保证，函数要求低。缺点缺点：收敛速度慢，不能求重根和复根。：收敛速度慢，不能求重根和复根。二分法的精度二分法的精度东北林业大学理学院东

4、北林业大学理学院761( )101,2f xxx 例 .求方程在区间上的一个实根，允许误 差 =0.03。解：解：(ln(2 1)ln0.03)/ln25.k 迭代次数 计算结果计算结果4.3 4.3 迭代法迭代法东北林业大学理学院东北林业大学理学院8v迭代法迭代法：基本思想是通过构造一个递推关系式，即迭代格式，计算出一个根的近似值序列，并希望该序列能收敛。v不动点不动点：将方程 改写成等价的形式( )0f x ( )xx*( *),*( )xxxxx若满足称为的 不动点。v不动点迭代法不动点迭代法：选择一个初始值 ，可得0 x10()xx1() (0,1,2)kkxxk反复迭代可得：称此方法

5、为 不动点迭代法。不动点迭代法的几何意义不动点迭代法的几何意义东北林业大学理学院东北林业大学理学院9111( )( )*(, ()( (), ()( )(, ()kkkkkkkkxxyxyxxpxxxxxyyxpxx求的不动点，就是求和的交点。从点出发，沿平行 轴方向前进到点，从该点沿 轴前进交与点。东北林业大学理学院东北林业大学理学院10302( )10*f xxxxx 例 .求方程在=1.5附近的根。解：解：3311.1 (0,1,2,)kkxxxxk将方程改写成：建立迭代公式：计算结果计算结果不动点不动点存在性存在性东北林业大学理学院东北林业大学理学院11 , ( );(2)1, , (

6、 )( )( ) , xa baxbLx ya bxyL xyxa b(1)对任意有存在正常数对都有：.则在上存在唯一的不动点。定理定理1 1( ) , xC a b设满足下面两个条件：*kxx到的迭代序列收敛到，并有误差估计：定理定理2 20( ) , , xC a bxC a b设满足定理1中的两个条件则对1101*1*1kkkkkxxxxLLxxxxL注注1 1：若：若L L已知，由定理已知，由定理2 2，根据误差可估计迭代次数；，根据误差可估计迭代次数；注注2 2：当：当L L1 1时，上述方法不可靠。时，上述方法不可靠。不动点迭代法不动点迭代法收敛性收敛性东北林业大学理学院东北林业大

7、学理学院120( ), , ,kxxxa bx对于迭代公式若对迭代序列都收敛，这种收敛称为 全局收敛。全局收敛全局收敛：0( )*,( ),*kxxxxxxxxRx设有不动点，若存在R:,对于任意R 迭代产生的序列且收敛到，则称此迭代法 局部收敛。局部收敛局部收敛：*( )( )*( )1,( )xxxxxxx设为的不动点，在某临域连续，且在迭代法局部收敛。定理定理3 3不动点迭代法不动点迭代法收敛速度收敛速度东北林业大学理学院东北林业大学理学院1311()( )*,*,lim0,kkkkkkkxxxxxexxece设迭代收敛到的根若则称该迭代方程为 P阶收敛的。P P阶收敛阶收敛：C称为 渐

8、进误差常数。渐进误差常数渐进误差常数：(1)(1)( )*( )*( *)( *)( *)0,( *)0ppxxxxxPxxxx设在附近有充分多阶连续导数，则迭代公式关于是 阶收敛的充分必要条件是：。定理定理4 41P 时称 线性收敛。线性收敛：线性收敛：1P 时称 超线性收敛。超线性收敛：超线性收敛：2P 时称 平方收敛。平方收敛：平方收敛：2430 *3xx例 .用不同的方法求方程。解：解：2211( )4141( )1,( 3)0.1341,2令 (-3)迭代格式：(-3)所以迭代格式为 线性收敛。kkkxxxxxxxx 121( )21213( )(1),( 3)0,2( 3)03令

9、()3迭代格式：()所以迭代格式为 平方收敛。kkkxxxxxxxx方法方法1 1方法方法2 2东北林业大学理学院东北林业大学理学院14东北林业大学理学院东北林业大学理学院15两种方法计算结果比较两种方法计算结果比较(x(x* *=1.7320508)=1.7320508)注注1 1：迭代方法：迭代方法2 2 比比 方法方法1 1收敛快收敛快注注2 2：迭代方程的：迭代方程的 收敛速度收敛速度 依赖于依赖于 迭代函数迭代函数 的选取。的选取。4.4 Newton4.4 Newton迭代法迭代法东北林业大学理学院东北林业大学理学院16v基本思想：基本思想：是将非线性方程 逐步归结为某种线性方程来

10、求解。v计算公式：计算公式：设函数 具有二阶连续导数，由泰勒公式可得略去余项，得到：( )0f x ( )f x ()( )kkkf xf xfxxxR x ()kkkf xf xfxxx从而得到Newton迭代公式：1()(0,1,2,)()kkkkf xxxkfxNewtonNewton迭代法的几何意义迭代法的几何意义东北林业大学理学院东北林业大学理学院171111( )0( )0*(,()0(,()0kkkkkkf xyf xyxxf xyxxf xyx方程的根，就是求和的交点横坐标。从点做切线，与的交点的横坐标为,再从点做切线与的交点的横坐标为，注注1 1：只有初值充分接近根：只有初值

11、充分接近根x x* *，迭代序列才能很快收敛到，迭代序列才能很快收敛到x x* *。注注2 2：NewtonNewton迭代法迭代法 实际是一种实际是一种 单点迭代法。单点迭代法。NewtonNewton迭代法收敛定理迭代法收敛定理东北林业大学理学院东北林业大学理学院1801( )*( *)0,0,*lim0*kkkf xxfxxxxxxxx设在附近连续可导,则存在当时,Newton迭代序列超线性收敛于，即：定理定理5 5证明：证明：( )( *)( )( *)*( )( *)f xf xxxxxfxfx( )( *)( )( )(*)(*)( )( )f xf xfxfxxxxfxfx( )

12、( *)( )( )*( )xxfxfxxxxfx介于 和之间。故故两边令两边令*( *)0.xxx，可得证毕。( )( )( )f xxxfx注：为迭代函数。东北林业大学理学院东北林业大学理学院19012( )*( *)0,0,*( *)lim2( *)*kkkf xxfxxxxxxfxfxxx设在附近二次连续可导,则存在当时,Newton迭代序列至少二阶收敛于,即:定理定理6 6证明：证明：1()*()kkkkf xxxxxfx(*)()()( *)()kkkkxxfxf xf xfx由由TaylorTaylor展开：展开：得得21()*2()kkkkkkfxxxxxxfx介于 和之间。2

13、()( *)()()( *)( *)2!kkkkkff xf xfxxxxx两边对两边对 k k 取极限得证。取极限得证。注注1 1：当：当f (xf (x* *)=0)=0 时，时，NewtonNewton迭代法是超二阶收敛的。迭代法是超二阶收敛的。注注2 2：定理：定理5 5 和定理和定理6 6 说明说明NewtonNewton迭代法迭代法 收敛与否收敛与否 与初值有关。与初值有关。东北林业大学理学院东北林业大学理学院200015020aaxxa例 .建立求的Newton迭代格式，要求不含除法；并证明：当初值 满足时，此迭代格式收敛。解：解：11( ),(2).kkkf xaxxaxx令得

14、Newton迭代公式：1kkrax 记 表征迭代误差，则221111(2)(1)kkkkkkraxaxaxaxr 20000201,lim0kkkkrrxxrra故 当初值 满足时，所以。1limkkxa即 ， 迭代法收敛。东北林业大学理学院东北林业大学理学院21000( ) , ( ) ( )0;( )0, , ;( ) , ; , () ()0;( )0 , kf xa bf a f bfxxa bfxxa bxa bfxf xxf xa b设在有根区间上二阶导数存在,且满足：(1)(2)(3)不变号,(4)初值且使则Newton迭代序列收敛于在内的唯一根。定理定理7 7几几何何解解释释东

15、北林业大学理学院东北林业大学理学院226cos0,0,1xxx例 .用Newton迭代法求解方程。解：解：00( )cos ,(0) (1)0,0,1( )0,( )cos0,7,0,1,()0,( )00,1f xxx fffxfxxxf xf x令：在上,由定理只有Newton迭代序列一定收敛到在内的唯一根。计算结果计算结果0(01)x .NewtonNewton迭代法的变形迭代法的变形简化简化NewtonNewton迭代法迭代法东北林业大学理学院东北林业大学理学院231()(0,1,)kkkf xxxkCv简化简化NewtonNewton迭代法：迭代法：其中C为常数，一般可取C= ，此方

16、法也称平行弦法。0()fx注：一般的简注：一般的简化化NewtonNewton迭代迭代法为一阶收敛。法为一阶收敛。NewtonNewton迭代法的变形迭代法的变形NewtonNewton下山法下山法东北林业大学理学院东北林业大学理学院241()(0,1,)()kkkkf xxxkfxvNewtonNewton下山法：下山法：其中 称为 下山因子下山因子。(01)v选择下山因子的原则：选择下山因子的原则：要使1()()(0,1,)kkf xf xk下山因子在计算过程中可以变动，一般选择下山因子时从 开始，逐次将减半进行试算，直到能使下降条件成立为止。若当计算到某步时取不到满足要求的值（或值小到无

17、法容忍），这时称“下山失败”，需要另取初值 重新算起。10 x东北林业大学理学院东北林业大学理学院25701.5xxx3例 .用Newton下山法求解方程-1在附近的实根。解：解：计算结果计算结果0(0.6)x 取初值x0=0.6,分别用Newton法和Newton下山法计算重根情形重根情形东北林业大学理学院东北林业大学理学院26(1)()( )()( )2, ()0,( )0()()()0()0mmmf xxxg xmg xxf xmf xfxfxfx设,整数则称 为方程重根。此时，故故两边令两边令()1()12()11()2( )( )( )1( *)( *)(*)()(*)!1( *)(

18、 *)(*)()(*)(1)!( )1(*)*()mmmmmmf xxxfxf xfxxxfxxmxfxfxxxfxxmfxxxxxmf2迭代函数： 和在 和之间东北林业大学理学院东北林业大学理学院27*( )( *)1()lim102,()1*Newton*xxxxxmxxxmmx 则，由故，从而迭代法对 重根是线性收敛的。+1Newton()=(0 1)()( )( )( )( )02kkkkf xxxmkfxf xxxmfxx此时可将迭代公式改为：，即取迭代函数：容易得到：，从而上述迭代格式具有 阶收敛。修正的修正的 NewtonNewton迭代公式迭代公式东北林业大学理学院东北林业大学

19、理学院28( )( )*( )0( )( )()( )() ( )( )( )0( )() ( )mf xxxf xmfxf xxxg xxxg xxxxmg xxxg x定义：，假设为的 重根，即：则：，故 为的单根。212Newton( )( )( )( )( )( )( ) ( )()()(0 1)()() ()kkkkkkkxf x fxxxxxfxf x fxf xfxxxkfxf xfx由迭代法，其迭代函数为从而构造迭代法：，它是二阶收敛的称为 修正的修正的NewtonNewton迭代公式迭代公式。东北林业大学理学院东北林业大学理学院292sin02xx例8.求解方程的正根。解：解

20、：分别采取三种迭代公式111sin212(cos)2sin21cos24sincos2sin2cos4cos2sin5kkkkkkkkkkkkkkkkkkkkkxxxxxxxxxxxxxxxxxxxxx（1）（2）（3）东北林业大学理学院东北林业大学理学院30计算结果计算结果0()2x1x2x3x4x5x14x15x可见，方法（可见，方法（2 2）和方法（）和方法（3 3）比方法（）比方法（1 1）收敛得快）收敛得快4.5 4.5 迭代的加速方法迭代的加速方法东北林业大学理学院东北林业大学理学院31v迭代加速：迭代加速：对于收敛的迭代过程，只要迭代足够多次，就可以使结果达到任意的精度，但有时迭

21、代过程收敛缓慢，从而使计算量变得很大，因此迭代方程的加速是个重要的课题。v迭代加速的主要方法：迭代加速的主要方法：（1 1）Aitken 加速方法加速方法（2 2）Steffensen 迭代法迭代法AitkenAitken加速收敛方法加速收敛方法东北林业大学理学院东北林业大学理学院32 kxv基本思想：基本思想：通过序列 构造一个更快收敛的序列 11( )*(0)*kkkkkxxxxxxxxCC Cxxxx设是一个线性收敛的序列，收敛于方程的根。故：， kx121221212121*22kkkkkkkkkkkkkkkkxxxxxxxxxxx xxxxxxxxxx从而：即： 21210 1 22

22、*kkkkkkkkkxxxxkxxxxxx定义：， ，下面的定理说明序列比更快地收敛到。东北林业大学理学院东北林业大学理学院33 1*lim01*.kkkkkkxxxxCCxxxxx设序列线性收敛于，即，则序列比更快地收敛于定理定理8 8证明：证明：212*limlim*kkkkkkxxxxCCxxxx， 21*21*2*kkkkkkkxxxxxxxxxxxxxx从而：212122*1*1*21*1*lim10*21kkkkkkkkkkkxxxxxxxxxxxxxxxxCxxxxCC 即：从而：。SteffensenSteffensen迭代方法迭代方法东北林业大学理学院东北林业大学理学院34v

23、基本思想：基本思想：将不动点迭代法与Aitken方法结合起来可建立如下SteffensonSteffenson（斯蒂芬森）迭代方法：21()()()0 1 22kkkkkkkkkkkyxzyyxxxkzyx， ( )( )0( *)*kxxxxx可以证明，当迭代函数连续可微，或存在，则上式产生的序列局部收敛于。东北林业大学理学院东北林业大学理学院350cos0,xxx例9.分别利用不动点迭代法和Steffensen迭代法求解方程 =0。解：解：计算结果（计算结果（SteffensenSteffensen迭代法）迭代法）东北林业大学理学院东北林业大学理学院36计算结果（不动点迭代法）计算结果（不

24、动点迭代法）00 x 11x 20.54030230586814x 30.857553215846393x 40.654289790497779x 12 0.735604740436347x13 0.741425086610109x170.739567202212256x18 0.738760319874211x19 0.739303892396906x4.6 4.6 多点迭代法多点迭代法东北林业大学理学院东北林业大学理学院37v基本思想：基本思想：在计算新的迭代值 时，充分利用函数 及 在点 的信息，从而减少计算量，提高迭代收敛速度。v最简单的多点迭代法：最简单的多点迭代法：（1 1）弦截法

25、）弦截法（2 2）抛物线法）抛物线法1kx( )f x( )fx12,kkxxv多点迭代法的迭代格式：多点迭代法的迭代格式：111(,),(0 1)kkkk nxxxxk ，弦截法弦截法东北林业大学理学院东北林业大学理学院38v迭代公式：迭代公式：11111()()()()()()kkkkkkkkkf xf xxxxf xf xf xf xv几何意义：几何意义：抛物线法抛物线法东北林业大学理学院东北林业大学理学院39v抛物线法抛物线法 迭代公式：迭代公式：12122 ()4 () ,kkkkkkkf xxxf xf xxxv弦截法弦截法 和和 抛物线法的收敛速度：抛物线法的收敛速度：1121,

26、()kkkkkkkf xxf xxxxx其中：15( )0( )1.618*2fxfxpx若，连续，则弦截法按阶收敛到。1.840*px而抛物线法可按阶收敛到。4.7 4.7 数值实验及程序数值实验及程序东北林业大学理学院东北林业大学理学院40v二分法实验二分法实验vNewtonNewton下山法实验下山法实验vNewtonNewton迭代法实验：迭代法实验：v弦截法实验弦截法实验二分法实验二分法实验东北林业大学理学院东北林业大学理学院41matlab程序如下：（程序如下：（Dichotomy.m）% % 二分法求解方程二分法求解方程f_name(x)=0f_name(x)=0在区间在区间a,

27、ba,b的解的解% eps% eps为误差限，区间端点为误差限，区间端点a a和和b b由键盘输入，由键盘输入，% % 函数函数f_namef_name在区间在区间a,ba,b连续，且连续，且f_name(a)f_name(a)* *f_name(b)0f_name(b)0% % 逐次将有根区间长度缩半，当区间长度小于逐次将有根区间长度缩半，当区间长度小于epseps时，区间中点为近似解时，区间中点为近似解function x,it= Dichotomy(f_name,eps)if nargin0 % % 两端点函数值同号，重新输入两端点函数值同号，重新输入 fprintf(n两端点函数值同号

28、，请重新输两端点函数值同号，请重新输n); a=input(输入左端点输入左端点a=：); b=input(输入右端点输入右端点b=：); 东北林业大学理学院东北林业大学理学院42fa=feval(f_name,a); fb=feval(f_name,b);End% % 二分法计算方程的根二分法计算方程的根while b-a=eps it=it+1; % % 循环次数循环次数 xm=(b+a)/2; % % 计算中点计算中点 fxm=feval(f_name,xm); % % 中点的函数值中点的函数值 if fxm*fa0 a=xm; fa=fxm; else b=xm; fb=fxm; en

29、dendx=(b+a)/2;fprintf(n二分次数：二分次数：%dn,it);fprintf(方程的近似解：方程的近似解：%fn,x); matlab程序（程序（f3.m） % %求根函数求根函数function y=f3(x)y=x3-x-1;东北林业大学理学院东北林业大学理学院433( )101.0,1.5f xxx 例11.计算方程在区间内的一个实根。解：解：计算过程如下：输入：x,it= Dichotomy(f3)；输出：输入左端点a=：1输入右端点b=：1.5 二分次数：9，方程的近似解：1.324707NewtonNewton法实验法实验东北林业大学理学院东北林业大学理学院44

30、matlab程序如下：（程序如下：（Newton.m）% % 牛顿法求解方程牛顿法求解方程f_name(x)=0f_name(x)=0在区间在区间a,ba,b的解的解% eps% eps为误差限，区间端点为误差限，区间端点a a和和b b由键盘输入，由键盘输入，% % 函数函数f_name(x)f_name(x)在区间在区间a,ba,b连续，连续，fd_name(x)fd_name(x)为函数为函数f_name(x)f_name(x)的导函数的导函数% fd_name(x)% fd_name(x)不为不为0 0；% % 逐次迭代，当相邻两次计算出的点之间距离小于逐次迭代，当相邻两次计算出的点之

31、间距离小于epseps时，迭代结束时，迭代结束function x,it= Newton(f_name,fd_name,eps)if nargin=eps it=it+1; % % 循环次数循环次数 x0=x1; x1=x0-feval(f_name,x0)/feval(fd_name,x0);endx=x1;fprintf(n迭代次数：迭代次数：%dn,it);fprintf(方程的近似解：方程的近似解：%fn,x);matlab程序：（程序：（f4.m）% %求根函数求根函数function y=f4(x)y=x.*exp(x)-1; matlab程序：（程序：（f5.m）function

32、 y=f5(x) % % 函数函数f4f4的导函数的导函数y=(x+1).*exp(x);东北林业大学理学院东北林业大学理学院46( )10 xf xxe 例12.利用Newton法计算方程的实根。解：解：计算过程如下：输入： x,it= Newton(f4,f5)；输出： 输入左端点a=：-1输入右端点b=：1是否重新输入区间端点YES（输入非0），NO（输入0）：0输入起始点:x0=0.5迭代次数：3方程的近似解：0.567143NewtonNewton下山法实验下山法实验东北林业大学理学院东北林业大学理学院47matlab程序如下：（程序如下：（Newton_Down.m）% % 牛顿法

33、下山法求解方程牛顿法下山法求解方程f_name(x)=0f_name(x)=0在区间在区间a,ba,b的解的解% eps% eps为误差限，初始点可以任意选取为误差限，初始点可以任意选取% % 函数函数f_name(x)f_name(x)在区间在区间a,ba,b连续，连续，fd_name(x)fd_name(x)为函数为函数f_name(x)f_name(x)的导函数的导函数% fd_name(x)% fd_name(x)不为不为0 0；% % 逐次迭代，当相邻两次计算出的点之间距离小于逐次迭代，当相邻两次计算出的点之间距离小于epseps时，迭代结束时，迭代结束function x,it=

34、Newton_Down(f_name,fd_name,eps)if nargin=f0; k=k/2; x1=x0-k*feval(f_name,x0)/feval(fd_name,x0); f1=abs(feval(f_name,x1);endfprintf(n迭代次数迭代次数 下山因子下山因子k x1 f(x1)n)fprintf( %5d %8f %8f %14fn,it,k,x1,feval(f_name,x1);while abs(x1-x0)=eps it=it+1; % % 循环次数循环次数 k=1; x0=x1; f0=f1; x1=x0-k*feval(f_name,x0)/feval(fd_name,x0); f1=abs(feval(f_name,x1); while f1=f0; k=k/2; x1=x0-k*feval(f_name,x0)/feval(fd_name,x0); f1=abs(feval(f_name,x1)