数值分析-第7章-非线性方程的数值解法课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,远在公元前1700年的古巴比伦人就已有关于一、二次方程的解法。九章算术(公元前50100年)其中“方程术”有联立一次方程组的一般解法。,1535年意大利数学家坦特格里亚(TorTaglia)发现了三次方程的解法，卡当(HCardano)从他那里得到了这种解法，于1545年在其名著大法中公布了三次方程的公式解，称为卡当算法。,后来卡当的学生弗瑞里(Ferrari)又提出了四次方程的解法。此成果更激发了数学家们的情绪，但在以后的二个世纪中，求索工作始终没有成效，导致人们对高次代数方程解的存在性产生了怀疑。,远在公元前1700年的古巴比伦人就已有关于一、二次方程的解法,1799年，高斯证明了代数方程必有一个实根或复根的定理，称此为代数基本定理，并由此可以立刻推理n次代数方程必有n个实根或复根。,但在以后的几十年中仍然没有找出高次代数方程的公式解。一直到18世纪，法国数学家拉格朗日用根置换方法统一了二、三、四方程的解法。,但求解五次方程时未能如愿,开始意识到有潜藏其中的奥妙,用现代术语表示就是置换群理论问题。,在继续探索5次以上方程解的艰难历程中，第一个重大突破的是挪威数学家阿贝尔(NAbel1802-1829)1824年阿贝尔发表了“五次方程代数解法不可能存在”的论文，但并未受到重视，连数学大师高斯也未理解这项成果的重要意义。,1799年，高斯证明了代数方程必有一个实根或复根的定理，称此,1828年17岁的法国数学家伽罗华(EGalois 1811-1832)写出了划时代的论文“关于五次方程的代数解法问题”，指出即使在公式中容许用n次方根，并用类似算法求五次或更高次代数方程的根是不可能的,文章呈交法兰西科学院后，因辈份太低遭到冷遇，且文稿丢失。1830年伽罗华再进科学院递稿，得到泊松院士的判词“完全不能理解”。,后来伽罗华命运不佳，投考名校巴黎工科大学落榜，屈就高等师院，并卷入政事两次入狱，被开除学籍，又决斗受伤，死于1832年。决斗前，他把关于五次代数求解的研究成果写成长信，留了下来。,1828年17岁的法国数学家伽罗华(EGalois 181,十四年后，法国数学家刘维尔(JLiouville)整理并发表了伽罗华的遗作，人们才意识到这项近代数学发展史上的重要成果的宝贵。,38年后，即1870年，法国数学家若当(CJordan)在专著论置换与代数方程中阐发了伽罗华的思想，一门现代数学的分支群论诞生了。,在前几个世纪中，曾开发出一些求解代数方程的有效算法，它们构成了数值分析中的古典算法。至于超越方程则不存在一般的求根方式。,在科学研究的数学问题中更多的是非线性问题，它们又常常归结为非线性方程或非线性方程组的求解问题。,十四年后，法国数学家刘维尔(JLiouville)整理并发,第7章 非线性方程与方程组的数值解法,/*,Numerical Solutions of Nonlinear Equations*/,7.1 方程求根与二分法,7.2 不动点迭代法及其收敛性,7.3 迭代收敛的加速方法,7.4 牛顿法,7.5 弦截法与抛物线法,7.6 求根问题的敏感性与多项式的零点,7.7 非线性方程组的数值解法,第7章 非线性方程与方程组的数值解法/*Numeric,7.1 方程求根与二分法,7.1.1 引言,（1.1）,单变量,非线性,方程的一般形式,其中 也可以是无穷区间.,（1.2）,如果函数 是多项式函数，即,其中 为实数，则称方程(1.2)为,次代数方程,.,超越函数,不能表示为多项式的函数,如,(,x,)=3,x,5,-2,x,4,+8,x,2,-7,x,+1=0,(,x,)=e,2,x,+1-,x,ln(sin,x,)-2=0,高次代数方程,超越方程,代数方程与超越方程,7.1 方程求根与二分法 7.1.1 引言（1.1）单变,方程的根与函数的零点,如果实数 满足 ，,（1.1）,则称 是方程(1.1)的,根,，或称 是 的,零点,.,若 可分解为,其中 为正整数，,则称 为方程(1.1)的,重根,，或 为 的,重零点,，,时为,单根,.,若 是 的 重零点，且 充分光滑，则,结论,次方程在复数域有且只有 个根（含重根，重根为 个根）.,方程的根与函数的零点如果实数 满足 ，（,设,f,(,x,),C,a,b,且,f,(,a,),f,(,b,)0,至少存在,(,a,b,)，使,f,(,)=0.,根的存在性定理,闭区间上连续函数的介值定理,如果,f,(,x,)在,a,b,上,单调递增,或,递减,的，则,f,(,x,)=0仅有一个实根。,有根区间,通常方程根的数值解法大致分为2个步骤进行：,本章将介绍常用的求解非线性方程的近似根的几种数值解法,根的搜索。,寻找根的大概位置，及有根区间，进而找出有唯一根的区间。,根的精确化。,即将每一个根用区间隔离开来，这个过程实际上是获得方程,各根的初始近似值。,将根的初始近似值按某种方法逐步精确化，直到满足预先要求,的精度为止.,设 f(x)Ca,b,且 f(a)f(b)0,如何求方程 的有根区间？,(1)描图法,画出,y,=,f,(,x,)的略图，从而看出曲线与,x,轴交点的大致位置。,例1,求方程,3,x,-1-,cos,x,=,0,的有根区间。,方程等价变形为,3,x,-1=,cos,x，,y,=,3,x,-1,与,y,=cos,x,的图像只有一个交点位于0.5，1内,。,将,f,(,x,)=0等价变形为,g,1,(,x,)=,g,2,(,x,)的形式，,y,=,g,1,(,x,)与,y,=,g,2,(,x,)两曲线交点的横坐标所在的子区间即为有根区间。,(2)解析法,根据函数的连续性、介值定理和单调性寻找有根区间和唯一,根的区间。,如何求方程 的有根区间？(1)描图法画出y=f,对 的根进行搜索计算，,例2,求方程 的有根区间.,由此可知方程的有根区间为,(3)定步长搜索法,在某一区间,a,b,上,从,x,0,=,a,出发,以步长,h=,(,b-a,)/,n,其中,n,是正整数，在,a,b,内取定节点：,x,i,=,x,0,ih,(,i,=0,1,2，,),考察函数值,f,(,x,i,)的符号,当,f,(,x,),连续且,f,(,x,i,).,f,(,x,i+,1,)0，,则区间,x,i,x,i+,1,为有根区间,若导数不变号有唯一根。,解,对 的根进行搜索计算，例2 求方程,7.1.2 二分法,/*Bisection Method*/,求解方程,f,(,x,)=0的,近似根,的最直观、最简单方法。,原理,基本思想,设函数,f,(,x,),C,a,b,上连续,且,f,(,a,),f,(,b,)0,则,f,(,x,)=0在(,a,b,)内至少存在一个根。,逐步将区间二等分,通过判断区间端点,f,(,x,)的符号,将有根区间缩小,直至有根区间足够地小,便可求出,满足精度要求,的近似根。,具体做法,7.1.2 二分法/*Bisection Metho,以此类推,由二分法的过程知,(1),(2),(3),作为,根的近似,近似根的序列,（1.3）,且,以此类推由二分法的过程知(1)(2)(3)作为根的近似近似根,(4),只要二分足够多次（即 充分大），便有,这里 为,预定的精度,.,要使,解,：,例3,用二分法求方程 在区间 上的根，误差限为 ，问至少需对分多少次？,(4)只要二分足够多次（即 充分大），便有 这里 为预定,二分法的算法,二分法的算法,例4,求方程,在区间 内的一个实根，要求准确到小数点后第2位.,欲使,只需 ，即只要二分6次，便能达到预定的精度.,解,得到新的有根区间,例4 求方程 在区间 内的一个实根，要求准确到,二分法对多个零点的情况，只能算出其中一个零点。即使,f,(,x,)在,a,b,上有零点，也未必有,f,(,a,),f,(,b,)0。,不管有根区间多大,总能求出满足精度要求的根,且对函数,f,(,x,)的要求不高,只要连续即可,计算亦简单。,优点,缺点,注：,用二分法求根，最好先给出,f,(,x,),草图以确定根的大概位置。或用搜索程序，将,a,b,分为若干小区间，对每一个满足,f,(,a,k,),f,(,b,k,)0 的区间调用二分法程序，可找出区间,a,b,内的多个根，且不必要求,f,(,a,),f,(,b,)0。,二分法对多个零点的情况，只能算出其中一个零点。即使 f(x,7.2,不动点迭代法及其收敛性,迭代法,逐次逼近的方法,首先取一个粗糙的近似值，然后用同一个递推公式，反复,校正这个初值，直到满足预先给出的精度要求为止。,如何构造一个合适的递推公式？,7.2.1 不动点与不动点迭代法,/*,Fixed-Point Iteration*/,(2.1),若 满足 ，则 ；反之亦然，称,为函数 的一个,不动点,.,已知方程 在区间,a,b,内有一个根,x,*，在区间,a,b,求 的,零点,就,等价于,求 的,不动点,.,(2.2),称为,迭代函数,.,迭代格式,7.2 不动点迭代法及其收敛性 迭代法逐次逼近的方,格式的收敛性,得到序列 有极限,如果对任何 ，由迭代,不动点迭代法,且 为 的,不动点,。,不动点迭代,是一种,逐次逼近,的方法,用某个固定公式,反复校正,根的近似值,使之逐步精确化，最后得到满足精度要求的结果。,对预先给定的精度要求,，只要某个,k,满足,即可结束计算并取,迭代终止的判定,则称,迭代法收敛,，,格式的收敛性得到序列 有极限 如果对任何,例5,求方程,(2.3),在 附近的根,解,构造迭代格式。,方法一：,取迭代函数,构造迭代格式,取初值,发散,方法二：,取迭代函数,构造迭代格式,取初值,例5 求方程(2.3)在 附近的根,即为所求的根.,如果仅取6位数字，,结果 与 完全相同，,说明：迭代函数不唯一，迭代点列可能收敛，也可能发散，迭代收敛与否不仅与迭代函数有关，还与初始点有关。,即为所求的根.如果仅取6位数字，说明：迭代函数不,不动点迭代的几何解释,交点的横坐标,y=x,不动点迭代的几何解释交点的横坐标 y=x,x,y,y=x,x,y,y=x,x,y,y=x,x,y,y=x,x*,x*,x*,x*,y=g,(,x,),y=g,(,x,),y=g,(,x,),y=g,(,x,),x,0,p,0,x,1,p,1,x,0,p,0,x,1,p,1,x,0,p,0,x,1,p,1,x,0,p,0,x,1,p,1,xyy=xxyy=xxyy=xxyy=xx*,7.2.2 不动点的存在性与迭代法的收敛性,不动点的存在,唯一性定理,定理1,2,设 满足以下两个条件：,1,.对任意 有,2.存在正常数 ，使对任意 都有,(2.4),则,(1)在 上存在唯一的不动点,(2.5),得到的迭代,序列,(2)对任意 ，由,收敛到 的不动点 ，,并有误差估计,L,越 收敛越快,小,事前估计：选取,k,，,预先估计迭代次数。,7.2.2 不动点的存在性与迭代法的收敛性 不动点的存在定,定义函数,显然 ，,且,由零点定理知存在 ,使 ,即,唯一性,设 都是 的不动点，,故 的不动点是唯一的.,则由,即为 的不动点.,得,矛盾.,证明,(1),若 或 ，则不动点为 或 ，,因 ，,以下设 及 ，,存在性,定义函数显然 ，且由零点定理知存在,(2),设 是 在 上的唯一不动点，,由条件，可知,因 ，故当 时序列 收敛到 .,又由,误差估计,收敛性,由,（2.6）,得,反复递推得,(2)设 是 在,迭代过程的控制,只要相邻两次计算结果的偏差 足够小，即可保证,近似值 具有足够精度.,事后估计,事前估计：选取,k,，,预先估计迭代次数。,注：,定理1、2的条件(2)可替换为,(2.7),如果 且对任意 有,则由中值定理可知对 有,迭代过程的控制只要相邻两次计算结果的偏差 足,