第四章方程求根的迭代法VIP

1、School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt引言引言 在科学研究和工程设计中在科学研究和工程设计中, 经常会遇到的一大类问题是非经常会遇到的一大类问题是非线性方程线性方程 f(x)=0 (4.1)的求根问题，其中的求根问题，其中f(x)为非线性函数。为非线性函数。f(x)=0的根的根, 亦称为函数亦称为函数f(x)的零点的零点 如果如果f(x)可以分解成可以分解成 ,其中其中m为正整数为正整数且且 ,则称则称x*是是f(x)的的m重零点重零点,或称方程或称方程f(x)=0的的

2、m重根。重根。当当m=1时称时称x*为单根。若为单根。若f(x)存在存在m阶导数阶导数,则是方程则是方程f(x)的的m重重根根(m1) 当且仅当当且仅当)()()(*xgxxxfm0)(*xg0)(,0)()()(*)(*)1(*xfxfxfxfmm第四章第四章 方程求根的迭代法方程求根的迭代法School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt记笔记记笔记 当当f(x)不是不是x的线性函数时，称对应的函数方程为非线性方的线性函数时，称对应的函数方程为非线性方程。如果程。如果f(x)

3、是多项式函数，则称为代数方程，否则称为超越是多项式函数，则称为代数方程，否则称为超越方程（三角方程，指数、对数方程等）。一般称方程（三角方程，指数、对数方程等）。一般称n次多项式构次多项式构成的方程成的方程 )0(00111nnnnnaaxaxaxa为为n次代数方程次代数方程,当当n1时时,方程显然是非线性的。方程显然是非线性的。 一般稍微复杂的一般稍微复杂的3次以上的代数方程或超越方程次以上的代数方程或超越方程,很难甚至很难甚至无法求得精确解。本章将介绍常用的求解非线性方程的近似无法求得精确解。本章将介绍常用的求解非线性方程的近似根的几种数值解法根的几种数值解法 。School of Aut

4、omation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理pptSchool of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理pptn本章介绍方程的迭代解法，它既可以用来求解代数方程，本章介绍方程的迭代解法，它既可以用来求解代数方程，也可以用来解超越方程，并且仅限于求方程的实根。也可以用来解超越方程，并且仅限于求方程的实根。n运用迭代法求解方程的根应解决以下两个问题：运用迭代法求解方程的根应解决以下两个问题：q确定根的初值确定

5、根的初值;q将进一步精确化到所需要的精度。将进一步精确化到所需要的精度。School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt4.1 二分法二分法 二分法又称二分区间法二分法又称二分区间法,是求解方程是求解方程(4.1)的近似根的一种的近似根的一种常用的简单方法。常用的简单方法。 设函数设函数f(x)在闭区间在闭区间a,b上连续上连续,且且f(a)f(b)0,根据连续函根据连续函数的性质可知数的性质可知, f(x)= 0在在(a,b)内必有实根内必有实根,称区间称区间a,b为有根区为有

6、根区间。为明确起见间。为明确起见,假定方程假定方程f(x)=0在区间在区间a,b内有惟一实根内有惟一实根x*。 二分法的基本思想是二分法的基本思想是: 首先确定有根区间首先确定有根区间,将区间二等分将区间二等分, 通过判断通过判断f(x)的符号的符号, 逐步将有根区间缩小逐步将有根区间缩小, 直至有根区间足够直至有根区间足够地小地小, 便可求出满足精度要求的近似根。便可求出满足精度要求的近似根。School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt4.1.1确定有根区间的方法确定有根区

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

8、x)与与 x轴交点的横坐标。轴交点的横坐标。School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 由高等数学知识知由高等数学知识知, 设设f (x)为区间为区间a,b上的单值连续上的单值连续, 如果如果f (a)f (b)0 , 则则a,b中至少有一个实根。如果中至少有一个实根。如果f (x)在在a,b上上还是单调地递增或递减，则仅有一个实根。还是单调地递增或递减，则仅有一个实根。记笔记记笔记n由此可大体确定根所在子区间，方法有：由此可大体确定根所在子区间，方法有： (1) 画图法画

9、图法 (2) 逐步搜索法逐步搜索法y=f(x)abyxSchool of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt(1) 画图法画图法n 画出画出y = f (x)的略图，从而看出曲线与的略图，从而看出曲线与x轴交点的轴交点的 大致位置。大致位置。n 也可将也可将f (x) = 0分解为分解为 1(x)= 2(x)的形式，的形式， 1(x) 与与 2(x)两曲线交点的横坐标所在的子区间即为含根两曲线交点的横坐标所在的子区间即为含根 区间。区间。例如例如 xlogx-1= 0可以改写为可以改写

10、为logx=1/x画出对数曲线画出对数曲线y=logx,与双曲线与双曲线y= 1/x,它们交点的横坐标它们交点的横坐标位于区间位于区间2,3内内School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt(1) 画图法画图法xy1gxy 023yxSchool of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理pptn对于某些看不清根的函数，可以扩大一下曲线对于某些看不清根的函数，可以扩大一下曲线y

11、0 xy=f(x)y=kf(x)记笔记记笔记School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppty0 xABa1b1a2b2(2) 逐步搜索法逐步搜索法 对于给定的对于给定的f (x),设有根区间为设有根区间为A,B,从从x0=A出发出发,以步长以步长h=(B-A)/n(n是正整数是正整数),在在A,B内取定节点内取定节点:xi=x0ih (i=0,1,2,n),从左至右检查从左至右检查f (xi)的符号的符号,如发现如发现xi与端点与端点x0的函的函数值异号数值异号,则得到一个缩小

12、的有根子区间则得到一个缩小的有根子区间xi-1,xi。School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt例例4.1 方程方程f(x)=x3-x-1=0 确定其有根区间确定其有根区间解：用试凑的方法，不难发现解：用试凑的方法，不难发现 f(0)0 在区间（在区间（0，2）内至少有一个实根）内至少有一个实根 设从设从x=0出发出发,取取h=0.5为步长向右进行根的为步长向右进行根的 搜索搜索,列表如下列表如下xf(x)0 0.5 1.0 1.5 2 + +可以看出，在可以看出，在1.0

13、,1.5内必有一根。内必有一根。School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理pptn 用逐步搜索法进行实根隔离的关键是选取步长用逐步搜索法进行实根隔离的关键是选取步长h。n 要选择适当要选择适当h ，使之既能把根隔离开来，工作量，使之既能把根隔离开来，工作量 又不太大。又不太大。 n 为获取指定精度要求的初值为获取指定精度要求的初值,可在以上隔离根的可在以上隔离根的 基础上采用对分法继续缩小该含根子区间。基础上采用对分法继续缩小该含根子区间。 二分法可以看作是搜索法的一种改进。二分

14、法可以看作是搜索法的一种改进。School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 取有根区间取有根区间a,b之中点之中点, 将它分为两半将它分为两半,分点分点 ,这样就这样就可缩小有根区间可缩小有根区间4.2.2 二分法求根过程二分法求根过程 设方程设方程f(x)=0在区间在区间a,b内有根内有根,二分法就是逐步收缩有根二分法就是逐步收缩有根区间，最后得出所求的根。具体过程如下区间，最后得出所求的根。具体过程如下 :20bax y y=f(x) y=f(x) x* a x1 x*

15、x0 b a x0 x1 b a1 b1 a1 b1 a2 b2 a2 b2 School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 对压缩了的有根区间对压缩了的有根区间 施行同样的手法施行同样的手法, 即取中点即取中点 ,将区间将区间 再分为两半再分为两半,然后再确定有根区间然后再确定有根区间 ，其长度是，其长度是 的二分之一。的二分之一。 如此反复下去如此反复下去,若不出现若不出现 ,即可得出一系列有根即可得出一系列有根 区间序列：区间序列： 上述每个区间都是前一个区间的一半上述每

16、个区间都是前一个区间的一半,因此因此 的长度的长度11,ba2111bax11,ba22,ba11,ba0)(kxfkkbabababa,2211kkba ,)(21)(2111abababkkkkk 当当k时趋于零时趋于零,这些区间最终收敛于一点这些区间最终收敛于一点x* 即为所求的根即为所求的根 。School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 每次二分后每次二分后,取有根区间取有根区间 的中点的中点作为根的近似值，得到一个近似根的序列作为根的近似值，得到一个近似根的序列

17、该序列以根该序列以根x*为极限。为极限。 只要二分足够多次只要二分足够多次(即即k足够大足够大),便有便有这里这里为给定精度为给定精度,由于由于 ,则则 11122kkkkkababab1*22kkkkababxxkkba ,)(21kkkbax,210kxxxxkxx*kkbax,*School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt当给定精度当给定精度0后后,要想要想 成立成立,只要取只要取k满足满足 即可，亦即当即可，亦即当: kxx*)(211abk12lglg)lg(abk

18、时时,做到第做到第k+1次二分次二分,计算得到的计算得到的 就是满足精度要求的近就是满足精度要求的近似根似根 。 在程序中通常用相邻的在程序中通常用相邻的 与与 的差的绝对值或的差的绝对值或 与与 的差的绝对值是否小于的差的绝对值是否小于来决定二分区间的次数。来决定二分区间的次数。 kxkx1kxkakbSchool of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt y n 开 始 输 入 a , b, (a+b)/2 x f(a) f(x )0 ? xb x a |b-a|0 输 出 x 结

19、 束 y n 二分法算法实现二分法算法实现School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt例例4.2 证明方程证明方程 在区间在区间2, 3内有一个根内有一个根, 使用二使用二分法求误差不超过分法求误差不超过0.510-3 的根要二分多少次？的根要二分多少次？证明：证明： 令令 0523 xx52)(3xxxf016)3(, 01)2(ff且且f(x)在在2, 3上连续上连续,故方程故方程f(x)=0在在2,3内至少有一个根。又内至少有一个根。又 当时当时时，时， ,故故f(x)

20、在在2, 3上是单调递增函数上是单调递增函数,从而从而f(x)在在2, 3上有且仅有一根。上有且仅有一根。23)(2xxf3 , 2x0)( xf 给定误差限给定误差限 0.510-3 ,使用二分法时使用二分法时School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 误差限为误差限为 只要取只要取k满足满足 )(211*abxxkk311021)(21 abk即可，亦即即可，亦即 3102 k97.92110lg3gk所以需二分所以需二分10次便可达到要求。次便可达到要求。 二分法的优

21、点是不管有根区间二分法的优点是不管有根区间 多大多大,总能求出满足总能求出满足精度要求的根精度要求的根,且对函数且对函数f(x)的要求不高的要求不高,只要连续即可只要连续即可,计算亦计算亦简单简单;它的局限性是只能用于求函数的实根它的局限性是只能用于求函数的实根,不能用于求复根及不能用于求复根及重根重根,它的收敛速度与比值为它的收敛速度与比值为 的等比级数相同。的等比级数相同。 ba ,21School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt4.3 迭代法迭代法 对于一般的非线性方程

22、对于一般的非线性方程,没有通常所说的求根公式求其没有通常所说的求根公式求其精确解精确解,需要设计近似求解方法需要设计近似求解方法,即迭代法。它是一种逐次逼即迭代法。它是一种逐次逼近的方法近的方法,用某个固定公式反复校正根的近似值用某个固定公式反复校正根的近似值,使之逐步精使之逐步精确化，最后得到满足精度要求的结果。确化，最后得到满足精度要求的结果。4.3.1 迭代法的基本思想迭代法的基本思想 为求解非线性方程为求解非线性方程f(x)=0的根，先将其写成便于迭代的等的根，先将其写成便于迭代的等价方程价方程 (4.3)其中其中 为为x的连续函数。的连续函数。)(x)(xxSchool of Aut

23、omation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt即如果数即如果数 使使f(x)=0, 则也有则也有 , 反之反之, 若若 , 则则也有也有 , 称称 为迭代函数任取一个初值为迭代函数任取一个初值 , 代入式代入式 的右端的右端, 得到得到 *x)(*xx)(*xx0)(*xf)(x0 x)(xx)(01xx再将再将 代入式代入式 的右端的右端, 得到得到 ,依此类推依此类推, 得得到一个数列到一个数列 ， 其一般表示其一般表示 1x)(xx)(12xx)(23xx), 2 , 1 , 0()(1kxxkk

24、式式(4.4)称为求解非线性方程的简单迭代法。称为求解非线性方程的简单迭代法。 (4.4)School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt如果由迭代格式如果由迭代格式 产生的序列产生的序列 收敛收敛,即即 nx)(1kkxx*limxxnn则称迭代法收敛。则称迭代法收敛。 实际计算中当然不可能也没必要无穷多步地做下去实际计算中当然不可能也没必要无穷多步地做下去, 对预对预先给定的精度要求先给定的精度要求，只要某个，只要某个k满足满足1kkxx即可结束计算并取即可结束计算并取 kx

25、x* 当然，迭代函数当然，迭代函数 的构造方法是多种多样的。的构造方法是多种多样的。)( xSchool of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt例例4.3 用迭代法求方程用迭代法求方程 在在x=1.5附近的一个根。附近的一个根。解解 将方程改写成如下两种等价形式将方程改写成如下两种等价形式 013 xx1)(1)(3231xxxxxx相应地可得到两个迭代公式相应地可得到两个迭代公式1)(1)(321311kkkkkkxxxxxx如果取初始值如果取初始值 1.5，用上述两个迭代公式分别

26、迭代，计，用上述两个迭代公式分别迭代，计算结果。算结果。 0 xSchool of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt4.3.2 迭代法的几何意义迭代法的几何意义 通常将方程通常将方程f(x)=0化为与它同解的方程化为与它同解的方程 的方法不止的方法不止一种一种,有的收敛有的收敛,有的不收敛有的不收敛,这取决于这取决于 的性态的性态,方程方程 的求根问题在几何上就是确定曲线的求根问题在几何上就是确定曲线y= 与直线与直线y=x的交点的交点P*的横坐标。的横坐标。)(xx)(x)(xx)

27、(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)School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 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* 图图4-1 迭代法的几何意义迭代法的几何意义 School

28、of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt4.3.3 迭代法收敛的条件迭代法收敛的条件 对方程对方程f(x)=0可以构造不同的迭代公式可以构造不同的迭代公式, 但迭代公式但迭代公式并非总是收敛。那么并非总是收敛。那么,当迭代函数当迭代函数 满足什么条件时，相应满足什么条件时，相应的迭代公式才收敛呢？即使迭代收敛时，我们也不可能迭代的迭代公式才收敛呢？即使迭代收敛时，我们也不可能迭代很多次，而是迭代有限次后就停止，这就需要估计迭代值的很多次，而是迭代有限次后就停止，这就需要估计迭代值的误差

29、，以便适时终止迭代误差，以便适时终止迭代 。),2, 1 ,0()(1kxxkk)(xSchool of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt定理定理4.1 设函数设函数 在在a,b上具有连续的一阶导数上具有连续的一阶导数, 且满足且满足 （1）对所有的）对所有的xa,b 有有 a,b （2）存在）存在 0 L 1 ,使所有的使所有的xa,b有有 L则方程则方程 在在a,b上的解上的解 存在且唯一，对任意的存在且唯一，对任意的 a ,b ，迭代过程，迭代过程 均收敛于均收敛于 。并有误。

30、并有误差估计式差估计式 )(x)(x)(x)(xx*x0 x)(1kkxx*x1*1kkkxxLLxx01*1xxLLxxkk School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt由连续函数介值定理知由连续函数介值定理知, 必有必有 a, b, 使使 所以有解存在所以有解存在, 即即假设有两个解假设有两个解 和和 ； , a, b，则，则 ，由微分中值定理有由微分中值定理有其中其中是介于是介于x*和和 之间的点，从而有之间的点，从而有a,b，进而有，进而有 由条件由条件(2)有有 1

31、, 所以所以 - =0，即，即 = ，解唯一。，解唯一。证证: 构造函数构造函数 ,由条件由条件对任意的对任意的xa, b a, b有有xxx)()(0)()(0)()(bbbaaa)(x*x0)()(*xxx*xx*xx)(*xx)(xx)()()(*xxxxxxx0)(1)(*xx)(x*xx*xxSchool of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt按迭代过程按迭代过程 ,有有 )(1kkxx)()()(1*1*kkkxxxxxx1*1*)(kkkxxLxxxx0*2*21*xx

32、LxxLxxLxxkkkk 由于由于L1,所以有所以有 ,可见可见L越小越小,收敛越快收敛越快 *limxxkk再证误差估计式再证误差估计式 1*1kkkxxLLxx01*1xxLLxxkk School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 1*1*kkkkkxxxxLxxLxx)(1*kkkxxxxL1*)1 (kkkxxLxxL1*1kkkxxLLxx 即即 得证。得证。 2121211)()()(kkkkkkkkxxLxxxxxx012121*1111xxLLxxLLxxL

33、xxkkkkkk即即 得证。得证。 School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 10)(xx 开 始 输 入 x0,N 1 kk+ 1 k x1 x0 输 出 近 似 根 x1 |x1- x0|? 输 出 迭 代 失 败 标 志 结 束 n k0），使），使 )(1kkxx)(xx*xkkxxe*ceepkkk1lim则称序列则称序列 是是 p 阶收敛的阶收敛的,c称渐近误差常数。特别地称渐近误差常数。特别地,p=1时称时称为线性收敛为线性收敛,p=2时称为平方收敛。时称为

34、平方收敛。1 p 2时称为超线性收敛。时称为超线性收敛。 kx 数数p的大小反映了迭代法收敛的速度的快慢，的大小反映了迭代法收敛的速度的快慢，p愈大，则收敛愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。 School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt定理定理4.3 设迭代过程设迭代过程 , 若若 在所求根在所求根 的邻域连的邻域连续且续且 则迭代过程在则迭代过程在 邻域是邻域是p阶收敛的。阶收敛的

35、。证证: 由于由于 即在即在 邻域邻域 , 所以所以 有局部收敛性有局部收敛性, 将将 在在 处泰勒展开处泰勒展开 )(1kkxx)()(xp*x0)(, 0)()()(*)(*) 1(* xxxxpp*x0)(* x*x1)(* x)(1kkxx)(kx*xpkpkkkxxpxxxxxxxx)(!1)(! 21)()()(*)(2* 根据已知条件得根据已知条件得 pkpkxxpxx)(!1)()(*)(*由迭代公式由迭代公式 )(1kkxx及及)(*xx有有pkpkxxpxx)(!)(*)(*10!)(lim*)(1pxeeppkkkSchool of Automation Engineer

36、ing自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt例例4.7 已知迭代公式已知迭代公式 收敛于收敛于 证明该迭代公式平方收敛。证明该迭代公式平方收敛。证证: 迭代公式相应的迭代函数为迭代公式相应的迭代函数为21132kkkxxx3*3x2132)(xxx436)(232)(xxxx ，将将 代入，代入，根据定理根据定理4.3可知，迭代公式平方收敛。可知，迭代公式平方收敛。3*3x032336)(0)(33* xx，为了使迭代过程收敛或提高收敛的速度为了使迭代过程收敛或提高收敛的速度, 可设法可设法 提高初值的精度以减少迭代的次数提高初值的

37、精度以减少迭代的次数 提高收敛的阶数提高收敛的阶数 pSchool of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 用迭代法可逐步精确方程用迭代法可逐步精确方程 根的近似值，但必须要根的近似值，但必须要找到找到 的等价方程的等价方程 ,如果如果 选得不合适选得不合适,不仅影不仅影响收敛速度响收敛速度,而且有可能造成迭代格式发散。能否找到一种迭代而且有可能造成迭代格式发散。能否找到一种迭代方法方法,既结构简单既结构简单,收敛速度快收敛速度快,又不存在发散的问题。这就是本又不存在发散的问题。这就

38、是本节要介绍的牛顿迭代法节要介绍的牛顿迭代法2.4.1 牛顿迭代法的基本思想牛顿迭代法的基本思想 牛顿迭代法一种重要和常用的迭代法牛顿迭代法一种重要和常用的迭代法, 它的基本思想是将它的基本思想是将非线性函数非线性函数f(x)逐步线性化逐步线性化, 从而将非线性方程从而将非线性方程f(x)=0近似地转近似地转化为线性方程求解。化为线性方程求解。4.4 牛顿迭代法牛顿迭代法 0)(xf0)(xf)(xx)(xSchool of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 对于方程对于方程 ,设其

39、近似根为设其近似根为 ， 函数函数f(x)可在可在 附近作泰勒展开附近作泰勒展开 0)(xfkxkx 2)(21)()()(kkkkkxxxfxxxfxfxf忽略高次项忽略高次项,用其线性部分作为函数用其线性部分作为函数f(x)的近似，的近似， )()()(kkkxxxfxfxf 设设 的根的根 ,则有则有 ,即即 0)(xf*x0)(*xf0)()(*kkkxxxfxf)()(*kkkxfxfxx将右端取为将右端取为 ,即即 是比是比 更接近于更接近于 的近似值的近似值 )()(1kkkkxfxfxx)2,1 ,0(k1kx1kxkx*x这就是著名的牛顿迭代公式这就是著名的牛顿迭代公式Sch

40、ool of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt2.4.2 牛顿迭代法的几何解释牛顿迭代法的几何解释 方程方程f(x)=0的根的根x*是曲线是曲线y=f(x)与与x轴交点的横坐标轴交点的横坐标,设设xk是根是根x*的某个近似值的某个近似值,过曲线过曲线y=f(x)的横坐标为的横坐标为xk的点的点Pk=(xk, f (xk)引切引切线交线交x轴于轴于xk+1 , 并将其作为并将其作为x* y y=f(x) Pk Pk+1 Pk+2 x* xk+2 xk+1 xk x 新的近似值新的近似值

41、,重复上述重复上述过程过程,可见一次次用切可见一次次用切线方程来求解方程线方程来求解方程f(x)=0的根的根,所以亦称所以亦称为牛顿切线法。为牛顿切线法。School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt（1） f(a) f(b)0,那么那么 Newton迭代法迭代法产生的数列产生的数列xn+1一定收敛一定收敛f(x)=0在在a,b中的唯一根中的唯一根。0)(, 0)(, 0)( 0 xfxfxf为例证明（其它情况类似）为例证明（其它情况类似） (). 设设 f(x)在在a,b满足

42、下列条件满足下列条件:以以School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 将将f()在在 xn 处作处作2阶阶Taylor展开展开1212222 02 nnnnnnnnnnnnnnnnx)x()x( f)(fx)x()x( f)(f)x( f)x(fx)x(!)(f)x)(x( f)x(f)(f 说明数列说明数列 xn+1有下界有下界. 又又nnnnnxxfxfxx )( )(1所以所以xn+1收敛。设收敛。设 xxnnlim1则由则由Newton迭代法迭代法, x,)x(f,

43、)x( f)x(fxx0故故xn+1单调递减。单调递减。School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt2.4.3 牛顿迭代法的收敛性牛顿迭代法的收敛性定理定理4.4 设设 是方程是方程 的单根的单根, 且且f(x)在在 的某邻域的某邻域内有连续的二阶导数内有连续的二阶导数, 则牛顿法在则牛顿法在 附近局部收敛附近局部收敛, 且至少二且至少二阶收敛阶收敛, 有有 *x0)(xf*x*x)(2)(limlim*2*1*1xfxfxxxxeekkkkkk 证证: 牛顿迭代公式对应的迭

44、代函数为牛顿迭代公式对应的迭代函数为 若若 是方程是方程 的单根的单根,则有则有 , 从而从而 )()()(xfxfxx*x0)(xf0)(*xf0)(* xf0)()()()(2* xfxfxfx由定理由定理4.2知知,牛顿迭代法在牛顿迭代法在 附近局部收敛。又由定理附近局部收敛。又由定理4.3知知, 迭代公式至少具有二阶收敛速度。迭代公式至少具有二阶收敛速度。 *xSchool of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt利用泰勒公式利用泰勒公式kkkkkxxxxfxxxfxfxf,)

45、(2)()()()(0*2* 2*)()(2)()()(kkkkkxxxffxfxfxx 2*)()(2)()()(kkkkkxxxffxxfxfx 2*1)()(2)(kkkxxxffxx )(2)(lim*2*1*xfxfxxxxkkk 所以所以 证毕证毕School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理pptyx0B=x0f (x)0 xn+1X*ayx0Bf (x)0a=x0yx0B=x0f (x)0ayx0Bf (x)0a =x0 4.4.3 牛顿迭代法的收敛性牛顿迭代法的收敛

46、性School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理pptyx10 x0X*0 x0X*x2 不满足迭代条件时，可能导致迭代值远离根的情况而找不不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况到根或死循环的情况4.4.3 牛顿迭代法的收敛性牛顿迭代法的收敛性School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理pptNewton法的收敛性依赖于法的收敛性依赖于x0

47、的选取。的选取。x*x0 x0 x0School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt ?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 牛顿迭代法的算法实现牛顿迭代法的算法实现School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章

48、方程求根的迭代法方程求根的迭代法整理ppt例例4.11 用用求求 x=e-x的根的根,=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.56714School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt用用NewtonNewton迭代法求下面方程的一个正根迭代法求下

49、面方程的一个正根, ,计算结果精确计算结果精确到到7 7位小数位小数. .02010223 xxx322 ( )21020,(0)200,(2)160.0,2 ,( ) 34 x100, ( )640. f xxxxfffxxfxx 设在上满足迭代定理的条件由由NewtonNewton迭代法迭代法 得得取取初初值值,x2020 x1 1 = 1.4666667 ,x4 4 = 1.3688081x5 5 = 1.3688081)()(1kkkkxfxfxx104310102223 kkkkkkkxxxxxxx迭代迭代5 5次次精度达精度达10-7x* * 1.3688081kx*x)(xfy

50、kxSchool of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt4.4.5 牛顿下山法牛顿下山法 通常通常,牛顿迭代法的收敛性依赖于初始值牛顿迭代法的收敛性依赖于初始值 的选取的选取,如果如果 偏离所求的根偏离所求的根 比较远比较远,则牛顿法可能发散。为了防止迭代发散则牛顿法可能发散。为了防止迭代发散,我们对牛顿迭代法的迭代过程再附加一项要求我们对牛顿迭代法的迭代过程再附加一项要求,即具有单调性即具有单调性 0 x0 x*x)()(1kkxfxf 将牛顿迭代法与下山法结合起来使用将牛顿迭代法

51、与下山法结合起来使用,即在下山法保证函即在下山法保证函数值下降的前提下数值下降的前提下,用牛顿迭代法加快收敛速度。把这一算法用牛顿迭代法加快收敛速度。把这一算法称为牛顿下山法。即称为牛顿下山法。即满足这项要求的算法称下山法。满足这项要求的算法称下山法。)()(1kkkkxfxfxx其中其中(01)为下山因子为下山因子 School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 下山因子的选择是个逐步探索的过程，设从下山因子的选择是个逐步探索的过程，设从=1开始反复开始反复将将减半进行试算减

52、半进行试算, 即逐次取即逐次取为为从中挑选下山因子，直至找到其中某个从中挑选下山因子，直至找到其中某个使单调性条件使单调性条件成立，则称成立，则称“下山成功下山成功”，否则，否则“下山失败下山失败”，这时需另选初值重算。这时需另选初值重算。,21,21,12)()(1kkxfxfSchool of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt4.5 弦截法弦截法 牛顿迭代法虽然具有收敛速度快的优点，但每迭代一次都牛顿迭代法虽然具有收敛速度快的优点，但每迭代一次都要计算导数要计算导数 , 当当 比

53、较复杂时比较复杂时, 不仅每次计算不仅每次计算 带带来很多不便，而且还可能十分麻烦，如果用不计算导数的迭来很多不便，而且还可能十分麻烦，如果用不计算导数的迭代方法，往往只有线性收敛的速度。本节介绍的弦截法便是代方法，往往只有线性收敛的速度。本节介绍的弦截法便是一种不必进行导数运算的求根方法。弦截法在迭代过程中不一种不必进行导数运算的求根方法。弦截法在迭代过程中不仅用到前一步仅用到前一步 处的函数值，而且还使用处的函数值，而且还使用 处的函数值处的函数值来构造迭代函数，这样做能提高迭代的收敛速度。来构造迭代函数，这样做能提高迭代的收敛速度。)(kxf )(xf)(kxfkx1kxSchool o

54、f Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 2.5.1 弦截法的基本思想弦截法的基本思想 为避免计算函数的导数为避免计算函数的导数 ，使用差商，使用差商 替代牛顿公式中的导数替代牛顿公式中的导数 ,便得到迭代公式便得到迭代公式 称为弦截迭代公式，称为弦截迭代公式， 相应的迭代法称为弦截法相应的迭代法称为弦截法。)()()(11kkkkxxxfxf)(kxf )()()()(111kkkkkkkxxxfxfxfxx),2, 1(k)(kxf School of Automation Engineering自自 动动 化化 工工 程程 学学 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt2.5.2 弦截法几何意义弦截法几何意义 弦截法也称割线法弦截法也称割线法,其几何意义是用过曲线上两其几何意义是用过曲线上两点点 、 的割线来代替曲线的割线来代