《数值分析第七章非线性方程(组)的数值解法》由会员分享，可在线阅读，更多相关《数值分析第七章非线性方程(组)的数值解法（87页珍藏版）》请在金锄头文库上搜索。
1、数值分析数值分析NumericalAnalysis第七章非线性方程（组）的数值解法郑州大学研究生课程郑州大学研究生课程 （2010-20112010-2011学年第一学期）学年第一学期）ISCM 2007,Beijing China1第七章 非线性方程（组）的数值解法 7.1 7.1 引言引言7.2 7.2 二分区间法二分区间法7.3 7.3 迭代法及其加速迭代法及其加速7.4 7.4 牛顿迭代法牛顿迭代法7.5 7.5 弦截法弦截法7.6 7.6 解非线性方程组的迭代解法解非线性方程组的迭代解法ISCM 2007,Beijing China/877.1 引言 在在科科学学研研究究和和工工程程
2、设设计计中中,经经常常会会遇遇到到的的一一大大类类问题是问题是非线性方程非线性方程 f(x)=0 的求根问题，其中的求根问题，其中f(x)为非线性函数。为非线性函数。方程方程f(x)=0的根的根,亦称为函数亦称为函数 f(x)的的零点零点。非线性方程的例子（1）在光的衍射理论中,需要求x-tanx=0=0的根（2）在行星轨道的计算中,需要求x-asinx=b的根ISCM 2007,Beijing China/877.1 引言 当当f(x)f(x)不是不是x x的线性函数时，称对应的函数方程的线性函数时，称对应的函数方程 f(x)=0为为非线性方程非线性方程。如果如果f(x)f(x)是多项式函数
3、，则称为是多项式函数，则称为代数方程代数方程。否则为否则为超越方程超越方程（三角方程，指数、对数方程等）。（三角方程，指数、对数方程等）。一般称一般称n n次多项式构成的方程次多项式构成的方程 为为n n次代数方程次代数方程,当当n n1 1时时,方程显然是非线性的方程显然是非线性的ISCM 2007,Beijing China/877.1 引言 f(x)=0如果如果f(x)可以分解成可以分解成 ,其中其中m为为正整数且正整数且 ,则称则称x x*是是f(x)f(x)的的m重零点重零点,或或称方程称方程f(x)=0的的m重根重根。当。当m=1时称时称x x*为为单根单根。ISCM 2007,B
4、eijing China/877.1 引言公元前公元前17001700年的古巴比伦人有关于一、二次方程的解法。年的古巴比伦人有关于一、二次方程的解法。九章算术九章算术(公元前公元前5010050100年年)其中其中“方程术方程术”有联立一有联立一次方程组的一般解法。次方程组的一般解法。15351535年意大利数学家坦特格里亚年意大利数学家坦特格里亚(TorTaglia)(TorTaglia)发现了三次方程发现了三次方程的解法，卡当的解法，卡当(HCardano)(HCardano)从他那里得到了这种解法，于从他那里得到了这种解法，于15451545年在其名著大法中公布了三次方程的公式解，称年在
5、其名著大法中公布了三次方程的公式解，称为卡当算法。为卡当算法。后来卡当的学生弗瑞里后来卡当的学生弗瑞里(Ferrari)(Ferrari)又提出了四次方程的解法。又提出了四次方程的解法。此成果更激发了数学家们的情绪，但在以后的二个世纪中，此成果更激发了数学家们的情绪，但在以后的二个世纪中，求索工作始终没有成效，导致人们对高次代数方程解的存求索工作始终没有成效，导致人们对高次代数方程解的存在性产生了怀疑。在性产生了怀疑。代数方程求根的历史ISCM 2007,Beijing China/877.1 引言代数方程求根的历史17991799年，高斯证明了代数方程必有一个实根或复根的定理，年，高斯证明了
6、代数方程必有一个实根或复根的定理，称此为称此为代数基本定理代数基本定理，并由此可以立刻推理，并由此可以立刻推理n n次代数方程次代数方程必有必有n n个实根或复根。个实根或复根。但在以后的几十年中仍然没有找出高次代数方程的公式解。但在以后的几十年中仍然没有找出高次代数方程的公式解。一直到一直到1818世纪，法国数学家拉格朗日用根置换方法统一了世纪，法国数学家拉格朗日用根置换方法统一了二、三、四方程的解法。二、三、四方程的解法。在继续探索在继续探索5 5次以上方程解的艰难历程中，第一个重大突次以上方程解的艰难历程中，第一个重大突破的是挪威数学家阿贝尔破的是挪威数学家阿贝尔(NAbel1802-1
7、829)1824(NAbel1802-1829)1824年阿年阿贝尔发表了贝尔发表了“五次方程代数解法不可能存在五次方程代数解法不可能存在”的论文，但的论文，但并未受到重视，连数学大师高斯也未理解这项成果的重要并未受到重视，连数学大师高斯也未理解这项成果的重要意义。意义。ISCM 2007,Beijing China/877.1 引言代数方程求根的历史18281828年年1717岁的法国数学家伽罗华岁的法国数学家伽罗华(EGalois 1811-1832)(EGalois 1811-1832)写写出了划时代的论文出了划时代的论文“关于五次方程的代数解法问题关于五次方程的代数解法问题”，指，指出
8、即使在公式中容许用出即使在公式中容许用n n次方根，并次方根，并用类似算法求五次或更用类似算法求五次或更高次代数方程的根是不可能的。高次代数方程的根是不可能的。ISCM 2007,Beijing China/877.1 引言理论上已证明，对于次数n=4的多项式方程,它的根可以用公式表示,而次数大于5的多项式方程,它的根一般不能用解析表达式表示.因此对于f(x)=0的函数方程,一般来说,不存在根的解析表达式,而实际应用中,也不一定必需得到求根的解析表达式,只要得到满足精度要求的根的近似值就可以了。常用的求根方法分为区间法和迭代法两大类。求根问题包括：根的存在性、根的范围和根的精确化。ISCM 2
9、007,Beijing China/877.1 引言数值解法的三个步骤数值解法的三个步骤判定根的存在性。判定根的存在性。即方程有没有根？如果有即方程有没有根？如果有根，有几个根？根，有几个根？确定根的分布范围。确定根的分布范围。即将每一个根用区间隔即将每一个根用区间隔离开来，这个过程实际上是获得方程各根的离开来，这个过程实际上是获得方程各根的初始近似值。初始近似值。根的精确化。根的精确化。将根的初始近似值按某种方法将根的初始近似值按某种方法逐步精确化，直到满足预先要求的精度为止。逐步精确化，直到满足预先要求的精度为止。ISCM 2007,Beijing China/87定理1(根的存在定理)假
10、设函数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/877.2 二分区间法 设函数设函数f(x)f(x)在闭区间在闭区间a,ba,b上连续上连续,且且f(f(a)f()f(b)0,)0,根据连续函数的性质可知根据连续函数的性质可知,f(x)=0)=0在在(a,b)(a,b)内必有
11、实根内必有实根,称区间称区间a,ba,b为为有根区间有根区间。假定方程假定方程f(x)=0f(x)=0在区间在区间a,ba,b内有惟一实根内有惟一实根x x*。二分法的基本思想二分法的基本思想是是:首先确定有根区间首先确定有根区间,将区间将区间二等分二等分,通过判断通过判断f(x)f(x)的符号的符号,逐步将有根区间缩小逐步将有根区间缩小,直至直至有根区间足够地小有根区间足够地小,便可求出满足精度要求的近便可求出满足精度要求的近似根。似根。ISCM 2007,Beijing China/877.2 二分区间法q 基本思想将有根区间进行对分，判断出解在某个分段内，然后将有根区间进行对分，判断出解
12、在某个分段内，然后再对该段对分，依次类推，直到满足给定的精度为止再对该段对分，依次类推，直到满足给定的精度为止q 适用范围适用范围求有根区间内的求有根区间内的 奇数重实根奇数重实根q 数学原理：数学原理：介值定理介值定理设设 f(x)在在 a,b 上连续，且上连续，且 f(a)f(b)0，则由介值定，则由介值定理可得，在理可得，在(a,b)内至少存在一点内至少存在一点 使得使得 f()=0ISCM 2007,Beijing China/87确定有根区间的方法确定有根区间的方法为了确定根的初值，首先必须圈定根所在的范围，为了确定根的初值，首先必须圈定根所在的范围，称为称为圈定根圈定根或或根的隔离
13、根的隔离。在上述基础上，采取适当的数值方法确定具有一定在上述基础上，采取适当的数值方法确定具有一定 精度要求的初值。精度要求的初值。对于代数方程，其根的个数（实或复的）与其次数对于代数方程，其根的个数（实或复的）与其次数 相同相同。至于超越方程，其根可能是一个、几个或无。至于超越方程，其根可能是一个、几个或无 解，并没有什么固定的圈根方法解，并没有什么固定的圈根方法 求方程根的问题，就几何上讲求方程根的问题，就几何上讲,是求曲线是求曲线 y=f(x)与与 x轴交点的横坐标。轴交点的横坐标。ISCM 2007,Beijing China/877.2 二分区间法 设设f(x)为区间为区间a,b上的
14、单值连续上的单值连续,如果如果f(a)f(b)0,则则a,b中至少有一个实根。中至少有一个实根。如果如果f(x)在在a,b上还是单调地递增或递减，则仅上还是单调地递增或递减，则仅有一个实根。有一个实根。y=f(x)abyxISCM 2007,Beijing China/877.2 二分区间法n由此可大体确定根所在子区间，方法有：由此可大体确定根所在子区间，方法有：(1)画图法画图法 (2)逐步搜索法逐步搜索法确定有根区间的方法确定有根区间的方法ISCM 2007,Beijing China/877.2 二分区间法(1)画图法画图法 画出画出y=f(x)的略图，从而看出曲线与的略图，从而看出曲线
15、与x轴交点的轴交点的 大致位置。大致位置。也可将也可将f(x)=0分解为分解为 1(x)=2(x)的形式，的形式，1(x)与与 2(x)两曲线交点的横坐标所在的子区间即为含根两曲线交点的横坐标所在的子区间即为含根 区间。区间。例如例如 xlogx-1=0=0可以改写为可以改写为logx=1/x画出对数曲线画出对数曲线y=logx,与双曲线与双曲线y=1/x,它们交它们交 点的横坐标位于区间点的横坐标位于区间2,32,3内内确定有根区间的方法确定有根区间的方法ISCM 2007,Beijing China/877.2 二分区间法(1)画图法画图法023yx确定有根区间的方法确定有根区间的方法IS
16、CM 2007,Beijing China/877.2 二分区间法(1)画图法画图法y0 xy=f(x)y=kf(x)确定有根区间的方法确定有根区间的方法ISCM 2007,Beijing China/877.2 二分区间法y0 xABa1b1a2b2(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。确定有根区间的方法确定有根区间的方法ISCM 2007,Beijing China/877.2 二分区间法例例 方程方程f(x)=xf(x)=x3 3-x-1=0 -x-1=0 确定其有根区间确定其有根区间解：用试凑的方法，不难发现解：用试凑的方法，不难发现 f(0)0 f(0)0 在区间（在区间（0 0，2 2）内至少有一个实根）内至少
