第2章 非线性方程求根(张武)

1、第二章第二章 方程求根方程求根f f(x)=0(x)=0张武张武上海大学计算机学院上海大学计算机学院引言引言本章主要讨论单变量非线性方程 的求根问题，这里 一类特殊的问题是多项式方程的求根问题，其中系数为 实数. .,)(,Rbaxfx),0()(01110aaxaxaxaxfnnnn), 1 , 0(niai0)(xf迭代法迭代法迭代法是数值计算中一种典型的重要方法，尤迭代法是数值计算中一种典型的重要方法，尤其是计算机的普遍使用，使迭代法的应用更为其是计算机的普遍使用，使迭代法的应用更为广泛。广泛。所谓迭代法就是用某种收敛于所给问题的精确所谓迭代法就是用某种收敛于所给问题的精确解的极限过程，

2、来逐步逼近的一种计算方法，解的极限过程，来逐步逼近的一种计算方法，从而可以用有限个步骤算出精确解的具有指定从而可以用有限个步骤算出精确解的具有指定精度的近似解。简单说迭代法是一种逐步逼近精度的近似解。简单说迭代法是一种逐步逼近的方法。的方法。, 2 , 1 , 0132588. 1133086. 133086. 1135721. 135721. 115 . 11)(5 . 1013132323121301033kxxxxxxxxxxxxxxxxkk重复步骤，代入，将代入，将代入，将解：改写方程。用六位有效数字计算附近的一个根在例：求方程k kx xk kk kx xk k01.551.3247

3、611.3572161.3247321.3308671.3247231.3258881.3247241.32494迭代法迭代法6称称为为迭迭代代公公式式。称称为为迭迭代代函函数数，次次近近似似，称称为为称称为为初初始始近近似似，是是方方程程的的根根。即即即即则则可可得得若若序序列列有有极极限限，即即，列列出出发发，作作序序再再从从某某一一数数化化为为先先将将方方程程对对于于一一般般形形式式的的方方程程)()(0)()(lim,2, 1 ,0,)()(0)(10100nnnnnnnxgxxgnxxaafagaaxnxgxxxxgxxf迭代法的结束条件迭代法的结束条件71kkxx例例4 4：求方程

4、：求方程 在在0, 0.50, 0.5内的根，精确内的根，精确到到1010-5-5。0133xx迭代法例题迭代法例题83*0331k ( )10 1.5. 1 1 1(0,1,2) k 0 1 2 7 8 x 1.51.357211.330861.324kkf xxxxxxxxxk例：求方程 在附近的根解：（ ） 将方程改写为由此建立迭代公式331k721.32472 2 11.k 0 1 2 x1.52.37512.39 kkxxxx迭代收敛。（ ） 若将方程改写为建立迭代公式 迭代不收敛。迭代过程的收敛性迭代过程的收敛性定理定理: : 设迭代函数设迭代函数 在在 上具有连续的一上具有连续的

5、一阶导数，且阶导数，且 （1 1）当）当 时，有时，有 ； （2 2）存在正数）存在正数 ，使对任意的，使对任意的 ，有有 成立。则成立。则 在在 上存在唯一的上存在唯一的解解 ，并且对任意选取的初值，并且对任意选取的初值 ，迭代过，迭代过程程 所产生的迭代所产生的迭代数列收敛于数列收敛于 。 ,ba9)(xaxb( )axb1L,xa b( )1xL( )xx , a b*x0,xa b1() , 0,1, 2,kkxxk*x10迭代过程的收敛性证明迭代过程的收敛性证明证明：先证证明：先证*x的存在性的存在性。由条件可知，在由条件可知，在, a b上上( ) x存在，所以存在，所以( ) x

6、是连续函数，令是连续函数，令( )( )g xxx则则( )g x在在, a b上也连续，由条件（上也连续，由条件（1）可得，）可得，( )( )0g aaa，( )( )0g bbb由连续函数的性质可知，在由连续函数的性质可知，在, a b上必存在一点上必存在一点*x，使，使*()0g x。即即*()xx。11迭代过程的收敛性证明（续迭代过程的收敛性证明（续1）再证其唯一性设有再证其唯一性设有*12,x x，均满足（，均满足（3.6）即）即*1122(),()xxxx，则由微分中值定理得，则由微分中值定理得*121212()()( )()xxxxxx 即即*12()1( )0 xx 其中其中

7、在在*1x与与*2x之间，所以之间，所以 , a b又由条件（又由条件（2），），( )1xL，则，则1( )0 所以只有所以只有*120 xx，即，即*12xx，*x唯一唯一。12迭代过程的收敛性证明（续迭代过程的收敛性证明（续2）最后来证明最后来证明 kx的收敛性的收敛性。由微分中值定理由微分中值定理*1()()( )()kkkxxxxxx 其中其中在在*x与与kx之间，由条件（之间，由条件（2）*1, (0,1,2,)kkxxL xxk应用不等式（应用不等式（3.11），由归纳法可得），由归纳法可得*10kkkxxL xxL xx因为因为1L ，所以有，所以有*0limlim0kkkkx

8、xL xx即即lim*kkxx，迭代收敛，迭代收敛。 13迭代过程的收敛性迭代过程的收敛性满足如下条件满足如下条件（1）当）当 时时( ) , xa b( ) , xC a b（2） ( ) , xa b在上满足李普希斯条件即对任意即对任意12, , x xa b成立成立1212()xxL xx其中其中01L，我们称，我们称L为李普希斯常数。为李普希斯常数。则方程在则方程在a,b上存在唯一解上存在唯一解并且并且迭代格式收敛。并有误差估计迭代格式收敛。并有误差估计101kkLxxxL定理：设函数定理：设函数 , xa b例题分析例题分析14求方程求方程 在在0，1 内的一个根内的一个根 。 29

9、sin10 xx11sin13nnxxcos11( )66sin1xxx解：将方程写成迭代格式解：将方程写成迭代格式由于由于迭代法收敛，任取初值，比如迭代法收敛，任取初值，比如00.4x 当当k=14时，有时，有140.39184690700265x可以看作方程很好的近似根。可以看作方程很好的近似根。利用程序进行计算，得到一列近似值。利用程序进行计算，得到一列近似值。例例2： 求方程求方程01)(3xxxfkakbkxkf (xk)的符号的符号011.51.25-11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3

10、281+51.31251.32811.3203-61.32031.32811.3242-迭代法是一种逐次逼近法，这种方法使用某个固迭代法是一种逐次逼近法，这种方法使用某个固定公式所谓迭代公式反复校正根的近似值，使之逐定公式所谓迭代公式反复校正根的近似值，使之逐步精确化，直至满足精度要求的结果。步精确化，直至满足精度要求的结果。迭代法的求根过程分成两步，第一步先提供根的迭代法的求根过程分成两步，第一步先提供根的某个猜测值，即所谓迭代初值，然后将迭代初值逐步某个猜测值，即所谓迭代初值，然后将迭代初值逐步加工成满足精度要求的根。加工成满足精度要求的根。迭代法的设计思想是，将隐式方程迭代法的设计思想是

11、，将隐式方程 归结为计算一组显式公式归结为计算一组显式公式 ，也就是说，也就是说，迭代过程实质上是一个逐步显式化的过程。迭代过程实质上是一个逐步显式化的过程。迭代法总结迭代法总结16 xx1kkxx二分法二分法17abx1x2ab11xxkk 2)(xf 或或x* 2xx*根的存在性根的存在性18( ) , ( ) ( )0( )0 , f xa bf a f bf xa b定理：若在，则方程在内至少有一个根。二分法步骤二分法步骤191计算计算 在有解区间在有解区间a, b端点处的值，端点处的值， 。2计算计算 在区间中点处的值在区间中点处的值 。3判断若判断若 ，则，则 即是根，否则检验：即

12、是根，否则检验：反复执行步骤反复执行步骤2、3，便可得到一系列有根区间：，便可得到一系列有根区间：二分法步骤（续）二分法步骤（续）204、当、当11kkab时时)(211kkkbax5、则、则即为根的近似即为根的近似简单简单; 对对f (x) 要求不高要求不高(只要连续即可只要连续即可) .无法求复根及偶重根无法求复根及偶重根 收敛慢收敛慢 优点优点缺点缺点二分法误差估计二分法误差估计21bxyo)(xfy a0 x1x1a1b)(211abxxkk 的近似值的近似值。上式也称为二分法上式也称为二分法的误差估计式的误差估计式。对于事先给定的精度对于事先给定的精度误差估计、对分次数误差估计、对分

13、次数22 对二分法，因为数值分析的结果允许含有一对二分法，因为数值分析的结果允许含有一定的误差定的误差。所以对给定的误差精度所以对给定的误差精度 ，只要选择，只要选择足够大的足够大的k，就可使得，就可使得*122kkkkbabaxx这时即可用这时即可用kx作为作为*x，从式，从式(3.4)易求得二分次数易求得二分次数ln() ln2 1bak二分法程序框图二分法程序框图23定义定义f (x)f (a) f (b)0f (a) f (b)=0f (a) =0打印打印b, k打印打印a, k结束结束是是是是是是否否否否否否m=(a+b)/2|a-b|0打印打印m, ka=mb=m结束结束k=K+1

14、是是是是否否否否输入输入 ,bak = 0例题分析例题分析2401)(3xxxfkakbkxkf (xk)的符号的符号011.51.25-11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-例例1：求下列方程位于：求下列方程位于【1，1.5】内的一个根。内的一个根。例题分析（续例题分析（续1）25例例3 利用二分法求方程利用二分法求方程2sincos0 xx，在，在0,1内的根内的根(0.01)解：令解：令 ( )2sincos

15、f xxx取取000,1ab有有(0)0,(1)0ff利用上述二分法，可以得到如下的计算结果利用上述二分法，可以得到如下的计算结果（表（表3.1）。由表由表3.1可以看出，当可以看出，当7k 时，时，771128ba，所以可以将，所以可以将77,a b的中点作为所求根的中点作为所求根*x的近似值的近似值。例题分析（续例题分析（续2）26kkakbkx()kf x 的符号的符号0010.510.510.7520.7510.87530.750.8750.812540.81250.8750.8437550.843750.8750.8593760.843750.859370.8515670.85156

16、0.859370.85547取取*0.8555x ，即满足精度要求，即满足精度要求。二分法总结二分法总结27二分法是求实根的近似计算中行之有效的最简单方法，二分法是求实根的近似计算中行之有效的最简单方法，易于在计算机上实现，且对于函数易于在计算机上实现，且对于函数的性质要求不高，仅仅要的性质要求不高，仅仅要求它在有根区间上连续，且区间端点的求它在有根区间上连续，且区间端点的函数值异号即可函数值异号即可。它它的缺点是不能求偶数重根，也不能求复根，收敛速度与以的缺点是不能求偶数重根，也不能求复根，收敛速度与以 为公比的等比数列相同，为公比的等比数列相同，不算太快，因此一般在求方程近似不算太快，因此

17、一般在求方程近似根时，不太单独使用，常用它来为其它方法求方程近似根提根时，不太单独使用，常用它来为其它方法求方程近似根提供好的初始值供好的初始值。12牛顿法牛顿法281、牛顿法的思想、牛顿迭代公式；、牛顿法的思想、牛顿迭代公式；2、牛顿法的收敛性；、牛顿法的收敛性；3、牛顿法的收敛速度；、牛顿法的收敛速度；3、弦截法思想。、弦截法思想。一般迭代法一般迭代法29称为迭代公式。称为迭代函数，次近似，称为称为初始近似，是方程的根。即即则可得若序列有极限，即，出发，作序列再从某一数先将方程化为对于一般形式的方程)()(0)()(lim,2, 1 ,0,)()(0)(10100nnnnnnnxgxxgn

18、xxaafagaaxnxgxxxxgxxf由前面的讨论可知，选择合适的迭代函数由前面的讨论可知，选择合适的迭代函数 ，是提高迭代数列是提高迭代数列 的收敛速度的关键。本节介绍一种的收敛速度的关键。本节介绍一种确定迭代函数确定迭代函数 的方法的方法 牛顿法。牛顿法是求解方牛顿法。牛顿法是求解方程程 的一种重要方法，它的最大优点是方程在单的一种重要方法，它的最大优点是方程在单根附近具有较高的收敛速度，它还可以用于求代数方程根附近具有较高的收敛速度，它还可以用于求代数方程的重根、复根；也可以拓广用于求解非线性方程组的问的重根、复根；也可以拓广用于求解非线性方程组的问题。题。一般迭代法（续）一般迭代法

19、（续）30( )x kx( )0f x ( )x牛顿法牛顿法31取取 在在 x x0 0 做一阶做一阶TaylorTaylor展开展开: :将将 看成高阶小量，则有：看成高阶小量，则有：)*)()(*)(0000 xxxfxfxf )()(*000 xfxfxx 只要只要 ，每一步迭代都有，每一步迭代都有 ，而，而 且且*limxxkk ，则，则 的根。的根。1()()kkkkf xxxfx（牛顿公式）（牛顿公式）20000)(! 2)()()()(xxfxxxfxfxf ， 在在 x x0 0 和和 x x 之之间。间。()0kfx从几何的角度来分析一下牛顿公式的直观结构，方程从几何的角度来

20、分析一下牛顿公式的直观结构，方程 的根就是曲线的根就是曲线 与与 轴的交点。设轴的交点。设 为为 的一个近似值，过曲线的一个近似值，过曲线 上横坐标为上横坐标为 的的点点 ，引一条切线，其方程为，引一条切线，其方程为牛顿法几何表示牛顿法几何表示32( )0f x ( )yf x( )yf x*xkxkxx(,()kkp xf x()()()kkkyf xfxxx令其为零，得切线令其为零，得切线 与与 轴的交点为轴的交点为lx()()kkkf xxxfx将此式将此式 与上面求得的牛顿与上面求得的牛顿公式公式 进行比较即可知道：牛顿公进行比较即可知道：牛顿公式实际上就是用曲线式实际上就是用曲线 在

21、在 点点 处的切线与处的切线与 轴的交点作为曲线轴的交点作为曲线 与与 轴交点的近似，如下图所示轴交点的近似，如下图所示牛顿法几何表示（续牛顿法几何表示（续1）33( )yf x( )yf xxx1()()kkkkf xxxfx()()kkkf xxxfx(,()kkp xf x牛顿法几何表示（续牛顿法几何表示（续2）34x*x0 x1x2xyf(x)牛顿法例题牛顿法例题35例例 用牛顿法求解方程用牛顿法求解方程xxe在在00.5x 附近的根附近的根5(10 )解：将方程解：将方程xxe转化为等价方程转化为等价方程10 xxe 令令( )1xf xxe，则牛顿迭代公式为，则牛顿迭代公式为11(

22、1)1kkkxxkkkkkxkkx exexxxexx(0,1,2,)k 00.5x ，迭代结果如下表，迭代结果如下表3.6 ，与例，与例4、例、例6的迭代结果进行比较的迭代结果进行比较可见，牛顿公式的收敛速度是相当快的可见，牛顿公式的收敛速度是相当快的。牛顿法例题（续）牛顿法例题（续）3600.5x ，迭代结果如下表，迭代结果如下表取初值取初值kkx012340.50.57102040.56715550.56714330.5671432*0.567143x 牛顿法的收敛性牛顿法的收敛性37牛顿法收敛性示意图牛顿法收敛性示意图38牛顿法收敛性示意图（续）牛顿法收敛性示意图（续）39Newton

23、法的收敛性依赖于法的收敛性依赖于x0 的选取。的选取。x*x0 x0 x0牛顿法例题牛顿法例题4010 10. ( ) 1,( )(1)( ) ( )( )1 10.5kxxxxxkkkkxefxxefxexfxxexxxfxxxexxxx例：用牛顿法解方程解：牛顿法迭代函数为牛顿公式为可先用二分法或经验确定迭代初值，再按牛顿公式进行迭代。收敛速度定义收敛速度定义411*1()( ) (0121kkkkkpkxxxxxexxkeCCepppp 定义：设迭代过程收敛于方程的根,如果迭代误差当时成立下列渐进关系式为常数）则称该迭代过程是 阶收敛的。为线性收敛，为超线性为平收敛，方收敛。收敛速度定理

24、收敛速度定理421()*(1)*()* (),( )()()()0;() 0 kkpppxxxxxxxxxp定理：对于迭代过程如果在所求根 的邻近连续，并且则该迭代过程在点 邻近是 阶收敛的。收敛速度定理证明收敛速度定理证明43*1*( )*( )( )*11()0 1,()()( ) ()()()!( )()()!kkkppkkpppkkkpkxxxxxxxxxpexxxxxpep 证：由于故具有局部收敛性,将在根 处展开，由条件有牛顿法的收敛速度牛顿法的收敛速度44 12* () ,()0,() ()() () ()()() () ()()(kkkkxxa bxfxxxfxfxxxfxfx

25、fxxfxxfxfx迭 代 过 程 的 收 敛 速 度 依 赖 于 迭 代 函 数的 选取 。 如 果 当时则 该 迭 代 过 程 只可 能 是 线 性 收 敛 。 对 牛 顿 公 式其 迭 代 函 数 为由 于假 定是的 一 个 单 根 ， 即*)0,()0,()0,fxxx则由 上 式 知由 上 述 定 理 知 ， 牛 顿 法 在 根的邻 近 至 少 是 平 方 收 敛 的 。牛顿法应用牛顿法应用4521 01 ().2kkkCxCCCxxx对于给定正数，应用牛顿法解二次方程即导出求开方值的计算程序02211221010202000 11 () ()22. ,2.1 0,1. kkkkkk

26、kkkkkkkkkkkxxCxCxCxCxxxCxCxCxCxCxCxCxCxCqqxCCxCqxqkxC 现证此迭代公式对于初值都是收敛的。由迭代公式得记对任意总有，故当时，牛顿法优缺点牛顿法优缺点46Newton法具有收敛快，稳定性好，精度高等优点，法具有收敛快，稳定性好，精度高等优点，是求解非线性方程的有效方法之一。但它每次迭代均需是求解非线性方程的有效方法之一。但它每次迭代均需计算函数值与导数值，故计算量较大。而且当导数值提计算函数值与导数值，故计算量较大。而且当导数值提供有困难时，供有困难时， Newton法无法进行。法无法进行。（4）计算）计算f (xk+1)，并比较，并比较 与与

27、 的大小，分以下二种情况的大小，分以下二种情况)(1kxf)(kxf 2）若）若 ，则当，则当 且，取且，取x* xk，计算过程结束；，计算过程结束；)()(1kkxfxf否则若否则若 ，而，而 时，则把时，则把xk+1加上一个适当选定的小正数，加上一个适当选定的小正数，11)(kxf即取即取xk+1+ 作为新的作为新的xk值，并转向（值，并转向（3）重复计算；当）重复计算；当 ；且；且 ，则将下山因子缩小一半，取则将下山因子缩小一半，取 /2代入，并转向（代入，并转向（3）重复计算。）重复计算。 11)(kxf（3）计算）计算)( )(1kkkkxfxfxx1）若）若 ，则当，则当 时，取时

28、，取x* xk+1，计算过程结束；，计算过程结束； 当当 时，则把时，则把xk+1作为新的作为新的xk值，并重复回到（值，并重复回到（3）。）。牛顿下山法牛顿下山法47（1）选取初始近似值）选取初始近似值x0；（2）取下山因子）取下山因子 = 1；牛顿下山法计算步骤可归纳如下：牛顿下山法计算步骤可归纳如下：)()(1kkxfxf21kkxx21kkxx例题分析例题分析48例例5 5：求方程：求方程 的根的根k xk010.611/251.14063211.36681311.32628411.32472牛顿下山法的计算结果：牛顿下山法的计算结果：弦截法弦截法11111 (),(),() ,( )0(),(),(),( ),( )0( )0 kkkkkk rkkk rrrkkf xf xfxxxxf xf xf xf xp xp xf xxx基本思想：利用一些函数值来回避导数值的计算。设是的一组近似根，利用函数值构造插值多项式并适当选取的一个根作为的新的近似根，这就确定了一个迭代过程，记迭代函数为 ：1(,). 12kkk rxxxrr当时为弦截法，当时为抛物线