非线性方程的数值求法-二分法和简单迭代法.ppt

第七章 非线性方程与方程组的数值解法,引言 在科学研究和工程设计中,经常会遇到的一大类问题是非线性方程f(x)=0的求根问题，其中f(x)为非线性函数。方程f(x)=0的根,亦称为函数f(x)的零点 如果f(x)可以分解成,其中m为正整数且,则称x*是f(x)的m重零点,或称方程f(x)=0的m重根。当m=1时称x*为单根。若f(x)存在m阶导数,则x*是方程f(x)的m重根(m1)当且仅当,记笔记,当f(x)不是x的线性函数时，称对应的函数方程为非线性方程。如果f(x)是多项式函数，则称为代数方程，否则称为超越方程（三角方程，指数、对数方程等）。一般称n次多项式构成的方程,为n次代数方程,当n1时,方程显然是非线性的 一般稍微复杂的3次以上的代数方程或超越方程,很难甚至无法求得精确解。本章将介绍常用的求解非线性方程的近似根的几种数值解法,记笔记,通常方程根的数值解法大致分为三个步骤进行判定根的存在性。即方程有没有根？如果有 根，有几个根？确定根的分布范围。即将每一个根用区间隔 离开来，这个过程实际上是获得方程各根的 初始近似值。根的精确化。将根的初始近似值按某种方法 逐步精确化，直到满足预先要求的精度为止,本章介绍方程的迭代解法，它既可以用来求解代数方程，也可以用来解超越方程，并且仅限于求方程的实根。运用迭代法求解方程的根应解决以下两个问题：确定根的初值;将进一步精确化到所需要的精度。,记笔记,7.1 二分法,二分法又称二分区间法,是求解非线性方程的近似根的一种常用的简单方法。设函数f(x)在闭区间a,b上连续,且f(a)f(b)0,根据连续函数的性质可知,f(x)=0在(a,b)内必有实根,称区间a,b为有根区间。为明确起见,假定方程f(x)=0在区间a,b内有惟一实根x*。二分法的基本思想是:首先确定有根区间,将区间二等分,通过判断f(x)的符号,逐步将有根区间缩小,直至有根区间足够地小,便可求出满足精度要求的近似根。,确定有根区间的方法,为了确定根的初值，首先必须圈定根所在的范围，称为圈定根或根的隔离。在上述基础上，采取适当的数值方法确定具有一定 精度要求的初值。对于代数方程，其根的个数（实或复的）与其次数 相同。至于超越方程，其根可能是一个、几个或无 解，并没有什么固定的圈根方法 求方程根的问题，就几何上讲,是求曲线 y=f(x)与 x轴交点的横坐标。,由高等数学知识知,设f(x)为区间a,b上的单值连续,如果f(a)f(b)0,则a,b中至少有一个实根。如果f(x)在a,b上还是单调地递增或递减，则仅有一个实根。,记笔记,由此可大体确定根所在子区间，方法有：(1)画图法(2)逐步搜索法,y=f(x),a,b,y,x,(1)画图法,画出y=f(x)的略图，从而看出曲线与x轴交点的 大致位置。也可将f(x)=0分解为1(x)=2(x)的形式，1(x)与 2(x)两曲线交点的横坐标所在的子区间即为含根 区间。例如 xlogx-1=0可以改写为logx=1/x画出对数曲线y=logx,与双曲线y=1/x,它们交 点的横坐标位于区间2,3内,(1)画图法,0,2,3,y,x,对于某些看不清根的函数，可以扩大一下曲线,(1)画图法,记笔记,A,B,(2)逐步搜索法,(2)搜索法,对于给定的f(x),设有根区间为A,B,从x0=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为步长向右进行根的 搜索,列表如下,x,f(x),0 0.5 1.0 1.5 2,+,可以看出，在1.0,1.5内必有一根,用逐步搜索法进行实根隔离的关键是选取步长h 要选择适当h，使之既能把根隔离开来，工作量 又不太大。为获取指定精度要求的初值,可在以上隔离根的 基础上采用对分法继续缩小该含根子区间 二分法可以看作是搜索法的一种改进。,取有根区间a,b之中点,将它分为两半,分点,这样就可缩小有根区间,7.1.2 二分法求根过程,设方程f(x)=0在区间a,b内有根,二分法就是逐步收缩有根区间，最后得出所求的根。具体过程如下,对压缩了的有根区间 施行同样的手法,即取中点,将区间 再分为两半,然 后再确定有根区间,其长度是 的 二分之一 如此反复下去,若不出现,即可得出一 系列有根区间序列：上述每个区间都是前一个区间的一半,因此 的长度,当k时趋于零,这些区间最终收敛于一点x*即为 所求的根。,每次二分后,取有根区间 的中点作为根的近似值，得到一个近似根的序列 该序列以根x*为极限 只要二分足够多次(即k足够大),便有这里为给定精度,由于,则,当给定精度0后,要想 成立,只要取k满足 即可，亦即当:,时,做到第k+1次二分,计算得到的 就是满足精度要求的近似根。在程序中通常用相邻的 与 的差的绝对值或 与 的差的绝对值是否小于来决定二分区间的次数。,二分法算法实现,例 设 已知，求在区间1.5,2内根的近似值.计算结果列表如下：,取,误差限,例 证明方程 在区间2,3内有一个根 使用二分法求误差不超过0.510-3 的根要二 分多少次？证明 令,且f(x)在2,3上连续,故方程f(x)=0在2,3内至少有一个根。又 当时，,故f(x)在2,3上是单调递增函数,从而f(x)在2,3上有且仅有一根。,给定误差限 0.510-3,使用二分法时,误差限为 只要取k满足,即可，亦即,所以需二分10次便可达到要求。二分法的优点是不管有根区间 多大,总能求出满足精度要求的根,且对函数f(x)的要求不高,只要连续即可,计算亦简单;它的局限性是只能用于求函数的实根,不能用于求复根及重根。,7.2 不动点迭代法及其收敛性,对于一般的非线性方程,没有通常所说的求根公式求其精确解,需要设计近似求解方法,即迭代法。它是一种逐次逼近的方法,用某个固定公式反复校正根的近似值,使之逐步精确化，最后得到满足精度要求的结果。,7.2.1 迭代法的基本思想 为求解非线性方程f(x)=0的根，先将其写成便于迭代的等价方程(5.3)其中 为x的连续函数,即如果数 使f(x)=0,则也有,反之,若,则也有,称 为迭代函数 任取一个初值,代入式 的右端,得到,再将 代入式 的右端,得到,依此类推,得到一个数列，其一般表示,式(5.4)称为求解非线性方程的简单迭代法。,(5.4),如果由迭代格式 产生的序列 收敛,即,则称迭代法收敛。,实际计算中当然不可能也没必要无穷多步地做下去,对预先给定的精度要求，只要某个k满足,即可结束计算并取,当然，迭代函数 的构造方法是多种多样的。,例.用迭代法求方程 在 内的实根。取,解：对方程进行如下三种变形：,建立迭代格式：,这是一个发散的迭代格式。,建立迭代格式：,该迭代格式收敛。,建立迭代格式：,该迭代格式收敛。,结论：可见，对 的迭代函数,(1)不唯一,(2)发散或收敛,(3)收敛的快、慢。,下面将讨论两个问题：收敛性和收敛速度。,首先，看一下迭代法的几何意义：,迭代法的几何意义,通常将方程f(x)=0化为与它同解的方程的方法不止一种,有的收敛,有的不收敛,这取决于 的性态,方程 的求根问题在几何上就是确定曲线y=与直线y=x的交点P*的横坐标(图7-2所示),(a),(b),图7-2 迭代法的几何意义,7.2.4 迭代法的算法框图,二、收敛条件,定理 设函数在有限区间 上满足如下条件：,（1）当,即,（2）存在正常数，对 恒成立,则 在 上的解 存在惟一；,产生的序列 收敛到.,证明：由（1）知，于 连续，令：,则：,故：在 上至少有一个根.,现证有唯一根.反之，若,均有：,则由(2）有,即：,矛盾.现证收敛.记,推论 若条件(2)改为 在 上有界且,则定理1中的结论成立.,例 求,在0，1内的一个实根.,将方程化为等价方程,因为,此时定理1中的条件（1）成立，又,所以定理1中条件（2）也成立，对于0，1中任意初值，迭代序列,收敛，计算结果如下表，取,注.方程 也可化为等价方程,但此时定理、推论条件不成立，迭代序列不能保证收敛。,例5 对方程,构造收敛的迭代格式,求其最小正根,计算过程保留4位小数。解 容易判断1,2是方程的有根区间,且在此区间 内,所以此方程在区间1,2有 且仅有一根。将原方程改写成以下两种等价形式。,即 不满足收敛条件。,即 此时迭代公式满足迭代收敛条件。,误差估计：,在上面定理的条件下，有误差估计式：,（7.7）,（证明思路:只需证明下列两个结论成立即可。）,(1)证明,两边整理后得结论。,(2)以下证明：,事实上，由(1),即证,存在的困难：的值很难满足在隔根区间内。,7.2.5 局部收敛性 当迭代函数较复杂时,通常只能设法使迭代过程在根的邻域(局部)收敛。定理 设 在 的根 的邻域中有连续的一阶导数,且 则迭代过程 具有局部收敛性。证:由于,存在充分小邻域:,使成立 这里L为某个定数,根据微分中值定理 由于,又当时,故有由定理1知 对于任意的 都收敛,例6 设,要使迭代过程 局部收敛到,求 的取值范围。解：由在根 邻域具有局部收敛性时,收敛 条件,所以,例7 已知方程 在 内有根,且在上满足,利用 构造一个迭代函数,使 局部收敛于。解:由 可得,故,迭代公式,局部收敛,例.用迭代法求方程 在 内的实根。取,解：对方程进行如下三种变形：,理论分析：,由上述定理知，迭代格式发散，和计算结果吻合。,理论分析：,由定理知，迭代格式收敛，和计算结果吻合。,理论分析：,由定理知，迭代格式收敛，和计算结果吻合。,而且，由（5）式知，和都收敛，但收敛的效果比好。,收敛速度的粗略判别：值愈小，迭代法收敛得愈快.若，则收敛快；接近于1，则收敛很慢。,三、迭代过程的收敛速度（收敛阶）,定义 设迭代序列,收敛于,阶收敛方法.,收敛速度的阶：判断迭代方法收敛快慢的重要标准。,定理 设,是,的根，,于,的邻域,(*),则只要初始值 选得充分接近，迭代方法,阶收敛，且有,例 8 已知迭代公式 收敛于 证明该迭代公式平方收敛。证:迭代公式相应的迭代函数为,将 代入，,根据定理7.3可知，迭代公式平方收敛。,为了使迭代过程收敛或提高收敛的速度,可设法 提高初值的精度以减少迭代的次数 提高收敛的阶数 p,7.3 迭代过程的加速*（1）加权法设 是根 的某个近似值,用迭代公式校正一次得 又 根据中值定理有,其中,当 范围不大时,设 变化不大,其估计值为L,则有,可见,若将迭代值 与 加权平均,则可得到的,是比 更好的近似根,迭代：改进：或合并写成：,例9 用加权法加速技术求方程 在0.5附近的一个根。解：因为在 附近 取L=-0.6，建立如下迭代公式,仍取,逐次计算得=0.56658=0.56714。迭代4次便可得到精度 的结果,而不用加速技术需迭代18次,效果显著。,（2）埃特金（Aitken）方法在加权法中,估计L的值有时不太方便。假设在求得 以后,先求出由,利用中值定理可得(在求根区间变化不大,用某个定值L近似地替代之)L 将迭代值 再迭代一次,得新的迭代值则 将上述两个方程联立消去常数L化简可得,这样得到埃特金加速公式,例 用埃特金方法求方程 在初值 附近的一个根,精度要求，,取迭代格式,解 埃特金方法迭代格式为,只迭代二次就得到满足精度要求的解。,