方程求根(计算方法).ppt

计算方法(力学系本科生),第二章方程求根(Rootsfinding),2.1问题的提出,第二章方程求根,2.1问题的提出,实际问题,f(x)=0,f:RR,定义：如存在x*使得f(x*)=0,则称x*为方程的根或函数f(x)的零点。,特别地，如果,m=1,x*为f(x)=0的单根或f(x)的单零点,m1,x*为f(x)=0的m重根或f(x)的m重零点,2.1问题的提出,f(x)是n次代数多项式,f(x)=0是n次代数方程,f(x)是超越函数,f(x)=0是超越方程,2.1问题的提出,例如:,1.n次代数方程:,2.超越方程:,2.1问题的提出,Remarks:,1.非线性方程的根可为实根或复根；复根总是共轭出现。,2.Galois(伽罗瓦)在1830年就已经从理论上证明对于次数高于4次的代数方程，其根不能用方程系数的解析式表示；一般的超越方程更没有解析的求根公式！1。,2.1问题的提出,3.根的个数。,n次代数方程有?个根(包括实根和复根),n为奇数时,至少有一个根是实根,对于超越方程,根可能0无穷个,2.1问题的提出,方程求根步骤,(1)对给定区间进行扫描,确定仅存在单根的区间,此区间内的任意一点可视为根的近似值。,(2)用迭代方法使根精确到所要求精度。,2.1问题的提出,扫描流程,2.1问题的提出,【历史注记】人们很早就探索了高次方程的数值解的求法。巴比伦泥板中有平方表和立方表，利用它们可以解某些特殊的二次和三次方程。中国古人相当系统地解决了求高次方程数值解的问题，九章算术以算法形式给出了二次方程及正系数三次方程正根的具体计算程序；7世纪王孝通也给出了求三次方程正根的数值解法；11世纪贾宪在黄帝九章算法细草中创“开方作法本源图”,用“立成释锁法”解三次和三次以上高次方程,同时他又提出一种更为简便的“增乘开方法”；13世纪秦九韶在数书九章中的“正负开方术”最后完成，提供了一个用算筹布列解任何次数字方程的可行算法。,2.1问题的提出,阿拉伯人对高次代数方程的数值解法亦有研究，花拉子米(9世纪)第一个给出了二次方程的一般解法,奥马海亚姆(1100年)给出了一些特殊三次方程的解法。1541年塔尔塔利亚得到三次方程的一般解法。1545年卡尔达诺在其名著大术一书中发展了塔尔塔利亚的这一成果，并记载了费拉里得到的四次方程的一般解法。牛顿在1736年出版的流数法一书中，给出了著名的高次代数方程的一种数值解法,1690年Raphson也提出了类似的方法，它们的结合就是现代常用的方法牛顿法(也叫Newton-Raphson方法)。它是一种广泛用于高次代数方程求解的迭代法，亦称为切线法，并不断产生新的变形,2.1问题的提出,如修正牛顿法，拟牛顿法等。1797年，高斯给出“代数基本定理”，指出高次代数方程根的存在性。1819年，霍纳提出求高次代数方程数值解的另一种方法霍纳法，其思想及计算程序与秦九韶的方法近似，类似的方法鲁非尼在1804年也提出过，霍纳法也有广泛的应用，它的现代改进形式叫劈因子法。现在常用的代数方程数值解法还有伯努利法和劳斯表格法。,2.1问题的提出,有多种数值算法可以求解非线性方程，我们在本章将学习其中得几种，它们是：,二分法(bisectionmethod),迭代法(iterationmethod),牛顿法(Newtonmethod),牛顿下山法(Newtondownhillmethod)。,牛顿(1),牛顿(NewtonIsaac1643.1.4-1727.3.31)：英国数学家、物理学家、天文学家、自然哲学家。生于林肯郡伍尔索普，卒于伦敦。早年在格兰瑟姆读书，1661年以优异成绩考入剑桥大学三一学院，数学上受教于巴罗。1664年毕业后曾为躲避鼠疫回乡，16651666年做出流数法、万有引力和光的分析三大发明，年仅23岁。1667年回剑桥在三一学院执教。1669年继巴罗之后任卢卡斯数学教授职位。晚年致力于哲学和公务，1696年任造币厂监督，3年后任厂长。1703年当选为英国皇家学会主席。他在数学上以创建微积分学而著名，其流数法始于1665年，系统叙述于流数法和无穷级数(1671年完,成，1736年出版)，首先发表在自然哲学的数学原理(1687)中。其中借助运动学中描述的连续量及其变化率阐述他的流数理论，并创用字母上加一点表示流动变化率。讨论的基本问题是：已知流量间的关系，求它们的流数的关系以及逆运算，确定了微分与积分这两类运算的互逆关系，即微积分学基本定理。此外，他还论述了有理指数的二项式定理(1664年)，n次代数方程根的m次幂和的公式(1707年)，数论、解析几何学、曲线分类、变分法等问题。在物理学上发现了万有引力定律(1666-1684)，并据此指出行星运行成椭圆轨道的原因。1666年用三棱镜实验光的色散现象，1668年发明并,牛顿(2),亲手制作了第一具反射望远镜。在哲学上深信物质、运动、空间和时间的客观存在性，坚持用观察和实验方法发现自然界的规律，力求用数学定量方法表述的定律说明自然现象，其科学研究方法支配后世近300年的物理学研究。,牛顿(3),牛顿像(1),牛顿像(2),牛顿像(3),牛顿像(4),牛顿像(5),牛顿像(6),牛顿像(7),牛顿像(8),高斯(1),高斯(Gauss,CarlFriedrich1777.4.30-1855.2.23)：德国数学家、物理学家、天文学家。生于不伦瑞克，卒于格丁根。高斯是近代数学奠基者之一，在历史上影响之大，可以和阿基米德、牛顿、欧拉并列。他幼年时就表现出超人的数学天才。1795年进入格丁根大学学习。第二年他发现正十七边形的尺规作图法，并给出可用尺规作出的正多边形的条件，解决了欧几里得以来悬而未决的问题。1798年转入黑尔姆施泰特大学，1799年获博士学位。1807年以后一直在格丁根大学任教授。高斯的数学研究几乎遍及所有领域，在数论、代数学、非欧几何、复变函数和微分几何等方面都,做出了开创性贡献。他还把数学应用于天文学。大地测量学和磁学的研究，发明了最小二乘法原理。高斯的数论研究总结在算术研究(1801)中，这本书奠定了近代数论的基础，它不仅是数论方面划时代之作，也是数学史上不可多得的经典著作之一。高斯对代数学的重要贡献是证明了代数基本定理，他的存在性证明开创了数学研究的新途径。高斯在1816年左右就得到非欧几何的原理，发现椭圆函数的双周期性，但这些工作在他生前都没有发表出来。他还深入研究复变函数，建立了一些基本概念并发现了著名的柯西积分定理。1828年高斯出版了关于曲面的一般研究，全面系统阐述了空间,高斯(2),曲面的微分几何学，并提出了内蕴曲面理论。高斯的曲面理论后来由黎曼进一步发展。高斯一生共发表155篇学术论文，他对待学问十分严谨，只是把他自己认为是十分成熟的作品发表出来。其著作还有地磁概论(1839)和论与距离平方成反比的引力和斥力的普遍定律(1840)等。,高斯(3),高斯像(1),高斯像(2),高斯像(3),高斯像(4),2.2二分法,第二章方程求根,2.2二分法,定义：如果函数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,初始区间选择不合适,stop,给定f(x),a0,b0,(5)x=(a0+b0)/2,f=f(x)ifthenstop.,(6)Iff1f0,thenb0=x,f2=felsea0=x,f1=f,endif,(7)Goto(3),2.2二分法,定理2.1：如果区间a,b上的连续函数f应用二分算法,f(a)f(b)|f(xk+1)|。通常先令开始，若上式不成立则减半，直到上式成立,如果已经很小，上式仍不成立，则下山失败。,意味着新的若不满足下山条件，则加大上一步结果的权重。,2.5牛顿法下山法,例2.10用牛顿下山法求方程f(x)=x3-x-1=0在1.5附近的根，精确到7位有效数字，取x0=0.6。,2.5牛顿法下山法,解：应用牛顿下山公式,2.5牛顿法下山法,2.6割线法,第二章方程求根,在牛顿法中，需要计算f(x)的导数f(x)，有时不易求f(x),可以考虑用一个容易计算的近似值来代替f(x),2.6割线法,于是！,在开始迭代时,必须给定两个点(x0,x1),然后才能迭代，计算中要注意f(xk)-f(xk-1)的值以防止溢出,可以用,判断是否收敛。,作业：写出割线法的算法。,2.6割线法,2.7迭代过程加速方法,第二章方程求根,加速方法的构造,2.3迭代过程加速方法,假设在根x*附近变化不大，约为L，由微分中值定理有：,从上式整理得,于是,Aitken加速方法,为了避免计算L，记,用联立消去L,得,由此得Aitken迭代加速公式,2.3迭代过程加速方法,2.3迭代过程加速方法,2.3迭代过程加速方法,例2.11用迭代加速公式求在x=0.5附近的根。,解：,在x=0.5附近，经过三次迭代，得到x*=0.56714,2.3迭代过程加速方法,例2.12用Aitken方法求x3-x-1=0在x=1.5附近的根。,解：用Aitken迭代公式迭代5次，得到x*=1.32472,本章小结,第二章方程求根,本章介绍了求解非线性方程的数值方法：二分法，迭代法，牛顿法，割线法，还学习了牛顿下山法和迭代加速方法。,小结,二分法收敛速度慢，但总是收敛的，牛顿法在根的附近收敛速度非常快，是平方收敛，但收敛对初始值的选取要求苛刻，牛顿法还要求计算一阶导数，通常计算导数值的计算量大，有时