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

计算方法 (力学系本科生),第二章 方程求根 (Roots finding ),2.1 问题的提出,第二章 方程求根,2.1 问题的提出,实际问题,f(x)=0, f: R R,定义：如存在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 问题的提出,有多种数值算法可以求解非线性方程，我们在本章将学习其中得几种，它们是：,二分法(bisection method),迭代法(iteration method),牛顿法(Newton method),牛顿下山法(Newton downhill method)。,牛顿(1),牛顿(Newton Isaac 1643.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, Carl Friedrich 1777.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对于在a,b上有唯一单实根不充分也不必要。如图所示：,2.2 二分法,二分法实际上是一种简单的区间求根方法(Bracketing method)，区间法的基本思想是把方程的根限定在一个区间中，区间长度不断缩小，当区间长度充分小时就得到了近似解。二分法就是简单地每次把区间从中间一分为二，区间长度每次减半。,2.2 二分法,二分法具体作法：,二分初始选取区间a0,b0，使得f(a0)f(b0)0 ，说明根在区间 (a0+b0)/2, b0 ，令a1= (a0+b0)/2, b1=b0则得到更新区间a1,b1 。,2.2 二分法,不断重复这个过程直到 ， 为给定精度，于是得到方程根 。,新区间长度总是旧区间长度的一半，二分k次后区间假设为ak,bk，其长度为，,2.2 二分法,所以对于精度 ，由11111,得到循环次数为nnn,2.2 二分法,二分法的特点：,2.2 二分法,2)实施简单，仅需函数值,1)收敛总能得到保证,3) 收敛速度慢,二分法算法:,f1=f(a0), f2=f(b0),(3) if then stop.,if then stop.,(4) if then stop.,2.2 二分法,(2) if f1f20, 初始区间选择不合适, stop,给定f(x), a0, b0,(5) x=(a0+b0)/2, f=f(x) if then stop.,(6) If f1f0, then b0=x, f2=f else a0=x, f1=f, endif,(7) Goto (3),2.2 二分法,定理2.1：如果区间a,b上的连续函数f应用二分算法, f(a)f(b)0，则n步后将算出一个近似根，其误差至多为,2.2 二分法,例2.1 用二分法求方程f(x)=x3+4x2-10=0在区间1,1.5上的根，使得根误差不大于0.005，需要作几次二分？,2.2 二分法,解：由f(1)=-5, f(1.5)=2.375,且当 时， 知方程在所给区间内有唯一根。,2.2 二分法,由,得到,所以n=6就可以得到误差不大于0.005的近似根。,作业：证明1-x-sinx=0在0,1(x单位为弧度)内有唯一根，使用二分法求误差不大于5e-5的根要迭代多少次？,2.2 二分法,【思考题 2.1】如何编程用二分法计算区间内的N个实根(假设至少有N个实根)。,2.3 迭代法(iteration methods),第二章 方程求根,2.3 迭代法,基本思想: 设欲求方程f(x)=0的根, 变成形式 ,或 , 于是方程f(x)=0 的根是直线y=x与曲线 的交点。,用数学式表示迭代公式为：,如果迭代序列xk极限存在，则迭代收敛，并且 ；如果迭代序列xk极限不存在，则称迭代过程发散。,解法1：将原方程写成x=x3-1。取迭代函数 构造迭代格式,例2.2 用迭代法求x3-x-1=0在x0=1.5附近的根。,2.3 迭代法,以初值x0=1.5代入计算，得到如下结果,2.3 迭代法,很明显，xk发散，方法失败。,2.3 迭代法,解法2：将原方程写成 。取迭代函数 构造迭代格式,取初值x0=1.5，计算得到,2.3 迭代法,可见迭代8次，近似解已收敛于1.3247。,2.3 迭代法,解法1和解法2的情况可用下面两个图示意：,定理2.2 假设迭代函数 在a,b上存在一阶连续导数,且满足下列两个条件,2.3 迭代法,(1) 对于任意 有,(2) 存在正数L1，使对于任意 有,2.3 迭代法,(a)方程 在a,b上有唯一根,(b)对于 a,b内任意初始值,迭代 均收敛于方程根,(c)且有误差估计,则：,2.3 迭代法,条件(2)意味着 斜率小于1, 即曲线 比直线y=x更平。,几何解释：,条件(1)意味着初始及后续每次迭代函数值仍在初始区间a,b内；,2.3 迭代法,(a)作函数 。,所以必有 使,定理证明：,即,2.3 迭代法,再证根的唯一性。假设在区间a,b上存在两个根 ，则,由微分中值定理及条件(2)知存在,由于L0，必有 ，即根唯一。,2.3 迭代法,(b)由微分中值定理知，存在 使,反复利用上式，有,因为L1，所以 时,即,2.3 迭代法,(c)误差。注意到,于是,所以,2.3 迭代法,把,代入上式得,于是,2.3 迭代法,可以看出，L越小收敛越快，当L接近1时，收敛很慢。因为L为常数，所以一般用 来判断迭代收敛。,2.3 迭代法,2.3 迭代法,2.3 迭代法,2.3 迭代法,2.3 迭代法,定义 如果存在邻域 ，迭代过程 对于任意初始值 收敛，则称迭代过程在根 附近具有局部收敛性。,2.3 迭代法,定理2.3：设在方程 根x*附近有 连续一阶导数，且 ， 则迭代过程 具有局部收敛性。,使得,利用微分中值定理有,证明：取x*附近的一个 邻域,2.3 迭代法,由于,即,于是取 满足(1)对任意 ， ；(2)对任意,所以，迭代过程具有局部收敛性。,迭代法的收敛速度,2.3 迭代法,定义： 当 时，有 ，( 且为常数)，则称迭代过程是p阶收敛。特别地，当 p=1, 01时，称作超线性收敛； p=2时称作平方收敛。其中 称作迭代误差。,2.3 迭代法,由微分中值定理有,简单迭代法收敛速度一般是线性的。,简单迭代法的收敛速度。,2.3 迭代法,例2.3 设两个迭代格式分别是线性收敛和平方收敛的，且,若取精度 ，试估计这两个迭代格式各所需的迭代次数。,解：,2.3 迭代法,得,由,所以线性迭代格式需迭代54次。,2.3 迭代法,于是,所以,故平方收敛的迭代格式只需迭代6次。,2.3 迭代法,定理2.4：若 在 的根 附近有连续 阶导数且p-1阶导数全为零， , 则 p阶局部收敛，且有,如果p=1，要求,2.3 迭代法,证明：由定理2.3知，迭代格式局部收敛。应用泰勒级数展开并注意到p-1导数全为零，有,2.3 迭代法,于是,或,2.3 迭代法,于是,2.3 迭代法,例2.4 判断能不能直接用简单迭代法求解下列的方程？,解：判断方程 能否用简单迭代法求根，要看在根的邻域是否有,2.3 迭代法,对于(1)，,所以(1)可以用简单迭代法求解。,对于(2)，可知f(1)0, f(3)0,所以1,3为有根区间。,所以(2)不能用简单迭代法求解。,2.3 迭代法,例2.5 证明对于任何初始值 ,由迭代公式 所产生的序列 都收敛于 的根.,证明: 记 则,(1)当 ,故序列 收敛于 的根.,2.3 迭代法,(2)当对于任意 ,把 看作新的迭代初值,由(1)知命题得证.,2.3 迭代法,例2.6 利用迭代格式证明,证明: 考虑迭代格式,2.3 迭代法,则,记,2.3 迭代法,当 时,1.,所以迭代格式产生的序列 收敛于方程,在0,2内的唯一根x=2, 即,2.3 迭代法,作业：证明用迭代格式,产生的序列，对于 均收敛于,作业：为求方程 在,附近的一个根，将方程改写成为下列各式, 试分析各格式收敛性.,2.4 牛顿法(Newton method),第二章 方程求根,【历史注记】1685年Wallis出版了一本名为代数的书，描述了由牛顿发明的一种求解方程的方法。1690年Raphson也发表了这个方法，但略有修改。于是现在通常把这个方法叫牛顿法或Newton-Raphson法。事实上，牛顿本人在1669年就讨论了这个方法，并以方程x3-2x-5=0 为例作了说明，Wallis在其著作中也使用了这个例子，此后每一个学数值分析的学生都认识这个历史悠久的方程。,2.4 牛顿法,牛顿法的解释：使用牛顿法时总假设函数f(x)是一阶可微的，这在几何上 f(x)表示的图形(曲线)在每个点上都有确定的斜率，因而有唯一切线。现在我们利用线性化的思想，设曲线 f(x)上某一点(x0,f(x0)有一条切线，该切线在该点的近旁是f(x)曲线的一个很好近似(以直代曲)。,2.4 牛顿法,2.4 牛顿法,从分析观点来讲，这种以直线代曲线就意味着切线线性函数,在x0的近旁接近于函数f(x)，并且在x0处l(x)和f(x)值相等。因此，可取l(x)的零点为f(x)零点的一个近似。,2.4 牛顿法,l(x)的零点为x1=x0-f(x0)/f(x0)。这样，从初始点x0出发，由上式就得到了一个新点，重复这个过程(迭代)，就能产生一系列点,2.4 牛顿法,如果收敛的话，这个点列将趋向于f(x)的一个零点。,还可以用另外的方式说明牛顿法。假设x0是对于f(x)的一个根的近似，可以想象，如果给x0加上一个修正值h就可以成为f(x)的精确根，即f(x+h)=0。如果f(x)的各阶导数在x0处存在，则f(x)在x0处泰勒展开为,2.4 牛顿法,用上式很难求出h，于是考虑线性化，对于上式进行截断,于是,2.4 牛顿法,得到一个新的近似根，,重复这个过程就是牛顿法。,回顾前面过程，可以发现，实际上并不需要有二阶导数，因为我们只使用了泰勒展开的前两项，仅要求在根的一个邻域中导数连续即可。,2.4 牛顿法,牛顿法是方程求根十分重要和有效的方法，其基本思想是将非线性方程线性化构造迭代公式。,设方程f(x)=0有近似根xk，将函数f(x)在xk处一阶泰勒展开,2.4 牛顿法,于是方程线性化为,这个线性化方程的根为,按照迭代法，其迭代函数为,2.4 牛顿法,牛顿法的收敛速度,牛顿法可以看成迭代公式,如果x*是f(x)=0的一个单根，则f(x*)=0，,于是由上节定理知牛顿法有二阶收敛速度。,2.4 牛顿法,【注记】可以证明对于重根情形，牛顿法是1阶局部收敛。,迭代收敛判据有：,2.5 牛顿法下山法,第k次迭代xk充分接近于方程根x*，|f(xk)|充分小，接近于零。这两个判据不等价，第一个能严格保证收敛，第二个并不能。虽然第一个判据很严格，但是实现起来有困难，因为x*未知，第二个判据尽管不严格，但易于实现。 后两个判据在实际中采用较多。,2.5 牛顿法下山法,牛顿法算法,2.4 牛顿法,以及最大迭代次数N。,已知函数f(x)及f(x),给定x0,2.4 牛顿法,2.4 牛顿法,例2.7 用牛顿法求方程 在x=0.5附近的根。,2.4 牛顿法,解：把方程写成 于是,取x0=0.5，得到,2.4 牛顿法,用简单迭代法 得,2.4 牛顿法,例2.8 用牛顿法求Leonardo方程,的根,设x0=2，要求,解：,2.4 牛顿法,故,【注】Leonardo在1225年研究了该方程，并得到x=1.368808107的结果，此时f(x)=-0.000000009，这在当时是非常重要的结果，但无人知道他是如何得到的。,例2.9 用牛顿法求 的近似值，精度 。,2.4 牛顿法,解：化为求x2-115=0的正根，牛顿迭代公式为,取初值x0=10，经过4次迭代，得x*=10.723805,【思考题 】对于牛顿迭代公式，证明,2.4 牛顿法,2.5 牛顿下山法,第二章 方程求根,牛顿法的收敛性和初始迭代值有关，如果初始迭代值离方程根较近，则迭代收敛性可以保证；如果初始值距离方程根较远，则收敛过程可能发散。但是通常情况下很难给出一个离根较近的初始值，因为根无法预先知道。,2.5 牛顿法下山法,我们发现这样一个事实：通常在根附近|f(x)|是单调下降的，即越接近根， |f(x)|越小，所以|f(xk)|f(xk+1)| 。于是我们把这个条件作为一个约束引入到迭代方程。满足这个约束条件的算法叫下山法。,2.5 牛顿法下山法,具体作法：先得到牛顿法结果,把 与xk作加权平均得到：,叫下山因子, 时即为牛顿法。,2.5 牛顿法下山法,可以通过选取 值使得|f(xk)|f(xk+1)|。通常先令 开始，若上式不成立则 减半，直到上式成立,如果 已经很小，上式仍不成立，则下山失败。,意味着新的 若不满足下山条件，则加大上一步结果的权重。,2.5 牛顿法下山法,例2.10 用牛顿下山法求方程f(x)=x3-x-1=0在1.5附近的根，精确到7位有效数