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

《数值分析第七章非线性方程组的数值解法课件.ppt》由会员分享，可在线阅读，更多相关《数值分析第七章非线性方程组的数值解法课件.ppt（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数值分析第七章非线性方程组的数值解法第1页，此课件共84页哦2/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis第七章 非线性方程（组）的数值解法 7.1 7.1 引言引言7.2 7.2 二分区间法二分区间法7.3 7.3 迭代法及其加速迭代法及其加速7.4 7.4 牛顿迭代法牛顿迭代法7.5 7.5 弦截法弦截法7.6 7.6 解非线性方程组的迭代解法解非线性方程组的迭代解法第2页，此课件共84页哦3/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.1 引言 在科学研究和工程设计中在科学研究和工程设计

2、中,经常会遇到的一大类问题是经常会遇到的一大类问题是非非线性方程线性方程 f(x)=0 的求根问题，其中的求根问题，其中f(x)为非线性函数。为非线性函数。方程方程f(x)=0的根的根,亦称为函数亦称为函数 f(x)的的零点零点。非线性方程的例子（1）在光的衍射理论中,需要求x-tanx=0=0的根（2）在行星轨道的计算中,需要求x-asinx=b的根第3页，此课件共84页哦4/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.1 引言 当当 f(x)不是不是x x的线性函数时，称对应的函数方程的线性函数时，称对应的函数方程 f(x)=0为为非线性

3、方程非线性方程。如果如果 f(x)(x)是多项式函数，则称为是多项式函数，则称为代数方程代数方程。否则为否则为超越方程超越方程（三角方程，指数、对数方程等）（三角方程，指数、对数方程等）。一般称。一般称n次多项式构成的方程次多项式构成的方程 )0(00111nnnnnaaxaxaxa为为n次代数方程次代数方程,当当n n1 1时时,方程显然是非线性的方程显然是非线性的第4页，此课件共84页哦5/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.1 引言如果如果f(x)可以分解成可以分解成 ,其中其中m为为正整数且正整数且 ,则称则称x*是是f(x)

4、(x)的的m重零点重零点,或或称方程称方程f(x)=0的的m重根重根。当。当m=1时称时称x*为为单根单根。)()()(*xgxxxfm0)(*xg 求方程根的问题，就几何上讲求方程根的问题，就几何上讲,是求曲线是求曲线 y=f(x)与与 x轴轴交点交点的横坐标。的横坐标。第5页，此课件共84页哦6/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.1 引言公元前公元前17001700年的古巴比伦人有关于一、二次代数方程的解法。年的古巴比伦人有关于一、二次代数方程的解法。九章算术九章算术(公元前公元前5010050100年年)其中其中“方程术方程术

5、”有联立一次方程有联立一次方程组的一般解法。组的一般解法。15351535年意大利数学家坦特格里亚年意大利数学家坦特格里亚(TorTaglia)(TorTaglia)发现了三次代数方发现了三次代数方程的解法，卡当程的解法，卡当(HCardano)(HCardano)从他那里得到了这种解法，于从他那里得到了这种解法，于15451545年年在其名著在其名著大法大法中公布了三次方程的公式解，称为卡当算法中公布了三次方程的公式解，称为卡当算法。后来卡当的学生弗瑞里后来卡当的学生弗瑞里(Ferrari)(Ferrari)又提出了四次代数方程的解法。此又提出了四次代数方程的解法。此成果更激发了数学家们的情

6、绪，但在以后的二个世纪中，求索工作成果更激发了数学家们的情绪，但在以后的二个世纪中，求索工作始终没有成效，导致人们对高次代数方程解的存在性产生了怀疑。始终没有成效，导致人们对高次代数方程解的存在性产生了怀疑。代数方程求根的历史第6页，此课件共84页哦7/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.1 引言代数方程求根的历史17991799年，高斯证明了代数方程必有一个实根或复根的定理，称此年，高斯证明了代数方程必有一个实根或复根的定理，称此为为代数基本定理代数基本定理，并由此可以立刻推理，并由此可以立刻推理n n次代数方程必有次代数方程必有n

7、 n个实根个实根或复根。或复根。但在以后的几十年中仍然没有找出高次代数方程的公式解。一直到但在以后的几十年中仍然没有找出高次代数方程的公式解。一直到1818世纪，法国数学家拉格朗日用根置换方法统一了二、三、四次方程世纪，法国数学家拉格朗日用根置换方法统一了二、三、四次方程的解法。的解法。在继续探索在继续探索5 5次以上方程解的艰难历程中，第一个重大突破的是次以上方程解的艰难历程中，第一个重大突破的是挪威数学家阿贝尔挪威数学家阿贝尔(N(NAbel1802-1829)1824Abel1802-1829)1824年阿贝尔发表了年阿贝尔发表了“五次方程的代数解法不可能存在五次方程的代数解法不可能存在

8、”的论文，但并未受到重视，连数的论文，但并未受到重视，连数学大师高斯也未理解这项成果的重要意义。学大师高斯也未理解这项成果的重要意义。第7页，此课件共84页哦8/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.1 引言代数方程求根的历史18281828年年1717岁的法国数学家伽罗华岁的法国数学家伽罗华(E(EGalois 1811-1832)Galois 1811-1832)写出了划写出了划时代的论文时代的论文“关于五次方程的代数解法问题关于五次方程的代数解法问题”，指出即使在公式中容，指出即使在公式中容许用许用n n次方根，并次方根，并用类似

9、算法求五次或更高次代数方程的根是用类似算法求五次或更高次代数方程的根是不可能的。不可能的。”，“他一劳永逸地发现了一个折磨了数学家几个世纪的谜团的答他一劳永逸地发现了一个折磨了数学家几个世纪的谜团的答案：在什么条件下一个方程有解？案：在什么条件下一个方程有解？”第8页，此课件共84页哦9/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.1 引言理论上已证明，对于次数n=4的多项式方程,它的根可以用公式表示,而次数大于5的多项式方程,它的根一般不能用解析表达式表示.因此对于f(x)=0的函数方程,一般来说,不存在根的解析表达式,而实际应用中,也不一

10、定必需得到求根的解析表达式,只要得到满足精度要求的根的近似值就可以了。常用的求根方法分为区间法和迭代法两大类。求根问题包括：根的存在性、根的范围和根的精确化。第9页，此课件共84页哦10/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.1 引言第10页，此课件共84页哦11/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis定理1(根的存在定理，介值定理介值定理)假设函数 y=f(x)C a,b,且 f(a)f(b)0,则至少存在一点x(a,b)使得 f(x)=0。定理2 假设函数 y=f(x)在 a,b

11、 上单调连续,且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(sfsfsfsfmm7.1 引言y=f(x)abyx第11页，此课件共84页哦12/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.2 二分区间法 设函数设函数f(x)在闭区间在闭区间 a,b 上连续上连续,且且f(a)f(b)0,)0,根据根据连续函数的性质可知连续函数的性质可知,f(x)=0)=0在在(a,b)内必有实根

12、内必有实根,称区间称区间 a,b 为为有根区间有根区间。假定方程假定方程 f(x)=0 0在区间在区间 a,b 内有惟一实根内有惟一实根x*。二分法的基本思想二分法的基本思想是是:首先确定一个有根区间首先确定一个有根区间,将区间二将区间二等分等分,通过判断通过判断f(x)在区间端点的符号在区间端点的符号,逐步将有根区间缩逐步将有根区间缩小小,直至直至有根区间足够地小有根区间足够地小,便可求出满足精度要求的近便可求出满足精度要求的近似根。似根。第12页，此课件共84页哦13/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.2 二分法 基本思想将有根

13、区间进行对分，判断出解在某个分段内，然后再对将有根区间进行对分，判断出解在某个分段内，然后再对该段对分，依次类推，直到满足给定的精度为止该段对分，依次类推，直到满足给定的精度为止q 适用范围适用范围求有根区间内的求有根区间内的 奇数重实根奇数重实根q 数学原理：数学原理：介值定理介值定理设设 f(x)在在 a,b 上连续，且上连续，且 f(a)f(b)0，则由介值定，则由介值定理可得，在理可得，在(a,b)内至少存在一点内至少存在一点 使得使得 f()=0ba2ba*x第13页，此课件共84页哦14/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis二

14、分法是一种确定有根区间的方法二分法是一种确定有根区间的方法 为了确定根的初值，首先必须圈定根所在的范围，为了确定根的初值，首先必须圈定根所在的范围，称为称为圈定根圈定根或或根的隔离根的隔离。在上述基础上，采取适当的数值方法确定具有一定在上述基础上，采取适当的数值方法确定具有一定 精度要求的初值。精度要求的初值。对于代数方程，其根的个数（实或复的）与其次数对于代数方程，其根的个数（实或复的）与其次数 相同相同。至于超越方程，其根可能是一个、几个或无。至于超越方程，其根可能是一个、几个或无 解，并没有什么固定的圈根方法解，并没有什么固定的圈根方法第14页，此课件共84页哦15/87郑州大学研究生2

15、014-2015学年课程 数值分析 Numerical Analysis7.2 区间法 设设f(x)为区间为区间a,b上的连续函数上的连续函数,如果如果f(a)f(b)0,则则a,b中至少有一个实根。中至少有一个实根。如果如果f(x)在在a,b上还是单调地递增或递减，则仅有一个上还是单调地递增或递减，则仅有一个实根。实根。y=f(x)abyx第15页，此课件共84页哦16/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.2 区间法由此可大体确定根所在子区间，方法有：由此可大体确定根所在子区间，方法有：(1)画图法画图法 (2)逐步搜索法逐步搜索法

16、确定有根区间的方法确定有根区间的方法第16页，此课件共84页哦17/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.2 区间法(1)画图法画图法 画出画出y=f(x)的略图，从而看出曲线与的略图，从而看出曲线与x轴交点的轴交点的 大致位置。大致位置。也可将也可将f(x)=0分解为分解为 1(x)=2(x)的形式，的形式，1(x)与与 2(x)两曲线交点的横坐标所在的子区间即为含根两曲线交点的横坐标所在的子区间即为含根 区间。区间。例如例如 xlogx-1=0=0可以改写为可以改写为logx=1/x画出对数曲线画出对数曲线y=logx,与双曲线与双

17、曲线y=1/x,它们交它们交 点的横坐标位于区间点的横坐标位于区间2,32,3内内确定有根区间的方法确定有根区间的方法第17页，此课件共84页哦18/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.2 区间法(1)画图法画图法xy1gxy 023yx确定有根区间的方法确定有根区间的方法第18页，此课件共84页哦19/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.2 区间法(1)画图法画图法y0 xy=f(x)y=kf(x)确定有根区间的方法确定有根区间的方法第19页，此课件共84页哦20/87郑州

18、大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.2 区间法y0 xABa1b1a2b2(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。确定有根区间的方法确定有根区间的方法第20页，此课件共84页哦21/87郑州大

19、学研究生2014-2015学年课程 数值分析 Numerical Analysis7.2 区间法例例7.2.17.2.1 方程方程f(x)=(x)=x3 3-x-1=0 -1=0 确定其有根区间确定其有根区间解：用试凑的方法，不难发现解：用试凑的方法，不难发现 f(0)0 (0)0(2)0 在区间（在区间（0 0，2 2）内至少有一个实根）内至少有一个实根 设从设从x=0=0出发出发,取取h=0.5=0.5为步长向右进行根的为步长向右进行根的 搜索搜索,列表如下列表如下确定有根区间的方法确定有根区间的方法第21页，此课件共84页哦22/87郑州大学研究生2014-2015学年课程 数值分析 N

20、umerical Analysis7.2 区间法xf(x)0 0.5 1.0 1.5 20 0.5 1.0 1.5 2 +可以看出，在可以看出，在1.0,1.51.0,1.5内必有一根内必有一根确定有根区间的方法确定有根区间的方法第22页，此课件共84页哦23/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.2 二分区间法二分法求根过程二分法求根过程 取有根区间取有根区间a,b之中点之中点,将它分为两半将它分为两半,分点分点 ,这样就可得缩小有根区间这样就可得缩小有根区间20bax y y=f(x)y=f(x)x*a x1 x*x0 b a x0

21、 x1 b a1 b1 a1 b1 a2 b2 a2 b2 11,ba第23页，此课件共84页哦24/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.2 二分区间法 对压缩了的有根区间对压缩了的有根区间 施行同样的手法施行同样的手法,即取中点即取中点 ,将区间将区间 再分为两半再分为两半,然然 后再确定有根区间后再确定有根区间 ,其长度是其长度是 的的 二分之一。二分之一。11,ba2111bax11,ba22,ba11,ba y y=f(x)y=f(x)x*a x1 x*x0 b a x0 x1 b a1 b1 a1 b1 a2 b2 a2 b

22、2 第24页，此课件共84页哦25/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.2 二分区间法 如此反复下去如此反复下去,若不出现若不出现 ,即可得出一即可得出一 系列有根区间序列：系列有根区间序列：上述每个区间都是前一个区间的一半上述每个区间都是前一个区间的一半,因此因此 的长度的长度0)(kxfkkbabababa,2211)(21)(2111abababkkkkk 当当k时趋于零时趋于零,这些区间最终收敛于一点这些区间最终收敛于一点x*即为即为 所求的根所求的根。第25页，此课件共84页哦26/87郑州大学研究生2014-2015学年课

23、程 数值分析 Numerical Analysis7.2 二分区间法每次二分后每次二分后,取有根区间取有根区间 的中点的中点作为根的近似值，得到一个近似根的序列作为根的近似值，得到一个近似根的序列 该序列以根该序列以根x x*为极限为极限 只要二分足够多次只要二分足够多次(即即k足够大足够大),),便有便有这里这里为给定精度为给定精度,由于由于 ,则则 kkba,)(21kkkbax,210kxxxxkxx*kkbax,*第26页，此课件共84页哦27/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.2 二分区间法11122kkkkkababab

24、1*22kkkkababxx第27页，此课件共84页哦28/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.2 二分区间法当给定精度当给定精度0 0后后,要想要想 成立成立,只要只要取取k满足满足 即可，亦即当即可，亦即当:kxx*)(211abklg()lg1lg 2bakK时时,做到第做到第K+1次二分次二分,计算得到的计算得到的 就是满足就是满足精度要求的近似根精度要求的近似根。kx第28页，此课件共84页哦29/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis y n 开 始 输 入 a,b,(

25、a+b)/2 x f(a)f(x)0?xb x a|b-a|0 输 出 x 结 束 y n 二分区间法算法实现二分区间法算法实现第29页，此课件共84页哦30/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 例例7.2.2 7.2.2 证明方程证明方程 在区间在区间2,3内有一个根内有一个根,使用二分法求误差不超过使用二分法求误差不超过0.510-3 的根要二的根要二 分多少次？分多少次？证明证明 令令 0523 xx且且f(x)f(x)在在2,3上连续上连续,故方程故方程f(x)=0f(x)=0在在2,32,3内至少有一内至少有一个根。又个根。又

26、 当时当时时，时，,故故f(x)f(x)在在2,32,3上是单调递增函数上是单调递增函数,从而从而f(x)f(x)在在2,32,3上有且仅有一根。上有且仅有一根。23)(2xxf3,2x0)(xf 给定误差限给定误差限 0.510-3,使用二分法时使用二分法时52)(3xxxf016)3(,01)2(ff第30页，此课件共84页哦31/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.2 二分区间法 误差限为误差限为 只要取只要取k满足满足)(211*abxxkk311021)(21 abk即可，亦即即可，亦即 3102 k97.92110lg3g

27、k所以需二分所以需二分1010次便可达到要求。次便可达到要求。第31页，此课件共84页哦32/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.2 二分区间法二分法的优点二分法的优点不管有根区间不管有根区间 多大多大,总能求出满足精度要求的根总能求出满足精度要求的根,且且对函数对函数f(x)的要求不高的要求不高,只要连续即可只要连续即可,计算亦简单计算亦简单;二分法的二分法的局限性局限性只能用于求函数的实根只能用于求函数的实根,不能用于求复根及偶数重根不能用于求复根及偶数重根,它的它的收敛速度与比值为收敛速度与比值为 的等比级数相同。的等比级数相同

28、。ba,21第32页，此课件共84页哦33/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 例7.2.3 求方程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.8125 0.7812 5 0.7812 0.7656 60.7656 0.7734 7 0.7734 0.7695 8 0.7695 0.7714

29、90.7714 0.7724 100.7724 0.7729 取x10=0.7729，误差为|x*-x10|=1/211。第33页，此课件共84页哦34/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.3 迭代法及其加速为求解非线性方程为求解非线性方程f(x)=0)=0的根，先将其写成便于迭代的的根，先将其写成便于迭代的等价等价方程方程 其中其中 为为x的连续函数的连续函数)(x)(xx迭代法的基本思想迭代法的基本思想 如果数如果数 使使 f(x*)=0,则也有则也有 ,反之反之,若若 ,则也有则也有 ,称称 为为迭代函数迭代函数，而称，而称x*

30、为为 的的不动点不动点。*x)(*xx)(*xx0)(*xf)(x)(x第34页，此课件共84页哦35/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.3 迭代法及其加速任取一个初值任取一个初值 ,代入式代入式 的右端的右端,得到得到 0 x)(xx)(01xx再将再将 代入式代入式 的右端的右端,得到得到 ,依此类依此类推推,得到一个数列得到一个数列 ，其一般表示其一般表示 1x)(xx)(12xx)(23xx),2,1,0()(1kxxkk称为求解非线性方程的称为求解非线性方程的简单迭代法简单迭代法。第35页，此课件共84页哦36/87郑州大

31、学研究生2014-2015学年课程 数值分析 Numerical Analysis7.3 迭代法及其加速如果由迭代格式如果由迭代格式 产生的序列产生的序列 收敛收敛,即即 nx)(1kkxx*limxxnn则称则称迭代法收敛迭代法收敛。第36页，此课件共84页哦37/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.3 迭代法及其加速 实际计算中当然不可能也没必要无穷多步地做下去实际计算中当然不可能也没必要无穷多步地做下去,对对预先给定的精度要求预先给定的精度要求，只要某个，只要某个k k满足满足1kkxx即可结束计算并取即可结束计算并取 kxx*

32、第37页，此课件共84页哦38/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.3 迭代法及其加速例例7.3.1 用迭代法求方程用迭代法求方程 在在x=1.5附近的一个根附近的一个根解解 将方程改写成如下两种等价形式将方程改写成如下两种等价形式 013 xx1)(1)(3231xxxxxx相应地可得到两个迭代公式相应地可得到两个迭代公式1)(1)(321311kkkkkkxxxxxx第38页，此课件共84页哦39/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.3 迭代法及其加速如果取初始值如果取初

33、始值 1.51.5，用上述两个迭代公式分，用上述两个迭代公式分别迭代，计算结果为别迭代，计算结果为 0 x第39页，此课件共84页哦40/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.3 迭代法及其加速迭代法的几何意义迭代法的几何意义 通常将方程通常将方程f(x)=0)=0化为与它同解的方程化为与它同解的方程的方法不止一种的方法不止一种,有的收敛有的收敛,有的不收敛有的不收敛,这取决于这取决于 的的性态。性态。方程方程 的求根问题在几何上就是确定曲线的求根问题在几何上就是确定曲线 与直线与直线y=x的交点的交点P*的横坐标。的横坐标。)(xx)

34、(x)(xx()yx第40页，此课件共84页哦41/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.3 迭代法及其加速 y=x y y=)(x y=x 1)(0*x 0)(1*x P0 P2P*Q1 Q2 x1 x0 x2 x*x y x0 x x1 x2 x3 x*y=)(x)(x P*P1 迭代法的几何意义迭代法的几何意义 第41页，此课件共84页哦42/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.3 迭代法及其加速 y=x y y=x y=)(x 1)(*x 1)(*x （c）（d）P*x

35、1 x0 x y x0 x x1 x2 x3 x*y=)(x)(x x*x2 P*迭代法的几何意义迭代法的几何意义 第42页，此课件共84页哦43/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.3 迭代法及其加速迭代法的收敛性迭代法的收敛性 对方程对方程f(x)=0可以构造不同的迭代公式可以构造不同的迭代公式,但但迭代公式迭代公式并非总是收敛。那么并非总是收敛。那么,当迭代函数当迭代函数 满足什满足什么条件时，相应的迭代公式才收敛呢？么条件时，相应的迭代公式才收敛呢？),2,1,0()(1kxxkk)(x第43页，此课件共84页哦44/87郑州

36、大学研究生2014-2015学年课程 数值分析 Numerical Analysis定理定理7.3.1 设函数设函数 在在a,b上有连续的一阶导上有连续的一阶导 数数,且满足且满足 （1）对所有的）对所有的xa,b 有有 a,b(映内映内)（2）存在）存在 0 L 1,使所有的使所有的xa,b有有 L （压缩性）（压缩性）则方程则方程 在在a,b上的解上的解 存在且唯一存在且唯一，对任意，对任意的初值的初值 a,b，迭代过程，迭代过程均收敛于均收敛于 。并有误差估计式。并有误差估计式)(x)(x)(x)(xx*x0 x)(1kkxx*x1*1kkkxxLLxx01*1xxLLxxkk 第44页

37、，此课件共84页哦45/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis由连续函数介值定理知由连续函数介值定理知,必有必有 a,b,使使 所以有解存在所以有解存在,即即假设有两个解假设有两个解 和和 ,a,b，则，则，由微分中值定理有由微分中值定理有其中其中是介于是介于x*和和 之间的点之间的点 从而有从而有a,b，进而有，进而有 由条件由条件(2)有有 1,所以所以 -=0，即，即 =，解，解唯一。唯一。证证:构造函数构造函数 ,由条件对任意的由条件对任意的xa,b a,b有有xxx)()(0)()(0)()(bbbaaa)(x*x0)()(*xx

38、x*xx*xx)(*xx)(xx)()()(*xxxxxxx0)(1)(*xx)(x*xx*xx第45页，此课件共84页哦46/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis按迭代过程按迭代过程 ,有有)(1kkxx)()()(1*1*kkkxxxxxx1*1*)(kkkxxLxxxx0*2*21*xxLxxLxxLxxkkkk 由于由于L1,L1,所以有所以有 ,可见可见L L越小越小,收敛越快收敛越快 *limxxkk再证误差估计式再证误差估计式 1*1kkkxxLLxx01*1xxLLxxkk 第46页，此课件共84页哦47/87郑州大学研究

39、生2014-2015学年课程 数值分析 Numerical Analysis 1*1*kkkkkxxxxLxxLxx)(1*kkkxxxxL1*)1(kkkxxLxxL1*1kkkxxLLxx 即即 得证。得证。2121211)()()(kkkkkkkkxxLxxxxxx2*11210111kkkkkkLLLxxxxxxxxLLL即即 得证。得证。第47页，此课件共84页哦48/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 10)(xx 开 始 输 入 x0,N 1 kk+1 k x1 x0 输 出 近 似 根 x1|x1-x0|?输 出 迭 代

40、 失 败 标 志 结 束 n k0c0），使），使 )(1kkxx)(xx*xkkxxe*迭代法的收敛速度迭代法的收敛速度ceepkkk1lim则称序列则称序列 是是 p 阶收敛阶收敛的的,c称称渐近误差常数渐近误差常数。特。特别地别地,p=1=1时称为时称为线性收敛线性收敛,p=2=2时称为时称为平方收敛平方收敛。1 1 p 2 0 xn+1X*ayx0Bf(x)0a=x0yx0B=x0f(x)0ayx0Bf(x)0a=x0牛顿迭代法的收敛性牛顿迭代法的收敛性第67页，此课件共84页哦68/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.4 牛

41、顿(Newton)迭代法 牛顿迭代法对初值牛顿迭代法对初值x x0 0的选取要求比较高。的选取要求比较高。x x0 0必须充分靠必须充分靠近近x x*才能保证局部收敛。才能保证局部收敛。定理定理7.4.2 如果在有根区间如果在有根区间a,b上上连续且不变号，在连续且不变号，在a,b上取初始近似根上取初始近似根x0满足，满足，则牛顿迭代法产生的迭代序列单调收敛于方程则牛顿迭代法产生的迭代序列单调收敛于方程f(x)=0在该区间上的唯一解。在该区间上的唯一解。)(,0)(,0)()(xfxfbfaf 0)()(00 xfxf第68页，此课件共84页哦69/87郑州大学研究生2014-2015学年课程

42、 数值分析 Numerical AnalysisNewton法的收敛性依赖于法的收敛性依赖于x0 的选取。的选取。x*x0 x0 x0 不满足迭代条件时，可能导致迭代值远离根不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况的情况而找不到根或死循环的情况第69页，此课件共84页哦70/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis?0)(0 xf 1000)()(xxfxfx?01 xx 开 始 输 入 x0,N 1k k+1 k x1 x0 输出x1 输出迭代 失败标志 结 束 n kN?n n y 输出奇 异标志 y y 牛顿

43、迭代法的算法实现牛顿迭代法的算法实现第70页，此课件共84页哦71/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 牛顿法的优点 牛顿法是目前求解非线性方程(组)的主要方法至少二阶局部收敛，收敛速度较快，特别是当迭代点充分至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠近精确解时。可求重根和复根。靠近精确解时。可求重根和复根。牛顿的缺点 对重根收敛速度较慢（线性收敛）对重根收敛速度较慢（线性收敛）对初值的选取很敏感，要求初值相当接近真解对初值的选取很敏感，要求初值相当接近真解在实际计算中，可以先用其它方法获得真解的一个粗糙近似在实际计算中，可以

44、先用其它方法获得真解的一个粗糙近似，然后再用牛顿法求解。，然后再用牛顿法求解。第71页，此课件共84页哦72/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.5 弦截法牛顿迭代法虽然具有牛顿迭代法虽然具有收敛速度快收敛速度快的优点，但每迭的优点，但每迭代一次都要计算导数代一次都要计算导数 ,当当 比较复杂时比较复杂时,不仅每次计算不仅每次计算 带来很多不便，而且还可能带来很多不便，而且还可能十分麻烦，如果用不计算导数的迭代方法，往往十分麻烦，如果用不计算导数的迭代方法，往往只有线性收敛的速度。本节介绍的弦截法便是一只有线性收敛的速度。本节介绍的弦

45、截法便是一种不必进行导数运算的求根方法。种不必进行导数运算的求根方法。)(kxf)(xf)(kxf第72页，此课件共84页哦73/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.5 弦截法 弦截法在迭代过程中不仅用到前一步弦截法在迭代过程中不仅用到前一步 处的函数值处的函数值，而且还使用，而且还使用 处的函数值来构造迭代函数，这处的函数值来构造迭代函数，这样做能提高迭代的收敛速度。样做能提高迭代的收敛速度。称之为称之为多点迭代法多点迭代法。kx1kx第73页，此课件共84页哦74/87郑州大学研究生2014-2015学年课程 数值分析 Numer

46、ical Analysis7.5 弦截法弦截法的基本思想弦截法的基本思想 为避免计算函数的导数为避免计算函数的导数 ，使用差商，使用差商 替代牛顿公式中的导数替代牛顿公式中的导数 ,便得到迭代公式便得到迭代公式 称为称为弦截迭代公式弦截迭代公式，相应的迭代法称为，相应的迭代法称为弦截法弦截法。)()()(11kkkkxxxfxf)(kxf 111()()()()kkkkkkkxxxxf xf xf x),2,1(k)(kxf 第74页，此课件共84页哦75/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.5 弦截法弦截法的几何意义弦截法的几何意义

47、 弦截法也称割线法弦截法也称割线法,其几何意义是用过曲线上两点其几何意义是用过曲线上两点 、的割线来代替曲线的割线来代替曲线,用割线与用割线与x轴交点的横轴交点的横座标作为方程的近似根座标作为方程的近似根 再过再过)(,(000 xfxP)(,(111xfxP2x P1 y=f(x)x0 x2 x3 x1 x*P3 P0 P2 P1点和点点和点 作割线求作割线求出出 ,再过再过P2点和点点和点 作割线求出作割线求出 ,余余此类推，当收敛时可求出满此类推，当收敛时可求出满足精度要求的足精度要求的)(,(222xfxP3x)(,(333xfxP4xkx第75页，此课件共84页哦76/87郑州大学研

48、究生2014-2015学年课程 数值分析 Numerical Analysis7.5 弦截法 可以证明，弦截法具有超线性收敛，收敛的阶约可以证明，弦截法具有超线性收敛，收敛的阶约为为1.618，它与前面介绍的一般迭代法一样都是，它与前面介绍的一般迭代法一样都是线性化方法，但也有区别。即一般迭代法在计算线性化方法，但也有区别。即一般迭代法在计算 时只用到前一步的值时只用到前一步的值 ，故称之为，故称之为单点迭代法单点迭代法；而弦截法在求而弦截法在求 时要用到前两步的结果时要用到前两步的结果 和和 ，使用这种方法必须给出两个初始近似根使用这种方法必须给出两个初始近似根 ，这，这种方法称为种方法称为

49、多点迭代法多点迭代法。1kxkx1kx1kxkx10,xx第76页，此课件共84页哦77/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis?0)(0 xf?0)(1xf?0)()(01xfxf 2010111)()()()(xxxxfxfxfx?12 xx 输 入 x0,x1,N 1k k+1 k x1 x0 x2 x1 f(x1)f(x0)f(x2)f(x1)输出x2 输出迭代 失败标志 结 束 n kN?n n y 输出奇 异标志 y y x0 x2 x1 x2 n y y n 输出x2 弦截法算法实现弦截法算法实现 第77页，此课件共84页哦7

50、8/87郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis7.5 弦截法例例7.5.1 用弦截法求方程用弦截法求方程 在在 初始初始 值邻近的一个根。要求值邻近的一个根。要求解：取解：取 ,令令 利用弦截迭代公式利用弦截迭代公式 易见取近似根易见取近似根 可满足精度要求。可满足精度要求。xex5.00 x0001.01kkxx5.00 x6.01xxexxf)()()()()(1111kkxxkkxkkkxxeexxexxxkkk56714.04x第78页，此课件共84页哦79/87郑州大学研究生2014-2015学年课程 数值分析 Numerical A