非方程的数值解法

1、教学目的教学目的 1. 掌握解非线性方程（组）的二分法和插值法；掌握解非线性方程（组）的二分法和插值法； 2. 掌握解非线性方程（组）的一般迭代法及有关收敛性掌握解非线性方程（组）的一般迭代法及有关收敛性的证明与牛顿法；的证明与牛顿法； 3. 掌握解非线性方程（组）的牛顿法掌握解非线性方程（组）的牛顿法 4. 了解加速收敛的方法。了解加速收敛的方法。教学重点及难点教学重点及难点 重点重点是解非线性方程（组）的牛顿法；是解非线性方程（组）的牛顿法；难点难点是迭代法的收敛性的证明。是迭代法的收敛性的证明。 第七章第七章 非线性方程非线性方程的数值解法的数值解法 代数方程求根问题是一个古老的数学问题

2、代数方程求根问题是一个古老的数学问题. .早在早在1616世纪就找到了三次，四次方程的求根公式世纪就找到了三次，四次方程的求根公式. .但直到但直到1919世世纪才证明了纪才证明了n5 5次的一般代数方程式不能用代数公式求次的一般代数方程式不能用代数公式求解解. .因此需要研究用数值方法求得满足一定精度的代数因此需要研究用数值方法求得满足一定精度的代数方程式的近似解方程式的近似解. . 而在工程和科学技术中许多问题常归结为求解非而在工程和科学技术中许多问题常归结为求解非线性方程式问题。例如在控制系统的设计领域中，在线性方程式问题。例如在控制系统的设计领域中，在研究人口增长率等问题中都最后可化为

3、方程求根的问研究人口增长率等问题中都最后可化为方程求根的问题。题。非线性方程的数值解法非线性方程的数值解法 求解非线性方程的根，就是求解求解非线性方程的根，就是求解高次方程高次方程或或超越方程超越方程(含有指数和对数等含有指数和对数等)，因为这类方程没有固定的求根公式。，因为这类方程没有固定的求根公式。 用用 f(x)表示方程左端的函数，则一般的非线性方程可表示表示方程左端的函数，则一般的非线性方程可表示为为 f (x) = 0. 本节的任务就是上述方程的本节的任务就是上述方程的根根或或函数的零点函数的零点。7.1 7.1 引言引言如果如果f(x)可以分解成可以分解成 , 其中其中m为正整数为

4、正整数且且 ,则称则称x*是是f(x)的的m重零点重零点,或称方程或称方程f(x)=0的的m重根。重根。当当m=1时称时称x*为单根。若为单根。若f(x)存在存在m阶导数阶导数,则是方程则是方程f(x)的的m重重根根(m1) 当且仅当当且仅当)()()(*xgxxxfm0)(*xg0)(,0)()()(*)(*)1(*xfxfxfxfmm 本章介绍方程的迭代解法，它既可以用来求解代数方程，本章介绍方程的迭代解法，它既可以用来求解代数方程，也可以用来解超越方程，并且仅限于求方程的实根。也可以用来解超越方程，并且仅限于求方程的实根。 运用迭代法求解方程的根应解决以下两个问题：运用迭代法求解方程的根

5、应解决以下两个问题：确定根的初值确定根的初值; ;将进一步精确化到所需要的精度。将进一步精确化到所需要的精度。 由高等数学知识知由高等数学知识知, 设设f (x)为区间为区间a,b上的单值连续上的单值连续, 如果如果f (a)f (b)0 , 则则a,b中至少有一个实根。如果中至少有一个实根。如果f (x)在在a,b上还上还是单调地递增或递减，则仅有一个实根。是单调地递增或递减，则仅有一个实根。n由此可大体确定根所在子区间，方法有：由此可大体确定根所在子区间，方法有： (1) (1) 画图法画图法 (2) (2) 逐步搜索法逐步搜索法y=f(x)abyx(1) (1) 画图法画图法 画出y =

6、 f (x)的略图，从而看出曲线与x轴交点的 大致位置。 也可将f (x) = 0分解为1(x)= 2(x)的形式，1(x) 与 2(x)两曲线交点的横坐标所在的子区间即为含根区间。例如 xlogx-1= 0可以改写为logx=1/x画出对数曲线y=logx,与双曲线y= 1/x,它们交 点的横坐标位于区间2,3内画图法画图法xy1ylogx 023yxn对于某些看不清根的函数，可以扩大一下曲线对于某些看不清根的函数，可以扩大一下曲线y0 xy=f(x)y=kf(x)y0 xABa1b1a2b2(2) 逐步搜索法逐步搜索法(2) 搜索法搜索法 对于给定的对于给定的f (x), 设有根区间为设有

7、根区间为A,B, 从从x0=A出发出发,以步长以步长h=(B-A)/n(n是正整数是正整数), 在在A,B内取定节点内取定节点:xi=x0ih (i=0,1,2,n), 从左至右检查从左至右检查f (xi)的符号的符号, 如发现如发现xi与端点与端点x0的的函数值异号函数值异号,则得到一个缩小的有根子区间则得到一个缩小的有根子区间xi-1,xi。例例1 方程方程f(x)=x3-x-1=0 确定其有根区间确定其有根区间解：用试凑的方法，不难发现解：用试凑的方法，不难发现 f(0)0 在区间在区间（0,2）内至少有一个实根内至少有一个实根 设从设从x=0出发出发,取取h=0.5为为步长向右进行根的

8、搜索步长向右进行根的搜索,列表如下列表如下xf(x)0 0.5 1.0 1.5 2 + +可以看出，在可以看出，在1.0,1.5内必有一根内必有一根 用逐步搜索法进行实根隔离的关键是选取步长用逐步搜索法进行实根隔离的关键是选取步长h要选择适当要选择适当h ，使之既能把根隔离开来，工作量又不太大。，使之既能把根隔离开来，工作量又不太大。 为获取指定精度要求的初值为获取指定精度要求的初值,可在以上隔离根的基础上采用可在以上隔离根的基础上采用对分法继续缩小该含根子区间对分法继续缩小该含根子区间 下面的二分法可以看作是搜索法的一种改进。下面的二分法可以看作是搜索法的一种改进。(3)方程求根的二分法方程

9、求根的二分法(对分法或分半法对分法或分半法) (bisection method)ba2ba *x);(21)1(000bax 找找中中点点：令令；即即中中点点的的函函数数值值计计算算：)()2(00 xff (3) 生成含根区间：生成含根区间：,0)(0*0 xxxf ，则则若若, 0)()(00 afxf若若,0101bbxa 取取, 0)()(010100 xbaaafxf 取取若若,00abhbbaa 令令首首先先满足下式满足下式: :生成含根区间生成含根区间.,11ba,11ba,)1(0011baba 2)2(11hab 0)()()3(11 bfaf .,220011bababa

10、得得继继续续以以上上过过程程取取代代以以例例1 ,102 在在x012 x不能求出所有根不能求出所有根,(,(即有可能漏根即有可能漏根) )。例例如图如图该点可求出该点可求出, ,注注1 :1 :改进的方法，改进的方法，试位法（比例求根法）。试位法（比例求根法）。xab但漏掉了四个点但漏掉了四个点2.2.不能用于求偶重根、复根；不能推广到多元方程组求解；不能用于求偶重根、复根；不能推广到多元方程组求解；缺点缺点: : 的等比级数的收敛速度的等比级数的收敛速度相同。相同。1.1.收敛速度不快收敛速度不快, ,仅与公比为仅与公比为 21即是线性收敛的。即是线性收敛的。3( )1011.5fxxx求

11、 方 程在 区 间 ，内 的 一 个实根，要求准确到小数点后的第实根，要求准确到小数点后的第2位。位。1,1.5,()0,( )0,abfafba b这 里.取的, 0)(,25.100 xfbax二等分，由于将区间中点0010111()()1.25,1.5,61fafxxaxbbab即与同 号 ， 故 在的 右 侧 有 方 程 的 一 个实 根 ， 这 时 ， 令而 新 的有 限 区 间 为。 二 分 过 程 可 如 此 反 复 下 去计 算 结 果 如 表。解解例例k)(kkkkxfxba1.32031.32811.3242-1.31251.32811.3203-1.31251.34381

12、.3281+1.31251.3751.3438+1.251.3751.3125-1.251.51.375+11.51.25-6543210表表6-1 1() / 20.005kba我 们 现 在 预 估 所 要 二 分 的 次 数 。 令可*6ln ()ln16,ln 20 .0 0 5,bakxx得 则 二 分 6 次 就 能 达 到 预 定 的精 度与 实 际 计 算 结 果 相 符 。 上述二分法的优点是算法简单上述二分法的优点是算法简单,而且在有限区间内而且在有限区间内,收敛性总能得到保证收敛性总能得到保证.值得注意的是值得注意的是,为了求出足够精确为了求出足够精确的近似解的近似解,往

13、往需要计算很多次函数值往往需要计算很多次函数值,是一种收敛较慢是一种收敛较慢的方法的方法,通常用通常用二分法二分法给出根的大致范围给出根的大致范围,再利用下面将再利用下面将介绍的更有效的方法求解方程介绍的更有效的方法求解方程.另一方面，二分法只使另一方面，二分法只使用于求一元方程的奇数重实根用于求一元方程的奇数重实根. 7.3 一元方程的不动点迭代法一元方程的不动点迭代法7.3.2 局部收敛性和加速收敛法局部收敛性和加速收敛法7.3.1 不动点迭代法及其收敛性不动点迭代法及其收敛性 迭代法是一种迭代法是一种逐次逼近法逐次逼近法。它是求解代数方程，超。它是求解代数方程，超越方程及方程组的一种基本

14、方法，但越方程及方程组的一种基本方法，但存在收敛性及收敛存在收敛性及收敛快慢的问题快慢的问题。 为用迭代法求解为用迭代法求解f (x)=0的近似根，首先需将此方程的近似根，首先需将此方程化为等价的方程化为等价的方程 x=(x) (7.3.1) 然而将然而将 f (x)=0 化为等价方程化为等价方程（7.3.1）的方法是很多的。的方法是很多的。3( )10f xxx 例例1转换成两种等价形式把0)(xf3132 ( )1, ( )1,xxxxxx或 简单迭代法简单迭代法又称为又称为不动点迭代法不动点迭代法，基本思想是首先构造不基本思想是首先构造不动点方程动点方程 x= (x)，即由方程，即由方程

15、 f(x)=0变换为等价形式变换为等价形式 x= (x), 式式中中(x)称为称为迭代函数。然后建立迭代格式：迭代函数。然后建立迭代格式：xk+1 = (xk)称为不称为不动点迭代格式。动点迭代格式。1limlim()(lim)kkkkkkxxx 知知a= (a)，即，即xk收敛于方程的根收敛于方程的根 a。 a称为函数称为函数 (x)的的不动点不动点 当给定初值当给定初值x0 后后, 由迭代格式由迭代格式xk+1 = (xk)可求得数列可求得数列xk。如果如果xk收敛于收敛于a，且，且(x)在在a连续，连续，则则a就是不动点方程的根。就是不动点方程的根。因为：因为：例例1 1对应的迭代法分别

16、为对应的迭代法分别为3131 1, 1,0,1,.kkkxxxxk或。0( )0( )( )kf xxxxxx显然在由方程转化为等价的方程时，选择不同的迭代函数，就会产生不同的序列即使初值选择一样 且这些序列的收敛情况也不会相同。0*(1)1,(2)5,( )12121.5,721.32471795724475由于既连续函数在区间 ，内变号从而 ，为有根区间。取它的中点为初值，既令迭代结果列于表。此方程有唯一实根。显然第一个迭代法收敛，第二个迭代法发散。fff xxx 表表 7-2012111.51.51.357208812.375000001.3308609612.39648441.3247

17、17961133kkxxk1( )01( )()2kkkkf xg xxg xxx因此对用迭代法求方程近似根需要研究下述问题：（）如何选取迭代函数使迭代过程收敛（ ）若收敛较慢时，怎样加速收敛。迭代法的几何意义：1( )( )*,( )( )*()kkxxyxyxxxxxxx从几何意义看，求方程根的问题，是求曲线与直线交点横坐标当迭代函数的导数函数在根处满足下述几种条件时，从几何上来看迭代过程的收敛情况如下图。数值分析数值分析数值分析数值分析记记y1=x , y2=(x) , 它们交点的横坐标它们交点的横坐标即为方程的根即为方程的根xy 1)(2xy )(,(00 xx )(,(11xx ),

18、(22xx)(,(22xx ),(11xx0 x2x1x pxy00 x1x2x )(2xy xy 1xy0数值分析数值分析数值分析数值分析xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1, a b从以上迭代函数的图像可以初步看出,如果迭代函数在区间是具有压缩性质,则迭代法收敛,否则发散. , , , | ( )( )| |, ( )1. , ( ). .x ya bxyk xykxyxkxa bx 所谓压缩性质是指对任意的其中 为小于1的常数.将上式两边

19、同除以则不难推出如果 则一定具有压缩性质为此有下述关于迭代法收敛性的定理 ( ),(a) ( )a,bba,b( )a,b, (c) ( )( )1, , , 定理7.1设有方程 设于一阶导数存在，（ ）当时，有满足条件：则有：xxxxxxxLxa b *0*1k*1*101 ( ) , ,(2) , ,() (k0,1,.) lim ;1(3) 1(4) ,(1,2,.)1kkkkkkkxxa bxxa bxxxxxxxxLLxxxxkL（ ）在上有唯一解对任意选取初始值迭代过程 收敛,即误差估计(4)(3),(2), : 只证证明,.)2 , 1(,2).2(0kbaxbaxk时，则有），

20、当取由定理条件（由中值定理有：记误差,*kkxxe*1()()( )()kkkxxxxc xx）有：又由条件（之间，即与在其中3,*bacxxckyxy=x0y=(x)aabb*x*1( )kkkxxcxxL xx由此递推可得：0*2*21*.xxLxxLxxLxxkkkk*k01,limLxx由故1(3).()kkxx由迭代公式有：1111()()( )()kkkkkkkkxxxxc xxL xx于是之间与在其中.1kkxxc*111*() -L x(1-L) kkkkkkkkkxxxxxxxxxxxxxxx11*111kkkkkxxLLxxLxx即11(4).:kkkkxxL xx由上面反

21、复利用代入上式中有0121211*1.1L 111xxLLxxLxxLLxxLxxkkkkkkkkLxxxxkkk11,3*1则误差时相邻两次迭代满足条件）可知，当计算得到的由定理结果（.,1.*11仍然可能很大误差很小即使时但要注意来控制算法终止因此在计算机上可利用kkkkkxxxxLxx由事实上数精度要求所需要迭代次可确定使误差达到给定结果利用定理时及给定精度要求及当已知另外,)4(,) 1(,10kLLxx01*1xxLLxxkk:解得(4) ln/ )1ln(ln01LLxxk 若从任何可取的初值出发都能保证收敛，则称它为若从任何可取的初值出发都能保证收敛，则称它为大范大范围收敛围收敛

22、。如若为了保证收敛性必须选取初值充分接近于所要。如若为了保证收敛性必须选取初值充分接近于所要求的根，则称它为求的根，则称它为局部收敛局部收敛。 通常局部收敛方法比大范围收敛方法收敛得快。因此，通常局部收敛方法比大范围收敛方法收敛得快。因此，一个合理的算法是先用一种大范围收敛方法求得接近于根的一个合理的算法是先用一种大范围收敛方法求得接近于根的近似值（如对分法），再以其作为新的初值使用局部收敛法近似值（如对分法），再以其作为新的初值使用局部收敛法（如迭代法）。（如迭代法）。 这里讨论迭代法的收敛性时，均指的是局部收敛性。这里讨论迭代法的收敛性时，均指的是局部收敛性。( )1, , ,.定理7.1

23、条件在一般情况下 可能对大范围的含根区间不满足而在根的邻近是成立的为此有下述迭代过程的局部收敛性结果xLxa b7.3.2 局部收敛性局部收敛性*01*1: (),( ),(, ),0,(, ),()(, ),()kkkkkxxxU xxxxU xxxxU xxxx定义迭代法的局部收敛 设 为的不动点若存在的一个邻域使得对任何初值由迭代法生成的序列满足且收敛到则称迭代法是局部收敛的.定理定理3 3 （迭代法的局部收敛定理）（迭代法的局部收敛定理）设设a是方程是方程x=(x)的根，如果的根，如果(1)迭代函数迭代函数(x)在在a的邻域可导；的邻域可导； (2)(2)在在a的某个邻域的某个邻域S=

24、 =x:|:|x- - a | | , ,对于任对于任 意的意的 x S 有有1| )( | Lx 则对于任意的初值则对于任意的初值 x0 0 S S ，迭代公式，迭代公式xn+1 1= =( (xn) ) 产生的数列产生的数列 xn ，收敛于方程的根，收敛于方程的根a 。1*对于例的两种迭代法，讨论它们的收敛性。解233111( )1, ( )(1)3xxxx(1)对于迭代函数其导数。有容易验证，对任意2 , 1 x。121. 0)(,2 , 1 45. 1 ,26. 1 )(11xx01*1,2,( )12xxx因此，对于任何初值由给出的迭代法都收敛到区间，上的唯一不动点 。3222( )

25、1, ( )3xxxx(2)对于迭代函数其导数。显然，22*01,2( )0 7 ( )1,7.1,对有，不满足定理的条件。从几何上可以说明，只要初值该迭代法发散。xxxxx: ( )ln(2)0f xxx例2 由迭代法解方程*12: (1)(0)(2)0, (-1.9)(-1)0 0,2-1.9,-1,.ffffx x解显然有即知方程于及内有根,记为YxY=x0-2-112*1x*2x0111111(2).0,2 ln(2),( )ln(2),(0)ln(2)0.6930,(2)ln(4)1.3682,( )02( )2,kkxxxxxxxx先考察取初值迭代过程的收敛性 其中迭代函数为显然及

26、为增函数，则当时，0又由111( )(0)1 (0,2).22xxx 则有1( )2xxYxY=x0-2-112*1x*2x01*1*610,2 ln(2)110 )2kkkxxxxxx于是由前一定理可知，当初值时,迭代过程收敛，如果要求 近似根准确到小数第位（即要求71514*71141410 .1/2.1.1461931,()0.8 10 xxLxxf x由计算结果可知且则k00.010.6931471820.99071046 .14 1.146193115 1.1461932*112*1002*2(3) 1.91.1 ln(2),( )()1,2 ln(2)( 1.9, 1,).kkkk

27、xxxxxxxxxxx 再讨论求， 内方程的根由迭代方程显然所以迭代过程初值不能保证收敛于2222 201*0212812 e22( )( )( )( 1)0.3861.( 1.9, 1( ) 1.9, 1, 1.9, 12.1,121.841405660,()0.2 10 .kxxxxkxxexxexxxxxexxxf x 若将方程转化为等价方程或则,且时）,所以当选取时,迭代过程收敛如取则迭代次有且1 ( )0,( )()kkkf xxxxx 由此例1*可见，对于方程迭代函数取不同形式，相应的迭代法产生的收敛情况也不一样，因此，我们应该选择迭代函数使构造的迭代过程收敛，且收敛较快。 有时，

28、对于一些不满足定理有时，对于一些不满足定理7.1的条件问题，可以的条件问题，可以通过转化，化为适合于迭代的形式。这要针对具体情通过转化，化为适合于迭代的形式。这要针对具体情况进行讨论况进行讨论。3例试问如何满足的已知, 13)( )( )(xxxx解，可得由)(xx,3)(3xxxx即可得等价方程。)(3(21xxx因此，令)(3(21)(xxx则有,21)( 321)(xx)(1kkxx因此，迭代式收敛。), 1 , 0(k( )x利用构造一个收敛的简单迭代函数？7.3.3 7.3.3 迭代法的收敛速度迭代法的收敛速度 一种迭代法具有实用价值，首先要求它是收敛的，其次还一种迭代法具有实用价值

29、，首先要求它是收敛的，其次还要求它收敛得比较快。要求它收敛得比较快。定义定义7.27.2 设迭代过程设迭代过程 收敛于收敛于 的根的根 , ,记迭代记迭代误差误差 , ,若存在常数若存在常数p（p1）和和c（c0），使使 )(1kkxx)(xx*xkkxxe*ceepkkk1lim则称序列则称序列 是是 p 阶收敛的阶收敛的, ,c称渐近误差常数。特别地称渐近误差常数。特别地, ,p=1=1时时称为称为线性收敛线性收敛, ,p=2=2时称为时称为平方收敛平方收敛。p 1时称为时称为超线性收敛超线性收敛。 kx 数数p 的大小反映了迭代法收敛的速度的快慢，的大小反映了迭代法收敛的速度的快慢，p愈

30、大，则愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种一种度量度量。 定理定理 设迭代过程设迭代过程 , 若若 在所求根在所求根 的邻域连续且的邻域连续且 则迭代过程在则迭代过程在 邻域是邻域是p阶收敛的。阶收敛的。)(1kkxx)()(xp*x*(1)*()()()0,pxxx*x0)(* x*x1)(* x)(1kkxx)(kx*xpkpkkkxxpxxxxxxxx)(!1)(! 21)()()(*)(2* 根据已知条件得根据已知条件得 pkpkxxpxx)(!1)()(*)(*由迭代公式由迭代公式 )(1kkxx及及)(

31、*xx有有pkpkxxpxx)(!)(*)(*10!)(lim*)(1pxeeppkkk( )*()0px证证: 由于由于 即在即在 邻域邻域 , 所以所以 有局部收敛性有局部收敛性, 将将 在在 处泰勒展开处泰勒展开 ( ) , ( )0 xxa bx上定理表明迭代过程的收敛速度依赖于迭代函数的选取，如果时。则迭代过程只可能是线性收敛的。例例5 已知迭代公已知迭代公式式 收敛于收敛于 证明该迭代公式平方收敛证明该迭代公式平方收敛.证证: 迭代公式相应的迭代函数为迭代公式相应的迭代函数为21132kkkxxx3*3x2132)(xxx436)(232)(xxxx ，将将 代入代入，根据定理可知

32、，迭代公式平方收敛。根据定理可知，迭代公式平方收敛。3*3x032336)(0)(33* xx，为了使迭代过程收敛或提高收敛的速度为了使迭代过程收敛或提高收敛的速度, 可设法可设法 提高提高初值的精度初值的精度以减少迭代的次数以减少迭代的次数 提高收敛的阶数提高收敛的阶数 pSteffensen迭代格式 0limlim112nCeeeennnnnnnnneeee112*211nnnnxxxxxxxx*nxx 对于线性收敛的迭代法，收敛很慢，所以要在这些迭代法的基础上考虑加速收敛的方法。设xk 线性收敛到x*，则迭代误差en 满足当n充分大时有 即nnnnnnxxxxxxx1221*2)(2*1

33、21*2)(2)(xxxxxxxxnnnn2*1212*2*2)(2)(xxxxxxxxxxxnnnnnn*121*2*22xxxxxxxxxnnnnnn21212*)2(nnnnnnxxxxxxx展开有：n已知 ，则 ，n改成nx)(1nnxx)(2nnxx nnnnnnnnnnnxyzxyxxyzxy2)()()(21 n=0，1，2，Steffensen迭代格式n也可以改写成n其中迭代函数,.)1 , 0()(1nxxnnxxxxxxx)(2)()()(2Steffensen迭代法收敛的充要条件n定理7.4.1 ,)(*1xxCx，设函数。件是的不动点的充分必要条是)()(*xxxxx，

34、则为足够小的正数，且1)(* xSteffensen迭代法收敛的充要条件n证明：必要性的不动点，是因为)(*xxx)(2)()()(2xxxxxxx由于，所以0)(lim*xxxx，故有0)(lim*xxxx)(*xx即的不动点。是所以)(*xxxSteffensen迭代法收敛的充要条件n充分性的不动点有是由)(*xxxxxxxxxxxxxx)(2)()(lim)(lim2*1)(2)()( 1)()( 2lim*xxxxxxxxoo型0 1)( 1)()( 2lim2*xxxxxx的不动点。是所以)(*xxxSteffensen算法的收敛速度n定理7.4.2 在定理7.4.2假设下，若 产生

35、的序列 至少平方收敛到 。,.2, 1 ,02)()()(21nxyzxyxxyzxySteffensennnnnnnnnnnn迭代格式则由 2C)(x0nx*x*xSteffensen算法的收敛速度的不动点，是证明：)(*xxx。即)(*xx1)(11)(lim)(lim*xxxxxxxxooxx型又因为Steffensen算法的收敛速度 *)(2)(lim*xxxxxxx及) 1)(2)()(lim*xxxxxoo型1)(2)()(*xxx2* 1)(xSteffensen算法的收敛速度 *)()(lim)(*xxxxxxx于是有*2)(2)()(lim*xxxxxxxxxxx*2*)(2

36、)()(lim1*xxxxxxxxxxx0 1)( 1)(12*2*xxSteffensen算法的收敛速度 由定理7.4.2知 至少以平方速度收敛到 。 也就是说：简单迭代法是线性收敛；Steffensen迭代至少平方以上收敛（加速收敛）。0nx*x例题n例7.9试用Steffensen算法求解方程n解法一、取 ，由013 xx31)(xxnnnnnnnnnnnxyzxyxxyzxy2)()()(21 n = 0，1，2，例题n取初值 ，计算结果如下：5 . 10 xN XnYnZn0 1.51.3572088081.3308609591 1.3248991811.3247523791.324

37、7244962 1.3247179571.3247179571.324717957例题n解法二、取 ，由n对于该迭代函数在一般迭代法中是发散的，而Steffensen格式却是收敛的。1)(3 xxnnnnnnnnnnnxyzxyxxyzxy2)()()(21 n=0，1，2，例题n取初值 ，计算结果如下：N XnYnZn0 1.52.3751.2396484371 1.4162929751.8409219155.2388727692 1.3556504421.4913982792.3172706993 1.3289487771.3470628831.4443512244 1.324804489

38、1.3251735441.3271172815 1.3247179441.3247181521.3247189806 1.3247179575 . 10 xSteffensen迭代格式几何解释 Steffensen迭代算法 11002001200100210:)3(;)4);2/()()3;3|2|)2);();() 1| )(|while)2(;,) 1 (xendwhilexxxyzxyxxthenxyzifyzxyxxx输出步做第做输入Steffensen迭代算法 1.1.理解理解收敛性、收敛阶收敛性、收敛阶的概念及的概念及二分法二分法思想方法思想方法。 2.2.会求会求用用二分法二分法

39、解解非线性方程时的非线性方程时的执行次数执行次数k 。ln() ln1.ln2b ak0 为给定的误差界为给定的误差界. . 3.3.理解简单迭代法的理解简单迭代法的思想方法，几何意义，压缩不动点定理。思想方法，几何意义，压缩不动点定理。 4. 掌握简单迭代法的收敛掌握简单迭代法的收敛( (局部局部) )定理定理（定理证明，会判断简单（定理证明，会判断简单迭代法是否收敛）迭代法是否收敛）。7.4.2 割线法与抛物线法割线法与抛物线法7.4.1 Newton迭代法迭代法 7.4 一元方程的常用迭代法一元方程的常用迭代法 用迭代法可逐步精确方程用迭代法可逐步精确方程 根的近似值根的近似值，但必须但

40、必须要找到要找到 的等价方程的等价方程 , ,如果如果 选得不合适选得不合适, ,不仅影响收敛速度不仅影响收敛速度, ,而且有可能造成迭代格式发散。能否找到而且有可能造成迭代格式发散。能否找到一种迭代方法一种迭代方法, ,既结构简单既结构简单, ,收敛速度快收敛速度快, ,又不存在发散的问题又不存在发散的问题。这就是本节要介绍的牛顿迭代法。这就是本节要介绍的牛顿迭代法. .1 1 牛顿迭代法的基本思想牛顿迭代法的基本思想 牛顿迭代法一种重要和常用的迭代法牛顿迭代法一种重要和常用的迭代法, , 它的基本思想是将它的基本思想是将非线性函数非线性函数f(x)逐步线性化逐步线性化, , 从而将非线性方

41、程从而将非线性方程f( (x)=0)=0近似地近似地转化为线性方程求解。转化为线性方程求解。0)(xf0)(xf)(xx)(x7.4.1 Newton迭代法迭代法 对于方程对于方程 , ,设其近似根为设其近似根为 , , 函数函数f (x)可可在在 附近作泰勒展开附近作泰勒展开 0)(xfkxkx 2)(21)()()(kkkkkxxxfxxxfxfxf忽略高次项忽略高次项, ,用其线性部分作为函数用其线性部分作为函数 f (x)的近似，的近似， )()()(kkkxxxfxfxf 设设 的根的根 , ,则有则有 , ,即即 0)(xf*x0)(*xf0)()(*kkkxxxfxf)()(*k

42、kkxfxfxx将右端取为将右端取为 , ,即即 是比是比 更接近于更接近于 的近似值的近似值 )()(1kkkkxfxfxx)2,1 ,0(k1kx1kxkx*x这就是著名的牛顿迭代公式这就是著名的牛顿迭代公式（7.4.2）（7.4.1）3 3 牛顿迭代法的几何解释牛顿迭代法的几何解释yx0b )(xfy a0 x1x2x任取初始值任取初始值 ， bax,0 )(xfy 上过点上过点 的切线方程的切线方程为：为：)(,(00 xfx)()(000 xxxfxfy 与与 轴交于点轴交于点1xx)()(0001xfxfxx 过点过点 的切线方程为的切线方程为)(,(11xfx)()(111xxx

43、fxfy 与与 轴交于点轴交于点x2x)()(1112xfxfxx 如此下去得牛顿迭代公如此下去得牛顿迭代公式式:)()(1kkkkxfxfxx 用切线代替曲线，用用切线代替曲线，用线性函数的零点作为线性函数的零点作为 f(x)的零点的近似值。的零点的近似值。牛顿迭代法也牛顿迭代法也称切线法称切线法因此牛顿法产生的序列xk如下图所示。 x0 x2x1过过P0的切线的切线过过P1的切线的切线将将(7.4.2)写成一般的不动点迭代写成一般的不动点迭代(7.3.3)的形式的形式,有有,)()()(xfxfxx 2)()()()(xfxfxfx 所以有所以有 ， Newton迭代法是超线迭代法是超线性

44、收敛的。更准确地，从性收敛的。更准确地，从(7.4.1)和和(7.4.2)可得下面的定理可得下面的定理.)0)( , 0)(* xfx （收敛的充分条件收敛的充分条件）设）设 f C2a, b，若，若(1) f (a) f (b) 0； 则则Newtons Method产生的序列产生的序列 xk 收敛到收敛到f (x) 在在 a, b 的唯一根。的唯一根。产生的序列单调有产生的序列单调有界，保证收敛。界，保证收敛。定理定理13 3 牛顿迭代法的收敛性牛顿迭代法的收敛性证明： 根的存在性 根的唯一性内至少有一个根。在知）及由条件（),(0)(,)(1baxfbaCxf。记此根为内有唯一根在上严格

45、单调函数，因此是故保号，知及由*,),(0)(,)()(,bCa,)(, 0)(xbaxfbaxfxfxfxf)()(0)()(0)(, 0)(, 0)(,0)()(0)(, 0)(, 0)(, 0)(010000001000*000 xxxfxfxxfxfxxxfxfxfbxxxfxfxfxfbfaf 即有，所以知，由，不妨设收敛性继续上述推理有代替。再以因此有两式相减展式由另一方面0101*20*01*20*0*00*0)()()(21)(21)()()(0 Taylor,xxxxxxxxffxxxxfxxxfxfxf 。，由根的唯一性知可得时当由。故必有极限，记。是单调减有下界的序列故序

46、列*10011*0)(,.2 , 1)()(lim.xaafnnxfxfxxaxxxxxxxnnnnnnnnnyx0ba x00)( xf0)( xfyx0bax00)( xf0)( xfyx0bax00)( xf0)( xfyx0Ba x00)( xf0)( xf例例1 用迭代法求用迭代法求 在隔根区间在隔根区间1.4,1.51.4,1.50123 xx内的根，要求准确到小数点后第内的根，要求准确到小数点后第4 4位。位。（1 1）牛顿迭代公式为牛顿迭代公式为nnnnnnnnnnnnnxxxxxxxxxxfxfxx2312231)()(2232231 （2 2）2 . 0)4 . 1( f2

47、 . 0)5 . 1( f 5 . 1 , 4 . 1 x当当 时有，时有，023)(2 xxxf06)( xxf因因 , ,故取故取 , ,牛顿迭代法收敛。牛顿迭代法收敛。0)5 . 1()5 . 1( ff5 . 10 x 推论 在定理1条件下， Newton迭代法具有平方收敛速度。*2*12*1()()()1()lim02()n 1证明类似定理 证明，一般有12其中，介于 与 之间，则故结论成立。nnnnnnnnfxxxxfxxxefxefx 12*( *)lim( *)2( *)kkkxxfxxxfx （局部收敛性局部收敛性）设）设 f C2a, b，若，若 x* 为为 f (x) 在

48、在a, b上的根，且上的根，且 f (x*) 0，则存在，则存在 x* 的邻域的邻域 使得任取初使得任取初值值 ，若，若Newtons Method产生的序列产生的序列 xk 收敛到收敛到x*，则至少二阶收敛，且，则至少二阶收敛，且*)(xB *)(0 xBx 定理定理2function y=newton(fname,dfname,x0,e,N)y=x0;x0=y+2*e;k=0;while abs(x0-y)e&k0,都有都有 ,并且并且 非增非增.因此因此 是有下界的非增序列是有下界的非增序列 ，从而有极限，从而有极限x*。对。对（7.4.3）的两边取极限）的两边取极限,得到得到

49、-a=0,因为因为 0，故有，故有x*= 。） ,2,1(kaxk0 xkxkxa 2*xkx211,0 , 1 ,22kkkkkkxaaxxxkxx由此可知由此可知证证 对对f(x)= -a, f(x)=2x, Newton迭代法为迭代法为2x例例2 设设a0,对方程对方程 -a=0. 试证试证:取任何初值取任何初值 0，Newton迭代法都收敛到算术根迭代法都收敛到算术根 。a0 x2x（7.4.3）练习练习1 用Newton法求 的近似解。解：由零点定理。0cos)(xxxf内有根。在)2, 0(0cosxx迭代公式得及由Newtonxxfsin1)(,.1 , 0sin1cos1nxx

50、xxxnnnnn085133739. 0739085133. 0739085133. 0739085178. 0;73936133. 044*43210 xxxxxxx故取得取练习练习n练习2 用Newton法计算 。解：220)(2aaxxf其中迭代公式得及由Newtonxxf2)(,.1 , 0)2(212221nxxxxxxnnnnnn。有十位有效数的近似值是已的精确值相比，。与，则取332102414213562. 1414215686. 11.416666675 . 1xxxxx设设x*是是f(x)=0的的m重根重根,，即，即2 m.0)(),()()(* xgxgxxxfm在前个定

51、理中在前个定理中,要要求求f(x*)=0 , 即即 是是方程的单根时方程的单根时, Newton法至少具有二阶局部收敛性。法至少具有二阶局部收敛性。下下面讨论重根的情形面讨论重根的情形.,0)(* xf*x由由Newton迭代函数迭代函数 的导数表达式的导数表达式,)(x.11)(*mx 从而，从而， 。因此只要。因此只要 ，这时的，这时的Newton迭代法线性收敛。迭代法线性收敛。*0()1x0)( kxf容易求出容易求出( )( ),( )f xxxfx*为了改善重根时为了改善重根时Newton法的收敛性，有如下两种方法法的收敛性，有如下两种方法。(1) 若改为取若改为取)()()(xfx

52、mfxx 容易验证容易验证 。 迭代至少二阶收敛迭代至少二阶收敛.0)(*x(2)若令若令 ,由由x*是是f(x)的的m重零点，有重零点，有)()()(xfxfx .)()()()()()()()(2xfxfxfxfxfxxxxx 这种方法也是至少二阶收敛的这种方法也是至少二阶收敛的.所以，所以，x*是是 的单零点的单零点.可将可将Newton法的迭代函数修改为法的迭代函数修改为)(x)()()()()()(*xgxxxmgxgxxx *1( )0(),()(0).():kkkkf xma mZf xxxmkfx 若若方方程程有有重重根根试试证证明明牛牛顿顿迭迭代代法法是是线线性性收收敛敛的的

53、 而而改改用用修修改改的的格格式式才才是是局局部部平平方方收收敛敛的的例例1( )(1)( )( )0( )()( ),( )0.( )()( )()( )() ( )( )( ):)mmmf xxxfxf xmf xxah xh afxm xah xxah xxa h xxxmh xxah x 对对牛牛顿顿格格式式, , 迭迭代代函函数数 ( (因因有有重重根根, ,故故有有且且代代入入迭迭代代函函数数式式( (证证明明( )1( )()( )( )()()( )()( )h xxmh xxa h xdh xxadx mh xxa h x ( (111,( )10.,( )()( ()( )

54、( )()()|1( )10lim|.kkkkkkkkxaamaxaxxaaxao xaaxCaaxm 代代入入有有于于是是 由由得得到到故故这这种种牛牛顿顿迭迭代代法法只只有有线线性性收收敛敛速速度度 212( )(2)( )() ( )( )()( )( )1( )()( )( )()()( )()( ),)01)21)2kkkkkkf xxxmfxxa h xxxmmh xxa h xmh xxmh xxa h xdh xm xadx mh xxa h xaaxaxaxaax 对对修修改改的的牛牛顿顿格格式式, , 迭迭代代函函数数 ( ( ( (此此时时( (再再由由( ( ( (12

55、|11|)|)|0|22.kkkaxCaax 得得到到( ( (因因此此修修改改后后的的牛牛顿顿格格式式是是平平方方收收敛敛的的例例7.9 方程方程 的根的根 是二重根是二重根.用三用三种方法求解种方法求解.04424 xx2* x解解 (1)用用Newton法有法有.4221kkkkxxxx (2)由由(7.4.4),m=2迭代公式为迭代公式为.2221kkkkxxxx*(3) 由由(7.4.5)确定的修改方法，迭代公式化简为确定的修改方法，迭代公式化简为.2)2(221kkkkkxxxxx 三种方法均取三种方法均取 =1.5,计算结果列于表计算结果列于表6-7.方法（方法（2）和方）和方法

56、法(3)都是二阶方法，都是二阶方法， 都达到了误差限为都达到了误差限为 的精确度的精确度,而普通而普通的的Newton法是一阶的法是一阶的,要近要近30次迭代才有相同精度的结果次迭代才有相同精度的结果.0 x0 x910 Xk X0 X1 X2 X3方法(1) 1.5 1.458333333 1.436607143 1.425497619方法(2) 1.5 1.416666667 1.414215686 1.414213562方法(3) 1.5 1.411764706 1.414211438 1.414213562表表7-7*Newton法的每步计算都要求提供函数的导数值，当函数法的每步计算都

57、要求提供函数的导数值，当函数f(x) 比较复杂时，提供它的导数值往往是有困难的。此时，比较复杂时，提供它的导数值往往是有困难的。此时，在在Newton迭代法（迭代法（7.4.2）中，可用）中，可用 或常数或常数D取代取代 迭代式变为迭代式变为)(0 xf),(kxf)()(01xfxfxxkkk.)(1Dxfxxkkk或或这称为这称为简化简化Newton法法。其迭代函数为。其迭代函数为。或Dxfxxxfxfxx)()()( )()(0简化简化Newton法一般为线性收敛。法一般为线性收敛。*()0 x通常* 牛顿下山法牛顿下山法* * * 通常通常,牛顿迭代法的收敛性依赖于初始值牛顿迭代法的收

58、敛性依赖于初始值 的选取的选取,如果如果 偏离偏离所求的根所求的根 比较远比较远,则牛顿法可能发散。为了防止迭代发散则牛顿法可能发散。为了防止迭代发散,我们我们对牛顿迭代法的迭代过程再附加一项要求对牛顿迭代法的迭代过程再附加一项要求,即具有单调性即具有单调性0 x0 x*x)()(1kkxfxf 将牛顿迭代法与下山法结合起来使用将牛顿迭代法与下山法结合起来使用,即在下山法保证即在下山法保证函数函数值下降值下降的前提下的前提下,用牛顿迭代法加快收敛速度。把这一算法称用牛顿迭代法加快收敛速度。把这一算法称为为牛顿下山法牛顿下山法。即。即满足这项要求的算法称下山法。满足这项要求的算法称下山法。)()

59、(1kkkkxfxfxx其中其中(01)为下山因子为下山因子 . 下山因子的选择是个逐步探索的过程，设从下山因子的选择是个逐步探索的过程，设从=1开始反开始反复将复将减半进行试算减半进行试算, 即逐次取即逐次取为为从中挑选下山因子，直至找到其中某个从中挑选下山因子，直至找到其中某个使单调性条件使单调性条件成立，则称成立，则称“下山成功下山成功”，否则，否则“下山失败下山失败”，这时需另选初值重算。这时需另选初值重算。,21,21,12)()(1kkxfxf7.4.2 割线法与抛物线法割线法与抛物线法 111 ,0(), (), ()( )( )00kkk rkkk rrrkx xxf xf x

60、f xf xP xP xf xx设是的一组近似根，利用对应的函数值，构造插值多项式，适当选取的一个根作为的新的近似根。1( ), (),( )kkkf xf xf x下面设法多利用以前各次计算的函数值来回避导数值计算，导出这种求根方法的基本原理是插值法。1()()( ),( )kkkkkkf xfxNewtonxxf xf xf法每迭代一次计算函数值导数值各一次，当 函数本身比较复杂时，求导数值更加困难。11, ,1(2(kkkk rgxg x xxrr。这样就确定了一个迭代过程，记迭代函数为 ，则下面具体考察弦截法）与抛物线）两种情形。1. 割线法割线法/弦截法弦截法1111111111111()(