方程求根计算方法.ppt

《方程求根计算方法.ppt》由会员分享，可在线阅读，更多相关《方程求根计算方法.ppt（128页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、方程求根计算方法现在学习的是第1页，共128页2.1问题的提出第二章方程求根现在学习的是第2页，共128页2.1问题的提出实际问题f(x)=0,f:RR定义：如存在x*使得f(x*)=0则称x*为方程的根或函数f(x)的零点。特别地，如果m=1x*为f(x)=0的单根或f(x)的单零点m1x*为f(x)=0的m重根或f(x)的m重零点现在学习的是第3页，共128页2.1问题的提出l f(x)是n次代数多项式f(x)=0是n次代数方程l f(x)是超越函数f(x)=0是超越方程现在学习的是第4页，共128页2.1问题的提出例如:1.n次代数方程:2.超越方程:现在学习的是第5页，共128页2.1

2、问题的提出Remarks:1.非线性方程的根可为实根或复根；复根总是共轭出现。2.Galois(伽罗瓦)在1830年就已经从理论上证明对于次数高于4次的代数方程，其根不能用方程系数的解析式表示；一般的超越方程更没有解析的求根公式！1。现在学习的是第6页，共128页2.1问题的提出3.根的个数。ln次代数方程有?个根(包括实根和复根)ln为奇数时,至少有一个根是实根l对于超越方程,根可能0无穷个现在学习的是第7页，共128页2.1问题的提出l方程求根步骤(1)对给定区间进行扫描,确定仅存在单根的区间,此区间内的任意一点可视为根的近似值。(2)用迭代方法使根精确到所要求精度。现在学习的是第8页，共

3、128页2.1问题的提出l扫描流程现在学习的是第9页，共128页2.1问题的提出【历史注记】人们很早就探索了高次方程的数值解的求法。巴比伦泥板中有平方表和立方表，利用它们可以解某些特殊的二次和三次方程。中国古人相当系统地解决了求高次方程数值解的问题，九章算术以算法形式给出了二次方程及正系数三次方程正根的具体计算程序；7世纪王孝通也给出了求三次方程正根的数值解法；11世纪贾宪在黄帝九章算法细草中创“开方作法本源图”,用“立成释锁法”解三次和三次以上高次方程,同时他又提出一种更为简便的“增乘开方法”；13世纪秦九韶在数书九章中的“正负开方术”最后完成，提供了一个用算筹布列解任何次数字方程的可行算法

4、。现在学习的是第10页，共128页2.1问题的提出阿拉伯人对高次代数方程的数值解法亦有研究，花拉子米(9世纪)第一个给出了二次方程的一般解法,奥马海亚姆(1100年)给出了一些特殊三次方程的解法。1541年塔尔塔利亚得到三次方程的一般解法。1545年卡尔达诺在其名著大术一书中发展了塔尔塔利亚的这一成果，并记载了费拉里得到的四次方程的一般解法。牛顿在1736年出版的流数法一书中，给出了著名的高次代数方程的一种数值解法,1690年Raphson也提出了类似的方法，它们的结合就是现代常用的方法牛顿法(也叫Newton-Raphson方法)。它是一种广泛用于高次代数方程求解的迭代法，亦称为切线法，并不

5、断产生新的变形,现在学习的是第11页，共128页2.1问题的提出如修正牛顿法，拟牛顿法等。1797年，高斯给出“代数基本定理”，指出高次代数方程根的存在性。1819年，霍纳提出求高次代数方程数值解的另一种方法霍纳法，其思想及计算程序与秦九韶的方法近似，类似的方法鲁非尼在1804年也提出过，霍纳法也有广泛的应用，它的现代改进形式叫劈因子法。现在常用的代数方程数值解法还有伯努利法和劳斯表格法。现在学习的是第12页，共128页2.1问题的提出l有多种数值算法可以求解非线性方程，我们在本章将学习其中得几种，它们是：l二分法(bisectionmethod)l迭代法(iterationmethod)l牛

6、顿法(Newtonmethod)l牛顿下山法(Newtondownhillmethod)。现在学习的是第13页，共128页牛顿(1)牛顿(NewtonIsaac1643.1.4-1727.3.31)：英国数学家、物理学家、天文学家、自然哲学家。生于林肯郡伍尔索普，卒于伦敦。早年在格兰瑟姆读书，1661年以优异成绩考入剑桥大学三一学院，数学上受教于巴罗。1664年毕业后曾为躲避鼠疫回乡，16651666年做出流数法、万有引力和光的分析三大发明，年仅23岁。1667年回剑桥在三一学院执教。1669年继巴罗之后任卢卡斯数学教授职位。晚年致力于哲学和公务，1696年任造币厂监督，3年后任厂长。1703

7、年当选为英国皇家学会主席。他在数学上以创建微积分学而著名，其流数法始于1665年，系统叙述于流数法和无穷级数(1671年完现在学习的是第14页，共128页成，1736年出版)，首先发表在自然哲学的数学原理(1687)中。其中借助运动学中描述的连续量及其变化率阐述他的流数理论，并创用字母上加一点表示流动变化率。讨论的基本问题是：已知流量间的关系，求它们的流数的关系以及逆运算，确定了微分与积分这两类运算的互逆关系，即微积分学基本定理。此外，他还论述了有理指数的二项式定理(1664年)，n次代数方程根的m次幂和的公式(1707年)，数论、解析几何学、曲线分类、变分法等问题。在物理学上发现了万有引力定

8、律(1666-1684)，并据此指出行星运行成椭圆轨道的原因。1666年用三棱镜实验光的色散现象，1668年发明并牛顿(2)现在学习的是第15页，共128页亲手制作了第一具反射望远镜。在哲学上深信物质、运动、空间和时间的客观存在性，坚持用观察和实验方法发现自然界的规律，力求用数学定量方法表述的定律说明自然现象，其科学研究方法支配后世近300年的物理学研究。牛顿(3)现在学习的是第16页，共128页牛顿像(1)现在学习的是第17页，共128页牛顿像(2)现在学习的是第18页，共128页牛顿像(3)现在学习的是第19页，共128页牛顿像(4)现在学习的是第20页，共128页牛顿像(5)现在学习的是

9、第21页，共128页牛顿像(6)现在学习的是第22页，共128页牛顿像(7)现在学习的是第23页，共128页牛顿像(8)现在学习的是第24页，共128页高斯(1)高斯(Gauss,CarlFriedrich1777.4.30-1855.2.23)：德国数学家、物理学家、天文学家。生于不伦瑞克，卒于格丁根。高斯是近代数学奠基者之一，在历史上影响之大，可以和阿基米德、牛顿、欧拉并列。他幼年时就表现出超人的数学天才。1795年进入格丁根大学学习。第二年他发现正十七边形的尺规作图法，并给出可用尺规作出的正多边形的条件，解决了欧几里得以来悬而未决的问题。1798年转入黑尔姆施泰特大学，1799年获博士学

10、位。1807年以后一直在格丁根大学任教授。高斯的数学研究几乎遍及所有领域，在数论、代数学、非欧几何、复变函数和微分几何等方面都现在学习的是第25页，共128页做出了开创性贡献。他还把数学应用于天文学。大地测量学和磁学的研究，发明了最小二乘法原理。高斯的数论研究总结在算术研究(1801)中，这本书奠定了近代数论的基础，它不仅是数论方面划时代之作，也是数学史上不可多得的经典著作之一。高斯对代数学的重要贡献是证明了代数基本定理，他的存在性证明开创了数学研究的新途径。高斯在1816年左右就得到非欧几何的原理，发现椭圆函数的双周期性，但这些工作在他生前都没有发表出来。他还深入研究复变函数，建立了一些基本

11、概念并发现了著名的柯西积分定理。1828年高斯出版了关于曲面的一般研究，全面系统阐述了空间高斯(2)现在学习的是第26页，共128页曲面的微分几何学，并提出了内蕴曲面理论。高斯的曲面理论后来由黎曼进一步发展。高斯一生共发表155篇学术论文，他对待学问十分严谨，只是把他自己认为是十分成熟的作品发表出来。其著作还有地磁概论(1839)和论与距离平方成反比的引力和斥力的普遍定律(1840)等。高斯(3)现在学习的是第27页，共128页高斯像(1)现在学习的是第28页，共128页高斯像(2)现在学习的是第29页，共128页高斯像(3)现在学习的是第30页，共128页高斯像(4)现在学习的是第31页，共

12、128页2.2二分法第二章方程求根现在学习的是第32页，共128页2.2二分法l定义：如果函数f(x)在区间a,b上连续，且f(a)f(b)0，则方程在区间a,b上一定有实根，a,b叫方程的有根区间。【注记】f(a)f(b)0时在a,b上有根的情形。即，f(a)f(b)0对于在a,b上有实根是充分的,但不必要；f(a)f(b)0但有实根abxf(x)2.2二分法现在学习的是第34页，共128页l二分法实际上是一种简单的区间求根方法(Bracketingmethod)，区间法的基本思想是把方程的根限定在一个区间中，区间长度不断缩小，当区间长度充分小时就得到了近似解。二分法就是简单地每次把区间从中

13、间一分为二，区间长度每次减半。2.2二分法现在学习的是第35页，共128页l二分法具体作法：二分初始选取区间a0,b0，使得f(a0)f(b0)0，然后把区间二等分，等分点为(a0+b0)/2，如果f(a0+b0)/2)=0，则得到了方程的根，如果f(a0)f(a0+b0)/2)0，说明根在区间(a0+b0)/2,b0，令a1=(a0+b0)/2,b1=b0则得到更新区间a1,b1。2.2二分法现在学习的是第36页，共128页不断重复这个过程直到，为给定精度，于是得到方程根。l新区间长度总是旧区间长度的一半，二分k次后区间假设为ak,bk，其长度为，2.2二分法现在学习的是第37页，共128页

14、所以对于精度，由11111得到循环次数为nnn2.2二分法现在学习的是第38页，共128页l二分法的特点：2.2二分法2)实施简单，仅需函数值1)收敛总能得到保证3)收敛速度慢现在学习的是第39页，共128页二分法算法:(1)f1=f(a0),f2=f(b0)(3)ifthenstop.ifthenstop.(4)ifthenstop.2.2二分法(2)iff1f20,初始区间选择不合适,stop给定f(x),a0,b0,现在学习的是第40页，共128页(5)x=(a0+b0)/2,f=f(x)ifthenstop.(6)Iff1f0,thenb0=x,f2=f elsea0=x,f1=f,e

15、ndif(7)Goto(3)2.2二分法现在学习的是第41页，共128页l定理2.1：如果区间a,b上的连续函数f应用二分算法,f(a)f(b)0，则n步后将算出一个近似根，其误差至多为2.2二分法现在学习的是第42页，共128页l例2.1用二分法求方程f(x)=x3+4x2-10=0在区间1,1.5上的根，使得根误差不大于0.005，需要作几次二分？2.2二分法解：由f(1)=-5,f(1.5)=2.375,且当时，知方程在所给区间内有唯一根。现在学习的是第43页，共128页2.2二分法由得到所以n=6就可以得到误差不大于0.005的近似根。l作业：证明1-x-sinx=0在0,1(x单位为

16、弧度)内有唯一根，使用二分法求误差不大于5e-5的根要迭代多少次？现在学习的是第44页，共128页2.2二分法【思考题2.1】如何编程用二分法计算区间内的N个实根(假设至少有N个实根)。现在学习的是第45页，共128页2.3迭代法(iterationmethods)第二章方程求根现在学习的是第46页，共128页2.3迭代法l基本思想:设欲求方程f(x)=0的根,变成形式,或,于是方程f(x)=0的根是直线y=x与曲线的交点。用数学式表示迭代公式为：如果迭代序列xk极限存在，则迭代收敛，并且；如果迭代序列xk极限不存在，则称迭代过程发散。现在学习的是第47页，共128页解法1：将原方程写成x=x

17、3-1。取迭代函数构造迭代格式l例2.2用迭代法求x3-x-1=0在x0=1.5附近的根。2.3迭代法以初值x0=1.5代入计算，得到如下结果现在学习的是第48页，共128页2.3迭代法k0123xk1.52.375 12.396 1903.78很明显，xk发散，方法失败。现在学习的是第49页，共128页2.3迭代法解法2：将原方程写成。取迭代函数构造迭代格式取初值x0=1.5，计算得到现在学习的是第50页，共128页2.3迭代法k012378xk1.51.357 1.3301.3251.32471.3247可见迭代8次，近似解已收敛于1.3247。现在学习的是第51页，共128页2.3迭代法

18、解法1和解法2的情况可用下面两个图示意：解法1解法2现在学习的是第52页，共128页l定理2.2假设迭代函数在a,b上存在一阶连续导数,且满足下列两个条件2.3迭代法(1)(1)对于任意对于任意有有(2)存在正数L0，必有，即根唯一。现在学习的是第57页，共128页2.3迭代法(b)由微分中值定理知，存在使反复利用上式，有因为L1，所以时即现在学习的是第58页，共128页2.3迭代法(c)误差。注意到于是所以现在学习的是第59页，共128页2.3迭代法把代入上式得于是现在学习的是第60页，共128页2.3迭代法l可以看出，L越小收敛越快，当L接近1时，收敛很慢。因为L为常数，所以一般用来判断迭

19、代收敛。现在学习的是第61页，共128页2.3迭代法现在学习的是第62页，共128页2.3迭代法现在学习的是第63页，共128页2.3迭代法现在学习的是第64页，共128页2.3迭代法现在学习的是第65页，共128页2.3迭代法l定义如果存在邻域，迭代过程对于任意初始值收敛，则称迭代过程在根附近具有局部收敛性。现在学习的是第66页，共128页2.3迭代法l定理2.3：设在方程根x*附近有连续一阶导数，且，则迭代过程具有局部收敛性。使得利用微分中值定理有证明：取x*附近的一个邻域现在学习的是第67页，共128页2.3迭代法由于即于是取满足(1)对任意，；(2)对任意所以，迭代过程具有局部收敛性。

20、现在学习的是第68页，共128页l迭代法的收敛速度2.3迭代法l定义：当时，有，(且为常数)，则称迭代过程是p阶收敛。特别地，当p=1,0c1时，称作超线性收敛；p=2时称作平方收敛。其中称作迭代误差。现在学习的是第69页，共128页2.3迭代法由微分中值定理有简单迭代法收敛速度一般是线性的。l简单迭代法的收敛速度。现在学习的是第70页，共128页2.3迭代法l例2.3设两个迭代格式分别是线性收敛和平方收敛的，且若取精度，试估计这两个迭代格式各所需的迭代次数。解：现在学习的是第71页，共128页2.3迭代法得由所以线性迭代格式需迭代54次。现在学习的是第72页，共128页2.3迭代法于是所以故

21、平方收敛的迭代格式只需迭代6次。现在学习的是第73页，共128页2.3迭代法l定理2.4：若在的根附近有连续 阶导数且p-1阶导数全为零，,则p阶局部收敛，且有如果p=1，要求现在学习的是第74页，共128页2.3迭代法证明：由定理2.3知，迭代格式局部收敛。应用泰勒级数展开并注意到p-1导数全为零，有现在学习的是第75页，共128页2.3迭代法于是或现在学习的是第76页，共128页2.3迭代法于是现在学习的是第77页，共128页2.3迭代法例2.4判断能不能直接用简单迭代法求解下列的方程？解：判断方程能否用简单迭代法求根，要看在根的邻域是否有现在学习的是第78页，共128页2.3迭代法对于(

22、1)，所以(1)可以用简单迭代法求解。对于(2)，可知f(1)0,f(3)|f(xk+1)|。于是我们把这个条件作为一个约束引入到迭代方程。满足这个约束条件的算法叫下山法。2.5牛顿法下山法现在学习的是第111页，共128页l具体作法：先得到牛顿法结果把与xk作加权平均得到：叫下山因子,时即为牛顿法。2.5牛顿法下山法现在学习的是第112页，共128页l可以通过选取值使得|f(xk)|f(xk+1)|。通常先令开始，若上式不成立则减半，直到上式成立 如果已经很小，上式仍不成立，则下山失败。l意味着新的若不满足下山条件，则加大上一步结果的权重。2.5牛顿法下山法现在学习的是第113页，共128页

23、l例2.10用牛顿下山法求方程f(x)=x3-x-1=0在1.5附近的根，精确到7位有效数字，取x0=0.6。2.5牛顿法下山法解：应用牛顿下山公式现在学习的是第114页，共128页2.5牛顿法下山法kxkf(xk)010.6-1.3840001117.8999805716.42101/29.249990781.200701/321.140624-0.656644211.3668140.186641611.3247180.000000现在学习的是第115页，共128页2.6割线法第二章方程求根现在学习的是第116页，共128页l在牛顿法中，需要计算f(x)的导数f(x)，有时不易求f(x),可

24、以考虑用一个容易计算的近似值来代替f(x)2.6割线法于是！现在学习的是第117页，共128页l在开始迭代时,必须给定两个点(x0,x1),然后才能迭代，计算中要注意f(xk)-f(xk-1)的值以防止溢出,可以用判断是否收敛。l作业：写出割线法的算法。2.6割线法现在学习的是第118页，共128页2.7迭代过程加速方法第二章方程求根现在学习的是第119页，共128页l加速方法的构造2.3迭代过程加速方法假设在根x*附近变化不大，约为L，由微分中值定理有：从上式整理得于是现在学习的是第120页，共128页lAitken加速方法 为了避免计算L，记 用联立消去L得由此得Aitken迭代加速公式2

25、.3迭代过程加速方法现在学习的是第121页，共128页2.3迭代过程加速方法现在学习的是第122页，共128页2.3迭代过程加速方法l例2.11用迭代加速公式求在x=0.5附近的根。解：在x=0.5附近，经过三次迭代，得到x*=0.56714现在学习的是第123页，共128页2.3迭代过程加速方法l例2.12用Aitken方法求x3-x-1=0在x=1.5附近的根。解：用Aitken迭代公式迭代5次，得到x*=1.32472现在学习的是第124页，共128页本章小结第二章方程求根现在学习的是第125页，共128页l本章介绍了求解非线性方程的数值方法：二分法，迭代法，牛顿法，割线法，还学习了牛顿

26、下山法和迭代加速方法。小结l二分法收敛速度慢，但总是收敛的，牛顿法在根的附近收敛速度非常快，是平方收敛，但收敛对初始值的选取要求苛刻，牛顿法还要求计算一阶导数，通常计算导数值的计算量大，有时甚至不可能计算导数值。现在学习的是第126页，共128页割线法不需要计算导数，需要两个初始点。牛顿法每次需要两个值f(xk),f(xk)，割线法每次迭代只需计算一个函数值，因此实际上割线法的计算效率有时比牛顿法更高。牛顿法和割线法必须给出根附近的初始点。小结l迭代收敛阶的概念现在学习的是第127页，共128页小结【思考题】欲求f(x)=0的根，对于下面的每种情况，分别有哪些相应的方法数值方法可以使用？(1)仅仅已知f(x)的求解方法。(2)已知f(x)和f(x)的求解方法。现在学习的是第128页，共128页