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

y=xyy=)(xϕy=x1)(0*′xϕ0)(1*′−xϕP0P2P*Q1Q2x1x0x2x*xyx0xx1x2x3x*y=)(xϕP*P1数值分析NumericalAnalysis第七章非线性方程（组）的数值解法郑州大学研究生课程（2010-2011学年第一学期）2/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis第七章非线性方程（组）的数值解法§7.1引言§7.2二分区间法§7.3迭代法及其加速§7.4牛顿迭代法§7.5弦截法§7.6解非线性方程组的迭代解法3/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.1引言引例引例在相距在相距100m100m的两座建筑物的两座建筑物((高度相等的点高度相等的点))之之间悬挂一根电缆，仅允许电缆在中间昀多下垂间悬挂一根电缆，仅允许电缆在中间昀多下垂1m1m，，试计算所需电缆的昀大长度试计算所需电缆的昀大长度((如图所示如图所示))。。ya+1a-50O50x4/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.1引言由于空中电缆的曲线是悬链线由于空中电缆的曲线是悬链线,,建立如图所建立如图所示的坐标系后示的坐标系后,,悬链线方程悬链线方程为为[]50,502)(−∈+=−xeeayaxax由题设知曲线的昀底点(0,y(0))与昀高点(50,y(50))之间的高度差为1m,所以应有y(50)=y(0)+1,即5/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.1引言5050()12aaaeea−+=+ya+1a-50O50x要计算电缆的长度,必须先求出上述方程中的a,由于它是关于a的非线性方程,没有现成的公式可用,因此只能寻求其他解法.6/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis非线性方程的例子（1）在光的衍射理论中,需要求x-tanx=0的根（2）在行星轨道的计算中,需要求x-asinx=b的根§7.1引言7/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.1引言在科学研究和工程设计中,经常会遇到的一大类问题是非线性方程f(x)=0的求根问题，其中f(x)为非线性函数。方程f(x)=0的根,亦称为函数f(x)的零点。8/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.1引言如果f(x)可以分解成,其中m为正整数且,则称x*是f(x)的m重零点,或称方程f(x)=0的m重根。当m=1时称x*为单根。)()()(*xgxxxfm−=0)(*≠xg9/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.1引言当f(x)不是x的线性函数时，称对应的函数方程为非线性方程。★如果f(x)是多项式函数，则称为代数方程。★否则为超越方程（三角方程，指数、对数方程等）。一般称n次多项式构成的方程)0(00111≠=++++−−nnnnnaaxaxaxa为n次代数方程,当n＞1时,方程显然是非线性的10/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.1引言¾公元前1700年的古巴比伦人有关于一、二次方程的解法。《九章算术》(公元前50~100年)其中“方程术”有联立一次方程组的一般解法。¾1535年意大利数学家坦特格里亚(TorTaglia)发现了三次方程的解法，卡当(H·Cardano)从他那里得到了这种解法，于1545年在其名著《大法》中公布了三次方程的公式解，称为卡当算法。¾后来卡当的学生弗瑞里(Ferrari)又提出了四次方程的解法。此成果更激发了数学家们的情绪，但在以后的二个世纪中，求索工作始终没有成效，导致人们对高次代数方程解的存在性产生了怀疑。代数方程求根的历史11/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.1引言代数方程求根的历史¾1799年，高斯证明了代数方程必有一个实根或复根的定理，称此为代数基本定理，并由此可以立刻推理n次代数方程必有n个实根或复根。¾但在以后的几十年中仍然没有找出高次代数方程的公式解。一直到18世纪，法国数学家拉格朗日用根置换方法统一了二、三、四方程的解法。¾在继续探索5次以上方程解的艰难历程中，第一个重大突破的是挪威数学家阿贝尔(N·Abel1802-1829)1824年阿贝尔发表了“五次方程代数解法不可能存在”的论文，但并未受到重视，连数学大师高斯也未理解这项成果的重要意义。12/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.1引言代数方程求根的历史¾1828年17岁的法国数学家伽罗华(E·Galois1811-1832)写出了划时代的论文“关于五次方程的代数解法问题”，指出即使在公式中容许用n次方根，并用类似算法求五次或更高次代数方程的根是不可能的。13/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.1引言理论上已证明，对于次数n=4的多项式方程,它的根可以用公式表示,而次数大于5的多项式方程,它的根一般不能用解析表达式表示.因此对于f(x)=0的函数方程,一般来说,不存在根的解析表达式,而实际应用中,也不一定必需得到求根的解析表达式,只要得到满足精度要求的根的近似值就可以了。常用的求根方法分为区间法和迭代法两大类。求根问题包括：根的存在性、根的范围和根的精确化。14/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.1引言数值解法的三个步骤数值解法的三个步骤①①判定根的存在性。判定根的存在性。即方程有没有根？如果有即方程有没有根？如果有根，有几个根？根，有几个根？②②确定根的分布范围。确定根的分布范围。即将每一个根用区间隔即将每一个根用区间隔离开来，这个过程实际上是获得方程各根的离开来，这个过程实际上是获得方程各根的初始近似值。初始近似值。③③根的精确化。根的精确化。将根的初始近似值按某种方法将根的初始近似值按某种方法逐步精确化，直到满足预先要求的精度为止。逐步精确化，直到满足预先要求的精度为止。15/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis定理1(根的存在定理)假设函数y=f(x)∈C[a,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重根的充分必要条件是0)(,0)()()()()1(≠===′=−sfsfsfsfmm§7.1引言16/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§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)的符号,逐步将有根区间缩小,直至有根区间足够地小,便可求出满足精度要求的近似根。17/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.2二分区间法‰基本思想将有根区间进行对分，判断出解在某个分段内，然后再对该段对分，依次类推，直到满足给定的精度为止‰适用范围求有根区间内的奇数重实根‰数学原理：介值定理设f(x)在[a,b]上连续，且f(a)f(b)0，则由介值定理可得，在(a,b)内至少存在一点ξ使得f(ξ)=0ba2ba+*x18/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis确定有根区间的方法¾为了确定根的初值，首先必须圈定根所在的范围，称为圈定根或根的隔离。¾在上述基础上，采取适当的数值方法确定具有一定精度要求的初值。¾对于代数方程，其根的个数（实或复的）与其次数相同。至于超越方程，其根可能是一个、几个或无解，并没有什么固定的圈根方法¾求方程根的问题，就几何上讲,是求曲线y=f(x)与x轴交点的横坐标。19/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.2二分区间法设f(x)为区间[a,b]上的单值连续,如果f(a)·f(b)0,则[a,b]中至少有一个实根。如果f(x)在[a,b]上还是单调地递增或递减，则仅有一个实根。y=f(x)abyx20/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.2二分区间法„由此可大体确定根所在子区间，方法有：(1)画图法(2)逐步搜索法确定有根区间的方法21/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§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]内确定有根区间的方法22/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.2二分区间法(1)画图法xy1=gxy=α023yx确定有根区间的方法23/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.2二分区间法(1)画图法y0xy=f(x)y=kf(x)确定有根区间的方法24/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.2二分区间法y0xABa1b1a2b2(2)搜索法对于给定的f(x),设有根区间为[A,B],从x0=A出发,以步长h=(B-A)/n(n是正整数),在[A,B]内取定节点:xi=x0＋ih(i=0,1,2,…,n),从左至右检查f(xi)的符号,如发现xi与端点x0的函数值异号,则得到一个缩小的有根子区间［xi-1,xi］。确定有根区间的方法25/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.2二分区间法例7.2.1方程f(x)=x3-x-1=0确定其有根区间解：用试凑的方法，不难发现f(0)0f(2)0在区间（0，2）内至少有一个实根设从x=0出发,取h=0.5为步长向右进行根的搜索,列表如下确定有根区间的方法26/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.2二分区间法xf(x)00.51.01.52–––++可以看出，在[1.0,1.5]内必有一根确定有根区间的方法27/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.2二分区间法二分法求根过程①取有根区间[a,b]之中点,将它分为两半,分点,这样就可缩小有根区间20bax+=yy=f(x)y=f(x)x*ax1x*x0bax0x1ba1b1a1b1a2b2a2b228/100郑州大学研究生2010-2011学年课程数值分析NumericalAnalysis§7.2二分区间法②对压缩了的有根区间施行同样的手法,即取中点,将区间再分为两半,然后再确定有根区间,其长度是的二分之一。[]11,ba2111b