数值分析第七章非线性方程(组)的数值解法.ppt

数值分析Numerical Analysis,第七章非线性方程（组）的数值解法,郑州大学研究生课程（2010-2011学年第一学期）,ISCM 2007,Beijing China,第七章 非线性方程（组）的数值解法,7.1 引言7.2 二分区间法7.3 迭代法及其加速7.4 牛顿迭代法7.5 弦截法7.6 解非线性方程组的迭代解法,ISCM 2007,Beijing China,7.1 引言,在科学研究和工程设计中,经常会遇到的一大类问题是非线性方程 f(x)=0 的求根问题，其中f(x)为非线性函数。方程f(x)=0的根,亦称为函数 f(x)的零点。,非线性方程的例子（1）在光的衍射理论中,需要求x-tanx=0的根（2）在行星轨道的计算中,需要求x-asinx=b的根,ISCM 2007,Beijing China,7.1 引言,当f(x)不是x的线性函数时，称对应的函数方程 f(x)=0为非线性方程。如果f(x)是多项式函数，则称为代数方程。否则为超越方程（三角方程，指数、对数方程等）。一般称n次多项式构成的方程,为n次代数方程,当n1时,方程显然是非线性的,ISCM 2007,Beijing China,7.1 引言,f(x)=0如果f(x)可以分解成,其中m为正整数且,则称x*是f(x)的m重零点,或称方程f(x)=0的m重根。当m=1时称x*为单根。,ISCM 2007,Beijing China,7.1 引言,公元前1700年的古巴比伦人有关于一、二次方程的解法。九章算术(公元前50100年)其中“方程术”有联立一次方程组的一般解法。1535年意大利数学家坦特格里亚(TorTaglia)发现了三次方程的解法，卡当(HCardano)从他那里得到了这种解法，于1545年在其名著大法中公布了三次方程的公式解，称为卡当算法。后来卡当的学生弗瑞里(Ferrari)又提出了四次方程的解法。此成果更激发了数学家们的情绪，但在以后的二个世纪中，求索工作始终没有成效，导致人们对高次代数方程解的存在性产生了怀疑。,代数方程求根的历史,ISCM 2007,Beijing China,7.1 引言,代数方程求根的历史,1799年，高斯证明了代数方程必有一个实根或复根的定理，称此为代数基本定理，并由此可以立刻推理n次代数方程必有n个实根或复根。但在以后的几十年中仍然没有找出高次代数方程的公式解。一直到18世纪，法国数学家拉格朗日用根置换方法统一了二、三、四方程的解法。在继续探索5次以上方程解的艰难历程中，第一个重大突破的是挪威数学家阿贝尔(NAbel1802-1829)1824年阿贝尔发表了“五次方程代数解法不可能存在”的论文，但并未受到重视，连数学大师高斯也未理解这项成果的重要意义。,ISCM 2007,Beijing China,7.1 引言,代数方程求根的历史,1828年17岁的法国数学家伽罗华(EGalois 1811-1832)写出了划时代的论文“关于五次方程的代数解法问题”，指出即使在公式中容许用n次方根，并用类似算法求五次或更高次代数方程的根是不可能的。,ISCM 2007,Beijing China,7.1 引言,理论上已证明，对于次数n=4的多项式方程,它的根可以用公式表示,而次数大于5的多项式方程,它的根一般不能用解析表达式表示.因此对于f(x)=0的函数方程,一般来说,不存在根的解析表达式,而实际应用中,也不一定必需得到求根的解析表达式,只要得到满足精度要求的根的近似值就可以了。常用的求根方法分为区间法和迭代法两大类。求根问题包括：根的存在性、根的范围和根的精确化。,ISCM 2007,Beijing China,7.1 引言,数值解法的三个步骤 判定根的存在性。即方程有没有根？如果有 根，有几个根？确定根的分布范围。即将每一个根用区间隔 离开来，这个过程实际上是获得方程各根的 初始近似值。根的精确化。将根的初始近似值按某种方法 逐步精确化，直到满足预先要求的精度为止。,ISCM 2007,Beijing China,定理1(根的存在定理)假设函数y=f(x)Ca,b,且f(a)f(b)0,则至少存在一点x(a,b)使得f(x)=0定理2 假设函数y=f(x)在a,b上单调连续,且f(a)f(b)0,则恰好只存在一点x(a,b)使得f(x)=0定理3 假设函数y=f(x)在x=s的某一邻域内充分可微，则s是方程f(x)=0的m重根的充分必要条件是,7.1 引言,ISCM 2007,Beijing China,7.2 二分区间法,设函数f(x)在闭区间a,b上连续,且f(a)f(b)0,根据连续函数的性质可知,f(x)=0在(a,b)内必有实根,称区间a,b为有根区间。假定方程f(x)=0在区间a,b内有惟一实根x*。二分法的基本思想是:首先确定有根区间,将区间二等分,通过判断f(x)的符号,逐步将有根区间缩小,直至有根区间足够地小,便可求出满足精度要求的近似根。,ISCM 2007,Beijing China,7.2 二分区间法,基本思想,将有根区间进行对分，判断出解在某个分段内，然后再对该段对分，依次类推，直到满足给定的精度为止,ISCM 2007,Beijing China,确定有根区间的方法,为了确定根的初值，首先必须圈定根所在的范围，称为圈定根或根的隔离。在上述基础上，采取适当的数值方法确定具有一定 精度要求的初值。对于代数方程，其根的个数（实或复的）与其次数 相同。至于超越方程，其根可能是一个、几个或无 解，并没有什么固定的圈根方法 求方程根的问题，就几何上讲,是求曲线 y=f(x)与 x轴交点的横坐标。,ISCM 2007,Beijing China,7.2 二分区间法,设f(x)为区间a,b上的单值连续,如果f(a)f(b)0,则a,b中至少有一个实根。如果f(x)在a,b上还是单调地递增或递减，则仅有一个实根。,y=f(x),a,b,y,x,ISCM 2007,Beijing China,7.2 二分区间法,由此可大体确定根所在子区间，方法有：(1)画图法(2)逐步搜索法,确定有根区间的方法,ISCM 2007,Beijing China,7.2 二分区间法,(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内,确定有根区间的方法,ISCM 2007,Beijing China,7.2 二分区间法,(1)画图法,0,2,3,y,x,确定有根区间的方法,ISCM 2007,Beijing China,7.2 二分区间法,(1)画图法,确定有根区间的方法,ISCM 2007,Beijing China,7.2 二分区间法,A,B,(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。,确定有根区间的方法,ISCM 2007,Beijing China,7.2 二分区间法,例 方程f(x)=x3-x-1=0 确定其有根区间解：用试凑的方法，不难发现 f(0)0 在区间（0，2）内至少有一个实根 设从x=0出发,取h=0.5为步长向右进行根的 搜索,列表如下,确定有根区间的方法,ISCM 2007,Beijing China,7.2 二分区间法,x,f(x),0 0.5 1.0 1.5 2,+,可以看出，在1.0,1.5内必有一根,确定有根区间的方法,ISCM 2007,Beijing China,7.2 二分区间法,二分法求根过程,取有根区间a,b之中点,将它分为两半,分点,这样就可缩小有根区间,ISCM 2007,Beijing China,7.2 二分区间法,对压缩了的有根区间 施行同样的手法,即取中点,将区间 再分为两半,然 后再确定有根区间,其长度是 的 二分之一。,ISCM 2007,Beijing China,7.2 二分区间法,如此反复下去,若不出现,即可得出一 系列有根区间序列：上述每个区间都是前一个区间的一半,因此 的长度,当k时趋于零,这些区间最终收敛于一点x*即为 所求的根。,ISCM 2007,Beijing China,7.2 二分区间法,每次二分后,取有根区间 的中点作为根的近似值，得到一个近似根的序列 该序列以根x*为极限 只要二分足够多次(即k足够大),便有这里为给定精度,由于,则,ISCM 2007,Beijing China,7.2 二分区间法,ISCM 2007,Beijing China,7.2 二分区间法,当给定精度0后,要想 成立,只要取k满足 即可，亦即当:,时,做到第K+1次二分,计算得到的 就是满足精度要求的近似根。,ISCM 2007,Beijing China,二分区间法算法实现,ISCM 2007,Beijing China,例7.2.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,使用二分法时,ISCM 2007,Beijing China,7.2 二分区间法,误差限为 只要取k满足,即可，亦即,所以需二分10次便可达到要求。,ISCM 2007,Beijing China,7.2 二分区间法,二分法的优点不管有根区间 多大,总能求出满足精度要求的根,且对函数f(x)的要求不高,只要连续即可,计算亦简单;二分法的局限性只能用于求函数的实根,不能用于求复根及偶数重根,它的收敛速度与比值为 的等比级数相同。,ISCM 2007,Beijing China,例 求方程f(x)=x 3 e-x=0的一个实根。因为 f(0)0。故f(x)在(0,1)内有根用二分法解之，(a,b）=（0,1)计算结果如表：kak bk xk f(xk)符号00 1 0.5000 10.5000 0.7500 20.7500 0.8750 3 0.87500.8125 4 0.81250.7812 5 0.7812 0.7656 60.7656 0.7734 7 0.7734 0.7695 8 0.7695 0.7714 90.7714 0.7724 100.7724 0.7729 取x10=0.7729，误差为|x*-x10|=1/211。,ISCM 2007,Beijing China,7.3 迭代法及其加速,为求解非线性方程f(x)=0的根，先将其写成便于迭代的等价方程 其中 为x的连续函数,迭代法的基本思想,如果数 使f(x*)=0,则也有,反之,若,则也有,称 为迭代函数，而称x*为 的不动点。,ISCM 2007,Beijing China,7.3 迭代法及其加速,任取一个初值,代入式 的右端,得到,再将 代入式 的右端,得到,依此类推,得到一个数列，其一般表示,称为求解非线性方程的简单迭代法。,ISCM 2007,Beijing China,7.3 迭代法及其加速,如果由迭代格式 产生的序列 收敛,即,则称迭代法收敛。,ISCM 2007,Beijing China,7.3 迭代法及其加速,实际计算中当然不可能也没必要无穷多步地做下去,对预先给定的精度要求，只要某个k满足,即可结束计算并取,ISCM 2007,Beijing China,7.3 迭代法及其加速,例 用迭代法求方程 在x=1.5附近的一个根解 将方程改写成如下两种等价形式,相应地可得到两个迭代公式,ISCM 2007,Beijing China,7.3 迭代法及其加速,如果取初始值 1.5，用上述两个迭代公式分别迭代，计算结果为,ISCM 2007,Beijing China,7.3 迭代法及其加速,迭代法的几何意义,通常将方程f(x)=0化为与它同解的方程的方法不止一种,有的收敛,有的不收敛,这取决于 的性态。方程 的求根问题在几何上就是确定曲线y=与直线y=x的交点P*的横坐标。,ISCM 2007,Beijing China,7.3 迭代法及其加速,迭代法的几何意义,ISCM 2007,Beijing China,7.3 迭代法及其加速,迭代法的几何意义,ISCM 2007,Beijing China,7.3 迭代法及其加速,迭代法的收敛性,对方程f(x)=0可以构造不同的迭代公式,但迭代公式并非总是收敛。那么,当迭代函数 满足什么条件时，相应的迭代公式才收敛呢？,ISCM 2007,Beijing China,定理7.3.1 设函数 在a,b上有连续的一阶导 数,且满足（1）对所有的xa,b 有 a,b（2）存在 0 L 1,使所有的xa,b有 L则方程 在a,b上的解 存在且唯一，对任意的初值 a,b，迭代过程均收敛于。并有误差估计式,ISCM 2007,Beijing China,由连续函数介值定理知,必有 a,b,使 所以有解存在,即假设有两个解 和,a,b，则，由微分中值定理有其中是介于x*和 之间的点 从而有a,b，进而有 由条件(2)有 1,所以-=0，即=，解唯一。,证:构造函数,由条件对任意的xa,b a,b有,ISCM 2007,Beijing China,按迭代过程,有,由于L1,所以有,可见L越小,收敛越快,再证误差估计式,ISCM 2007,Beijing China,即 得证。,即 得证。,ISCM 2007,Beijing China,迭代法的算法框图,ISCM 2007,Beijing China,7.3 迭代法及其加速,例 对方程,构造收敛的迭代格式,求其最小正根。解 容易判断1,2是方程的有根区间,且在此区间 内,所以此方程在区间1,2有 且仅有一根。将原方程改写成以下两种等价形式,ISCM 2007,Beijing China,7.3 迭代法及其加速,即 不满足收敛条件。,即 此时迭代公式满足迭代收敛条件。,ISCM 2007,Beijing China,7.3 迭代法及其加速,迭代法的局部收敛性,定理 设 在 的根 的邻域中有连续的一阶导数,且 则迭代过程 具有局部收敛性。,定义（局部收敛性）如果存在x*的某个邻域，当初值x0属于此邻域时，迭代过程 收敛，则称此迭代过程具有局部收敛性。,ISCM 2007,Beijing China,7.3 迭代法及其加速,证明:由于,存在充分小邻域:,使成立 这里L为某个定数,根据微分中值定理 由于,又当时,故有由定理知 对于任意的 都收敛,ISCM 2007,Beijing China,例 设,要使迭代过程 局部收敛到,求 的取值范围。解：由在根 邻域具有局部收敛性时,收敛 条件,所以,ISCM 2007,Beijing China,例 已知方程 在 内有根,且在上满足,利用 构造一个迭代函数,使 局部收敛于。解:由 可得,故,迭代公式,局部收敛,ISCM 2007,Beijing China,7.3 迭代法及其加速,定义 设迭代过程 收敛于 的根,记迭代误差若存在常数p（p1）和c（c0），使,迭代法的收敛速度,则称序列 是 p 阶收敛的,c称渐近误差常数。特别地,p=1时称为线性收敛,p=2时称为平方收敛。1 p 2时称为超线性收敛。,ISCM 2007,Beijing China,7.3 迭代法及其加速,数p的大小反映了迭代法收敛的速度的快慢，p愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。,ISCM 2007,Beijing China,定理 设迭代过程,若 在所求根 的邻域连续且 则迭代过程在 邻域是p阶收敛的。证:由于 即在 邻域,所以 有局部收敛性,将 在 处泰勒展开,根据已知条件得,由迭代公式,及,有,ISCM 2007,Beijing China,7.3 迭代法及其加速,例 已知迭代公式 收敛于 证明该迭代公式平方收敛。证:迭代公式相应的迭代函数为,根据定理可知，迭代公式平方收敛。,ISCM 2007,Beijing China,7.4 牛顿(Newton)迭代法,用迭代法可逐步精确方程 根的近似值，但必须要找到 的等价方程,如果 选得不合适,不仅影响收敛速度,而且有可能造成迭代格式发散。能否找到一种迭代格式,既结构简单,收敛速度快,又不存在发散的问题。这就是本节要介绍的牛顿迭代法.,ISCM 2007,Beijing China,7.4 牛顿(Newton)迭代法,牛顿迭代法的基本思想,牛顿迭代法一种重要和常用的迭代法,它的基本思想是将非线性函数f(x)逐步线性化,从而将非线性方程f(x)=0近似地转化为线性方程求解。,对于方程,设其近似根为,函数f(x)可在 附近作泰勒展开,ISCM 2007,Beijing China,7.4 牛顿(Newton)迭代法,忽略高次项,用其线性部分作为函数f(x)的近似，,设 的根,则有,即,可得牛顿迭代公式,ISCM 2007,Beijing China,7.4 牛顿(Newton)迭代法,牛顿迭代法的几何意义,方程f(x)=0的根x*是曲线y=f(x)与x轴交点的横坐标,设xk是根x*的某个近似值,过曲线y=f(x)的横坐标为xk的点Pk=(xk,f(xk)引切线交x轴于xk+1,并将其作为x*,新的近似值,重复上述过程,可见一次次用切线方程来求解方程f(x)=0的根,所以亦称为牛顿切线法。,ISCM 2007,Beijing China,7.4 牛顿(Newton)迭代法,牛顿迭代法的收敛性,定理 设 是方程 的单根,且f(x)在 的某邻域内有连续的二阶导数,则牛顿法在 附近局部收敛,且至少二阶收敛,有,ISCM 2007,Beijing China,7.4 牛顿(Newton)迭代法,证:牛顿迭代公式对应的迭代函数为 若 是方程 的单根,则有,从而,由定理知,牛顿迭代法在 附近局部收敛。又由定理知,迭代公式至少具有二阶收敛速度。,ISCM 2007,Beijing China,7.4 牛顿(Newton)迭代法,利用泰勒公式,ISCM 2007,Beijing China,7.4 牛顿(Newton)迭代法,所以,证毕,ISCM 2007,Beijing China,牛顿迭代法的收敛性,ISCM 2007,Beijing China,7.4 牛顿(Newton)迭代法,牛顿迭代法对初值x0的选取要求比较高。x0必须充分靠近x*才能保证局部收敛。定理 如果在有根区间a,b上连续且不变号，在a,b上取初始近似根x0满足，则牛顿迭代法产生的迭代序列单调收敛于方程f(x)=0在该区间上的唯一解。,ISCM 2007,Beijing China,结论：Newton法的收敛性依赖于x0 的选取。,x*,不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况,ISCM 2007,Beijing China,牛顿迭代法的算法实现,ISCM 2007,Beijing China,牛顿法的优点,牛顿法是目前求解非线性方程(组)的主要方法,至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠近精确解时。可求重根和复根。,在实际计算中，可以先用其它方法获得真解的一个粗糙近似，然后再用牛顿法求解。,ISCM 2007,Beijing China,7.5 弦截法,牛顿迭代法虽然具有收敛速度快的优点，但每迭代一次都要计算导数,当 比较复杂时,不仅每次计算 带来很多不便，而且还可能十分麻烦，如果用不计算导数的迭代方法，往往只有线性收敛的速度。本节介绍的弦截法便是一种不必进行导数运算的求根方法。,ISCM 2007,Beijing China,7.5 弦截法,弦截法在迭代过程中不仅用到前一步 处的函数值，而且还使用 处的函数值来构造迭代函数，这样做能提高迭代的收敛速度。称之为多点迭代法。,ISCM 2007,Beijing China,7.5 弦截法,弦截法的基本思想,为避免计算函数的导数，使用差商 替代牛顿公式中的导数,便得到迭代公式 称为弦截迭代公式，相应的迭代法称为弦截法。,ISCM 2007,Beijing China,7.5 弦截法,弦截法的几何意义,弦截法也称割线法,其几何意义是用过曲线上两点、的割线来代替曲线,用割线与x轴交点的横座标作为方程的近似根 再过,P1点和点 作割线求出,再过P2点和点 作割线求出,余此类推，当收敛时可求出满足精度要求的,ISCM 2007,Beijing China,7.5 弦截法,可以证明，弦截法具有超线性收敛，收敛的阶约为1.618，它与前面介绍的一般迭代法一样都是线性化方法，但也有区别。即一般迭代法在计算 时只用到前一步的值，故称之为单点迭代法；而弦截法在求 时要用到前两步的结果 和，使用这种方法必须给出两个初始近似根，这种方法称为多点迭代法。,ISCM 2007,Beijing China,弦截法算法实现,ISCM 2007,Beijing China,7.5 弦截法,例 用弦截法求方程 在 初始 值邻近的一个根。要求解：取,令 利用弦截迭代公式 易见取近似根 可满足精度要求。,ISCM 2007,Beijing China,FindRoot1.FindRootlhs=rhs,x,x0 searches for a numerical solution to the equation lhs=rhs,starting with x=x0.2.FindRootlhs=rhs,x,x0,x1 searches for a solution using x0 and x1 as the first two values of x.This form must be used if symbolic derivatives of the equation cannot be found.,Mathematica中的数值求根方法,ISCM 2007,Beijing China,7.5 解非线性方程组的迭代解法,考虑非线性方程组在点(x0,y0)作二元Taylor展开，并取线性部分,ISCM 2007,Beijing China,7.5 解非线性方程组的迭代解法,这是关于x,y的线性方程组。从而将非线性方程组进行了线性化。这是目前解决非线性问题的主要方法。,ISCM 2007,Beijing China,7.5 解非线性方程组的迭代解法,ISCM 2007,Beijing China,7.5 解非线性方程组的迭代解法,最后我们得到求解非线性方程组的牛顿迭代格式,ISCM 2007,Beijing China,7.5 解非线性方程组的迭代解法,例 解非线性方程组解：取Jacobi矩阵为,ISCM 2007,Beijing China,7.5 解非线性方程组的迭代解法,继续做下去，直到 时停止。,ISCM 2007,Beijing China,7.5 解非线性方程组的迭代解法,f1x_,y_:=4-x2-y2;f2x_,y_:=1-Expx-y;,FindRootf1x,y,f2x,y,x,1.0,y,-1.7 x=1.00417,y=-1.72964 FindRootf1x,y,f2x,y,x,1.0,y,1.7 x=-1.81626,y=0.837368,ISCM 2007,Beijing China,非线性方程的解通常叫做方程的根,也叫做函数的零点,本章讨论了求解非线性方程近似根常用的一些数值方法。先要确定有根区间,且对于收敛的迭代格式,这个区间要足够小。针对各种求根的数值方法的特点,要考虑其收敛性、收敛速度和计算量。二分法是逐步将含根区间分半,主要用来求实根;迭代法是一种逐次逼近的方法,起着把根的精确值一步一步算出来的作用;牛顿法具有较快的收敛速度,但对初值选取要求较高。弦截法避开了导数的计算,具有超线性的收敛速度,每计算一步,要用到前面两步的信息。,本章小结,