数值分析－非线性方程的数值解法学习教案.pptx

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

1、会计学1数值分析数值分析(fnx)非线性方程的数值解法非线性方程的数值解法第一页，共78页。记笔记记笔记第二章第二章第二章第二章非线性方程的数值非线性方程的数值非线性方程的数值非线性方程的数值(shz)(shz)解法解法解法解法 由题设知曲线的最底点由题设知曲线的最底点(0,y(0)(0,y(0)与最高点与最高点(50,y(50)(50,y(50)之间的高度之间的高度(god)(god)差为差为1m,1m,所以应所以应有有y(50)=y(0)+1,y(50)=y(0)+1,即即 要计算电缆的长度要计算电缆的长度(chngd),(chngd),必须先求出必须先求出上述方程中上述方程中的的a,a,

2、由于它是关于由于它是关于a a的非线性方程的非线性方程,没有现成没有现成的公式可用的公式可用,因此只能寻求其他解法因此只能寻求其他解法.第2页/共78页第二页，共78页。第二章第二章第二章第二章非线性方程非线性方程非线性方程非线性方程(fngchng)(fngchng)的数值解法的数值解法的数值解法的数值解法 再如求解方程再如求解方程再如求解方程再如求解方程(fngchng)(fngchng)的近似根的近似根的近似根的近似根方法方法方法方法1:1:将方程将方程将方程将方程(fngchng)(fngchng)同解变换成同解变换成同解变换成同解变换成然后画两条曲线然后画两条曲线然后画两条曲线然后画

3、两条曲线 这两条曲线的交点的横座标大致为这两条曲线的交点的横座标大致为这两条曲线的交点的横座标大致为这两条曲线的交点的横座标大致为x=2.5x=2.5第3页/共78页第三页，共78页。第二章第二章第二章第二章非线性方程的数值非线性方程的数值非线性方程的数值非线性方程的数值(shz)(shz)解法解法解法解法 再如求解方程再如求解方程再如求解方程再如求解方程(fngchng)(fngchng)的近的近的近的近似根似根似根似根方法方法方法方法(fngf)2:(fngf)2:原方程可原方程可原方程可原方程可变换为变换为变换为变换为根据高等数学知识根据高等数学知识根据高等数学知识根据高等数学知识(零点

4、定理零点定理零点定理零点定理)知知知知,设函数设函数设函数设函数f(x)f(x)在闭区间在闭区间在闭区间在闭区间a,ba,b上连续上连续上连续上连续,且且且且f(a)f(a)与与与与f(b)f(b)异号异号异号异号,在在在在(a,b)(a,b)内内内内至少存在一点至少存在一点至少存在一点至少存在一点,使使使使f()=0f()=0而而而而f(2)f(2)ff(3)0,(3)1)当且仅当当且仅当第6页/共78页第六页，共78页。记笔记记笔记第二章第二章第二章第二章非线性方程的数值非线性方程的数值非线性方程的数值非线性方程的数值(shz)(shz)解法解法解法解法 当当f(x)f(x)不是不是x x

5、的线性函数时，称对应的函数方程的线性函数时，称对应的函数方程为非线性方程。如果为非线性方程。如果(rgu)f(x)(rgu)f(x)是多项式函数，则是多项式函数，则称为代数方程，否则称为超越方程（三角方程，指称为代数方程，否则称为超越方程（三角方程，指数、对数方程等）。一般称数、对数方程等）。一般称n n次多项式构成的方程次多项式构成的方程 为为n n次代数方程次代数方程(dish fngchng),(dish fngchng),当当n n1 1时时,方程显然方程显然是非线性的是非线性的 一般稍微复杂的一般稍微复杂的3 3次以上的代数方程次以上的代数方程(dish(dish fngchng)f

6、ngchng)或超越方程或超越方程,很难甚至无法求得精确解。本章很难甚至无法求得精确解。本章将介绍常用的求解非线性方程的近似根的几种数值解法将介绍常用的求解非线性方程的近似根的几种数值解法 第7页/共78页第七页，共78页。记笔记记笔记第二章第二章第二章第二章非线性方程非线性方程非线性方程非线性方程(fngchng)(fngchng)的数值解法的数值解法的数值解法的数值解法 通常方程根的数值解法大致分为三个步骤进行通常方程根的数值解法大致分为三个步骤进行通常方程根的数值解法大致分为三个步骤进行通常方程根的数值解法大致分为三个步骤进行 判定根的存在性。即方程有没有根？如果有判定根的存在性。即方程

7、有没有根？如果有判定根的存在性。即方程有没有根？如果有判定根的存在性。即方程有没有根？如果有根，有几个根？根，有几个根？根，有几个根？根，有几个根？确定根的分布范围。即将每一个根用区间隔确定根的分布范围。即将每一个根用区间隔确定根的分布范围。即将每一个根用区间隔确定根的分布范围。即将每一个根用区间隔(jing)(jing)离开来，这个过程实际上是获得方程各根的离开来，这个过程实际上是获得方程各根的离开来，这个过程实际上是获得方程各根的离开来，这个过程实际上是获得方程各根的初始近似值。初始近似值。初始近似值。初始近似值。根的精确化。将根的初始近似值按某种方法根的精确化。将根的初始近似值按某种方法

8、根的精确化。将根的初始近似值按某种方法根的精确化。将根的初始近似值按某种方法逐步精确化，直到满足预先要求的精度为止逐步精确化，直到满足预先要求的精度为止逐步精确化，直到满足预先要求的精度为止逐步精确化，直到满足预先要求的精度为止 第8页/共78页第八页，共78页。n n远在公元前远在公元前远在公元前远在公元前17001700年的古巴比伦人就已有关于一、二次年的古巴比伦人就已有关于一、二次年的古巴比伦人就已有关于一、二次年的古巴比伦人就已有关于一、二次方程的解法。九章算术方程的解法。九章算术方程的解法。九章算术方程的解法。九章算术(公元前公元前公元前公元前5010050100年年年年)其中其中其

9、中其中“方程术方程术方程术方程术”有联立一次方程组的一般解法。有联立一次方程组的一般解法。有联立一次方程组的一般解法。有联立一次方程组的一般解法。n n15351535年意大利数学家坦特格里亚年意大利数学家坦特格里亚年意大利数学家坦特格里亚年意大利数学家坦特格里亚(TorTaglia)(TorTaglia)发现了发现了发现了发现了三次方程的解法，卡当三次方程的解法，卡当三次方程的解法，卡当三次方程的解法，卡当(HCardano)(HCardano)从他那里得到从他那里得到从他那里得到从他那里得到了这种解法，于了这种解法，于了这种解法，于了这种解法，于15451545年在其名著大法中公布了三年在

10、其名著大法中公布了三年在其名著大法中公布了三年在其名著大法中公布了三次方程的公式解，称为卡当算法。次方程的公式解，称为卡当算法。次方程的公式解，称为卡当算法。次方程的公式解，称为卡当算法。n n后来卡当的学生弗瑞里后来卡当的学生弗瑞里后来卡当的学生弗瑞里后来卡当的学生弗瑞里(Ferrari)(Ferrari)又提出了四次方程又提出了四次方程又提出了四次方程又提出了四次方程的解法。此成果更激发了数学家们的情绪，但在以的解法。此成果更激发了数学家们的情绪，但在以的解法。此成果更激发了数学家们的情绪，但在以的解法。此成果更激发了数学家们的情绪，但在以后的二个世纪后的二个世纪后的二个世纪后的二个世纪(

11、shj)(shj)中，求索工作始终没有成效，中，求索工作始终没有成效，中，求索工作始终没有成效，中，求索工作始终没有成效，导致人们对高次代数方程解的存在性产生了怀疑。导致人们对高次代数方程解的存在性产生了怀疑。导致人们对高次代数方程解的存在性产生了怀疑。导致人们对高次代数方程解的存在性产生了怀疑。第二章第二章第二章第二章非线性方程的数值非线性方程的数值非线性方程的数值非线性方程的数值(shz)(shz)解法解法解法解法第9页/共78页第九页，共78页。n n17991799年，高斯证明了代数方程必有一个实根或复根年，高斯证明了代数方程必有一个实根或复根年，高斯证明了代数方程必有一个实根或复根年

12、，高斯证明了代数方程必有一个实根或复根的定理，称此为代数基本定理，并由此可以立刻的定理，称此为代数基本定理，并由此可以立刻的定理，称此为代数基本定理，并由此可以立刻的定理，称此为代数基本定理，并由此可以立刻推理推理推理推理n n次代数方程必有次代数方程必有次代数方程必有次代数方程必有n n个实根或复根。个实根或复根。个实根或复根。个实根或复根。n n但在以后的几十年中仍然没有找出高次代数方程但在以后的几十年中仍然没有找出高次代数方程但在以后的几十年中仍然没有找出高次代数方程但在以后的几十年中仍然没有找出高次代数方程的公式解。一直到的公式解。一直到的公式解。一直到的公式解。一直到1818世纪，法

13、国数学家拉格朗日世纪，法国数学家拉格朗日世纪，法国数学家拉格朗日世纪，法国数学家拉格朗日用用用用(ryng)(ryng)根置换方法统一了二、三、四方程的根置换方法统一了二、三、四方程的根置换方法统一了二、三、四方程的根置换方法统一了二、三、四方程的解法。解法。解法。解法。n n但求解五次方程时未能如愿但求解五次方程时未能如愿但求解五次方程时未能如愿但求解五次方程时未能如愿,开始意识到有潜藏其开始意识到有潜藏其开始意识到有潜藏其开始意识到有潜藏其中的奥妙中的奥妙中的奥妙中的奥妙,用现代术语表示就是置换群理论问题。用现代术语表示就是置换群理论问题。用现代术语表示就是置换群理论问题。用现代术语表示就

14、是置换群理论问题。n n在继续探索在继续探索在继续探索在继续探索5 5次以上方程解的艰难历程中，第一个次以上方程解的艰难历程中，第一个次以上方程解的艰难历程中，第一个次以上方程解的艰难历程中，第一个重大突破的是挪威数学家阿贝尔重大突破的是挪威数学家阿贝尔重大突破的是挪威数学家阿贝尔重大突破的是挪威数学家阿贝尔(NAbel1802-(NAbel1802-1829)18241829)1824年阿贝尔发表了年阿贝尔发表了年阿贝尔发表了年阿贝尔发表了“五次方程代数解法不五次方程代数解法不五次方程代数解法不五次方程代数解法不可能存在可能存在可能存在可能存在”的论文，但并未受到重视，连数学大的论文，但并未

15、受到重视，连数学大的论文，但并未受到重视，连数学大的论文，但并未受到重视，连数学大师高斯也未理解这项成果的重要意义。师高斯也未理解这项成果的重要意义。师高斯也未理解这项成果的重要意义。师高斯也未理解这项成果的重要意义。第10页/共78页第十页，共78页。n n18281828年年年年1717岁的法国数学家伽罗华岁的法国数学家伽罗华岁的法国数学家伽罗华岁的法国数学家伽罗华(EGalois 1811-1832)(EGalois 1811-1832)写写写写出了划时代的论文出了划时代的论文出了划时代的论文出了划时代的论文(lnwn)“(lnwn)“关于五次方程的代数解法关于五次方程的代数解法关于五次

16、方程的代数解法关于五次方程的代数解法问题问题问题问题”，指出即使在公式中容许用，指出即使在公式中容许用，指出即使在公式中容许用，指出即使在公式中容许用n n次方根，并用类似次方根，并用类似次方根，并用类似次方根，并用类似算法求五次或更高次代数方程的根是不可能的算法求五次或更高次代数方程的根是不可能的算法求五次或更高次代数方程的根是不可能的算法求五次或更高次代数方程的根是不可能的n n文章呈交法兰西科学院后，因辈份太低遭到冷遇，且文文章呈交法兰西科学院后，因辈份太低遭到冷遇，且文文章呈交法兰西科学院后，因辈份太低遭到冷遇，且文文章呈交法兰西科学院后，因辈份太低遭到冷遇，且文稿丢失。稿丢失。稿丢失

17、。稿丢失。18301830年伽罗华再进科学院递稿，得到泊松院士年伽罗华再进科学院递稿，得到泊松院士年伽罗华再进科学院递稿，得到泊松院士年伽罗华再进科学院递稿，得到泊松院士的判词的判词的判词的判词“完全不能理解完全不能理解完全不能理解完全不能理解”。n n后来伽罗华命运不佳，投考名校巴黎工科大学落榜，屈后来伽罗华命运不佳，投考名校巴黎工科大学落榜，屈后来伽罗华命运不佳，投考名校巴黎工科大学落榜，屈后来伽罗华命运不佳，投考名校巴黎工科大学落榜，屈就高等师院，并卷入政事两次入狱，被开除学籍，又决就高等师院，并卷入政事两次入狱，被开除学籍，又决就高等师院，并卷入政事两次入狱，被开除学籍，又决就高等师院

18、，并卷入政事两次入狱，被开除学籍，又决斗受伤，死于斗受伤，死于斗受伤，死于斗受伤，死于18321832年。决斗前，他把关于五次代数求解年。决斗前，他把关于五次代数求解年。决斗前，他把关于五次代数求解年。决斗前，他把关于五次代数求解的研究成果写成长信，留了下来。的研究成果写成长信，留了下来。的研究成果写成长信，留了下来。的研究成果写成长信，留了下来。第11页/共78页第十一页，共78页。n n十四年后，法国数学家刘维尔十四年后，法国数学家刘维尔十四年后，法国数学家刘维尔十四年后，法国数学家刘维尔(JLiouville)(JLiouville)整理并发整理并发整理并发整理并发表了伽罗华的遗作，人们

19、才意识到这项近代数学发展史表了伽罗华的遗作，人们才意识到这项近代数学发展史表了伽罗华的遗作，人们才意识到这项近代数学发展史表了伽罗华的遗作，人们才意识到这项近代数学发展史上的重要成果的宝贵。上的重要成果的宝贵。上的重要成果的宝贵。上的重要成果的宝贵。n n3838年后，即年后，即年后，即年后，即18701870年，法国数学家若当年，法国数学家若当年，法国数学家若当年，法国数学家若当(CJordan)(CJordan)在专著在专著在专著在专著论置换与代数方程中阐发了伽罗华的思想，一门现论置换与代数方程中阐发了伽罗华的思想，一门现论置换与代数方程中阐发了伽罗华的思想，一门现论置换与代数方程中阐发了

20、伽罗华的思想，一门现代数学的分支代数学的分支代数学的分支代数学的分支群论诞生了。群论诞生了。群论诞生了。群论诞生了。n n在前几个世纪中，曾开发出一些在前几个世纪中，曾开发出一些在前几个世纪中，曾开发出一些在前几个世纪中，曾开发出一些(yxi)(yxi)求解代数方程的求解代数方程的求解代数方程的求解代数方程的有效算法，它们构成了数值分析中的古典算法。至于超有效算法，它们构成了数值分析中的古典算法。至于超有效算法，它们构成了数值分析中的古典算法。至于超有效算法，它们构成了数值分析中的古典算法。至于超越方程则不存在一般的求根方式。越方程则不存在一般的求根方式。越方程则不存在一般的求根方式。越方程则

21、不存在一般的求根方式。第12页/共78页第十二页，共78页。n n本章本章本章本章(bn zhn(bn zhn)介绍方程的迭代解法，它介绍方程的迭代解法，它介绍方程的迭代解法，它介绍方程的迭代解法，它既可以用来求解代数方程，也可以用来解既可以用来求解代数方程，也可以用来解既可以用来求解代数方程，也可以用来解既可以用来求解代数方程，也可以用来解超越方程，并且仅限于求方程的实根。超越方程，并且仅限于求方程的实根。超越方程，并且仅限于求方程的实根。超越方程，并且仅限于求方程的实根。n n运用迭代法求解方程的根应解决以下两个运用迭代法求解方程的根应解决以下两个运用迭代法求解方程的根应解决以下两个运用迭

22、代法求解方程的根应解决以下两个问题：问题：问题：问题：n n确定根的初值确定根的初值确定根的初值确定根的初值;n n将进一步精确化到所需要的精度。将进一步精确化到所需要的精度。将进一步精确化到所需要的精度。将进一步精确化到所需要的精度。记笔记记笔记第13页/共78页第十三页，共78页。2.2 2.2 二分法二分法二分法二分法二分法又称二分区间法二分法又称二分区间法,是求解方程是求解方程(2.1)的近似根的一种常用的简单方法。的近似根的一种常用的简单方法。设函数设函数f(x)在闭区间在闭区间a,b上连续上连续(linx),且且f(a)f(b)0,根据连续根据连续(linx)函数的性质可函数的性质

23、可知知,f(x)=0在在(a,b)内必有实根内必有实根,称区间称区间a,b为有根区间。为有根区间。为明确起见为明确起见,假定方程假定方程f(x)=0在区间在区间a,b内有内有惟一实根惟一实根x*。二分法的基本思想是二分法的基本思想是:首先确定有根区间首先确定有根区间,将区间二等分将区间二等分,通过判断通过判断f(x)的符号的符号,逐步将有逐步将有根区间缩小根区间缩小,直至有根区间足够地小直至有根区间足够地小,便可求便可求出满足精度要求的近似根。出满足精度要求的近似根。第14页/共78页第十四页，共78页。确定确定确定确定(qudng)(qudng)(qudng)(qudng)有根区间的方有根区

24、间的方有根区间的方有根区间的方法法法法n n 为了确定根的初值，首先必须圈定根所在的范围，为了确定根的初值，首先必须圈定根所在的范围，为了确定根的初值，首先必须圈定根所在的范围，为了确定根的初值，首先必须圈定根所在的范围，n n 称为圈定根或根的隔离。称为圈定根或根的隔离。称为圈定根或根的隔离。称为圈定根或根的隔离。n n 在上述基础上，采取适当的数值方法确定具有一定在上述基础上，采取适当的数值方法确定具有一定在上述基础上，采取适当的数值方法确定具有一定在上述基础上，采取适当的数值方法确定具有一定n n 精度精度精度精度(jn(jn d)d)要求的初值。要求的初值。要求的初值。要求的初值。n

25、n 对于代数方程，其根的个数（实或复的）与其次数对于代数方程，其根的个数（实或复的）与其次数对于代数方程，其根的个数（实或复的）与其次数对于代数方程，其根的个数（实或复的）与其次数n n 相同。至于超越方程，其根可能是一个、几个或无相同。至于超越方程，其根可能是一个、几个或无相同。至于超越方程，其根可能是一个、几个或无相同。至于超越方程，其根可能是一个、几个或无 n n 解，并没有什么固定的圈根方法解，并没有什么固定的圈根方法解，并没有什么固定的圈根方法解，并没有什么固定的圈根方法n n 求方程根的问题，就几何上讲求方程根的问题，就几何上讲求方程根的问题，就几何上讲求方程根的问题，就几何上讲,

26、是求曲线是求曲线是求曲线是求曲线 y=f(x)y=f(x)与与与与n n x x轴交点的横坐标。轴交点的横坐标。轴交点的横坐标。轴交点的横坐标。第15页/共78页第十五页，共78页。由高等数学知识知由高等数学知识知,设设f(x)f(x)为区间为区间a,ba,b上的单值连续上的单值连续,如如果果f(a)f(b)0,f(a)f(b)0,则则a,ba,b中至少中至少(zhsh(zhsh o)o)有一个实根。如果有一个实根。如果f f(x)(x)在在a,ba,b上还是单调地递增或递减，则仅有一个实根。上还是单调地递增或递减，则仅有一个实根。记笔记记笔记n由此可大体确定根所在子区间，方法由此可大体确定根

27、所在子区间，方法(fngf)有：有：n(1)画图法画图法n(2)逐步搜索法逐步搜索法y=f(x)abyx第16页/共78页第十六页，共78页。(1)(1)画图画图画图画图(hu t)(hu t)法法法法n n 画出画出画出画出y=f(x)y=f(x)的略图，从而看出曲线与的略图，从而看出曲线与的略图，从而看出曲线与的略图，从而看出曲线与x x轴交点的轴交点的轴交点的轴交点的 n n 大致位置。大致位置。大致位置。大致位置。n n 也可将也可将也可将也可将f(x)=0f(x)=0分解为分解为分解为分解为 1(x)=1(x)=2(x)2(x)的形式，的形式，的形式，的形式，1(x)1(x)n n

28、与与与与 2(x)2(x)两曲线交点的横坐标所在的子区间即为含根两曲线交点的横坐标所在的子区间即为含根两曲线交点的横坐标所在的子区间即为含根两曲线交点的横坐标所在的子区间即为含根n n 区间。区间。区间。区间。n n例如例如例如例如 xlogx-1=0 xlogx-1=0n n可以改写为可以改写为可以改写为可以改写为logx=1/xlogx=1/xn n画出对数曲线画出对数曲线画出对数曲线画出对数曲线y=logx,y=logx,与双曲线与双曲线与双曲线与双曲线y=1/x,y=1/x,它们它们它们它们(t(t men)men)交交交交n n 点的横坐标位于区间点的横坐标位于区间点的横坐标位于区间

29、点的横坐标位于区间2,32,3内内内内第17页/共78页第十七页，共78页。(1)(1)画图画图画图画图(hu t)(hu t)法法法法023yx第18页/共78页第十八页，共78页。n对于某些对于某些(mu xi)看不清根的函数，可以扩大一下曲看不清根的函数，可以扩大一下曲线线y0 xy=f(x)y=kf(x)(1)(1)(1)画图画图画图画图画图画图(hu t)(hu t)(hu t)法法法法法法记笔记记笔记第19页/共78页第十九页，共78页。y0 xABa1b1a2b2(2)逐步逐步(zhb)搜索法搜索法(2)(2)搜索搜索(su(su su)su)法法 对于给定的对于给定的f(x),

30、f(x),设有根区间为设有根区间为A,B,A,B,从从x0=Ax0=A出发出发,以步长以步长h=(B-A)/n(nh=(B-A)/n(n是正整数是正整数),),在在A,BA,B内取定内取定节点节点:xi=x0:xi=x0ih(i=0,1,2,n),ih(i=0,1,2,n),从左至右检查从左至右检查f f(xi)(xi)的符号的符号,如发现如发现xixi与端点与端点x0 x0的函数值异号的函数值异号,则得则得到一个到一个(y)(y)缩小的有根子区间缩小的有根子区间xi-1,xixi-1,xi。第20页/共78页第二十页，共78页。例例例例1 1 1 1 方程方程方程方程f(x)=x3-x-1=

31、0 f(x)=x3-x-1=0 f(x)=x3-x-1=0 f(x)=x3-x-1=0 确定其有根区间确定其有根区间确定其有根区间确定其有根区间(q jin)(q jin)(q jin)(q jin)解：用试凑的方法，不难发现解：用试凑的方法，不难发现解：用试凑的方法，不难发现解：用试凑的方法，不难发现 f(0)0 f(0)0 f(0)0 f(0)0 在区间在区间在区间在区间(q jin)(q jin)(q jin)(q jin)（0 0 0 0，2 2 2 2）内至少有一个实根）内至少有一个实根）内至少有一个实根）内至少有一个实根 设从设从设从设从x=0 x=0 x=0 x=0出发出发出发出

32、发,取取取取h=0.5h=0.5h=0.5h=0.5为步长向右进行根的为步长向右进行根的为步长向右进行根的为步长向右进行根的 搜索搜索搜索搜索,列表如下列表如下列表如下列表如下x xf(x)f(x)0 0.5 1.0 1.5 20 0.5 1.0 1.5 2 +可以可以(ky)(ky)看出，在看出，在1.0,1.51.0,1.5内必有一根内必有一根第21页/共78页第二十一页，共78页。n n 用逐步搜索法进行实根隔离的关键是选取步长用逐步搜索法进行实根隔离的关键是选取步长用逐步搜索法进行实根隔离的关键是选取步长用逐步搜索法进行实根隔离的关键是选取步长h h h hn n 要选择适当要选择适当

33、要选择适当要选择适当h h h h，使之既能把根隔离开来，工作量，使之既能把根隔离开来，工作量，使之既能把根隔离开来，工作量，使之既能把根隔离开来，工作量n n 又不太大。又不太大。又不太大。又不太大。n n 为获取指定精度要求的初值为获取指定精度要求的初值为获取指定精度要求的初值为获取指定精度要求的初值,可在以上隔离根的可在以上隔离根的可在以上隔离根的可在以上隔离根的n n 基础上采用对分法继续缩小该含根子基础上采用对分法继续缩小该含根子基础上采用对分法继续缩小该含根子基础上采用对分法继续缩小该含根子(gn zi)(gn zi)(gn zi)(gn zi)区间区间区间区间n n n n 二分

34、法可以看作是搜索法的一种改进。二分法可以看作是搜索法的一种改进。二分法可以看作是搜索法的一种改进。二分法可以看作是搜索法的一种改进。第22页/共78页第二十二页，共78页。取有根区间取有根区间a,b之中点之中点,将它分为两半将它分为两半,分点分点,这样这样(zhyng)就可缩小有根区间就可缩小有根区间 二分法求根过程二分法求根过程(guchng)(guchng)设设方方程程(fngchng)f(x)=0在在区区间间a,b内内有有根根,二二分分法法就就是是逐逐步步收收缩缩有有根根区区间间，最最后后得得出出所所求求的的根。具体过程如下根。具体过程如下第23页/共78页第二十三页，共78页。对压缩了

35、的有根区间对压缩了的有根区间 施行同样的手法施行同样的手法,即取中点即取中点 ,将区间将区间 再分为两半再分为两半,然然 后再确定有根区间后再确定有根区间 ,其长度是其长度是 的的 二分之一二分之一 如如此此反反复复(fnf)(fnf)下下去去,若若不不出出现现 ,即即可可得出一得出一 系列有根区间序列：系列有根区间序列：上述每个区间都是前一个区间的一半上述每个区间都是前一个区间的一半,因此因此 的长度的长度 当当kk时趋于零时趋于零,这些区间这些区间(q jin)(q jin)最终收最终收敛于一点敛于一点x*x*即为即为 所求的根所求的根 。第24页/共78页第二十四页，共78页。每次二分后

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

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

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

39、管有根区间二分法的优点是不管有根区间 多大多大,总能求出总能求出满足精度要求的根满足精度要求的根,且对函数且对函数f(x)f(x)的要求不高的要求不高,只要连续即可只要连续即可,计算计算(j sun)(j sun)亦简单亦简单;它的局限性是只能用于求函数的实它的局限性是只能用于求函数的实根根,不能用于求复根及重根不能用于求复根及重根,它的收敛速度与比值为它的收敛速度与比值为 的等的等比级数相同。比级数相同。第29页/共78页第二十九页，共78页。2.3 2.3 迭代法迭代法迭代法迭代法 对于一般的非线性方程对于一般的非线性方程,没有通常所说的求没有通常所说的求根公式求其精确解根公式求其精确解,

40、需要设计近似求解方法需要设计近似求解方法,即迭即迭代法。它是一种逐次逼近代法。它是一种逐次逼近(bjn)(bjn)的方法的方法,用某个用某个固定公式反复校正根的近似值固定公式反复校正根的近似值,使之逐步精确化，使之逐步精确化，最后得到满足精度要求的结果。最后得到满足精度要求的结果。为求解非线性方程f(x)=0的根，先将其写成便于(biny)迭代的等价方程 (2.3)其中 为x的连续函数第30页/共78页第三十页，共78页。2.3 2.3 迭代法迭代法迭代法迭代法即如果数即如果数 使使f(x)=0,则也有则也有 ,反之反之,若若 ,则也有则也有 ,称称 为迭代函数为迭代函数(hnsh)任取一个初

41、值任取一个初值 ,代入式代入式 的右的右端端,得到得到 再将再将 代入式代入式 的右端的右端,得到得到(d do),依此类推依此类推,得到得到(d do)一个数列一个数列 ，其一般表示其一般表示 式式(2.4)(2.4)称为求解称为求解(qi ji)(qi ji)非线性方程的简单非线性方程的简单迭代法。迭代法。(2.4)(2.4)第31页/共78页第三十一页，共78页。如果由迭代格式如果由迭代格式 产生的序列产生的序列(xli)(xli)收敛收敛,即即 则称迭代法收敛则称迭代法收敛(shulin)(shulin)。实实际际计计算算中中当当然然不不可可能能也也没没必必要要(byo)无无穷穷多多步

42、步地地做做下下去去,对对预预先先给给定定的的精精度度要要求求，只只要要某某个个k满足满足即可结束计算并取即可结束计算并取 当然，迭代函数当然，迭代函数 的构造方法是多种多样的。的构造方法是多种多样的。第32页/共78页第三十二页，共78页。例例4 4 用迭代法求方程用迭代法求方程 在在x=1.5x=1.5附近的一个根附近的一个根解解 将方程改写成如下两种等价将方程改写成如下两种等价(dngji)(dngji)形形式式 相相应应(xingyng)(xingyng)地地可可得得到到两两个个迭迭代代公式公式如果取初始值如果取初始值 1.51.5，用上述两个迭代，用上述两个迭代(di(di di)di

43、)公式分别迭代公式分别迭代(di di)(di di)，计算结果见，计算结果见P21 P21 第33页/共78页第三十三页，共78页。2.3.2迭代法的几何迭代法的几何(jh)意义意义 通常将方程通常将方程f(x)=0f(x)=0化为与它同解的方程化为与它同解的方程的方法不止一种的方法不止一种(y zhn),(y zhn),有的收敛有的收敛,有的不收敛有的不收敛,这取决于这取决于 的性态的性态,方程方程 的求根问题在几何的求根问题在几何上就是确定曲线上就是确定曲线y=y=与直线与直线y=xy=x的交点的交点P*P*的横的横坐标坐标(图图2-32-3所示所示)(a)(b)第34页/共78页第三十

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

45、便适时终止迭代第36页/共78页第三十六页，共78页。定理定理2.1 设函数设函数 在在a,b上具有连续的一阶导上具有连续的一阶导 数数,且满足且满足 （1）对所有的）对所有的xa,b 有有 a,b （2）存在）存在 0 L 1,使所有的使所有的xa,b有有 L则方程则方程 在在a,b上的解上的解 存在且唯一存在且唯一，对任意的，对任意的 a,b，迭代，迭代(di di)过程过程均收敛于均收敛于 。并有误差估计式。并有误差估计式 第37页/共78页第三十七页，共78页。由连续函数介值定理知由连续函数介值定理知,必有必有 a,b,使使 所以所以(suy)有解存在有解存在,即即假设有两个解假设有两

46、个解 和和 ,a,b，则，则，由微分中值定理有由微分中值定理有其中其中是介于是介于x*和和 之间的点之间的点 从而有从而有a,b，进而有，进而有 由条件由条件(2)有有 1,所以所以(suy)-=0，即，即 =，解唯一。，解唯一。证证:构造函数构造函数 ,由条件由条件(tiojin)对任意的对任意的xa,b a,b有有第38页/共78页第三十八页，共78页。按迭代按迭代(di di)(di di)过程过程 ,有有 由于由于L1,L0），使），使 则称序列则称序列 是是 p p 阶收敛的阶收敛的,c,c称渐近误差称渐近误差(wch)(wch)常数。特别地常数。特别地,p=1,p=1时称为线性收敛

47、时称为线性收敛,p=2,p=2时时称为平方收敛。称为平方收敛。1 p 21 p 0 xn+1X*ayx0Bf(x)0a=x0yx0B=x0f(x)0ayx0Bf(x)0a=x0 牛顿牛顿(ni dn)迭代法的收敛性迭代法的收敛性第59页/共78页第五十九页，共78页。牛顿迭代法对初值牛顿迭代法对初值x0的选取要求的选取要求(yoqi)比较高。比较高。x0必须充分靠近必须充分靠近x*才能保证局部收敛。才能保证局部收敛。定理定理2.5如果在有根区间如果在有根区间a,b上上连续且不变号，在连续且不变号，在a,b上取初始近似根上取初始近似根x0满足，满足，则牛顿迭代法产生的迭代序列单调收敛于方程则牛顿

48、迭代法产生的迭代序列单调收敛于方程f(x)=0在该区间上的唯一解。在该区间上的唯一解。证明证明（略略）第60页/共78页第六十页，共78页。yx10 x0X*0 x0X*x2不满足迭代条件时，可能导致迭代值远离不满足迭代条件时，可能导致迭代值远离(yunl)根的情况而找不到根或死循环的情况根的情况而找不到根或死循环的情况 牛顿牛顿(ni dn)迭代法的收敛性迭代法的收敛性第61页/共78页第六十一页，共78页。2.4.4牛牛顿顿(nidn)迭迭代代法法的的算算法法实实现现第62页/共78页第六十二页，共78页。例例2.11 用牛顿迭代法求用牛顿迭代法求 x=e-x的根的根,=10-4解：因解：

49、因 f(xk)=x ex 1,f(xk)=ex(x+1)建立建立(jinl)迭代公式迭代公式取取x0=0.5,逐次逐次(zhc)计算得计算得x1=0.57102,x2=0.56716，x3=0.56714第63页/共78页第六十三页，共78页。2.4.5牛顿牛顿(nidn)下山法下山法 通常通常,牛顿迭代法的收敛性依赖于初始值牛顿迭代法的收敛性依赖于初始值 的选取的选取,如果如果 偏离所求的根偏离所求的根 比较远比较远,则牛顿法可能发散。则牛顿法可能发散。为了防止迭代发散为了防止迭代发散,我们对牛顿迭代法的迭代过程再我们对牛顿迭代法的迭代过程再附加一项要求附加一项要求(yoqi),(yoqi)

50、,即具有单调性即具有单调性 将牛顿迭代法与下山法结合起来使用将牛顿迭代法与下山法结合起来使用(shyng),(shyng),即在下山法保证函数值下降的前提下即在下山法保证函数值下降的前提下,用牛顿迭代法加用牛顿迭代法加快收敛速度。把这一算法称为牛顿下山法。即快收敛速度。把这一算法称为牛顿下山法。即满足这项要求的算法称下山法。满足这项要求的算法称下山法。其中其中(01)(01)为下山因子为下山因子 第64页/共78页第六十四页，共78页。下下山山因因子子的的选选择择是是个个逐逐步步探探索索的的过过程程，设设从从=1开开始始反反复复将将减减半半(jin bn)进进行行试试算算,即即逐逐次次取取为为