第3章_非线性方程求根

1、1求方程f(x)=0的根是最常见的数学问题之一，当f(x) 是一次多项式时，称f(x)=0为线性方程，否则称之为非线性方程.第第3 3章章 非线性方程求根非线性方程求根非线性方程的分两类：. 01 : )., 1 , 0(R, 0, 0 , . 1301110 xxniaaaxaxaxainnnn如其中代数方程. 0 : , . 2xex如超越方程 ( )0 , ( ) , .f xxR f xC a b考虑单变量非线性方程的求根问题，其中2结束结束 当当f(x)=0=0是非线性方程时，是非线性方程时，对于不高于对于不高于4次的代次的代数方程已有求根公式，而高于数方程已有求根公式，而高于4次的

2、代数方程则无次的代数方程则无精确的求根公式，至于超越方程精确的求根公式，至于超越方程 就更无法求出其精就更无法求出其精确的解，确的解，但如果对任意的精度要求，能求出方程的但如果对任意的精度要求，能求出方程的近似根，则可以认为求根的计算问题已经解决，至近似根，则可以认为求根的计算问题已经解决，至少能满足实际要求少能满足实际要求. .因此，如何求得满足一定精度因此，如何求得满足一定精度要求的方程的近似根也就成为迫切需要解决的问题要求的方程的近似根也就成为迫切需要解决的问题，本章介绍几种常见的非线性方程的近似求根方法本章介绍几种常见的非线性方程的近似求根方法.3.1.1 引言本章主要讨论本章主要讨论

3、单变量非线性方程单变量非线性方程f(x)=0 (1.1)的求根问题，这里的求根问题，这里xR, f(x)Ca, b. 在科学与工程在科学与工程计算中有大量方程求根问题，其中一类特殊的问题计算中有大量方程求根问题，其中一类特殊的问题是多项式方程是多项式方程)2 . 1(),0()(01110 aaxaxaxaxfnnnn其中系数其中系数ai(i=0,1,n)为实数为实数.方程方程f(x)=0的的根根x*，又称为函数又称为函数f(x)的的零点零点，它使得，它使得f(x*)=0，若，若f(x)可分解为可分解为f(x)=(x- -x*)mg(x)，其中其中m为正整数，且为正整数，且g(x*)0. 当当

4、m=1时，则称时，则称x*为单为单根，若根，若m1称称x*为为(1.1)的的m重根重根，或，或x*为函数为函数f(x)的的m重零点重零点. 若若x*是是f(x)的的m重零点重零点，且，且g(x)充分光滑，则充分光滑，则当当f(x)为代数多项式为代数多项式(1.2)时，根据代数基本定理时，根据代数基本定理可知，可知，n次代数方程次代数方程f(x)=0在复数域有且只有在复数域有且只有n个根个根(含含复根，复根，m重根为重根为m个根个根). 0)(, 0)()()()()1( xfxfxfxfmmn=1,2时方程的根是大家熟悉的，时方程的根是大家熟悉的，n=3,4时虽有求时虽有求根公式但比较复杂，可

5、在数学手册中查到，但已不适根公式但比较复杂，可在数学手册中查到，但已不适合数值计算，而合数值计算，而n5时就不能用公式表示方程的根时就不能用公式表示方程的根.因因此，通常对此，通常对n3的多项式方程求根与一般连续函数方的多项式方程求根与一般连续函数方程程(1.1)一样都可采用迭代法求根一样都可采用迭代法求根.迭代法要求给出根迭代法要求给出根x*的一个近似，若的一个近似，若f(x)Ca, b且且f(a)f(b)0，根据连续函数性质中的介值定理可知方，根据连续函数性质中的介值定理可知方程程f(x)=0在在(a, b)内至少有一个实根，这时称内至少有一个实根，这时称a, b为方为方程程(1.1)的的

6、有根区间有根区间，通常可通过，通常可通过逐次搜索法逐次搜索法求得方程求得方程(1.1)的有根区间的有根区间. 若若 f(x)在在a,b内连续内连续, 且且 f(a) f(b)0, f(0)=10, f(3)=- -260. 可见可见f(x)仅有两个实根仅有两个实根, 分别位于分别位于(0, 3), (3, +), 又又f(4)=10, 所以第二根的隔根区间可缩小为所以第二根的隔根区间可缩小为(3, 4). 以上分析可用下表表示以上分析可用下表表示x(-,0) 0 (0,3) 3 (3,4) 4 (4,+) f(x) f (x) - 0+ - 0-+ 隔根区间(0,3)(3,4)9 设设f(x)

7、在在 a,b 上连续，若上连续，若f(a) f(b) 00, 0, f(b) 00或或 f(a) 0, 0.0.则根据则根据连续函数连续函数的介值定理的介值定理，在，在( (a,b) )内至少存在一点内至少存在一点 ，使，使f( ) =0.=0.3.2 二分法二分法 二分法是最简单、最直观的方法。二分法是最简单、最直观的方法。适用于求有限适用于求有限区间内的单实根或奇重实根区间内的单实根或奇重实根. 二分法的基本原理：二分法的基本原理： 二分法的具体方法如下：二分法的具体方法如下： 设设f(x)在区间在区间a, b上连续上连续, f(a)f(b)0, 则在则在a, b 内有方程的根内有方程的根

8、. 取取a, b的中点的中点 将区间一分为二将区间一分为二. 若若 f (x0)=0, 则则x0就是方程的根就是方程的根, 否则判别根否则判别根 x*在在 x0 的的左侧左侧还是还是右侧右侧., )(210bax 若若f(a) f(x0)0, 则则x*(a, x0), 令令 a1= a, b1=x0;若若f(x0) f(b)0, 则则x*(x0 , b), 令令 a1=x0, b1=b. . 不论出现哪种情况不论出现哪种情况, (a1, b1)均为均为新的有根区间新的有根区间, 它它的的长度只有原有根区间长度的一半长度只有原有根区间长度的一半, 达到了达到了压缩有根压缩有根区间区间的目的的目的

9、. 对压缩了的有根区间对压缩了的有根区间, 又可实行同样的步骤又可实行同样的步骤, 再压再压缩缩. 如此反复进行如此反复进行, 即可的一系列即可的一系列有根区间套有根区间套 ,11nnbababa 由于每一区间都是前一区间的一半，因此区间由于每一区间都是前一区间的一半，因此区间an , bn的长度为的长度为)(ababnnn 21若每次二分时所取区间中点都不是根，则上述过程将若每次二分时所取区间中点都不是根，则上述过程将无限进行下去无限进行下去. 当当 n 时，区间必将最终收缩为一时，区间必将最终收缩为一点点x* ，显然，显然x*就是所求的就是所求的根根. 若取区间若取区间an , bn的中点

10、的中点)(nnnbax 21作为作为x*的近似值，则有下述的近似值，则有下述误差估计式误差估计式11111 11*()()()22 22nnnnnnxxbabab a 只要只要 n 足够大足够大, (即区间二分次数足够多即区间二分次数足够多)，误差就可，误差就可足够小足够小.),(,*11 nnnbaxx 由于在偶重根附近曲线由于在偶重根附近曲线 y=f(x) 为上凹或下凸为上凹或下凸, 即即 f(a)与与f(b)的符号相同的符号相同, 因此因此不能用二分法求偶重根不能用二分法求偶重根. 例例2 用二分法求例用二分法求例1中方程中方程 f(x)=x3- -x- -1=0的实根的实根,要求误差不

11、超过要求误差不超过0.005. 解解 由例由例1可知可知x*(1, 1.5), 要想满足题意，即：要想满足题意，即：则要则要005. 021)15 . 1(21)(21211 nnnab|x*- -xn|0.005由此解得由此解得 取取n=6, 按二分法计算过程见按二分法计算过程见下表下表, x6 = 1.3242 为所求之近似根为所求之近似根., 6 . 512lg2 nn an bn xn f(xn)说明01234561.01251.31251.31251.320751.3751.34381.32811.32811.251.3751.31251.3

12、4381.32811.32031.3242-+-+-(1) f(a)0(2) 根据精 度要求，取到小数点后四位 即可.二分法的计算步骤二分法的计算步骤:步骤步骤1 准备准备 计算函数计算函数f(x)在区间在区间a, b端点处的值端点处的值f(a), f(b). 若若f(a)f(a+b)/2)0, 则以则以(a+b)/2代替代替b ，否则以，否则以(a+b)/2代替代替a.步骤步骤2 二分二分 计算函数计算函数f(x)在区间中点在区间中点(a+b)/2处的处的值值f(a+b)/2).步骤步骤3 判断判断 若若f(a+b)/2)=0，则，则(a+b)/2即是根，即是根，计算过程结束，否则检验计算过

13、程结束，否则检验. 反复执行步骤反复执行步骤2和步骤和步骤3，直到区间，直到区间a, b长度小于长度小于允许误差允许误差，此时中点，此时中点(a+b)/2即为所求近似根即为所求近似根.16二分法求根的算法二分法求根的算法:%input:区间端点区间端点a,b(f(a)f(b)0);最大二分次数最大二分次数N；精度；精度tol.%output:近似根近似根x，二分次数，二分次数k.1. k=0;fa=f(a) ;%函数函数f需要事先定义需要事先定义2. For k=1:N 2.1 x= (a+b)/2 ; fx=f(x); 2.2 if fx=0|(b-a)/2tol break end 2.3

14、 if fa*fx0 b=x; else a=x; end 3. disp(x); disp(k) 17 可见，二分法的优点是对函数的要求低可见，二分法的优点是对函数的要求低(只要求只要求f(x)连续连续)，方法简便、可靠，程序设计容易，事先估计计算次数容易，方法简便、可靠，程序设计容易，事先估计计算次数容易，收敛速度恒定；收敛速度恒定；缺点是不能求出偶重根，收敛速度较慢缺点是不能求出偶重根，收敛速度较慢. 取适当的步长取适当的步长h =(b-a)/m逐一检验小区间逐一检验小区间 a+kh,a+(k+1)h,(k=0,1,2,m-1) 的两端函数值是否异号，的两端函数值是否异号，若异号，则按以

15、上二分法求出其中的根；若同号则不作求根若异号，则按以上二分法求出其中的根；若同号则不作求根而转入检查下一个区间，只要而转入检查下一个区间，只要h选得较小，则可求出本区间选得较小，则可求出本区间内的所有奇重实根内的所有奇重实根(包括单实根包括单实根).h选得过大，可能漏掉某些根选得过大，可能漏掉某些根； h选得过小，则计算量增大选得过小，则计算量增大. 二分法的思想方法还可用于搜索一个较大区间二分法的思想方法还可用于搜索一个较大区间a,b内实根内实根的分布情况的分布情况(不包括偶重实根不包括偶重实根)，实际的作法是：，实际的作法是：3.3 迭代法及其收敛性3.3.1 不动点迭代法不动点迭代法 将

16、方程将方程f(x)=0改写为等价方程形式改写为等价方程形式 x= (x). (3.1)若要求若要求x*满足满足f(x*)=0，则，则x*= (x*)；反之亦然，称；反之亦然，称x*为为函数函数 (x)的一个的一个不动点不动点. 求求f(x)的零点就等于求的零点就等于求 (x)的的不动点不动点，选择一个初始近似值，选择一个初始近似值x0，将它代入，将它代入(3.1)右端右端，即可求得，即可求得 x1= (x0). .lim xxkk可以如此反复迭代计算可以如此反复迭代计算 xk+1= (xk) (k=0,1,2,). (3.2) (x)称为迭代函数称为迭代函数. 如果对任何如果对任何x0a, b

17、，由，由(3.2)得得到的序列到的序列xk有极限有极限则称迭代方程则称迭代方程(3.2)收敛收敛. 且且x*= (x*)为为 (x)的的不动点不动点，故称故称(3.2)为为不动点迭代法不动点迭代法. 上述迭代法是一种逐次逼近法，其基本思想是将上述迭代法是一种逐次逼近法，其基本思想是将隐式方程隐式方程(3.1)归结为一组显式的计算公式归结为一组显式的计算公式(3.2)，迭代，迭代过程实质上是一个逐步显式化过程过程实质上是一个逐步显式化过程.当当 (x)连续时，连续时，显然显然x*就是方程就是方程x= (x)之之根根(不动点不动点). 于是可以从数列于是可以从数列xk中求得满足精度要求的近似根中求

18、得满足精度要求的近似根. 这种求根方法这种求根方法称为称为不动点迭代法不动点迭代法, 1()(0,1,2,)kkxxk 称为称为迭代格式迭代格式, (x)称为称为迭代函数迭代函数, x0 称为称为迭代初值迭代初值,数列数列xk称为称为迭代序列迭代序列. 如果迭代序列收敛如果迭代序列收敛, 则称迭则称迭代格式代格式收敛收敛,否则称为否则称为发散发散. 1()(0,1,2,)kkxxk .lim xxkk 03224xxx分别按以上三种形式建立迭代公式，并取分别按以上三种形式建立迭代公式，并取x0=1进行进行迭代计算，结果如下：迭代计算，结果如下：14)(2 xxx 32)(243 xxxx 41

19、21)23()(xxxx 解解 对方程进行如下三种变形：对方程进行如下三种变形： 例例3 用迭代法求方程用迭代法求方程x4+2x2- -x- -3=0 在区间在区间1, 1.2内的实根内的实根.准确根准确根 x* = 1.124123029, 可见可见迭代公式不同迭代公式不同, 收敛情收敛情况也不同况也不同. 第二种公式比第一种公式收敛快得多第二种公式比第一种公式收敛快得多, 而而第三种公式第三种公式不收敛不收敛.73496,8.49530710 xx12()41kkkxxx 4213()23kkkkxxxx 12411()(32)kkkkxxxx 26271.124123xx671.1241

20、23xx 另参见书另参见书p44页页- -例例3- 3.3.2 迭代法的几何解释迭代法的几何解释以上可以看到迭代法可能收敛，也可能不收敛以上可以看到迭代法可能收敛，也可能不收敛. .一般说从一般说从f( (x)=0)=0构造出的构造出的x= (x)不止一种，有的收敛，有的不收敛不止一种，有的收敛，有的不收敛，这取决于，这取决于g(x)的性态的性态. .将将x= (x)写为写为它的解它的解( (x* *, ,y * *) )中的中的x * *就是就是x= (x)的根的根. .如图：如图：图图3-3-2 2 图图3-3-3 3 图图3-3-4 4 图图3-53-5(3.3)( )

21、yxyxxyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1图图3-3-2 2图图3-3-3 3 图图3-3-4 4 图图3-53-5 例例3表明原方程化为表明原方程化为(3.1)的形式不同，有的收敛的形式不同，有的收敛，有的发散，在收敛的方法中，收敛的快慢也不相，有的发散，在收敛的方法中，收敛的快慢也不相同。只有收敛的的迭代过程同。只有收敛的的迭代过程(3.2)才有意义，为此我才有意义，为此我们首先要研究们首先要研究 (x)的不定点的存在性及迭代法的

22、不定点的存在性及迭代法(3.2)的的收敛性收敛性. 首先考察首先考察 (x)在在a, b上不动点的存在唯一性上不动点的存在唯一性. 定理定理1 设设 (x)Ca, b满足以下两个条件：满足以下两个条件：1 对任意对任意xa, b有有a (x)b. .( )( ).(3.4)xyL xy2 存在正数存在正数La及及 (b)0, f(b)= (b)- -b0, 由连续函数性质可知存在由连续函数性质可知存在 x*(a, b) 使使 f(x*)=0，即，即x*= (x*)，x*即为即为 (x)的不动点的不动点. 再证不动点的再证不动点的唯一性唯一性. 设设x1*, x2*a, b都是都是 (x)的不动

23、点，则由的不动点，则由(3.4)得得.)()(21212121 xxxxLxxxx 引出矛盾，故引出矛盾，故 (x)的不动点只能是唯一的的不动点只能是唯一的. .证毕证毕. . 对定理对定理1条件条件2可以改为导数，即在使用时如果可以改为导数，即在使用时如果 (x)Ca, b且对任意且对任意xa, b有有( )1.(3.5)xL则由微分中值定理可知对任意则由微分中值定理可知对任意x, ya, b有有).,(, )()()()(bayxLyxyx 故定理中的条件故定理中的条件2是成立的是成立的. 见书见书p45. 在在 (x)的不动点存在唯一的情况下，可得到迭代的不动点存在唯一的情况下，可得到迭

24、代法法(3.2)收敛的一个收敛的一个充分条件充分条件.29定理定理3.23.2 设迭代函数设迭代函数 (x) Ca,b，且满足，且满足 (1) 对任意对任意x a,b，有，有a (x) b(b(映内性映内性) )； (2) (2) (x)在在( (a,b) )可导，并存在常数可导，并存在常数0L10L1，使得，使得对任意对任意x a,b，有，有 | (x)| | L1 ( L1 (压缩性压缩性) )则则 (x)在在a,b内存在唯一不动点。内存在唯一不动点。例例 判别判别 (x)=3=3-x 在在0, 1区间是否存在唯一不动点。区间是否存在唯一不动点。这是充分条件，不是必要条件。这是充分条件，不

25、是必要条件。（满足条件（满足条件1 1，不满足条件，不满足条件2 2，但该问题在，但该问题在00，11有有唯一不动点）唯一不动点）ln(3) = 1.0986122886681 ln(3) = 1.0986122886681 定理定理3.33.3 已知方程已知方程x= (x) ， (x)在在a,b连续，在连续，在(a,b)内可内可导；导；且满足：且满足：(1)(1)对任意的对任意的x a,b,有有 (x) a,b.(2)(2)对任意的对任意的x a,b,有有| | (x)| | L11，则对任意的，则对任意的x0 a,b ，迭代，迭代xk+1= (xk)生成的序列生成的序列 xk 必收敛于必收

26、敛于x= (x)的的根根x*，且，且*10|(3.6)1kkLxxxxL30*1|(3.7)1kkkLxxxxL或或称为全局收敛称为全局收敛。 证明证明 设设x*a, b是是 (x)在在a, b上的唯一不动点上的唯一不动点, ,由条件由条件1，可知，可知xka, b，再由，再由(3.4)得得.)()(011xxLxxLxxxxkkkk 因因0L1，故当，故当k时序列时序列xk收敛到收敛到x*.下面证明估计式下面证明估计式(3.6)，由，由(3.4)有有111)()( kkkkkkxxLxxxx .01212xxLxxLkkk 于是对任意正整数于是对任意正整数p有有.11)1()(0101012

27、11211xxLLxxLLLxxLLLxxxxxxxxkpkkpkpkkkpkpkpkpkkpk 上述令上述令p, 注意到注意到limxk+p=x* (p)即得即得(3.6)式式. 又由于对任意正整数又由于对任意正整数p有有.1111)(111211211kkkkpkkppkkpkpkpkpkkpkxxLxxLLxxLLLxxxxxxxx 上述令上述令p, 及及limxk+p=x* (p)即得即得(3.7)式式. 证毕证毕. 迭代过程是个极限过程迭代过程是个极限过程. 在用迭代法进行时，必在用迭代法进行时，必须按精度要求控制迭代次数须按精度要求控制迭代次数. 误差估计式误差估计式(3.6)原则

28、上原则上确定迭代次数，但它由于含有信息确定迭代次数，但它由于含有信息L而不便于实际应而不便于实际应用用. 而误差估计式而误差估计式(3.7)是实用的，只要是实用的，只要相邻两次计算相邻两次计算结果的偏差结果的偏差足够小即可保证近似值足够小即可保证近似值xk具有足够精度具有足够精度.34注注1 1：(3.6)式可用来估计迭代次数，但结果偏保守，次数偏式可用来估计迭代次数，但结果偏保守，次数偏大，一般用得不多。称为事前误差估计。大，一般用得不多。称为事前误差估计。注注2：(3.7)式可用在程序中置退出迭代的条件，式可用在程序中置退出迭代的条件，即当即当|xk-xk-1| 时，认为时，认为|x*-x

29、k-1|1时称时称超线性收敛超线性收敛，p=2时称时称平方收敛平方收敛. 3.5 迭代法的收敛阶迭代法的收敛阶 定理定理3-6 对于迭代过程对于迭代过程xk+1= (xk)，如果，如果 ( (p) )(x)在在所求根所求根x*的邻近连续，并且的邻近连续，并且(1)( )()()()0,()0. (3.8)ppxxxx则该迭代过程在则该迭代过程在x*的邻近是的邻近是p阶收敛的阶收敛的. 证明证明 由于由于(x*)=0，根据定理，根据定理3立即可以断定迭立即可以断定迭代过程代过程xk+1= (xk)具有局部收敛性具有局部收敛性. 再将再将 (xk)在根在根x*处做泰勒展开处做泰勒展开, 利用条件利

30、用条件(3.8), 则有则有.,)(!)()()()(之间之间与与在在 xxxxpxxkpkpk 注意到注意到 (xk)=xk+1， (x*)= x*，由上式得，由上式得,)(!)()(1pkpkxxpxx 因此对迭代误差，令因此对迭代误差，令k时有时有这表明迭代过程这表明迭代过程xk+1= (xk)确实为确实为p阶收敛阶收敛. 证毕证毕. .!)()(1pxeeppkk 上述定理告诉我们，迭代过程的收敛速度依赖于上述定理告诉我们，迭代过程的收敛速度依赖于迭代函数迭代函数 (x)的选取的选取. 如果如果xa, b但但 (x)0时，则时，则该迭代过程只可能是线性收敛该迭代过程只可能是线性收敛.)

31、0( aa的三阶方法的三阶方法. 假设假设 x0 充分靠近充分靠近 x*, 求求31)(limkkkxaxa 证明证明 首先由泰勒展式可得首先由泰勒展式可得113311limlim()()3!4()kkkkkkaxeaeaax 例子例子 证明迭代公式证明迭代公式 xk+1=xk(xk2+3a)/(3xk2+a)是求是求而而1/4a00，故此故此迭代公式是三阶方法迭代公式是三阶方法.3.4 牛 顿 法3.4.1 牛顿法及其收敛性)()()(000 xxxfxfxf 对于方程对于方程f(x)=0，如果，如果f(x)是线性函数，则它的是线性函数，则它的求根是容易的求根是容易的. 牛顿法实质上是一种线

32、性化方法，其牛顿法实质上是一种线性化方法，其基本思想是将非线性方程基本思想是将非线性方程f(x)=0逐步归结为某种线性逐步归结为某种线性方程来求解方程来求解. 设已知方程设已知方程f(x)=0有近似根有近似根x0，且在，且在 x0附近附近f(x)可可用一阶泰勒多项式近似，表示为用一阶泰勒多项式近似，表示为当当f (x0)0时，方程时，方程f(x)=0可用线性方程可用线性方程(切线切线) 近似代近似代替，即替，即 f(x0)+f (x0)(x- -x0)=0. (3.4.1)解此线性方程得解此线性方程得)()(000 xfxfxx 得迭代公式得迭代公式此式称为此式称为牛顿牛顿(Newton)迭代

33、公式迭代公式.1()(0,1,),(3.4.2)()kkkkf xxxkfx牛顿法有显然的牛顿法有显然的几何意义几何意义，方程，方程f(x)=0的根的根x*可可解释为曲线解释为曲线y=f(x)与与x轴交点的横坐标轴交点的横坐标. 设设xk是根是根x*的的某个近似值，过曲线某个近似值，过曲线y=f(x)上横坐标为上横坐标为xk的点的点Pk引切引切线，并将该切线与线，并将该切线与x轴交点的横坐标轴交点的横坐标xk+1作为作为x*的新的的新的近似值近似值. 注意到切线方程为注意到切线方程为这样求得的值这样求得的值xk+1必满足必满足(3.4.1), 从而就是牛顿公式从而就是牛顿公式(3.4.2)的计

34、算结果的计算结果. 由于这由于这种几何背景，所以牛顿迭种几何背景，所以牛顿迭代法也称代法也称切线法切线法.xyx*xky=f(x)xk+1PkPk+1xk+2).)()(kkkxxxfxfy .0 的根用牛顿法求方程xex例7例710 , 0,1,2, 1 0.5,kxkkkkNewtonxexxkxx迭代公式为:取初值计算结果如表kxk01230.50.571020.567160.567142 , 0115.CNewtonxCC对于给定正数应用迭代法于方程，导出求的迭代公式，并计算的近似值例例8 800.x可以证明，迭代公式皆平方收敛21 1 22kkkkkkxCCxxxxx0115, 10

35、Cx取初值，计算结果如表kxk012341010.75000010.72383710.72380510.723805( ),xf xxe解：( )1xfxe 2( ),( )2f xxC fxx解：牛顿迭代法的收敛性牛顿迭代法的收敛性)()()(xfxfxx 设设x*是是f(x)的一个单根，即的一个单根，即f(x*)=0，f (x*)0, 有有. 0)()()(, 0)()()()(2* xfxfxxfxfxfx 牛顿迭代法的迭代函数为牛顿迭代法的迭代函数为由定理由定理3-6可得式可得式. 0)(2)()(! 21)()(lim)(lim22!2121 xfxfxxxxxxxxxkkkkkk

36、(3.4.3)由此得到，当由此得到，当x*为为单根单根时，牛顿迭代法在根时，牛顿迭代法在根x*的的邻近是邻近是二阶二阶(平方平方)收敛收敛的的.关于关于x*为为重根重根时，牛顿迭代法在根时，牛顿迭代法在根x*的邻近的收的邻近的收敛性在后面讨论敛性在后面讨论.定理定理(局部收敛性局部收敛性) 设设f C2a, b, 若若x*为为f(x)在在a, b上的根，且上的根，且f (x*) 0，则存在，则存在x*的邻域的邻域U, 使得任取初使得任取初值值x0 U，牛顿法产生的序列，牛顿法产生的序列xk收敛到收敛到x*，且满足，且满足即有下面的局部收敛性定理即有下面的局部收敛性定理.)(2)()(lim21

37、 xfxfxxxxkkk牛顿法的牛顿法的优点优点是收敛快，是收敛快，缺点缺点每步迭代要计算每步迭代要计算f(xk)及及f (xk)，计算量较大，且有时，计算量较大，且有时f (xk)计算较困难；计算较困难；导数不存在不能用。导数不存在不能用。初始近似值初始近似值x0只在根只在根x*附近才附近才能保证收敛，如能保证收敛，如x0给的不合适可能不收敛给的不合适可能不收敛. 为克服这为克服这两个缺点，通常可用下述方法两个缺点，通常可用下述方法.1 牛顿下山法牛顿下山法, 牛顿法收敛性依赖初值牛顿法收敛性依赖初值x0的选取的选取, 如果如果x0偏离所求根偏离所求根x*较远较远, 则牛顿法可能发散则牛顿法

38、可能发散.Newtons Method收敛性依赖于收敛性依赖于x0的选取的选取.x*x0 x0 x03.4.2牛顿迭代法的变形牛顿迭代法的变形例如例如，用牛顿法求解方程，用牛顿法求解方程 x3- -x- -1=0. (3.4.4)此方程在此方程在x=1.5附近的一个根附近的一个根x*. 设取迭代初值设取迭代初值x0=1.5，用牛顿迭代法公式，用牛顿迭代法公式 3121.(3.4.5)31kkkkkxxxxx计算得计算得 x1=1.34783, x2=1.32520, x3=1.32472.迭代迭代3次得到的结果次得到的结果x3有有6位有效数字位有效数字.但是，如取但是，如取x0=0.6，用，用

39、(3.4.5)式迭代式迭代1次得次得 计算得计算得 x1=17.9.这个结果反而比这个结果反而比x0=0.6更偏离了所求的根更偏离了所求的根x*=1.32472. 为了防止迭代发散，我们对迭代过程再附加一项为了防止迭代发散，我们对迭代过程再附加一项要求，即具有单调性要求，即具有单调性.1()() .(3.4.6)kkf xf x满足这项要求的算法称为满足这项要求的算法称为下山法下山法.我们将牛顿法与下山法结合起来使用，即在下山我们将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛法保证函数值稳定下降的前提下，用牛顿法加快收敛速度速度. 为此，我们将牛顿法的结果

40、为此，我们将牛顿法的结果)()(1kkkkxfxfxx 与前一项的近似值与前一项的近似值xk适当加权平均作为新的改进值适当加权平均作为新的改进值11(1),(3.4.7)kkkxxx其中其中(00)重根重根时，则时，则f(x)可表为可表为 f(x)=(x- -x*)mg(x).其中其中g(x*)0，此时用牛顿迭代法，此时用牛顿迭代法(3.4.2)求求x*仍然收敛仍然收敛，只是，只是收敛速度将大大减慢收敛速度将大大减慢. 事实上，因为迭代公式事实上，因为迭代公式)()()()()()()(*1kkkkkkkkkkxgxxxmgxgxxxxfxfxx 令令ek=xkx*，则，则)()()(*11k

41、kkkkkkkxgexmgxgeexxe 可见用牛顿法求方程的重根时仅为可见用牛顿法求方程的重根时仅为线性收敛线性收敛. 011)()()(1limlim1 mxgexmgxgeekkkkkkkk从而有从而有两种两种提高求重根的收敛速度提高求重根的收敛速度的的方法方法：1) ) 取如下迭代函数取如下迭代函数. 0)(,)()()( xxfxfmxx 则则1( )(0,1,).(3.4.10)( )kkkkf xxxmkf x得到迭代公式得到迭代公式.m Newtonm称为带参数 的迭代法它具有平方收敛，但重数 一般是未知的.下面介绍一个下面介绍一个求重数求重数m的方法的方法，令，令211 kk

42、kkkxxxx 则则112121111kkkkkkkkkkkeeeeeeeeee 求求m重根具有重根具有2阶收敛阶收敛. 但要知道但要知道x*的的重数重数m.由式由式11lim1kkkeem .111limmmmkk 得得因此得估计因此得估计m的式子为的式子为.11km 对对f(x)=(x- -x*)mg(x), g(x*)0，令函数，令函数.)()()()()()()()(xgxxxmgxgxxxfxfx 则为求则为求(x)=0的单根的单根x*的问题，对它用牛顿法是二阶的问题，对它用牛顿法是二阶(平方平方)收敛的收敛的. 其迭代函数为其迭代函数为2) ) 将求重根问题化为求单根问题将求重根问

43、题化为求单根问题. .)()()()()()()()(2xfxfxfxfxfxxxxx 12()()(0,1,). (3.4.11)()()()kkkkkkkf xf xxxkf xf xfx从而构造出迭代方法为从而构造出迭代方法为()().kkfxfx该迭代格式仍具有平方收敛，但需要计算和4210 440*2.xxx用上述三种方法求的二重根例例 212 4kkkkxxxx：牛顿法；解解212 (3.4.10) 2kkkkxxxx；212(2) (3.4.11) .2kkkkkxxxxx计算结果如下： kxk(1)(2)(3)0123x0 x1x2x31.51.4583333331.43660

44、71431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.4142135623.5.3 迭代收敛的加速方法1 埃特金加速收敛方法 对于收敛的迭代过程，只要迭代足够多次，就可对于收敛的迭代过程，只要迭代足够多次，就可以使结果达到任意的精度，但是有时迭代过程收敛较以使结果达到任意的精度，但是有时迭代过程收敛较慢，从而使计算量变得很大，因此迭代过程的加速是慢，从而使计算量变得很大，因此迭代过程的加速是个重要的课题个重要的课题. 设设x0是根是根x*的某个近似值的某个近似值, 用迭代公式校正一次得用迭代公

45、式校正一次得 x1= (x0)而由微分中值定理，有而由微分中值定理，有.),)()()(0001之间之间与与在在xxxxxxxx 假设假设 (x)改变不大改变不大, 近似地取某个近似值近似地取某个近似值L, 则有则有由于由于 x2- -x*L(x1- -x*).10().(3.5.1)xxL xx 若将校正值若将校正值x1= (x0)再校正一次，又得再校正一次，又得 x2= (x1)将它与将它与(3.5.1)式联立，消去未知的式联立，消去未知的L，有，有 xxxxxxxx1021由此推知由此推知.2)(201220100122120 xxxxxxxxxxxxx . 0lim1 xxxxkkk在计算了在计算了x1及及x2之后，可用上式右端作为之后，可用上式右端作为x*的新近似的新近似,记作记作x 1，一般情形是由，一般情形是由xk计算计算xk+1, xk+2，记，记它表明序列它表明序列xk的收敛速度比的收敛速度比xk的收敛速度快的收敛速度快.2112122()2()(0,1,).(3.5.2)kkkkkkkkkkxxxxxxxxxkx(3.5.1)式称为式称为埃特金埃特金(Aitken) 2加速方法加速方法. 可以证明可以证明也称为也称为埃特金埃特金 ( Aitken ) 外推法外推法. 可以证明可以证明:)(1kkxx 为线性收