数值分析-非线性方程的数值解法课件.pptx

1、Tel： 86613747E-mail： 授课授课: 68学分：学分：4 y a+1 a -50 O 50 x 50,502)(xeeayaxax记笔记记笔记 由题设知曲线的最底点由题设知曲线的最底点(0,y(0)(0,y(0)与最高点与最高点(50,y(50)(50,y(50)之间的高度差为之间的高度差为1m,1m,所以应有所以应有y(50)=y(0)+1,y(50)=y(0)+1,即即 12)(5050aeeaaxa y a+1 a -50 O 50 x 要计算电缆的长度要计算电缆的长度, ,必必须先求出上述方程中须先求出上述方程中的的a ,a ,由于它是关于由于它是关于a a的非线性方程

2、的非线性方程, ,没有现没有现成的公式可用成的公式可用,因此只能寻求其他解法因此只能寻求其他解法. . 10 xxxyxy1lgxx1lg 10 xx010 xx RTbVVap)(20)()(2RTbVVapVf本章将介绍求解这种类型方程的近本章将介绍求解这种类型方程的近似解的数值方法似解的数值方法2.1 引言引言 在科学研究和工程设计中在科学研究和工程设计中, 经常会遇到的一大类经常会遇到的一大类问题是非线性方程问题是非线性方程f(x)=0 (2.1)的求根问题，其中的求根问题，其中f(x)为非线性函数。为非线性函数。方程方程f(x)=0的根的根, 亦称为函数亦称为函数f(x)的零点的零点

3、 如果如果f(x)可以分解成可以分解成 , ,其中其中m为为正整数且正整数且 , ,则称则称x x* *是是f(x)f(x)的的m重零点重零点, ,或称或称方程方程f(x)=0的的m重根。当重根。当m=1时称时称x x* *为单根。若为单根。若f(x)存在存在m阶导数阶导数, ,则是方程则是方程f(x)的的m重根重根( (m1) 当且仅当当且仅当)()()(*xgxxxfm0)(*xg0)(,0)()()(*)(*)1(*xfxfxfxfmm记笔记记笔记 当当f(x)f(x)不是不是x x的线性函数时，称对应的函数方程的线性函数时，称对应的函数方程为非线性方程。如果为非线性方程。如果f(x)f

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

5、解法 记笔记记笔记 远在公元前远在公元前1700年的古巴比伦人就已有关于一、年的古巴比伦人就已有关于一、二次方程的解法。九章算术二次方程的解法。九章算术(公元前公元前50100年年)其中其中“方程术方程术”有联立一次方程组的一般解法。有联立一次方程组的一般解法。1535年意大利数学家坦特格里亚年意大利数学家坦特格里亚(TorTaglia)发发现了三次方程的解法，卡当现了三次方程的解法，卡当(HCardano)从他那从他那里得到了这种解法，于里得到了这种解法，于1545年在其名著大法年在其名著大法中公布了三次方程的公式解，称为卡当算法。中公布了三次方程的公式解，称为卡当算法。后来卡当的学生弗瑞里

6、后来卡当的学生弗瑞里(Ferrari)又提出了四次方又提出了四次方程的解法。此成果更激发了数学家们的情绪，但程的解法。此成果更激发了数学家们的情绪，但在以后的二个世纪中，求索工作始终没有成效，在以后的二个世纪中，求索工作始终没有成效，导致人们对高次代数方程解的存在性产生了怀疑。导致人们对高次代数方程解的存在性产生了怀疑。1799年，高斯证明了代数方程必有一个实根或复年，高斯证明了代数方程必有一个实根或复根的定理，称此为代数基本定理，并由此可以立根的定理，称此为代数基本定理，并由此可以立刻推理刻推理n次代数方程必有次代数方程必有n个实根或复根。个实根或复根。但在以后的几十年中仍然没有找出高次代数

7、方程但在以后的几十年中仍然没有找出高次代数方程的公式解。一直到的公式解。一直到18世纪，法国数学家拉格朗日世纪，法国数学家拉格朗日用根置换方法统一了二、三、四方程的解法。用根置换方法统一了二、三、四方程的解法。但求解五次方程时未能如愿但求解五次方程时未能如愿,开始意识到有潜藏其开始意识到有潜藏其中的奥妙中的奥妙, 用现代术语表示就是置换群理论问题。用现代术语表示就是置换群理论问题。在继续探索在继续探索5次以上方程解的艰难历程中，第一个次以上方程解的艰难历程中，第一个重大突破的是挪威数学家阿贝尔重大突破的是挪威数学家阿贝尔(NAbel1802-1829) 1824年阿贝尔发表了年阿贝尔发表了“五

8、次方程代数解法五次方程代数解法不可能存在不可能存在”的论文，但并未受到重视，连数学的论文，但并未受到重视，连数学大师高斯也未理解这项成果的重要意义。大师高斯也未理解这项成果的重要意义。1828年年17岁的法国数学家伽罗华岁的法国数学家伽罗华(EGalois 1811-1832)写出了划时代的论文写出了划时代的论文“关于五次方程关于五次方程的代数解法问题的代数解法问题”，指出即使在公式中容许用，指出即使在公式中容许用n次次方根，并用类似算法求五次或更高次代数方程的根方根，并用类似算法求五次或更高次代数方程的根是不可能的是不可能的文章呈交法兰西科学院后，因辈份太低遭到冷遇，文章呈交法兰西科学院后，

9、因辈份太低遭到冷遇，且文稿丢失。且文稿丢失。1830年伽罗华再进科学院递稿，得年伽罗华再进科学院递稿，得到泊松院士的判词到泊松院士的判词“完全不能理解完全不能理解”。后来伽罗华命运不佳，投考名校巴黎工科大学落榜，后来伽罗华命运不佳，投考名校巴黎工科大学落榜，屈就高等师院，并卷入政事两次入狱，被开除学籍，屈就高等师院，并卷入政事两次入狱，被开除学籍，又决斗受伤，死于又决斗受伤，死于1832年。决斗前，他把关于五年。决斗前，他把关于五次代数求解的研究成果写成长信，留了下来。次代数求解的研究成果写成长信，留了下来。十四年后，法国数学家刘维尔十四年后，法国数学家刘维尔(JLiouville)整理整理并

10、发表了伽罗华的遗作，人们才意识到这项近代并发表了伽罗华的遗作，人们才意识到这项近代数学发展史上的重要成果的宝贵。数学发展史上的重要成果的宝贵。38年后，即年后，即1870年，法国数学家若当年，法国数学家若当(CJordan)在专著论置换与代数方程中阐发在专著论置换与代数方程中阐发了伽罗华的思想，一门现代数学的分支了伽罗华的思想，一门现代数学的分支群论诞群论诞生了。生了。在前几个世纪中，曾开发出一些求解代数方程的在前几个世纪中，曾开发出一些求解代数方程的有效算法，它们构成了数值分析中的古典算法。有效算法，它们构成了数值分析中的古典算法。至于超越方程则不存在一般的求根方式。至于超越方程则不存在一般

11、的求根方式。本章介绍方程的迭代解法，它既可以用本章介绍方程的迭代解法，它既可以用来求解代数方程，也可以用来解超越方来求解代数方程，也可以用来解超越方程，并且仅限于求方程的实根。程，并且仅限于求方程的实根。运用迭代法求解方程的根应解决以下两运用迭代法求解方程的根应解决以下两个问题：个问题：n确定根的初值确定根的初值;n将进一步精确化到所需要的精度。将进一步精确化到所需要的精度。记笔记记笔记2.2 二分法二分法 二分法又称二分区间法二分法又称二分区间法, ,是求解方程是求解方程(2.1)(2.1)的近的近似根的一种常用的简单方法。似根的一种常用的简单方法。 设函数设函数f(x)f(x)在闭区间在闭

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

13、至有根区间足够地小直至有根区间足够地小, , 便可求出满足精度便可求出满足精度要求的近似根。要求的近似根。2.1.1确定有根区间的方法确定有根区间的方法 为了确定根的初值，首先必须圈定根所在的范围，为了确定根的初值，首先必须圈定根所在的范围， 称为称为圈定根或根的隔离圈定根或根的隔离。 在上述基础上，采取适当的数值方法确定具有一定在上述基础上，采取适当的数值方法确定具有一定 精度要求的初值。精度要求的初值。 对于代数方程，其根的个数（实或复的）与其次数对于代数方程，其根的个数（实或复的）与其次数 相同。至于超越方程，其根可能是一个、几个或无相同。至于超越方程，其根可能是一个、几个或无 解，并没

14、有什么固定的圈根方法解，并没有什么固定的圈根方法 求方程根的问题，就几何上讲求方程根的问题，就几何上讲,是求曲线是求曲线 y=f (x)与与 x轴交点的横坐标。轴交点的横坐标。 由高等数学知识知由高等数学知识知, 设设f (x)为区间为区间a,b上的单上的单值连续值连续, 如果如果f (a)f (b)0 , 则则a,b中至少有一个中至少有一个实根。如果实根。如果f (x)在在a,b上还是单调地递增或递减，上还是单调地递增或递减，则仅有一个实根。则仅有一个实根。记笔记记笔记n由此可大体确定根所在子区间，方法有：由此可大体确定根所在子区间，方法有： (1) 画图法画图法 (2) 逐步搜索法逐步搜索

15、法y=f(x)abyx(1) 画图法画图法 画出画出y = f (x)的略图，从而看出曲线与的略图，从而看出曲线与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内内(1) 画图法画图法xy1gxy

16、023yxn对于某些看不清根的函数，可以扩大一下曲线对于某些看不清根的函数，可以扩大一下曲线y0 xy=f(x)y=kf(x)记笔记记笔记y0 xABa1b1a2b2(2) 逐步搜索法逐步搜索法(2) (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的函数值异号的函数值异号, ,则得到则得到一个缩小的有根子

17、区间一个缩小的有根子区间xi-1, ,xi。例例1 1 方程方程f(x)=xf(x)=x3 3-x-1=0 -x-1=0 确定其有根区间确定其有根区间解：用试凑的方法，不难发现解：用试凑的方法，不难发现 f(0)0f(0)0 在区间（在区间（0 0，2 2）内至少有一个实根）内至少有一个实根 设从设从x=0 x=0出发出发, ,取取h=0.5h=0.5为步长向右进行根的为步长向右进行根的 搜索搜索, ,列表如下列表如下x xf(x)f(x)0 0.5 1.0 1.5 20 0.5 1.0 1.5 2 + + + +可以看出，在可以看出，在1.01.0,1.5,1.5内必有一根内必有一根 用逐步

18、搜索法进行实根隔离的关键是选取步长用逐步搜索法进行实根隔离的关键是选取步长h 要选择适当要选择适当h ，使之既能把根隔离开来，工作量，使之既能把根隔离开来，工作量 又不太大。又不太大。 为获取指定精度要求的初值为获取指定精度要求的初值, ,可在以上隔离根的可在以上隔离根的 基础上采用对分法继续缩小该含根子区间基础上采用对分法继续缩小该含根子区间 二分法可以看作是搜索法的一种改进。二分法可以看作是搜索法的一种改进。 取有根区间取有根区间a,b之中点之中点, 将它分为两半将它分为两半,分点分点 ,这样就可缩小有根区间这样就可缩小有根区间2.2.2 二分法求根过程二分法求根过程 设方程设方程f(x)

19、=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 a2 b2 a2 b2 对压缩了的有根区间对压缩了的有根区间 施行同样的手法施行同样的手法, , 即取中点即取中点 , ,将区间将区间 再分为两半再分为两半, ,然然 后再确定有根区间后再确定有根区间 , ,其长度是其长度是 的的 二分之一二分之一 如此反复下去如此反复下去, ,若不出现若不出现 , ,即可得出一即可得出一

20、系列有根区间序列：系列有根区间序列： 上述每个区间都是前一个区间的一半上述每个区间都是前一个区间的一半, ,因此因此 的长度的长度11,ba2111bax11,ba22,ba11,ba0)(kxfkkbabababa,2211kkba ,)(21)(2111abababkkkkk 当当k时趋于零时趋于零, ,这些区间最终收敛于一点这些区间最终收敛于一点x x* * 即为即为 所求的根所求的根 。每次二分后每次二分后, ,取有根区间取有根区间 的中点的中点作为根的近似值，得到一个近似根的序列作为根的近似值，得到一个近似根的序列 该序列以根该序列以根x x* *为极限为极限 只要二分足够多次只要二

21、分足够多次( (即即k足够大足够大),),便有便有这里这里为给定精度为给定精度, ,由于由于 , ,则则 11122kkkkkababab1*22kkkkababxxkkba ,)(21kkkbax,210kxxxxkxx*kkbax,*当给定精度当给定精度0 0后后, ,要想要想 成立成立, ,只要只要取取k满足满足 即可，亦即当即可，亦即当: kxx*)(211abk12lglg)lg(abk时时, ,做到第做到第k+1次二分次二分, ,计算得到的计算得到的 就是就是满足精度要求的近似根满足精度要求的近似根 。 在程序中通常用相邻的在程序中通常用相邻的 与与 的差的绝的差的绝对值或对值或

22、与与 的差的绝对值是否小于的差的绝对值是否小于来来决定二分区间的次数。决定二分区间的次数。 kxkx1kxkakb y n 开 始 输 入 a , b, (a+b)/2 x f(a) f(x )0 ? xb x a |b-a|0 输 出 x 结 束 y n 二分法算法实现二分法算法实现例例 求求方程方程f( (x)=)=x3 3- -x-1=0 -1=0 在区间在区间1.0,1.5,1.5内内 的一的一 个实根个实根, 使误差不超过使误差不超过0.510-2。P19例例 证明方程证明方程 在区间在区间2, 3内有一个根内有一个根 , 使用二分法求误差不超过使用二分法求误差不超过0.510-3

23、的根要二的根要二 分多少次？分多少次？证明证明 令令 0523 xx52)(3xxxf016)3(, 01)2(ff且且f(x)f(x)在在2, 3上连续上连续, ,故方程故方程f(x)=0f(x)=0在在2,32,3内至少内至少有一个根。又有一个根。又 当时当时时，时， , ,故故f(x)f(x)在在2, 32, 3上是单调递增函数上是单调递增函数, ,从而从而f(x)f(x)在在2, 32, 3上有且仅有一根。上有且仅有一根。23)(2xxf3 , 2x0)( xf 给定误差限给定误差限 0.510-3 , ,使用二分法时使用二分法时 误差限为误差限为 只要取只要取k满足满足 )(211*

24、abxxkk311021)(21 abk即可，亦即即可，亦即 3102 k97.92110lg3gk所以需二分所以需二分1010次便可达到要求。次便可达到要求。 二分法的优点是不管有根区间二分法的优点是不管有根区间 多大多大, ,总总能求出满足精度要求的根能求出满足精度要求的根, ,且对函数且对函数f(x)f(x)的要求不高的要求不高, ,只要连续即可只要连续即可, ,计算亦简单计算亦简单; ;它的局限性是只能用于它的局限性是只能用于求函数的实根求函数的实根, ,不能用于求复根及重根不能用于求复根及重根, ,它的收敛速它的收敛速度与比值为度与比值为 的等比级数相同。的等比级数相同。 ba ,2

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

26、2.3) (2.3)其中其中 为为x x的连续函数的连续函数)(x)(xx2.3 迭代法迭代法即如果数即如果数 使使f(x)=0, 则也有则也有 , 反之反之, 若若 , 则也有则也有 , 称称 为迭代函数为迭代函数 任任取一个初值取一个初值 , 代入式代入式 的右端的右端, 得到得到 *x)(*xx)(*xx0)(*xf)(x0 x)(xx)(01xx再将再将 代入式代入式 的右端的右端, 得到得到 ,依此类推依此类推, 得到一个数列得到一个数列 ， 其一般表示其一般表示 1x)(xx)(12xx)(23xx), 2 , 1 , 0()(1kxxkk式式(2.4)(2.4)称为求解非线性方程

27、的称为求解非线性方程的简单迭代法简单迭代法。 (2.4)(2.4)如果由迭代格式如果由迭代格式 产生的序列产生的序列 收敛收敛, ,即即 nx)(1kkxx*limxxnn则称迭代法收敛。则称迭代法收敛。 实际计算中当然不可能也没必要无穷多步地做实际计算中当然不可能也没必要无穷多步地做下去下去, , 对预先给定的精度要求对预先给定的精度要求，只要某个只要某个k k满足满足1kkxx即可结束计算并取即可结束计算并取 kxx* 当然，迭代函数当然，迭代函数 的构造方法是多种多样的。的构造方法是多种多样的。)( x例例4 用迭代法求方程用迭代法求方程 在在x=1.5附近的一个根附近的一个根解解 将方

28、程改写成如下两种等价形式将方程改写成如下两种等价形式 013 xx1)(1)(3231xxxxxx相应地可得到两个迭代公式相应地可得到两个迭代公式1)(1)(321311kkkkkkxxxxxx如果取初始值如果取初始值 1.51.5，用上述两个迭代公，用上述两个迭代公式分别迭代，计算结果见式分别迭代，计算结果见P P2121 0 x2.3.2 迭代法的几何意义迭代法的几何意义 通常将方程通常将方程f(x)=0f(x)=0化为与它同解的方程化为与它同解的方程的方法不止一种的方法不止一种, ,有的收敛有的收敛, ,有的不收敛有的不收敛, ,这取决于这取决于 的性态的性态, ,方程方程 的求根问题在

29、几何上就是确定曲的求根问题在几何上就是确定曲线线y= 与直线与直线y=x的交点的交点P*的横坐标的横坐标( (图图2-3所示所示) ) )(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) 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* 图图2-3 迭代法的几何意义迭代法的几何意义 2.3.3 迭代法

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

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

32、于是介于x*和和 之间的点之间的点 从而有从而有a,b，进进而有而有 由条件由条件(2)有有 1, 所所以以 - =0，即，即 = ，解唯一。，解唯一。证证: 构造函数构造函数 ,由条件对任意的由条件对任意的xa, b a, b有有xxx)()(0)()(0)()(bbbaaa)(x*x0)()(*xxx*xx*xx)(*xx)(xx)()()(*xxxxxxx0)(1)(*xx)(x*xx*xx按迭代过程按迭代过程 ,有有 )(1kkxx)()()(1*1*kkkxxxxxx1*1*)(kkkxxLxxxx0*2*21*xxLxxLxxLxxkkkk 由于由于L1,L1,所以有所以有 , ,

33、可见可见L L越小越小, ,收敛越快收敛越快 *limxxkk再证误差估计式再证误差估计式 1*1kkkxxLLxx01*1xxLLxxkk 1*1*kkkkkxxxxLxxLxx)(1*kkkxxxxL1*)1 (kkkxxLxxL1*1kkkxxLLxx 即即 得证。得证。 2121211)()()(kkkkkkkkxxLxxxxxx012121*1111xxLLxxLLxxLxxkkkkkk即即 得证。得证。 10)(xx 开 始 输 入 x0,N 1 kk+ 1 k x1 x0 输 出 近 似 根 x1 |x1- x0|? 输 出 迭 代 失 败 标 志 结 束 n k0c0），），使

34、使 )(1kkxx)(xx*xkkxxe*ceepkkk1lim则称序列则称序列 是是 p 阶收敛的阶收敛的, ,c称渐近误差常数。称渐近误差常数。特别地特别地, ,p=1=1时称为线性收敛时称为线性收敛, ,p=2=2时称为平方收时称为平方收敛。敛。1 1 p 2 0 xn+1X*ayx0Bf(x)0a=x0yx0B=x0f(x)0ayx0Bf(x)0a =x0 2.4.3 牛顿迭代法的收敛性牛顿迭代法的收敛性 牛顿迭代法对初值牛顿迭代法对初值x0的选取要求比较高。的选取要求比较高。 x0必必须充分靠近须充分靠近x*才能保证局部收敛。才能保证局部收敛。定理定理2.5 如果在有根区间如果在有根

35、区间a,b上上连续且不变号，在连续且不变号，在a,b上取初始近似根上取初始近似根x0满足，满足，则牛顿迭代法产生的迭代序列单调收敛于方程则牛顿迭代法产生的迭代序列单调收敛于方程f(x)=0在该区间上的唯一解。在该区间上的唯一解。证明证明 （ 略略 ）)(, 0)(, 0)()(xfxfbfaf 0)()(00 xfxfyx10 x0X*0 x0X*x2 不满足迭代条件时，可能导致迭代值远离不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况根的情况而找不到根或死循环的情况2.4.3 牛顿迭代法的收敛性牛顿迭代法的收敛性 ?0)(0 xf 1000)()(xxfxfx ?01 x

36、x 开 始 输 入 x0,N 1 k k+ 1 k x1 x0 输 出 x1 输 出 迭 代 失 败 标 志 结 束 n k N ? n n y 输 出 奇 异 标 志 y y 2. .4. .4 牛顿迭代法的算法实现牛顿迭代法的算法实现例例2.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.567142. .4. .5 牛顿下山法牛顿

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

38、。把这一算法称为牛顿下山法。即满足这项要求的算法称下山法。满足这项要求的算法称下山法。)()(1kkkkxfxfxx其中其中(01)(01)为下山因子为下山因子 下山因子的选择是个逐步探索的过程，设从下山因子的选择是个逐步探索的过程，设从=1开始反复将开始反复将减半进行试算减半进行试算, 即逐次取即逐次取为为从中挑选下山因子，直至找到其中某个从中挑选下山因子，直至找到其中某个使单调性使单调性条件条件成立，则称成立，则称“下山成功下山成功”，否则，否则“下山失败下山失败”，这时需另选初值重算。这时需另选初值重算。,21,21,12)()(1kkxfxf2.5 弦截法弦截法 牛顿迭代法虽然具有收敛

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

40、收值来构造迭代函数，这样做能提高迭代的收敛速度。敛速度。)(kxf )(xf)(kxfkx1kx 2.5.1 弦截法的基本思想弦截法的基本思想 为避免计算函数的导数为避免计算函数的导数 ，使用差商，使用差商 替代牛顿公式中的导数替代牛顿公式中的导数 ,便得到迭代公式便得到迭代公式 称为弦截迭代公式，称为弦截迭代公式， 相应的迭代法称为弦截法相应的迭代法称为弦截法。)()()(11kkkkxxxfxf)(kxf )()()()(111kkkkkkkxxxfxfxfxx),2, 1(k)(kxf 2.5.2 弦截法几何意义弦截法几何意义弦截法也称割线法弦截法也称割线法, ,其几何意义是用过曲线上两

41、其几何意义是用过曲线上两点点 、 的割线来代替曲线的割线来代替曲线, ,用割用割线与线与x轴交点的横座标作为方程的近似根轴交点的横座标作为方程的近似根 再过再过P1点和点点和点 作割线求出作割线求出 , ,再再过过P2点和点点和点 作割线求出作割线求出 , ,余余此类推，当收敛时此类推，当收敛时可求出满足精度要可求出满足精度要求的求的 P1 y=f(x) x0 x2 x3 x1 x* P3 P0 P2 )(,(000 xfxP)(,(111xfxP2x)(,(222xfxP3x)(,(333xfxP4xkx 可以证明，弦截法具有超线性收敛，收敛可以证明，弦截法具有超线性收敛，收敛的阶约为的阶约

42、为1.618，它与前面介绍的一般迭代法，它与前面介绍的一般迭代法一样都是线性化方法，但也有区别。即一般迭一样都是线性化方法，但也有区别。即一般迭代法在计算代法在计算 时只用到前一步的值时只用到前一步的值 ，故称，故称之为单点迭代法；而弦截法在求之为单点迭代法；而弦截法在求 时要用到前时要用到前两步的结果两步的结果 和和 ，使用这种方法必须给出，使用这种方法必须给出两个初始近似根两个初始近似根 ，这种方法称为多点迭，这种方法称为多点迭代法代法。 1kxkx1kx1kxkx10,xx例例2.12 用弦截法求方程用弦截法求方程 在在 初始初始 值邻近的一个根。要求值邻近的一个根。要求解：取解：取 ,

43、 , 令令 利用弦截迭代公式利用弦截迭代公式 计算结果见计算结果见P34列表，列表， 易见取近似根易见取近似根 则可满足精度要求。则可满足精度要求。xex5 . 00 x0001. 01kkxx5 . 00 x6.01xxexxf)()()()()(1111kkxxkkxkkkxxeexxexxxkkk56714. 04x2. .5. .3 弦截法算法实现弦截法算法实现 ?0)(0 xf ?0)(1xf ?0)()(01xfxf 2010111)()()()(xxxxfxfxfx ?12 xx 输 入 x0, x1,N 1 k k+ 1 k x1 x0 x2 x1 f(x1)f(x0) f(x

44、2) f(x1) 输 出 x2 输 出 迭 代 失 败 标 志 结 束 n k N ? n n y 输 出 奇 异 标 志 y y x0 x2 x1 x2 n y y n 输 出 x2 补充补充 非线性方程组的数值解法非线性方程组的数值解法 二阶非线性方程组：二阶非线性方程组：0),(0),(21yxyxff方法：通过消元化为含有一个未知量的方程求方法：通过消元化为含有一个未知量的方程求 根问题，然后用牛顿法求解根问题，然后用牛顿法求解例：求解下列非方程组例：求解下列非方程组0) 13() 1(),(05),(2221xyxyxyxfyxfNewton法解方程组例法解方程组例由由 得得y=(3

45、x+1)/(x+1) 将代入得将代入得f(x)=x2+(3x+1)2/ (x+1)2-5=0 化简得化简得f(x)=4x4+ 2x3 +5x2-4x-4=0 然后用牛顿迭代法求出然后用牛顿迭代法求出x的近似值作为的近似值作为x*, 并并将将x*代入或后，再用牛顿迭代法求出代入或后，再用牛顿迭代法求出y的的近似值作为近似值作为y* 即可。即可。0) 13() 1(),(05),(2221xyxyxyxfyxf例例2.12 求求 052),(032),(22yxyxvyxyx 在在(x0,y0)=(-1,2)附近解附近解方法：通过消元化为含有一个未知量的方程求方法：通过消元化为含有一个未知量的方程

46、求根问题，然后用牛顿法求解根问题，然后用牛顿法求解解：由解：由得得x=3-2yx=3-2y并代入整理得：并代入整理得： 2 2（3-23-2y)y)2 2 y y2 2 5=05=0 7y 7y2 2 12y+13=012y+13=0 f(y)= 7y f(y)= 7y2 2 12y+13 f12y+13 f (y)=14y(y)=14y 1212 , 1 , 0,12141312721kyyyyykkkkky 0.74x 1.52例例2.12 求求 0sin2),(0cos2),(xyyxvyxyxkkkkkkyyyyyyyyyfyyyfyyyxvyxsin)cos21cos(212)cos

47、21sin(2sin21)cos21cos(2)(0)cos21sin(2)(0)cos21sin(2),(2,cos2111）代入（）得由（ 非线性方程的解通常叫做方程的根非线性方程的解通常叫做方程的根, ,也叫做函数也叫做函数的零点的零点, ,本章讨论了求解非线性方程近似根常用的一些本章讨论了求解非线性方程近似根常用的一些数值方法。先要确定有根区间数值方法。先要确定有根区间, ,且对于收敛的迭代格式且对于收敛的迭代格式, ,这个区间要足够小。针对各种求根的数值方法的特点这个区间要足够小。针对各种求根的数值方法的特点, ,要考虑其收敛性、收敛速度和计算量。要考虑其收敛性、收敛速度和计算量。 二分法是逐步将含根区间分半二分法是逐步将含根区间分半, ,主要用来求实根主要用来求实根; ;迭代法是一种逐次逼近的方法迭代法是一种逐次逼近的方法, ,起着把根的精确值一步起着把根的精确值一步一步算出来的作用一步算出来的作用; ;牛顿法具有较快的收敛速度牛顿法具有较快的收敛速度, ,但对但对初值选取要求较高。弦截法避开了导数的计算初值选取要求较高。弦截法避开了导数的计算, ,具有超具有超线性的收敛速度线性的收敛速度, ,每计算一步每计算一步, ,要用到前面两步的信息。要用到前面两步的信息。 本章小结本章小结