《《方程求根的二分法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《方程求根的二分法》PPT课件.ppt（26页珍藏版）》请在金锄头文库上搜索。
1、第六章非线性方程组的迭代解法 教学目的教学目的 1. 掌握解非线性方程（组）的二分法和插值法；掌握解非线性方程（组）的二分法和插值法； 2. 掌握解非线性方程（组）的一般迭代法及有关收敛性掌握解非线性方程（组）的一般迭代法及有关收敛性的证明与牛顿法；的证明与牛顿法； 3. 掌握解非线性方程（组）的牛顿法掌握解非线性方程（组）的牛顿法 4. 了解加速收敛的方法。了解加速收敛的方法。教学重点及难点教学重点及难点 重点重点是解非线性方程（组）的牛顿法；是解非线性方程（组）的牛顿法；难点难点是迭代法的收敛性的证明。是迭代法的收敛性的证明。 第第6章章 非线性方程和方程组非线性方程和方程组的数值解法的数
2、值解法第六章非线性方程组的迭代解法 代数方程求根问题是一个古老的数学问题代数方程求根问题是一个古老的数学问题. .早在早在1616世纪就找到了三次，四次方程的求根公式世纪就找到了三次，四次方程的求根公式. .但直到但直到1919世世纪才证明了纪才证明了n5 5次的一般代数方程式不能用代数公式求次的一般代数方程式不能用代数公式求解解. .因此需要研究用数值方法求得满足一定精度的代数因此需要研究用数值方法求得满足一定精度的代数方程式的近似解方程式的近似解. . 而在工程和科学技术中许多问题常归结为求解非而在工程和科学技术中许多问题常归结为求解非线性方程式问题。例如在控制系统的设计领域中，在线性方程
3、式问题。例如在控制系统的设计领域中，在研究人口增长率等问题中都最后可化为方程求根的问研究人口增长率等问题中都最后可化为方程求根的问题。题。第第6章章 非线性方程和方程组非线性方程和方程组的数值解法的数值解法第六章非线性方程组的迭代解法 6.1 6.1 引言引言 在在科科学学研研究究和和工工程程设设计计中中, , 经经常常会会遇遇到到的的一一大大类类问问题题是非线性方程是非线性方程 f(x)=0 (6.1)的求根问题，其中的求根问题，其中f(x)为非线性函数为非线性函数。 方程方程f(x)=0的根的根, 亦称为函数亦称为函数f(x)的零点的零点 如如果果f(x)可可以以分分解解成成 , 其其中中
4、m为为正正整整数数且且 ,则则称称x*是是f(x)的的m重重零零点点,或或称称方方程程f(x)=0的的m重重根根。当当m=1时时称称x*为为单单根根。若若f(x)存存在在m阶阶导导数数,则则是是方方程程f(x)的的m重重根根(m1) 当且仅当当且仅当第六章非线性方程组的迭代解法 当当 f (x)不是不是x的线性函数时，称对应的函数方程为非线性的线性函数时，称对应的函数方程为非线性方程。如果方程。如果f(x)是多项式函数，则称为是多项式函数，则称为代数方程代数方程，否则称为，否则称为超超越方程越方程（三角方程，指数、对数方程等）。一般称（三角方程，指数、对数方程等）。一般称n次多项式次多项式构成
5、的方程构成的方程 为为n次代数方程次代数方程, ,当当n1时时, ,方程显然是非线性的方程显然是非线性的. . 一般稍微复杂的一般稍微复杂的3 3次以上的代数方程或超越方程次以上的代数方程或超越方程, ,很难甚很难甚至无法求得精确解。本章将介绍常用的求解非线性方程的近至无法求得精确解。本章将介绍常用的求解非线性方程的近似根的几种数值解法似根的几种数值解法. . 第六章非线性方程组的迭代解法 通常方程根的数值解法大致分为三个步骤进行通常方程根的数值解法大致分为三个步骤进行通常方程根的数值解法大致分为三个步骤进行通常方程根的数值解法大致分为三个步骤进行判定根的存在性。即方程有没有根？如果有判定根的
6、存在性。即方程有没有根？如果有判定根的存在性。即方程有没有根？如果有判定根的存在性。即方程有没有根？如果有 根，有几个根？根，有几个根？根，有几个根？根，有几个根？确定根的分布范围。即将每一个根用区间隔确定根的分布范围。即将每一个根用区间隔确定根的分布范围。即将每一个根用区间隔确定根的分布范围。即将每一个根用区间隔 离开来，这个过程实际上是获得方程各根的离开来，这个过程实际上是获得方程各根的离开来，这个过程实际上是获得方程各根的离开来，这个过程实际上是获得方程各根的 初始近似值初始近似值初始近似值初始近似值. . . .根的精确化。将根的初始近似值按某种方法根的精确化。将根的初始近似值按某种方
7、法根的精确化。将根的初始近似值按某种方法根的精确化。将根的初始近似值按某种方法 逐步精确化，直到满足预先要求的精度为止逐步精确化，直到满足预先要求的精度为止逐步精确化，直到满足预先要求的精度为止逐步精确化，直到满足预先要求的精度为止. . . . 第六章非线性方程组的迭代解法 本章介绍方程的迭代解法，它既可以用来求解代本章介绍方程的迭代解法，它既可以用来求解代数方程，也可以用来解超越方程，并且仅限于求数方程，也可以用来解超越方程，并且仅限于求方程的实根。方程的实根。运用迭代法求解方程的根应解决以下两个问题：运用迭代法求解方程的根应解决以下两个问题：确定根的初值确定根的初值; ;将进一步精确化到
8、所需要的精度。将进一步精确化到所需要的精度。第六章非线性方程组的迭代解法 6.2 二分法二分法 二分法又称二分区间法二分法又称二分区间法, ,是求解方程是求解方程(2.1)(2.1)的近似的近似根的一种常用的简单方法。根的一种常用的简单方法。 设函数设函数f(x)在闭区间在闭区间 a,b 上连续上连续, ,且且f( (a) )f( (b)0,)0,根根据连续函数的性质可知据连续函数的性质可知, , f(x)= 0在在( (a,b) )内必有实根内必有实根, ,称区间称区间 a,ba,b为有根区间。为明确为有根区间。为明确起见起见, ,假定方程假定方程f(x)=0在区间在区间 a,b 内有惟一实
9、根内有惟一实根x* *。 二分法的基本思想是二分法的基本思想是: : 首先确定有根区间首先确定有根区间, ,将区将区间二等分间二等分, , 通过判断通过判断f(x)的符号的符号, , 逐步将有根区间缩逐步将有根区间缩小小, , 直至有根区间足够地小直至有根区间足够地小, , 便可求出满足精度要求便可求出满足精度要求的近似根。的近似根。第六章非线性方程组的迭代解法 确定有根区间的方法确定有根区间的方法 为了确定根的初值，首先必须圈定根所在的范围，为了确定根的初值，首先必须圈定根所在的范围， 称为称为圈定根或根的隔离圈定根或根的隔离。 在上述基础上，采取适当的数值方法确定具有一定在上述基础上，采取
10、适当的数值方法确定具有一定 精度要求的初值。精度要求的初值。 对于代数方程，其根的个数（实或复的）与其次数对于代数方程，其根的个数（实或复的）与其次数 相同。至于超越方程，其根可能是一个、几个相同。至于超越方程，其根可能是一个、几个或无或无 解，并没有什么固定的圈根方法解，并没有什么固定的圈根方法 求方程根的问题，就几何上讲求方程根的问题，就几何上讲, ,是求曲线是求曲线 y=f (x)与与 x x轴交点的横坐标。轴交点的横坐标。第六章非线性方程组的迭代解法 由高等数学知识知由高等数学知识知, , 设设f (x)为区间为区间 a,ba,b上的单上的单值连续值连续, , 如果如果f (a)f (
11、b)0 , , 则则 a,b 中至少有一个实中至少有一个实根。如果根。如果f (x)在在 a,b 上还是单调地递增或递减，则上还是单调地递增或递减，则仅有一个实根。仅有一个实根。n由此可大体确定根所在子区间，方法有：由此可大体确定根所在子区间，方法有： (1) (1) 画图法画图法 (2) (2) 逐步搜索法逐步搜索法y=f(x)y=f(x)a ab by yx x第六章非线性方程组的迭代解法 (1) 画图法画图法 画出y = f (x)的略图，从而看出曲线与x轴交点的 大致位置。 也可将f (x) = 0分解为1(x)= 2(x)的形式，1(x) 与 2(x)两曲线交点的横坐标所在的子区间即
12、为含根 区间。例如 xlogx-1= 0可以改写为logx=1/x画出对数曲线y=logx,与双曲线y= 1/x,它们交 点的横坐标位于区间2,3内第六章非线性方程组的迭代解法 (1) 画图法画图法023yx第六章非线性方程组的迭代解法 n对于某些看不清根的函数，可以扩大一下曲线对于某些看不清根的函数，可以扩大一下曲线y0xy=f(x)y=kf(x)(1) (1) (1) 画图法画图法画图法画图法画图法画图法第六章非线性方程组的迭代解法 y0xABa1b1a2b2(2) 逐步搜索法逐步搜索法(2) (2) 搜索法搜索法 对于给定的对于给定的f (x),设有根区间为设有根区间为A,B,从从x0=
13、A出发出发,以步长以步长h=(B-A)/n(n是正整数是正整数),在在A,B内取定节点内取定节点:xi=x0ih (i=0,1,2,n),从左至右检查从左至右检查f (xi)的符号的符号,如发现如发现xi与端点与端点x0的函数值异号的函数值异号,则得到一个缩小的有根子区间则得到一个缩小的有根子区间xi-1,xi。第六章非线性方程组的迭代解法 例例1 方程方程f(x)=x3-x-1=0 确定其有根区间确定其有根区间解：用试凑的方法，不难发现解：用试凑的方法，不难发现 f(0)0 在区间在区间（0,2）内至少有一个实根内至少有一个实根 设从设从x=0出发出发,取取h=0.5为为步长向右进行根的搜索
14、步长向右进行根的搜索,列表如列表如下下xf(x)0 0.5 1.0 1.5 2 + +可以看出，在可以看出，在1.0,1.5内必有一根内必有一根第六章非线性方程组的迭代解法 用逐步搜索法进行实根隔离的关键是选取步长用逐步搜索法进行实根隔离的关键是选取步长h 要选择适当要选择适当h ，使之既能把根隔离开来，工作量，使之既能把根隔离开来，工作量 又不太大。又不太大。 为获取指定精度要求的初值为获取指定精度要求的初值, ,可在以上隔离根的可在以上隔离根的 基础上采用对分法继续缩小该含根子区间基础上采用对分法继续缩小该含根子区间 二分法可以看作是搜索法的一种改进。二分法可以看作是搜索法的一种改进。第六
15、章非线性方程组的迭代解法 3方程求根的二分法方程求根的二分法(对分法或分半法对分法或分半法) (bisection method)1 1 条件条件2 2 主要依据主要依据 由连续函数介值定理由连续函数介值定理, ,则至少存在某个则至少存在某个即即 a,b 内至少有方程内至少有方程(2.1)(2.1)的一个根的一个根, ,称称 a,b 为为f( (x) ) 的一个的一个含根区间含根区间。3 3 主要思想（基本思想）主要思想（基本思想）把含根区间不断缩短，使含根区间之间含有一个满足误差把含根区间不断缩短，使含根区间之间含有一个满足误差要求的近似解。要求的近似解。考虑非线性方程考虑非线性方程 f (
16、x)=0 0 (6.1(6.1) ) 并且有并且有 第六章非线性方程组的迭代解法 (3) 生成含根区间：生成含根区间：4 4 具体过程（方法）具体过程（方法）满足下式满足下式: :生成含根区间生成含根区间第六章非线性方程组的迭代解法 , ,满足：满足：(3) 生成含根区间：生成含根区间：, ,满足（满足（6.26.2）式，）式，即即生成含根区间生成含根区间一般的一般的, ,第六章非线性方程组的迭代解法 满足（满足（6.26.2）式，即）式，即含根区间含根区间近似解序列近似解序列其极限为其极限为即序列即序列收敛于收敛于的一个根的一个根即即且且说明说明: :只要只要就有就有此时可计算或估计二分法执
17、行的次数此时可计算或估计二分法执行的次数k.对于给定的误差界对于给定的误差界第六章非线性方程组的迭代解法 事实上事实上, ,由由两边取对数得两边取对数得可取可取1.1.对函数要求低对函数要求低 ( (只要连续只要连续, ,在两个端点异号在两个端点异号) )。优点优点: :2.2.二分法是收敛的。二分法是收敛的。第六章非线性方程组的迭代解法 例例不能求出所有根不能求出所有根,(,(即有可能漏根即有可能漏根) )。例例如图如图该点可求出该点可求出, ,注注1 1 : :改进的方法，改进的方法，试位法（比例求根法）。试位法（比例求根法）。但漏掉了四个点但漏掉了四个点2.2.不能用于求偶重根、复根；不
18、能推广到多元方程组求解不能用于求偶重根、复根；不能推广到多元方程组求解；缺点缺点: : 的等比级数的收敛速度的等比级数的收敛速度相同。相同。1.1.收敛速度不快收敛速度不快, ,仅与公比为仅与公比为 即是线性收敛的。即是线性收敛的。注注2 2 : :另外还有区间搜索法。另外还有区间搜索法。第六章非线性方程组的迭代解法 实根，要求准确到小数点后的第实根，要求准确到小数点后的第2位。位。解解例例6.1第六章非线性方程组的迭代解法 1.32031.32811.3242-1.31251.32811.3203-1.31251.34381.3281+1.31251.3751.3438+1.251.3751
19、.3125-1.251.51.375+11.51.25-6543210表表6-1 第六章非线性方程组的迭代解法 例例 证明方程证明方程 在区间在区间2, 32, 3内有一个内有一个根根, , 使用二分法求误差不超过使用二分法求误差不超过0.50.51010-3 -3 的根要二的根要二分多少次？分多少次？证明证明 令令 且f(x)在2, 3上连续,故方程f(x)=0在2,3内至少有一个根。又 当时时， ,故f(x)在2, 3上是单调递增函数,从而f(x)在2, 3上有且仅有一根。 给定误差限给定误差限 0.510-3 , ,使用二分法时使用二分法时第六章非线性方程组的迭代解法 误差限为 只要取k
20、满足 即可，亦即 所以需二分所以需二分1010次便可达到要求。次便可达到要求。 二分法的优点是不管有根区间二分法的优点是不管有根区间 多大多大, ,总能总能求出满足精度要求的根求出满足精度要求的根, ,且对函数且对函数f(x)的要求不高的要求不高, ,只只要连续即可要连续即可, ,计算亦简单计算亦简单; ;它的局限性是只能用于求它的局限性是只能用于求函数的实根函数的实根, ,不能用于求复根及重根不能用于求复根及重根, ,它的收敛速度它的收敛速度与比值为与比值为 的等比级数相同。的等比级数相同。 第六章非线性方程组的迭代解法 上述二分法的优点是算法简单上述二分法的优点是算法简单,而且在有限区间内而且在有限区间内,收敛性总能得到保证收敛性总能得到保证.值得注意的是值得注意的是,为了求出足够精确为了求出足够精确的近似解的近似解,往往需要计算很多次函数值往往需要计算很多次函数值,是一种收敛较慢是一种收敛较慢的方法的方法,通常用通常用二分法二分法给出根的大致范围给出根的大致范围,再利用下面将再利用下面将介绍的更有效的方法求解方程介绍的更有效的方法求解方程.另一方面，二分法只使另一方面，二分法只使用于求一元方程的奇数重实根用于求一元方程的奇数重实根.
