数值分析－非线性方程的数值解法.pptx

《数值分析－非线性方程的数值解法.pptx》由会员分享，可在线阅读，更多相关《数值分析－非线性方程的数值解法.pptx（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章非线性方程的数值解法非线性方程的数值解法 引例引例在相距在相距100m的两座建筑物的两座建筑物(高度相等的点高度相等的点)之间悬挂一根电缆，仅允许电缆在中间最多下之间悬挂一根电缆，仅允许电缆在中间最多下垂垂1m，试计算所需电缆的长度试计算所需电缆的长度(如图所示如图所示)。由于空中电缆的曲线是由于空中电缆的曲线是悬链线悬链线,建立如图所示的建立如图所示的坐标系后坐标系后,悬链线方程为悬链线方程为第1页/共78页记笔记第二章第二章非线性方程的数值解法非线性方程的数值解法 由题设知曲线的最底点由题设知曲线的最底点(0,y(0)(0,y(0)与最高点与最高点(50,y(50)(50,y(

2、50)之间的高度差为之间的高度差为1m,1m,所以应有所以应有y(50)=y(0)+1,y(50)=y(0)+1,即即 要计算电缆的长度要计算电缆的长度,必必须先求出上述方程中须先求出上述方程中的的a,a,由于它是关于由于它是关于a a的非线性方程的非线性方程,没有现成没有现成的公式可用的公式可用,因此只能寻求其他解法因此只能寻求其他解法.第2页/共78页第二章第二章非线性方程的数值解法非线性方程的数值解法 再如求解方程再如求解方程的近似根的近似根方法方法1:将方程同解变换成将方程同解变换成然后画两条曲线然后画两条曲线这两条曲线的交点的横座标大致为这两条曲线的交点的横座标大致为x=2.5第3页

3、/共78页第二章第二章非线性方程的数值解法非线性方程的数值解法 再如求解方程再如求解方程的近似根的近似根方法方法2:原方程可变换为原方程可变换为根据高等数学知识根据高等数学知识(零点定理零点定理)知知,设函数设函数f(x)在闭区间在闭区间a,b上连续上连续,且且f(a)与与f(b)异号异号,在在(a,b)内至少存在一点内至少存在一点,使使f()=0而而f(2)f(3)1)当且仅当当且仅当第6页/共78页记笔记第二章第二章非线性方程的数值解法非线性方程的数值解法 当当f(x)f(x)不是不是x x的线性函数时，称对应的函数方程的线性函数时，称对应的函数方程为非线性方程。如果为非线性方程。如果f(

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

5、程的数值解法非线性方程的数值解法 通常方程根的数值解法大致分为三个步骤进行通常方程根的数值解法大致分为三个步骤进行判定根的存在性。即方程有没有根？如果有判定根的存在性。即方程有没有根？如果有根，有几个根？根，有几个根？确定根的分布范围。即将每一个根用区间隔确定根的分布范围。即将每一个根用区间隔离开来，这个过程实际上是获得方程各根的离开来，这个过程实际上是获得方程各根的初始近似值。初始近似值。根的精确化。将根的初始近似值按某种方法根的精确化。将根的初始近似值按某种方法逐步精确化，直到满足预先要求的精度为止逐步精确化，直到满足预先要求的精度为止第8页/共78页远在公元前远在公元前1700年的古巴比

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

7、四次方程的解法。此成果更激发了数学家们的情绪，方程的解法。此成果更激发了数学家们的情绪，但在以后的二个世纪中，求索工作始终没有成效，但在以后的二个世纪中，求索工作始终没有成效，导致人们对高次代数方程解的存在性产生了怀疑。导致人们对高次代数方程解的存在性产生了怀疑。第二章第二章非线性方程的数值解法非线性方程的数值解法第9页/共78页1799年，高斯证明了代数方程必有一个实根或年，高斯证明了代数方程必有一个实根或复根的定理，称此为代数基本定理，并由此可以复根的定理，称此为代数基本定理，并由此可以立刻推理立刻推理n次代数方程必有次代数方程必有n个实根或复根。个实根或复根。但在以后的几十年中仍然没有找

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

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

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

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

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

13、一种常用的简单方法。设函数设函数f(x)f(x)在闭区间在闭区间 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)的符号的符号,逐步将有根区间缩逐步将有根区间缩小小,直至有

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

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

16、第16页/共78页(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内内第17页/共78页(1)画图法画图法023yx第18页/共78页n对于某些

17、看不清根的函数，可以扩大一下曲线对于某些看不清根的函数，可以扩大一下曲线y0 xy=f(x)y=kf(x)(1)(1)画图法画图法画图法画图法记笔记第19页/共78页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的函数值异号的函数值异号,则得到一个缩小则得到一个缩小的有根子区间的有根子区

18、间xi-1,xi。第20页/共78页例例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内必有一根内必有一根第21页/共78页 用逐步搜索法进行

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

20、,b内内有有根根,二二分分法法就就是是逐逐步收缩有根区间，最后得出所求的根。步收缩有根区间，最后得出所求的根。具体过程如下具体过程如下第23页/共78页 对压缩了的有根区间对压缩了的有根区间 施行同样的手法施行同样的手法,即取中点即取中点 ,将区间将区间 再分为两半再分为两半,然然 后再确定有根区间后再确定有根区间 ,其长度是其长度是 的的 二分之一二分之一 如此反复下去如此反复下去,若不出现若不出现 ,即可得出一即可得出一 系列有根区间序列：系列有根区间序列：上述每个区间都是前一个区间的一半上述每个区间都是前一个区间的一半,因此因此 的长度的长度 当当k时趋于零时趋于零,这些区间最终收敛于一

21、点这些区间最终收敛于一点x x*即为即为 所求的根所求的根。第24页/共78页每次二分后每次二分后,取有根区间取有根区间 的中点的中点作为根的近似值，得到一个近似根的序列作为根的近似值，得到一个近似根的序列 该序列以根该序列以根x x*为极限为极限 只要二分足够多次只要二分足够多次(即即k足够大足够大),),便有便有这里这里为给定精度为给定精度,由于由于 ,则则 第25页/共78页当给定精度当给定精度0 0后后,要想要想 成立成立,只要只要取取k满足满足 即可，亦即当即可，亦即当:时时,做到第做到第k+1次二分次二分,计算得到的计算得到的 就是满就是满足精度要求的近似根足精度要求的近似根。在程

22、序中通常用相邻的在程序中通常用相邻的 与与 的差的绝的差的绝对值或对值或 与与 的差的绝对值是否小于的差的绝对值是否小于来来决定二分区间的次数。决定二分区间的次数。第26页/共78页二二分分法法算算法法实实现现第27页/共78页例例求求方程方程f(x)=)=x3 3-x-1=0 -1=0 在区间在区间1.0,1.5,1.5内内 的一的一 个实根个实根,使误差不超过使误差不超过0.510-2。P19例例 证明方程证明方程 在区间在区间2,3内有一个内有一个根根 ,使用二分法求误差不超过使用二分法求误差不超过0.510-3 的根要二的根要二 分多少次？分多少次？证明证明 令令 且且f(x)f(x)

23、在在2,3上连续上连续,故方程故方程f(x)=0f(x)=0在2,32,3内至少内至少有一个根。又有一个根。又 当时当时时，时，,故故f(x)f(x)在在2,32,3上是单调递增函数上是单调递增函数,从而从而f(x)f(x)在在2,32,3上有且仅有一根。上有且仅有一根。给定误差限给定误差限 0.510-3,使用二分法时使用二分法时第28页/共78页 误差限为误差限为 只要取只要取k满足满足即可，亦即即可，亦即 所以需二分所以需二分1010次便可达到要求。次便可达到要求。二分法的优点是不管有根区间二分法的优点是不管有根区间 多大多大,总总能求出满足精度要求的根能求出满足精度要求的根,且对函数且

24、对函数f(x)f(x)的要求不高的要求不高,只要连续即可只要连续即可,计算亦简单计算亦简单;它的局限性是只能用于它的局限性是只能用于求函数的实根求函数的实根,不能用于求复根及重根不能用于求复根及重根,它的收敛速它的收敛速度与比值为度与比值为 的等比级数相同。的等比级数相同。第29页/共78页2.3 迭代法迭代法 对于一般的非线性方程对于一般的非线性方程,没有通常所说的求根没有通常所说的求根公式求其精确解公式求其精确解,需要设计近似求解方法需要设计近似求解方法,即迭代法。即迭代法。它是一种逐次逼近的方法它是一种逐次逼近的方法,用某个固定公式反复校正用某个固定公式反复校正根的近似值根的近似值,使之

25、逐步精确化，最后得到满足精度要使之逐步精确化，最后得到满足精度要求的结果。求的结果。为求解非线性方程为求解非线性方程f(x)=0f(x)=0的根，先将其写成便于的根，先将其写成便于迭代的等价方程迭代的等价方程 (2.3)(2.3)其中其中 为为x x的连续函数的连续函数第30页/共78页2.3 迭代法迭代法即如果数即如果数 使使f(x)=0,则也有则也有 ,反之反之,若若 ,则也有则也有 ,称称 为迭代函数为迭代函数 任任取一个初值取一个初值 ,代入式代入式 的右端的右端,得到得到 再将再将 代入式代入式 的右端的右端,得到得到 ,依此类推依此类推,得到一个数列得到一个数列 ，其一般表示其一般

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

27、 将方程改写成如下两种等价形式将方程改写成如下两种等价形式 相应地可得到两个迭代公式相应地可得到两个迭代公式如果取初始值如果取初始值 1.51.5，用上述两个迭代公，用上述两个迭代公式分别迭代，计算结果见式分别迭代，计算结果见P P2121 第33页/共78页2.3.2迭代法的几何意义迭代法的几何意义 通常将方程通常将方程f(x)=0f(x)=0化为与它同解的方程化为与它同解的方程的方法不止一种的方法不止一种,有的收敛有的收敛,有的不收敛有的不收敛,这取决于这取决于 的性态的性态,方程方程 的求根问题在几何上就是确定曲的求根问题在几何上就是确定曲线线y=与直线与直线y=x的交点的交点P*的横坐

28、标的横坐标(图图2-3所示所示)(a)(b)第34页/共78页图图2-3迭代法的几何意义迭代法的几何意义 第35页/共78页2.3.3迭代法收敛的条件迭代法收敛的条件 对方程对方程f(x)=0可以构造不同的迭代公式可以构造不同的迭代公式,但迭代公式但迭代公式并非总是收敛。那么并非总是收敛。那么,当迭代函数当迭代函数 满足什满足什么条件时，相应的迭代公式才收敛呢？即使迭么条件时，相应的迭代公式才收敛呢？即使迭代收敛时，我们也不可能迭代很多次，而是迭代收敛时，我们也不可能迭代很多次，而是迭代有限次后就停止，这就需要估计迭代值的误代有限次后就停止，这就需要估计迭代值的误差，以便适时终止迭代差，以便适

29、时终止迭代第36页/共78页定理定理2.1设函数设函数 在在a,b上具有连续的一阶导上具有连续的一阶导 数数,且满足且满足（1）对所有的）对所有的xa,b有有a,b（2）存在存在0L1,使所有的使所有的xa,b有有L则方程则方程 在在a,b上的解上的解 存在且唯一存在且唯一，对任意的，对任意的 a,b，迭代过程迭代过程均收敛于均收敛于 。并有误差估计式。并有误差估计式 第37页/共78页由连续函数介值定理知由连续函数介值定理知,必有必有 a,b,使使 所以有解存在所以有解存在,即即假设有两个解假设有两个解 和和 ,a,b，则则，由微分中值定理有由微分中值定理有其中其中是介于是介于x*和和 之间

30、的点之间的点从而有从而有a,b，进进而有而有由条件由条件(2)有有 1,所以所以 -=0，即，即 =，解唯一。，解唯一。证证:构造函数构造函数 ,由条件由条件对任意的对任意的xa,b a,b有有第38页/共78页按迭代过程按迭代过程 ,有有 由于由于L1,L0c0），），使使 则称序列则称序列 是是 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 牛顿迭代法的收敛性牛顿迭代法的收

31、敛性第59页/共78页牛顿迭代法对初值牛顿迭代法对初值x0的选取要求比较高。的选取要求比较高。x0必必须充分靠近须充分靠近x*才能保证局部收敛。才能保证局部收敛。定理定理2.5如果在有根区间如果在有根区间a,b上上连续且不变号，在连续且不变号，在a,b上取初始近似根上取初始近似根x0满足，满足，则牛顿迭代法产生的迭代序列单调收敛于方程则牛顿迭代法产生的迭代序列单调收敛于方程f(x)=0在该区间上的唯一解。在该区间上的唯一解。证明证明（略略）第60页/共78页yx10 x0X*0 x0X*x2不满足迭代条件时，可能导致迭代值远离不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况

32、根的情况而找不到根或死循环的情况 牛顿迭代法的收敛性牛顿迭代法的收敛性第61页/共78页2.4.4牛牛顿顿迭迭代代法法的的算算法法实实现现第62页/共78页例例2.11 用用牛顿迭代法牛顿迭代法牛顿迭代法牛顿迭代法求求 x=e-x的根的根,=10-4解：因解：因 f(xk)=x ex 1,f(xk)=ex(x+1)建立迭代公式建立迭代公式取取x0=0.5,逐次计算得逐次计算得x1=0.57102,x2=0.56716，x3=0.56714第63页/共78页2.4.5牛顿下山法牛顿下山法 通常通常,牛顿迭代法的收敛性依赖于初始值牛顿迭代法的收敛性依赖于初始值 的选取的选取,如果如果 偏离所求的根

33、偏离所求的根 比较远比较远,则牛顿法可能发散。则牛顿法可能发散。为了防止迭代发散为了防止迭代发散,我们对牛顿迭代法的迭代过程再附我们对牛顿迭代法的迭代过程再附加一项要求加一项要求,即具有单调性即具有单调性 将牛顿迭代法与下山法结合起来使用将牛顿迭代法与下山法结合起来使用,即在下山即在下山法保证函数值下降的前提下法保证函数值下降的前提下,用牛顿迭代法加快收敛用牛顿迭代法加快收敛速度。把这一算法称为牛顿下山法。即速度。把这一算法称为牛顿下山法。即满足这项要求的算法称下山法。满足这项要求的算法称下山法。其中其中(01)(01)为下山因子为下山因子 第64页/共78页 下下山山因因子子的的选选择择是是

34、个个逐逐步步探探索索的的过过程程，设设从从=1开始反复将开始反复将减半进行试算减半进行试算,即逐次取即逐次取为为从从中中挑挑选选下下山山因因子子，直直至至找找到到其其中中某某个个使使单单调调性性条件条件成立，则称成立，则称“下山成功下山成功”，否则，否则“下山失败下山失败”，这时需另选初值重算。这时需另选初值重算。第65页/共78页2.5弦截法弦截法 牛牛顿顿迭迭代代法法虽虽然然具具有有收收敛敛速速度度快快的的优优点点，但但每每迭迭代代一一次次都都要要计计算算导导数数 ,当当 比比较较复复杂杂时时,不不仅仅每每次次计计算算 带带来来很很多多不不便便，而而且且还还可可能能十十分分麻麻烦烦，如如果

35、果用用不不计计算算导导数数的的迭迭代代方方法法，往往往往只只有有线线性性收收敛敛的的速速度度。本本节节介介绍绍的的弦弦截截法法便便是是一一种种不不必必进进行行导导数数运运算算的的求求根根方方法法。弦弦截截法法在在迭迭代代过过程程中中不不仅仅用用到到前前一一步步 处处的的函函数数值值，而而且且还还使使用用 处处的的函函数数值值来来构构造造迭迭代代函函数数，这这样样做做能能提提高高迭迭代代的的收收敛敛速度。速度。第66页/共78页弦截法的基本思想弦截法的基本思想 为避免计算函数的导数为避免计算函数的导数 ，使用差商，使用差商 替代牛顿公式中的导数替代牛顿公式中的导数 ,便得到迭代公式便得到迭代公式

36、 称为弦截迭代公式，称为弦截迭代公式，相应的迭代法称为弦截法相应的迭代法称为弦截法。第67页/共78页弦截法几何意义弦截法几何意义弦截法也称割线法弦截法也称割线法,其几何意义是用过曲线上两其几何意义是用过曲线上两点点 、的割线来代替曲线的割线来代替曲线,用割用割线与线与x轴交点的横座标作为方程的近似根轴交点的横座标作为方程的近似根 再过再过P1点和点点和点 作割线求出作割线求出 ,再再过过P2点和点点和点 作割线求出作割线求出 ,余余此类推，当收敛时此类推，当收敛时可求出满足精度要可求出满足精度要求的求的第68页/共78页 可以证明，弦截法具有超线性收敛，收敛可以证明，弦截法具有超线性收敛，收

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

38、利用弦截迭代公式利用弦截迭代公式 计算结果见计算结果见P34列表，列表，易见取近似根易见取近似根 则可满足精度要求。则可满足精度要求。第70页/共78页2.5.3 弦弦截截法法算算法法实实现现 第71页/共78页补充补充非线性方程组的数值解法非线性方程组的数值解法 二阶非线性方程组：二阶非线性方程组：方法：通过消元化为含有一个未知量的方程求方法：通过消元化为含有一个未知量的方程求根问题，然后用牛顿法求解根问题，然后用牛顿法求解例：求解下列非方程组例：求解下列非方程组第72页/共78页Newton法解方程组例法解方程组例由由得得y=(3x+1)/(x+1)将将代入代入得得f(x)=x2+(3x+

39、1)2/(x+1)2-5=0化简得化简得f(x)=4x4+2x3+5x2-4x-4=0然后用牛顿迭代法求出然后用牛顿迭代法求出x的近似值作为的近似值作为x*,并将并将x*代入代入或或后，再用牛顿迭代法求出后，再用牛顿迭代法求出y的近的近似值作为似值作为y*即可。即可。第73页/共78页例例2.12求求在在(x0,y0)=(-1,2)附近解附近解方法：通过消元化为含有一个未知量的方程求方法：通过消元化为含有一个未知量的方程求根问题，然后用牛顿法求解根问题，然后用牛顿法求解解：由解：由得得x=3-2yx=3-2y并代入并代入整理得：整理得：2 2（3-23-2y)y)2 2 y y2 2 5=05

40、=0 7y 7y2 2 12y+13=012y+13=0 f(y)=7y f(y)=7y2 2 12y+13 f(y)=14y12y+13 f(y)=14y 1212 y 0.74x 1.52第74页/共78页例例2.12求求第75页/共78页 非非线线性性方方程程的的解解通通常常叫叫做做方方程程的的根根,也也叫叫做做函函数数的的零零点点,本本章章讨讨论论了了求求解解非非线线性性方方程程近近似似根根常常用用的的一一些些数数值值方方法法。先先要要确确定定有有根根区区间间,且且对对于于收收敛敛的的迭迭代代格格式式,这这个个区区间间要要足足够够小小。针针对对各各种种求求根根的的数数值值方方法法的的特

41、特点点,要考虑其收敛性、收敛速度和计算量。要考虑其收敛性、收敛速度和计算量。二二分分法法是是逐逐步步将将含含根根区区间间分分半半,主主要要用用来来求求实实根根;迭迭代代法法是是一一种种逐逐次次逼逼近近的的方方法法,起起着着把把根根的的精精确确值值一一步步一一步步算算出出来来的的作作用用;牛牛顿顿法法具具有有较较快快的的收收敛敛速速度度,但但对对初初值值选选取取要要求求较较高高。弦弦截截法法避避开开了了导导数数的的计计算算,具具有有超超线性的收敛速度线性的收敛速度,每计算一步每计算一步,要用到前面两步的信息。要用到前面两步的信息。本章小结本章小结第76页/共78页作作业习题一2.12.13第77页/共78页感谢您的观看！第78页/共78页