计算方法第七章

1、第第第第第第7 7 7 7 7 7章章章章章章 非线性方程与方程组的非线性方程与方程组的非线性方程与方程组的非线性方程与方程组的非线性方程与方程组的非线性方程与方程组的数值解法数值解法数值解法数值解法数值解法数值解法7.17.1方程求根与二分法方程求根与二分法7.27.2不动点迭代法及其收敛性不动点迭代法及其收敛性 7.37.3迭代收敛的加速方法迭代收敛的加速方法* *7.47.4牛顿法牛顿法7.57.5弦截法与抛物线法弦截法与抛物线法7.67.6求根问题的敏感性与多项式的零点求根问题的敏感性与多项式的零点* *7.77.7非线性方程组的数值解法非线性方程组的数值解法* *2 在科学研究和工程

2、设计中在科学研究和工程设计中, 经常会遇到的一大类经常会遇到的一大类问题是非线性方程问题是非线性方程f(x)=0 (7.1)的求根问题，其中的求根问题，其中f(x)为为非线性函数非线性函数。 方程方程f(x)=0的根的根, 亦称为函数亦称为函数f(x)的的零点零点。 如果如果f(x)可以分解成可以分解成 , ,其中其中m为为正整数且正整数且 , ,则称则称x* *是是f(x)f(x)的的m重零点重零点, ,或称或称方程方程f(x)=0的的m重根重根。当。当m=1时称时称x* *为单根。若为单根。若f(x)存在存在m阶导数阶导数, ,则是方程则是方程f(x)的的m重根重根( (m1) 当且仅当当

3、且仅当)()()(*xgxxxfm0)(*xg0)(,0)()()(*)(*)1(*xfxfxfxfmm7.1 方程求根与二分法方程求根与二分法3非线性方程的概念非线性方程的概念 当当f( (x) )不是不是x的线性函数时，称对应的函数方程的线性函数时，称对应的函数方程为为非线性方程非线性方程。如果。如果f( (x) )是多项式函数，则称为是多项式函数，则称为代数代数方程方程，否则称为，否则称为超越方程超越方程（三角方程，指数、对数方（三角方程，指数、对数方程等）。一般称程等）。一般称n n次多项式构成的方程次多项式构成的方程 )0(00111nnnnnaaxaxaxa为为n n次代数方程次代

4、数方程, ,当当n n1 1时时, ,方程显然是非线性的方程显然是非线性的 一般稍微复杂的一般稍微复杂的3 3次以上的代数方程或超越方程次以上的代数方程或超越方程, ,很难甚至无法求得精确解。本章将介绍常用的求解很难甚至无法求得精确解。本章将介绍常用的求解非线性方程的近似根的几种数值解法非线性方程的近似根的几种数值解法 4求根步骤求根步骤5二分法二分法 二分法又称二分区间法二分法又称二分区间法, ,是求解方程是求解方程(7.1)(7.1)的近的近似根的一种常用的简单方法。似根的一种常用的简单方法。 设函数设函数f( (x) )在闭区间在闭区间 a,b 上连续上连续, ,且且f( (a) )f(

5、 (b)0,)0,根据连续函数的性质可知根据连续函数的性质可知, , f( (x)= 0)= 0在在( (a,b) )内必有实内必有实根根, ,称区间称区间 a,b 为有根区间。为明确起见为有根区间。为明确起见, ,假定方程假定方程f( (x)=0)=0在区间在区间 a,b 内有惟一实根内有惟一实根x* *。 二分法的基本思想二分法的基本思想是是: : 首先确定有根区间首先确定有根区间, ,将区将区间二等分间二等分, , 通过判断通过判断f( (x) )的符号的符号, , 逐步将有根区间缩逐步将有根区间缩小小, , 直至有根区间足够地小直至有根区间足够地小, , 便可求出满足精度要便可求出满足

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

7、几何上讲讲,是求曲线是求曲线 y=f (x)与与 x轴交点的横坐标。轴交点的横坐标。7有根区间的确定有根区间的确定 由高等数学知识知由高等数学知识知, 设设f (x)为区间为区间a,b上的单值上的单值连续连续, 如果如果f (a)f (b)0 , 则则a,b中至少有一个实根。中至少有一个实根。如果如果f (x)在在a,b上还是单调地递增或递减，则仅有上还是单调地递增或递减，则仅有一个实根。一个实根。y=f(x)abyxn大体确定根所在子区间的方法有：大体确定根所在子区间的方法有： (1) 画图法画图法 (2) 逐步搜索法逐步搜索法8画图法画图法 画出画出y = f (x)的略图，从而看出曲线与

8、的略图，从而看出曲线与x轴交点的轴交点的 大致位置。大致位置。 也可将也可将f (x) = 0分解为分解为 1(x)= 2(x)的形式，的形式， 1(x) 与与 2(x)两曲线交点的横坐标所在的子区间即为含根两曲线交点的横坐标所在的子区间即为含根 区间。区间。例如例如 xlogx-1= 0= 0可以改写为可以改写为logx=1/x画出对数曲线画出对数曲线y=logx, ,与双曲线与双曲线y= 1/x,它们交它们交 点的横坐标位于区间点的横坐标位于区间2,32,3内内9画图法画图法xy1gxy 023yx10y0 xABa1b1a2b2 对于给定的对于给定的f (x),设有根区间为设有根区间为A

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

10、少有一个实根 设从设从x=0 x=0出发出发, ,取取h=0.5h=0.5为步长向右进行根的为步长向右进行根的 搜索搜索, ,列表如下列表如下xf(f(x) )0 0.5 1.0 1.5 20 0.5 1.0 1.5 2 + + + +可以看出，在可以看出，在1.0,1.51.0,1.5内必有一根内必有一根12搜索法搜索法 用逐步搜索法进行实根隔离的关键是选取步长用逐步搜索法进行实根隔离的关键是选取步长h 要选择适当要选择适当h ，使之既能把根隔离开来，工作量，使之既能把根隔离开来，工作量 又不太大。又不太大。 为获取指定精度要求的初值为获取指定精度要求的初值, ,可在以上隔离根的可在以上隔离

11、根的 基础上采用对分法继续缩小该含根子区间基础上采用对分法继续缩小该含根子区间 二分法可以看作是搜索法的一种改进。二分法可以看作是搜索法的一种改进。13二分法求根过程二分法求根过程 取有根区间取有根区间a,b之中点之中点, 将它分为两半将它分为两半,分点分点 ,这样就可缩小有根区间这样就可缩小有根区间 设方程设方程f(x)=0在区间在区间a,b内有根，二分法就是逐内有根，二分法就是逐步收缩有根区间，最后得出所求的根。步收缩有根区间，最后得出所求的根。具体过程如下具体过程如下 20bax y y=f(x) y=f(x) x* a x1 x* x0 b a x0 x1 b a1 b1 a1 b1

12、a2 b2 a2 b2 14二分法求根过程二分法求根过程 对压缩了的有根区间对压缩了的有根区间 施行同样的手法施行同样的手法, , 即取中点即取中点 , ,将区间将区间 再分为两半再分为两半, ,然然 后再确定有根区间后再确定有根区间 , ,其长度是其长度是 的的 二分之一二分之一 如此反复下去如此反复下去, ,若不出现若不出现 , ,即可得出一即可得出一 系列有根区间序列：系列有根区间序列： 11,ba2111bax11,ba22,ba11,ba0)(kxfkkbabababa,2211 上述每个区间都是前一个区间的一半上述每个区间都是前一个区间的一半, ,因此因此 的长度的长度kkba ,

13、)(21)(2111abababkkkkk15二分法求根过程二分法求根过程 当当k时趋于零时趋于零, ,这些区间最终收敛于一点这些区间最终收敛于一点x* * 即为即为 所求的根所求的根 。每次二分后每次二分后, ,取有根区间取有根区间 的中点的中点 作为根的近似值，得到一个近似根的序列作为根的近似值，得到一个近似根的序列 该序列以根该序列以根x* *为极限为极限kkba ,)(21kkkbax,210kxxxx 只要二分足够多次只要二分足够多次( (即即k足够大足够大),),便有便有这里这里为给定精度为给定精度, ,由于由于 , ,则则 1*22kkkkababxxkxx*kkbax,*16二

14、分法求根过程二分法求根过程11122kkkkkababab当给定精度当给定精度0 0后后, ,要想要想 成立成立, ,只要只要取取k满足满足 即可，亦即当即可，亦即当: kxx*)(211abk)2.7(12lglg)lg(abk时时, ,做到第做到第k+1次二分次二分, ,计算得到的计算得到的 就是满就是满足精度要求的近似根足精度要求的近似根 。kx17二分法求根过程二分法求根过程时时, ,做到第做到第k+1次二分次二分, ,计算得到的计算得到的 就是满就是满足精度要求的近似根足精度要求的近似根 。 在程序中通常用相邻的在程序中通常用相邻的 与与 的差的绝的差的绝对值或对值或 与与 的差的绝

15、对值是否小于的差的绝对值是否小于来来决定二分区间的次数。决定二分区间的次数。 kxkx1kxkakb18二分法算法实现二分法算法实现 y n 开 始 输 入 a , b, (a+b)/2 x f(a) f(x )0 ? xb x a |b-a|0 输 出 x 结 束 y n 19例题例题例例7.2 7.2 证明方程证明方程 在区间在区间2, 3内有一个内有一个根根 , 使用二分法求误差不超过使用二分法求误差不超过0.510-3 的根要二分的根要二分多少次？多少次？证明证明: 令令 0523 xx, 52)(3xxxf016)3(, 01)2(ff且且f( (x) )在在2, 3上连续上连续,

16、,故方程故方程f(x)=0 0在在2,32,3内至少有内至少有一个根。又一个根。又 当当 时，时， , ,故故f( (x) )在在2, 32, 3上是单调递增函数上是单调递增函数, ,从而从而f( (x) )在在2, 32, 3上有且仅有一根。上有且仅有一根。23)(2xxf3 , 2x0)( xf 给定误差限给定误差限 0.510-3 , ,使用二分法时使用二分法时20例题例题 误差限为误差限为 只要取只要取k满足满足 )(211*abxxkk311021)(21 abk即可，亦即即可，亦即 3102 k97.92110lg3gk所以需二分所以需二分1010次便可达到要求。次便可达到要求。2

17、1小结小结 二分法的优点是不管有根区间二分法的优点是不管有根区间 多大多大, ,总总能求出满足精度要求的根能求出满足精度要求的根, ,且对函数且对函数f( (x) )的要求不高的要求不高, ,只要连续即可只要连续即可, ,计算亦简单计算亦简单; ;它的局限性是只能用于它的局限性是只能用于求函数的实根求函数的实根, ,不能用于求复根及重根不能用于求复根及重根, ,它的收敛速它的收敛速度与比值为度与比值为 的等比级数相同。的等比级数相同。ba ,21227.2 不动点迭代法及其收敛性不动点迭代法及其收敛性 对于一般的非线性方程对于一般的非线性方程, ,没有通常所说的求根没有通常所说的求根公式求其精

18、确解公式求其精确解, ,需要设计近似求解方法需要设计近似求解方法, ,即迭代法。即迭代法。它是一种逐次逼近的方法它是一种逐次逼近的方法, ,用某个固定公式反复校正用某个固定公式反复校正根的近似值根的近似值, ,使之逐步精确化，最后得到满足精度要使之逐步精确化，最后得到满足精度要求的结果。求的结果。23不动点迭代法的基本思想不动点迭代法的基本思想即如果数即如果数 使使f(x)=0, 则也有则也有 , 反之反之, 若若 , 则也有则也有 , 称称 为迭代函数。为迭代函数。 任取一个初值任取一个初值 , 代入式代入式 的右端的右端, 得得到到 *x)(*xx)(*xx0)(*xf)(x0 x)(xx

19、)(01xx 为求解非线性方程为求解非线性方程f(x)=0 0的根，先将其写成便于的根，先将其写成便于迭代的等价方程迭代的等价方程 (7.3)(7.3)其中其中 为为x的连续函数的连续函数)(x)(xx24不动点迭代法的基本思想不动点迭代法的基本思想再将再将 代入式代入式 的右端的右端, 得到得到 ,依此类推依此类推, 得到一个数列得到一个数列 ， 其一般表示其一般表示 1x)(xx)(12xx)(23xx), 2 , 1 , 0()(1kxxkk式式(7.4)(7.4)称为求解非线性方程的称为求解非线性方程的简单迭代法简单迭代法。 (7.4)(7.4)如果由迭代格式如果由迭代格式 产生的序列

20、产生的序列 收敛收敛, ,即即 nx)(1kkxx*limxxnn则称迭代法收敛。则称迭代法收敛。 25迭代法的基本思想迭代法的基本思想 实际计算中当然不可能也没必要无穷多步地做实际计算中当然不可能也没必要无穷多步地做下去下去, , 对预先给定的精度要求对预先给定的精度要求，只要某个，只要某个k k满足满足1kkxx即可结束计算并取即可结束计算并取 kxx* 当然，迭代函数当然，迭代函数 的构造方法是多种多样的。的构造方法是多种多样的。)( x26“不动点不动点”不动点不动点，是一个函数术语，在数学中是指，是一个函数术语，在数学中是指“被这个被这个函数函数映射映射到其自身一个点到其自身一个点”

21、。例如：例如： 定义在实数上的函数定义在实数上的函数f f， f(x) = x2 - 3x + 4 f(x) = x2 - 3x + 4，则则2 2是函数是函数f f的一个不动点，因为的一个不动点，因为f(2) = 2f(2) = 2。27例题例题例例7.37.3 用迭代法求方程用迭代法求方程 中的根。中的根。解解 将方程改写成如下等价形式将方程改写成如下等价形式 xexx)(相应地可得到迭代公式相应地可得到迭代公式kxkkexx)(12ln,210 xex在在取初始值取初始值 0.50.5，用上述迭代公式迭代，用上述迭代公式迭代，计算结果见表计算结果见表0 x28例题例题 k01234xk0

22、.50.606531 0.545239 0.579703 0.560065 k56789xk0.571172 0.564863 0.568438 0.566410 0.567560 k1011121314xk0.566907 0.567278 0.567067 0.567187 0.56711929迭代法的几何意义迭代法的几何意义 通常将方程通常将方程f(x)=0f(x)=0化为与它同解的方程化为与它同解的方程的方法不止一种的方法不止一种, ,有的收敛有的收敛, ,有的不收敛有的不收敛, ,这取决于这取决于 的性态的性态, ,方程方程 的求根问题在几何上就是确定曲的求根问题在几何上就是确定曲线

23、线y= 与直线与直线y=x的交点的交点P*的横坐标的横坐标( (如图所示如图所示) ) )(xx)(x)(xx)(x y=x y y=)(x y=x 1)(0*x 0)(1*x P0 P2P* Q1 Q2 x1 x0 x2 x* x y x0 x x1 x2 x3 x* y=)(x)(x P* P1 (a)(b)30迭代法的几何意义迭代法的几何意义 y=x y y=x y=)(x 1)(* x 1)(* x （c） （d） P* x1 x0 x y x0 x x1 x2 x3 x* y=)(x)(x x* x2 P* 31迭代法收敛的条件迭代法收敛的条件 对方程对方程f(x)=0可以构造不同的

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

25、有的）对所有的xa,b 有有 a,b （2）存在）存在 0 L 1 ,使所有的使所有的xa,b有有 L则方程则方程 在在a,b上的解上的解 存在且唯一存在且唯一，对任意的，对任意的 a ,b ，迭代过程，迭代过程均收敛于均收敛于 。并有误差估计式。并有误差估计式 )(x)(x)(x)(xx*x0 x)(1kkxx*x33迭代法收敛的条件迭代法收敛的条件1*1kkkxxLLxx01*1xxLLxxkk 34迭代法收敛的条件迭代法收敛的条件由连续函数介值定理知由连续函数介值定理知, 必有必有 a, b, 使使 所以有解存在所以有解存在, 即即假设有两个解假设有两个解 和和 , , a, b，则，则

26、 ，证证: 构造函数构造函数 ,由条件对任意的由条件对任意的xa, b a, b有有xxx)()(0)()(0)()(bbbaaa)(x*x0)()(*xxx*xx*xx)(*xx)(xx35迭代法收敛的条件迭代法收敛的条件由微分中值定理有由微分中值定理有其中其中 是介于是介于x*和和 之间的点之间的点 从而有从而有 a,b，进而，进而有有 由条件由条件(2)有有 1, 所以所以 - =0，即，即 = ，解唯一。，解唯一。)()()(*xxxxxxx0)(1)(*xx)(x*xx*xx按迭代过程按迭代过程 ,有有 )(1kkxx)()()(1*1*kkkxxxxxx1*1*)(kkkxxLxx

27、xx0*2*21*xxLxxLxxLxxkkkk 由于由于L1,L1,所以有所以有 , ,可见可见L L越小越小, ,收敛越快收敛越快 *limxxkk36迭代法收敛的条件迭代法收敛的条件再证误差估计式再证误差估计式 1*1kkkxxLLxx01*1xxLLxxkk 1*1*kkkkkxxxxLxxLxx)(1*kkkxxxxL1*)1 (kkkxxLxxL37迭代法收敛的条件迭代法收敛的条件1*1kkkxxLLxx 即即 得证。得证。 2121211)()()(kkkkkkkkxxLxxxxxx012121*1111xxLLxxLLxxLxxkkkkkk即即 得证。得证。 38迭代法的算法框

28、图迭代法的算法框图 10)(xx 开 始 输 入 x0,N 1 kk+ 1 k x1 x0 输 出 近 似 根 x1 |x1- x0|? 输 出 迭 代 失 败 标 志 结 束 n k0c0），使），使 )(1kkxx)(xx*xkkxxe*ceepkkk1lim则称序列则称序列 是是 p 阶收敛的阶收敛的, ,c称渐近误差常数。称渐近误差常数。特别地特别地, ,p=1=1时称为线性收敛时称为线性收敛, ,p=2=2时称为平方收时称为平方收敛。敛。1 1 p 2 2时称为超线性收敛。时称为超线性收敛。 kx44收敛速度收敛速度 数数p的大小反映了迭代法收敛的速度的快慢，的大小反映了迭代法收敛的

29、速度的快慢，p愈大，则收敛的速度愈快，故迭代法的收敛阶愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。是对迭代法收敛速度的一种度量。 45收敛阶数收敛阶数定理定理7.3 设迭代过程设迭代过程 , 若若 在所求根在所求根 的邻域连续且的邻域连续且 则迭代过程则迭代过程在在 邻域是邻域是p阶收敛的。阶收敛的。证证: 由于由于 即在即在 邻域邻域 , 所以所以 有局部收敛性有局部收敛性, 将将 在在 处泰勒展开处泰勒展开 )(1kkxx)()(xp*x0)(, 0)()()(*)(*) 1(* xxxxpp*x0)(* x*x1)(* x)(1kkxx)(kx*xpkpkkkx

30、xpxxxxxxxx)(!1)(! 21)()()(*)(2* 根据已知条件得根据已知条件得 pkpkxxpxx)(!1)()(*)(*46收敛阶数收敛阶数由迭代公式由迭代公式 )(1kkxx及及)(*xx有有pkpkxxpxx)(!)(*)(*10!)(lim*)(1pxeeppkkk47例题例题例例7.6 已知迭代公式已知迭代公式 收敛于收敛于 证明该迭代公式平方收敛。证明该迭代公式平方收敛。证证: 迭代公式相应的迭代函数为迭代公式相应的迭代函数为21132kkkxxx3*3x2132)(xxx436)(232)(xxxx ，将将 代入，代入，根据定理根据定理7.3可知，迭代公式平方收敛。

31、可知，迭代公式平方收敛。3*3x032336)(0)(33* xx，487.3 迭代收敛的加速方法迭代收敛的加速方法略略497.4 牛顿法牛顿法 用迭代法可逐步精确方程用迭代法可逐步精确方程 根的近似值根的近似值，但必须要找到，但必须要找到 的等价方程的等价方程 , ,如果如果 选得不合适选得不合适, ,不仅影响收敛速度不仅影响收敛速度, ,而且有可能造成迭代而且有可能造成迭代格式发散。能否找到一种迭代方法格式发散。能否找到一种迭代方法, ,既结构简单既结构简单, ,收敛收敛速度快速度快, ,又不存在发散的问题。这就是本节要介绍的又不存在发散的问题。这就是本节要介绍的牛顿迭代法牛顿迭代法。 0

32、)(xf0)(xf)(xx)(x牛顿迭代法一种重要和常用的迭代法牛顿迭代法一种重要和常用的迭代法, 它的基本思想它的基本思想是将非线性函数是将非线性函数f(x)逐步线性化逐步线性化, 从而将非线性方程从而将非线性方程f(x)=0近似地转化为线性方程求解。近似地转化为线性方程求解。50牛顿迭代公式牛顿迭代公式 对于方程对于方程 ,设其近似根为设其近似根为 , 函数函数f( (x) )可在可在 附近作泰勒展开附近作泰勒展开 0)(xfkxkx 2)(21)()()(kkkkkxxxfxxxfxfxf忽略高次项忽略高次项, ,用其线性部分作为函数用其线性部分作为函数f(x)f(x)的近似，的近似，

33、)()()(kkkxxxfxfxf 设设 的根的根 , ,则有则有 , ,即即 0)(xf*x0)(*xf0)()(*kkkxxxfxf)()(*kkkxfxfxx将左端取为将左端取为 , ,即即 是比是比 更接近于更接近于 的近似值的近似值 )()(1kkkkxfxfxx)2,1 ,0(k1kx1kxkx*x牛顿迭代公式牛顿迭代公式51牛顿迭代法的几何解释牛顿迭代法的几何解释 方程方程f( (x)=0)=0的根的根x* *是曲线是曲线y= =f( (x) )与与x轴交点的横坐轴交点的横坐标标, ,设设xk k是根是根x* *的某个近似值的某个近似值, ,过曲线过曲线y= =f( (x) )的

34、横坐标为的横坐标为xk k的点的点Pk=(xk, f (xk)引切线交引切线交x轴于轴于xk+1 , 并将其作为并将其作为x* * y y=f(x) Pk Pk+1 Pk+2 x* xk+2 xk+1 xk x 新的近似值新的近似值, ,重复重复上述过程上述过程, ,可见一可见一次次用切线方程来次次用切线方程来求解方程求解方程f( (x)=0)=0的的根根, ,所以亦称为牛所以亦称为牛顿切线法。顿切线法。52牛顿迭代法的收敛性牛顿迭代法的收敛性定理定理7.4 设设 是方程是方程 的单根的单根, 且且f(x)在在 的某的某邻域内有连续的二阶导数邻域内有连续的二阶导数, 则牛顿法在则牛顿法在 附近

35、局部收附近局部收敛敛, 且至少二阶收敛且至少二阶收敛, 有有 *x0)(xf*x*x)(2)(limlim*2*1*1xfxfxxxxeekkkkkk 证证: 牛顿迭代公式对应的迭代函数为牛顿迭代公式对应的迭代函数为 若若 是方程是方程 的单根的单根,则有则有 , 从而从而 )()()(xfxfxx*x0)(xf0)(*xf0)(* xf0)()()()(2* xfxfxfx53牛顿迭代法的收敛性牛顿迭代法的收敛性由定理由定理7.2知知,牛顿迭代法在牛顿迭代法在 附近局部收敛。又由附近局部收敛。又由定理定理7.3知知, 迭代公式至少具有二阶收敛速度。迭代公式至少具有二阶收敛速度。 *x利用泰勒

36、公式利用泰勒公式kkkkkxxxxfxxxfxfxf,)(2)()()()(0*2* 2*)()(2)()()(kkkkkxxxffxfxfxx 2*)()(2)()()(kkkkkxxxffxxfxfx 54牛顿迭代法的收敛性牛顿迭代法的收敛性2*1)()(2)(kkkxxxffxx )(2)(lim*2*1*xfxfxxxxkkk 所以所以 证毕证毕55牛顿迭代法的收敛性牛顿迭代法的收敛性yx10 x0X*0 x0X*x2 不满足迭代条件时，可能导致迭代值远离不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况根的情况而找不到根或死循环的情况56牛顿迭代法的算法实现牛顿迭代

37、法的算法实现 ?0)(0 xf 1000)()(xxfxfx ?01 xx 开 始 输 入 x0,N 1 k k+ 1 k x1 x0 输 出 x1 输 出 迭 代 失 败 标 志 结 束 n k N ? n n y 输 出 奇 异 标 志 y y 57例题例题例例7.7 用用求求 x ex 1 =0的根的根,=10-4解：因解：因 f (xk)= x ex 1 , f (xk)=ex ( x+1)建立迭代公式建立迭代公式nxnnnxxnnnxexxxeexxxnnn 1)1 (11取取x0=0.5,逐次计算得逐次计算得 x1=0.57102, x2=0.56716， x3=0.5671458

38、7.5 弦截法弦截法牛顿迭代法虽然具有收敛速度快的优点，但牛顿迭代法虽然具有收敛速度快的优点，但每迭代一次都要计算导数每迭代一次都要计算导数 , 当当 比较复比较复杂时杂时, 不仅每次计算不仅每次计算 带来很多不便，而且带来很多不便，而且还可能十分麻烦，如果用不计算导数的迭代还可能十分麻烦，如果用不计算导数的迭代方法，往往只有线性收敛的速度。本节介绍方法，往往只有线性收敛的速度。本节介绍的弦截法便是一种不必进行导数运算的求根的弦截法便是一种不必进行导数运算的求根方法。弦截法在迭代过程中不仅用到前一步方法。弦截法在迭代过程中不仅用到前一步 处的函数值处的函数值 ，而且还使用，而且还使用 处的函数值处的函数值来构造迭代函数，这样做能提高迭代的收敛来构造迭代函数，这样做能提高迭代的收敛速度。速度。)(kxf )(xf)(kxfkx1kx59弦截迭代公式弦截迭代公式 为避免计算函数的导数为避免计算函数的导数 ，使用差商，使用差商 替代牛顿公式中的导数替代牛顿公式中的导数 ,便得到迭代公式便得到迭代公式 称为弦截迭代公式，称为弦截迭代公式， 相