方程求根计算方法

《方程求根计算方法》由会员分享，可在线阅读，更多相关《方程求根计算方法（128页珍藏版）》请在金锄头文库上搜索。

1、计算方法 (力学系本科生)第二章第二章 方程求根方程求根(Roots finding )(Roots finding )2.1 问题的提出 第二章 方程求根2.1 问题的提出实际问题f(x)=0, f: R R定义：如存在x*使得f(x*)=0 则称x*为方程的根或函数f(x)的零点。 特别地，如果m=1x*为f(x)=0的单根或f(x)的单零点m1x*为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 问题的提出Remar

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

3、索了高次方程的数值解 的求法。巴比伦泥板中有平方表和立方表，利用它 们可以解某些特殊的二次和三次方程。中国古人相 当系统地解决了求高次方程数值解的问题，九章 算术以算法形式给出了二次方程及正系数三次方 程正根的具体计算程序；7世纪王孝通也给出了求 三次方程正根的数值解法；11世纪贾宪在黄帝九 章算法细草中创“开方作法本源图”,用“立成释锁 法”解三次和三次以上高次方程, 同时他又提出一种 更为简便的“增乘开方法”；13世纪秦九韶在数书 九章中的“正负开方术”最后完成，提供了一个用 算筹布列解任何次数字方程的可行算法。2.1 问题的提出阿拉伯人对高次代数方程的数值解法亦有研究，花 拉子米(9世纪

4、)第一个给出了二次方程的一般解法, 奥马海亚姆(1100年)给出了一些特殊三次方程的解 法。1541年塔尔塔利亚得到三次方程的一般解法。 1545年卡尔达诺在其名著大术一书中发展了塔 尔塔利亚的这一成果，并记载了费拉里得到的四次 方程的一般解法。牛顿在1736年出版的流数法 一书中，给出了著名的高次代数方程的一种数值解 法,1690年Raphson 也提出了类似的方法，它们的结 合就是现代常用的方法牛顿法(也叫Newton- Raphson方法)。它是一种广泛用于高次代数方程求 解的迭代法，亦称为切线法，并不断产生新的变形 ,2.1 问题的提出如修正牛顿法，拟牛顿法等。1797年，高斯给出“

5、代数基本定理”，指出高次代数方程根的存在性。 1819年，霍纳提出求高次代数方程数值解的另一种 方法霍纳法，其思想及计算程序与秦九韶的方 法近似，类似的方法鲁非尼在1804年也提出过，霍 纳法也有广泛的应用，它的现代改进形式叫劈因子 法。现在常用的代数方程数值解法还有伯努利法和 劳斯表格法。2.1 问题的提出 有多种数值算法可以求解非线性方程， 我们在本章将学习其中得几种，它们是 ： 二分法(bisection method) 迭代法(iteration method) 牛顿法(Newton method) 牛顿下山法(Newton downhill method)。 牛顿(1)牛顿(Newt

6、on Isaac 1643.1.4-1727.3.31)：英国数学 家、物理学家、天文学家、自然哲学家。生于林肯 郡伍尔索普，卒于伦敦。早年在格兰瑟姆读书， 1661年以优异成绩考入剑桥大学三一学院，数学上 受教于巴罗。1664年毕业后曾为躲避鼠疫回乡， 16651666年做出流数法、万有引力和光的分析三 大发明，年仅23岁。1667年回剑桥在三一学院执教 。1669年继巴罗之后任卢卡斯数学教授职位。晚年 致力于哲学和公务，1696年任造币厂监督，3年后 任厂长。1703年当选为英国皇家学会主席。他在数 学上以创建微积分学而著名，其流数法始于1665年 ，系统叙述于流数法和无穷级数(1671年

7、完成，1736年出版)，首先发表在自然哲学的数学 原理(1687)中。其中借助运动学中描述的连续量 及其变化率阐述他的流数理论，并创用字母上加一 点表示流动变化率。讨论的基本问题是：已知流量 间的关系，求它们的流数的关系以及逆运算，确定 了微分与积分这两类运算的互逆关系，即微积分学 基本定理。此外，他还论述了有理指数的二项式定 理(1664年)，n次代数方程根的m次幂和的公式 (1707年)，数论、解析几何学、曲线分类、变分法 等问题。在物理学上发现了万有引力定律(1666- 1684)，并据此指出行星运行成椭圆轨道的原因。 1666年用三棱镜实验光的色散现象，1668年发明并牛顿(2)亲手制

8、作了第一具反射望远镜。在哲学上深信物质 、运动、空间和时间的客观存在性，坚持用观察和 实验方法发现自然界的规律，力求用数学定量方法 表述的定律说明自然现象，其科学研究方法支配后 世近300年的物理学研究。牛顿(3)牛顿像(1)牛顿像(2)牛顿像(3)牛顿像(4)牛顿像(5)牛顿像(6)牛顿像(7)牛顿像(8)高斯(1)高斯(Gauss, Carl Friedrich 1777.4.30-1855.2.23)：德 国数学家、物理学家、天文学家。生于不伦瑞克， 卒于格丁根。高斯是近代数学奠基者之一，在历史 上影响之大，可以和阿基米德、牛顿、欧拉并列。 他幼年时就表现出超人的数学天才。1795年进入

9、格 丁根大学学习。第二年他发现正十七边形的尺规作 图法，并给出可用尺规作出的正多边形的条件，解 决了欧几里得以来悬而未决的问题。1798年转入黑 尔姆施泰特大学，1799年获博士学位。1807年以后 一直在格丁根大学任教授。高斯的数学研究几乎遍及所有领域，在数论、 代数学、非欧几何、复变函数和微分几何等方面都做出了开创性贡献。他还把数学应用于天文学。大 地测量学和磁学的研究，发明了最小二乘法原理。 高斯的数论研究总结在算术研究(1801)中，这 本书奠定了近代数论的基础，它不仅是数论方面划 时代之作，也是数学史上不可多得的经典著作之一 。高斯对代数学的重要贡献是证明了代数基本定理 ，他的存在性

10、证明开创了数学研究的新途径。高斯 在1816年左右就得到非欧几何的原理，发现椭圆函 数的双周期性，但这些工作在他生前都没有发表出 来。他还深入研究复变函数，建立了一些基本概念 并发现了著名的柯西积分定理。1828年高斯出版了 关于曲面的一般研究，全面系统阐述了空间高斯(2)曲面的微分几何学，并提出了内蕴曲面理论。高斯 的曲面理论后来由黎曼进一步发展。高斯一生共发 表155篇学术论文，他对待学问十分严谨，只是把 他自己认为是十分成熟的作品发表出来。其著作还 有地磁概论(1839)和论与距离平方成反比的 引力和斥力的普遍定律(1840)等。高斯(3)高斯像(1)高斯像(2)高斯像(3)高斯像(4)

11、2.2 二分法第二章 方程求根2.2 二分法v 定义：如果函数f(x)在区间a,b上连 续，且f(a)f(b)0时在a,b 上有根的情形。即，f(a)f(b)0但有实根abxf(x)2.2 二分法 二分法实际上是一种简单的区间求根 方法(Bracketing method)，区间法的基本 思想是把方程的根限定在一个区间中， 区间长度不断缩小，当区间长度充分小 时就得到了近似解。二分法就是简单地 每次把区间从中间一分为二，区间长度 每次减半。 2.2 二分法 二分法具体作法：二分初始选取区间a0,b0，使得 f(a0)f(b0)0 ，说明根在 区间 (a0+b0)/2, b0 ，令a1= (a0

12、+b0)/2, b1=b0则得到更新区间a1,b1 。2.2 二分法不断重复这个过程直到 ， 为给 定精度，于是得到方程根 。 新区间长度总是旧区间长度的一半，二 分k次后区间假设为ak,bk，其长度为，2.2 二分法所以对于精度 ，由11111得到循环次数为nnn2.2 二分法 二分法的特点：2.2 二分法2)实施简单，仅需函数值1)收敛总能得到保证3) 收敛速度慢 二分法算法:(1) f1=f(a0), f2=f(b0)(3) if then stop. if then stop. (4) if then stop.2.2 二分法(2) if f1f20, 初始区间选择不合适, stop给

13、定f(x), a0, b0,(5) x=(a0+b0)/2, f=f(x) if then stop.(6) If f1f0，必有 ，即根唯一。 2.3 迭代法(b)由微分中值定理知，存在 使反复利用上式，有 因为L1时，称作超线性收敛； p=2时称作平方收敛。其中 称 作迭代误差。 2.3 迭代法由微分中值定理有 简单迭代法收敛速度一般是线性的。 简单迭代法的收敛速度。2.3 迭代法F例2.3 设两个迭代格式分别是线性收 敛和平方收敛的，且若取精度 ，试估计这两个迭代格 式各所需的迭代次数。 解：2.3 迭代法得由所以线性迭代格式需迭代54次。2.3 迭代法于是所以故平方收敛的迭代格式只需迭

14、代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)|f(xk+1)| 。于是我们把 这个条件作为一个约束引入到迭代方程 。满足这个约束条件的算法叫

15、下山法。 2.5 牛顿法下山法 具体作法：先得到牛顿法结果把 与xk作加权平均得到： 叫下山因子, 时即为牛顿法。2.5 牛顿法下山法 可以通过选取 值使得|f(xk)|f(xk+1)|。 通常先令 开始，若上式不成立则 减 半，直到上式成立 如果 已经很小，上式仍不成立，则下 山失败。 意味着新的 若不满足下山条件，则加 大上一步结果的权重。2.5 牛顿法下山法F 例2.10 用牛顿下山法求方程f(x)=x3-x- 1=0在1.5附近的根，精确到7位有效数字 ，取x0=0.6。2.5 牛顿法下山法解：应用牛顿下山公式2.5 牛顿法下山法kxkf(xk)010.6-1.3840001117.8999805716.42101/29.249990781.200701/321.140624-0