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

1、ISCM 2007,Beijing China 1 y=x y y=)(x y=x 1)(0 * x 0)(1 * x P0 P2 P* Q1 Q2 x1 x0 x2 x* x y x0 x x1 x2 x3 x* y=)(x )(x P* P1 数值分析数值分析 Numerical Analysis 第七章 非线性方程（组）的数值解法 郑州大学研究生课程郑州大学研究生课程 （2014-20152014-2015学年第一学期）学年第一学期） ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 第七章

2、非线性方程（组）的数值解法 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,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.1 引言 在科学研究和工程设计中在科学研究和工程设计中, 经常会遇到的一大类经常会遇到的一大类 问题是问题是非线性方程非线性方程 f (x)=0 的求根问题，其中的求根问题，其中

3、f (x)为非为非 线性函数。线性函数。 方程方程f ( x) =0的根的根, 亦称为函数亦称为函数 f(x) 的的零点零点。 非线性方程的例子 （1）在光的衍射理论中,需要求x-tanx=0=0的根 （2）在行星轨道的计算中, 需要求x-asinx=b的根 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.1 引言 当当 f (x)不是不是x x的线性函数时，称对应的函数方程的线性函数时，称对应的函数方程 f (x)=0为为非线性方程非线性方程。 如果如果 f(x)(x)是多项式函数，则称为是

4、多项式函数，则称为代数方程代数方程。 否则为否则为超越方程超越方程（三角方程，指数、对数方程（三角方程，指数、对数方程 等）。一般称等）。一般称n次多项式构成的方程次多项式构成的方程 )0(0 01 1 1 n n n n n aaxaxaxa 为为n次代数方程次代数方程, ,当当n n1 1时时, ,方程显然是非线性的方程显然是非线性的 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.1 引言 如果如果f (x)可以分解成可以分解成 , ,其中其中m为为 正整数且正整数且 , ,则称则称x*

5、 *是是f(x)(x)的的m重零点重零点, ,或或 称方程称方程f (x)=0的的m重根重根。当。当m=1时称时称x* *为为单根单根。 )()()( * xgxxxf m 0)( * xg 求方程根的问题，就几何上讲求方程根的问题，就几何上讲,是求曲线是求曲线 y=f (x)与与 x轴轴交点交点的横坐标。的横坐标。 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.1 引言 公元前公元前17001700年的古巴比伦人有关于一、二次代数方程的解年的古巴比伦人有关于一、二次代数方程的解 法。法。九

6、章算术九章算术( (公元前公元前5010050100年年) )其中其中“方程术方程术”有联有联 立一次方程组的一般解法。立一次方程组的一般解法。 15351535年意大利数学家坦特格里亚年意大利数学家坦特格里亚(TorTaglia)(TorTaglia)发现了三次代数发现了三次代数 方程的解法，卡当方程的解法，卡当(HCardano)(HCardano)从他那里得到了这种解法，从他那里得到了这种解法， 于于15451545年在其名著年在其名著大法大法中公布了三次方程的公式解，中公布了三次方程的公式解， 称为卡当算法。称为卡当算法。 后来卡当的学生弗瑞里后来卡当的学生弗瑞里(Ferrari)(F

7、errari)又提出了四次代数方程的解又提出了四次代数方程的解 法。此成果更激发了数学家们的情绪，但在以后的二个世法。此成果更激发了数学家们的情绪，但在以后的二个世 纪中，求索工作始终没有成效，导致人们对高次代数方程纪中，求索工作始终没有成效，导致人们对高次代数方程 解的存在性产生了怀疑。解的存在性产生了怀疑。 代数方程求根的历史 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.1 引言代数方程求根的历史 17991799年，高斯证明了代数方程必有一个实根或复根的定理，年，高斯证明了代数方程必

8、有一个实根或复根的定理， 称此为称此为代数基本定理代数基本定理，并由此可以立刻推理，并由此可以立刻推理n n次代数方程次代数方程 必有必有n n个实根或复根。个实根或复根。 但在以后的几十年中仍然没有找出高次代数方程的公式解。但在以后的几十年中仍然没有找出高次代数方程的公式解。 一直到一直到1818世纪，法国数学家拉格朗日用根置换方法统一了世纪，法国数学家拉格朗日用根置换方法统一了 二、三、四次方程的解法。二、三、四次方程的解法。 在继续探索在继续探索5 5次以上方程解的艰难历程中，第一个重大突次以上方程解的艰难历程中，第一个重大突 破的是挪威数学家阿贝尔破的是挪威数学家阿贝尔(NAbel18

9、02-1829) 1824(NAbel1802-1829) 1824年阿年阿 贝尔发表了贝尔发表了“五次方程的代数解法不可能存在五次方程的代数解法不可能存在”的论文，的论文， 但并未受到重视，连数学大师高斯也未理解这项成果的重但并未受到重视，连数学大师高斯也未理解这项成果的重 要意义。要意义。 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.1 引言代数方程求根的历史 18281828年年1717岁的法国数学家伽罗华岁的法国数学家伽罗华(EGalois 1811-1832)(EGalois 1

10、811-1832)写写 出了划时代的论文出了划时代的论文“关于五次方程的代数解法问题关于五次方程的代数解法问题”，指，指 出即使在公式中容许用出即使在公式中容许用n n次方根，并次方根，并用类似算法求五次或更用类似算法求五次或更 高次代数方程的根是不可能的。高次代数方程的根是不可能的。”， “他一劳永逸地发现了一个折磨了数学家几个世纪的谜团他一劳永逸地发现了一个折磨了数学家几个世纪的谜团 的答案：在什么条件下一个方程有解？的答案：在什么条件下一个方程有解？” ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Anal

11、ysis 7.1 引言 理论上已证明，对于次数n=4的多项式方程,它的根 可以用公式表示,而次数大于5的多项式方程,它的根 一般不能用解析表达式表示. 因此对于f(x)=0的函数方程,一般来说,不存在根的解 析表达式,而实际应用中,也不一定必需得到求根的 解析表达式,只要得到满足精度要求的根的近似值就 可以了。 常用的求根方法分为区间法和迭代法两大类。 求根问题包括：根的存在性、根的范围和根的精确化。 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.1 引言 ISCM 2007,Beiji n

12、g China/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 上单调连续,且 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( sfsfsfsf mm 7.1 引言 y=f(x

13、) a b y x ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.2 二分区间法 设函数设函数f( (x) )在闭区间在闭区间 a, ,b 上连续上连续, ,且且f ( (a) )f( (b)0,)0, 根据连续函数的性质可知根据连续函数的性质可知, , f ( (x)= 0)= 0在在( (a, ,b) )内必有实内必有实 根根, ,称区间称区间 a, ,b 为为有根区间有根区间。 假定方程假定方程 f (x)= 0 0在区间在区间 a, ,b 内有惟一实根内有惟一实根x* *。 二分法的

14、基本思想二分法的基本思想是是: : 首先确定一个有根区间首先确定一个有根区间, ,将将 区间二等分区间二等分, , 通过判断通过判断f(x)在区间端点的符号在区间端点的符号, , 逐步将逐步将 有根区间缩小有根区间缩小, , 直至直至有根区间足够地小有根区间足够地小, , 便可求出满便可求出满 足精度要求的近似根。足精度要求的近似根。 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.2 二分法 q 基本思想 将有根区间进行对分，判断出解在某个分段内，然后将有根区间进行对分，判断出解在某个分段内

15、，然后 再对该段对分，依次类推，直到满足给定的精度为止再对该段对分，依次类推，直到满足给定的精度为止 q 适用范围适用范围 求有根区间内的求有根区间内的 奇数重实根奇数重实根 q 数学原理：数学原理：介值定理介值定理 设设 f(x) 在在 a, b 上连续，且上连续，且 f(a) f(b)0，则由介值定，则由介值定 理可得，在理可得，在 (a, b) 内至少存在一点内至少存在一点 使得使得 f( )=0 b a 2 ba *x ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 二分法是一种确定有根区

16、间的方法二分法是一种确定有根区间的方法 为了确定根的初值，首先必须圈定根所在的范围，为了确定根的初值，首先必须圈定根所在的范围， 称为称为圈定根圈定根或或根的隔离根的隔离。 在上述基础上，采取适当的数值方法确定具有一定在上述基础上，采取适当的数值方法确定具有一定 精度要求的初值。精度要求的初值。 对于代数方程，其根的个数（实或复的）与其次数对于代数方程，其根的个数（实或复的）与其次数 相同相同。至于超越方程，其根可能是一个、几个或无。至于超越方程，其根可能是一个、几个或无 解，并没有什么固定的圈根方法解，并没有什么固定的圈根方法 ISCM 2007,Beiji ng China/87 郑州大学

17、研究生2014-2015学年课程 数值分析 Numerical Analysis 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,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.2 区间法 n由此可大体确定根所在子区间，方法有：由此可大体确定

18、根所在子区间，方法有： (1) 画图法画图法 (2) 逐步搜索法逐步搜索法 确定有根区间的方法确定有根区间的方法 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.2 区间法 (1) 画图法画图法 画出画出y = f (x)的略图，从而看出曲线与的略图，从而看出曲线与x轴交点的轴交点的 大致位置。大致位置。 也可将也可将f (x) = 0分解为分解为 1(x)= 2(x)的形式，的形式， 1(x) 与与 2(x)两曲线交点的横坐标所在的子区间即为含根两曲线交点的横坐标所在的子区间即为含根 区间。

19、区间。 例如例如 xlogx-1= 0= 0 可以改写为可以改写为logx= =1/x 画出对数曲线画出对数曲线y=logx, ,与双曲线与双曲线y= 1/x,它们交它们交 点的横坐标位于区间点的横坐标位于区间2,32,3内内 确定有根区间的方法确定有根区间的方法 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.2 区间法 (1) 画图法画图法 x y 1 gxy 0 23 y x 确定有根区间的方法确定有根区间的方法 ISCM 2007,Beiji ng China/87 郑州大学研究生20

20、14-2015学年课程 数值分析 Numerical Analysis 7.2 区间法 (1) 画图法画图法 y 0 x y=f(x)y=kf(x) 确定有根区间的方法确定有根区间的方法 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.2 区间法 y 0 x A B a1b1a2b2 (2) 搜索法 对于给定的对于给定的f (x),设有根区间为设有根区间为A, ,B,从从x0=A出发出发, ,以步以步 长长h=(B-A)/n(n是是正整数正整数),在在A,B内取定节点内取定节点: :xi=x0

21、ih (i=0,1,2,n),从左至右检查从左至右检查f (xi)的符号的符号, ,如发现如发现xi与端点与端点x0 的函数值异号的函数值异号, ,则得到一个缩小的有根子区间则得到一个缩小的有根子区间xi-1, ,xi。 确定有根区间的方法确定有根区间的方法 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.2 区间法 例例7.2.17.2.1 方程方程f(x)=(x)=x3 3- -x-1=0 -1=0 确定其有根区间确定其有根区间 解：用试凑的方法，不难发现解：用试凑的方法，不难发现 f(0

22、)0 (0)0(2)0 在区间（在区间（0 0，2 2）内至少有一个实根）内至少有一个实根 设从设从x=0=0出发出发, ,取取h=0.5=0.5为步长向右进行根的为步长向右进行根的 搜索搜索, ,列表如下列表如下 确定有根区间的方法确定有根区间的方法 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.2 区间法 x f( (x) ) 0 0.5 1.0 1.5 20 0.5 1.0 1.5 2 + + + + 可以看出，在可以看出，在1.0,1.51.0,1.5内必有一根内必有一根 确定有根区

23、间的方法确定有根区间的方法 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.2 二分区间法二分法求根过程二分法求根过程 取有根区间取有根区间a,b之中点之中点, 将它分为两半将它分为两半,分点分点 ,这样就可得缩小有根区间这样就可得缩小有根区间 2 0 ba x y y=f(x) y=f(x) x* a x1 x* x0 b a x0 x1 b a1 b1 a1 b1 a2 b2 a2 b2 11 ,ba ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015

24、学年课程 数值分析 Numerical Analysis 7.2 二分区间法 对压缩了的有根区间对压缩了的有根区间 施行同样的手法施行同样的手法, , 即取中点即取中点 , ,将区间将区间 再分为两半再分为两半, ,然然 后再确定有根区间后再确定有根区间 , ,其长度是其长度是 的的 二分之一。二分之一。 11 ,ba 2 11 1 ba x 11 ,ba 22,b a 11 ,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 b2 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-

25、2015学年课程 数值分析 Numerical Analysis 7.2 二分区间法 如此反复下去如此反复下去, ,若不出现若不出现 , ,即可得出一即可得出一 系列有根区间序列：系列有根区间序列： 上述每个区间都是前一个区间的一半上述每个区间都是前一个区间的一半, ,因此因此 的长度的长度 0)( k xf kk babababa, 2211 )( 2 1 )( 2 1 11 ababab k kkkk 当当k时趋于零时趋于零, ,这些区间最终收敛于一点这些区间最终收敛于一点x* * 即为即为 所求的根所求的根 。 ISCM 2007,Beiji ng China/87 郑州大学研究生201

26、4-2015学年课程 数值分析 Numerical Analysis 7.2 二分区间法 每次二分后每次二分后, ,取有根区间取有根区间 的中点的中点 作为根的近似值，得到一个近似根的序列作为根的近似值，得到一个近似根的序列 该序列以根该序列以根x x* *为极限为极限 只要二分足够多次只要二分足够多次( (即即k足够大足够大),),便有便有 这里这里为给定精度为给定精度, ,由于由于 , ,则则 kk ba ,)( 2 1 kkk bax , 210k xxxx k xx* kk bax, * ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程

27、数值分析 Numerical Analysis 7.2 二分区间法 1 11 22 k kk kk ab ab ab 1 * 22 k kk k abab xx ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.2 二分区间法 当给定精度当给定精度0 0后后, ,要想要想 成立成立, ,只要只要 取取k满足满足 即可，亦即当即可，亦即当: k xx * )( 2 1 1 ab k lg()lg 1 lg 2 ba kK 时时, ,做到第做到第K+1次二分次二分, ,计算得到的计算得到的 就是就是

28、 满足精度要求的近似根满足精度要求的近似根 。 k x ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis y n 开 始 输 入 a , b, (a+b)/2 x f(a) f(x )0 ? xb x a |b-a| 0 输 出 x 结 束 y n 二分区间法算法实现 二分区间法算法实现 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 例例7.2.2 7.2.2 证明方程证明方程 在区间在区间2, 3内

29、有一内有一 个根个根 , 使用二分法求误差不超过使用二分法求误差不超过0.510-3 的根要二的根要二 分多少次？分多少次？ 证明证明 令令 052 3 xx 且且f(x)f(x)在在2, 3上连续上连续, ,故方程故方程f(x)=0f(x)=0在在2,32,3内至少内至少 有一个根。又有一个根。又 当时当时 时，时， , ,故故f(x)f(x)在在2, 32, 3上是单调递增函数上是单调递增函数, , 从而从而f(x)f(x)在在2, 32, 3上有且仅有一根。上有且仅有一根。 23)( 2 xxf3 , 2x 0)( x f 给定误差限给定误差限 0.510-3 , ,使用二分法时使用二分

30、法时 52)( 3 xxxf 016)3(, 01)2(ff ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.2 二分区间法 误差限为误差限为 只要取只要取k满足满足 )( 2 1 1 * abxx k k 3 1 10 2 1 )( 2 1 ab k 即可，亦即即可，亦即 3 102 k97.9 21 10lg3 g k 所以需二分所以需二分1010次便可达到要求。次便可达到要求。 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 N

31、umerical Analysis 7.2 二分区间法 二分法的优点二分法的优点 不管有根区间不管有根区间 多大多大, ,总能求出满足精度要求的总能求出满足精度要求的 根根, ,且对函数且对函数f( (x) )的要求不高的要求不高, ,只要连续即可只要连续即可, ,计算亦计算亦 简单简单; ; 二分法的二分法的局限性局限性 只能用于求函数的实根只能用于求函数的实根, ,不能用于求复根及偶数重根不能用于求复根及偶数重根, , 它的收敛速度与比值为它的收敛速度与比值为 的等比级数相同。的等比级数相同。 ba , 2 1 ISCM 2007,Beiji ng China/87 郑州大学研究生2014

32、-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.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.772

33、9 取x10=0.7729，误差为| x* -x10|=1/211 。 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.3 迭代法及其加速 为求解非线性方程为求解非线性方程f( (x)=0)=0的根，先将其写成便于迭代的根，先将其写成便于迭代 的的等价方程等价方程 其中其中 为为x的连续函数的连续函数)(x )(xx 迭代法的基本思想迭代法的基本思想 如果数如果数 使使 f(x*)=0, 则也有则也有 , 反之反之, 若若 , 则也有则也有 , 称称 为为迭代函数迭代函数，而，而 称称x* 为

34、为 的的不动点不动点。 * x)( * xx )( * xx0)( * xf)(x )(x ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.3 迭代法及其加速 任取一个初值任取一个初值 , 代入式代入式 的右端的右端, 得得 到到 0 x)(xx )( 01 xx 再将再将 代入式代入式 的右端的右端, 得到得到 , 依此类推依此类推, 得到一个数列得到一个数列 ， 其一般表示其一般表示 1 x )(xx)( 12 xx )( 23 xx ), 2 , 1 , 0()( 1 kxx kk 称为

35、求解非线性方程的称为求解非线性方程的简单迭代法简单迭代法。 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.3 迭代法及其加速 如果由迭代格式如果由迭代格式 产生的序列产生的序列 收敛收敛, , 即即 n x )( 1kk xx * limxx n n 则称则称迭代法收敛迭代法收敛。 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.3 迭代法及其加速 实际计算中当然不可能也没必要无穷多步地做实

36、际计算中当然不可能也没必要无穷多步地做 下去下去, , 对预先给定的精度要求对预先给定的精度要求，只要某个，只要某个k k满足满足 1kk xx 即可结束计算并取即可结束计算并取 k xx * ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.3 迭代法及其加速 例例7.3.1 用迭代法求方程用迭代法求方程 在在x=1.5附近的一个根附近的一个根 解解 将方程改写成如下两种等价形式将方程改写成如下两种等价形式 01 3 xx 1)( 1)( 3 2 3 1 xxx xxx 相应地可得到两个迭代公

37、式相应地可得到两个迭代公式 1)( 1)( 3 21 3 11 kkk kkk xxx xxx ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.3 迭代法及其加速 如果取初始值如果取初始值 1.51.5，用上述两个迭代公，用上述两个迭代公 式分别迭代，计算结果为式分别迭代，计算结果为 0 x ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.3 迭代法及其加速 迭代法的几何意义迭代法的几何意义

38、通常将方程通常将方程f( (x)=0)=0化为与它同解的方程化为与它同解的方程 的方法不止一种的方法不止一种, ,有的收敛有的收敛, ,有的不收敛有的不收敛, ,这取决于这取决于 的性态。的性态。 方程方程 的求根问题在几何上就是确定曲线的求根问题在几何上就是确定曲线 与直线与直线y=x的交点的交点P*的横坐标。的横坐标。 )(xx )(x )(xx ( )yx ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.3 迭代法及其加速 y=x y y=)(x y=x 1)(0 * x 0)(1 *

39、x P0 P2 P* Q1 Q2 x1 x0 x2 x* x y x0 x x1 x2 x3 x* y=)(x )(x P* P1 迭代法的几何意义迭代法的几何意义 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.3 迭代法及其加速 y=x y y=x y=)(x 1)( * x 1)( * x （c） （d） P* x1 x0 x y x0 x x1 x2 x3 x* y=)(x )(x x* x2 P* 迭代法的几何意义迭代法的几何意义 ISCM 2007,Beiji ng China/8

40、7 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.3 迭代法及其加速 迭代法的收敛性迭代法的收敛性 对方程对方程f(x)=0可以构造不同的迭代公式可以构造不同的迭代公式, 但迭代公式但迭代公式 并非总是收敛。那么并非总是收敛。那么, ,当迭代函数当迭代函数 满足什满足什 么条件时，相应的迭代公式才收敛呢？么条件时，相应的迭代公式才收敛呢？ ),2, 1 ,0()( 1 kxx kk )(x ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 定理定理7.

41、3.1 设函数设函数 在在a,b上有连续的一阶导上有连续的一阶导 数数, 且满足且满足 （1）对所有的）对所有的xa,b 有有 a,b(映内映内) （2）存在）存在 0 L 1 ,使所有的使所有的xa,b有有 L （压缩性）（压缩性） 则方程则方程 在在a,b上的解上的解 存在且唯一存在且唯一，对，对 任意的初值任意的初值 a ,b ，迭代过程，迭代过程 均收敛于均收敛于 。并有误差估计式。并有误差估计式 )(x )(x )(x )(xx * x 0 x)( 1kk xx * x 1 * 1 kkk xx L L xx 01 * 1 xx L L xx k k ISCM 2007,Beiji

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

43、)()( bbb aaa )(x * x 0)()( * xxx * xx * xx )( * xx ) ( xx ) )() ()( * xxxxxx x 0)(1) ( * xx)(x * xx * x x ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 按迭代过程按迭代过程 ,有有 )( 1 kk xx )()()( 1 * 1 * kkk xxxxxx 1 * 1 * )( kkk xxLxxxx 0 * 2 *2 1 * xxLxxLxxLxx k kkk 由于由于L1,L1,所以有所以

44、有 , ,可见可见L L越小越小, ,收敛越快收敛越快 * limxxk k 再证误差估计式再证误差估计式 1 * 1 kkk xx L L xx 01 * 1 xx L L xx k k ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 1 * 1 * kkkkk xxxxLxxLxx )( 1 * kkk xxxxL 1 * )1 ( kkk xxLxxL 1 * 1 kkk xx L L xx 即即 得证。得证。 2121211 )()()( kkkkkkkk xxLxxxxxx 2 * 11

45、210 111 k kkkkk LLL xxxxxxxx LLL 即即 得证。得证。 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 10 )(xx 开 始 输 入 x0,N 1 k k+ 1 k x1 x0 输 出 近 似 根 x1 |x1- x0|? 输 出 迭 代 失 败 标 志 结 束 n k0c0），使），使 )( 1kk xx )(xx * x kk xxe * 迭代法的收敛速度迭代法的收敛速度 c e e p k k k 1 lim 则称序列则称序列 是是 p 阶收敛阶收敛的的, ,

46、c称称渐近误差常数渐近误差常数。 特别地特别地, ,p=1=1时称为时称为线性收敛线性收敛, ,p=2=2时称为时称为平方收平方收 敛敛。1 1 p 2 0 xn+1 X* a y x0 B f(x)0 a=x0 y x0 B=x0 f(x)0 a y x0 B f(x)0 a =x0 牛顿迭代法的收敛性牛顿迭代法的收敛性 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.4 牛顿(Newton)迭代法 牛顿迭代法对初值牛顿迭代法对初值x x0 0的选取要求比较高。的选取要求比较高。 x x0

47、0必须充必须充 分靠近分靠近x x* *才能保证局部收敛。才能保证局部收敛。 定理定理7.4.2 如果在有根区间如果在有根区间a,b上上 连续且不变号，在连续且不变号，在a,b上取初始近似根上取初始近似根x0满足，满足， 则牛顿迭代法产生的迭代序列单调收敛于方程则牛顿迭代法产生的迭代序列单调收敛于方程 f(x)=0在该区间上的唯一解。在该区间上的唯一解。 )(, 0)(, 0)()(xfxfbfaf 0)()( 00 x fxf ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis Newton法的收敛

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

49、法实现 牛顿迭代法的算法实现 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis q 牛顿法的优点 q 牛顿法是目前求解非线性方程 (组) 的主要方法 至少二阶局部收敛，收敛速度较快，特别是当迭至少二阶局部收敛，收敛速度较快，特别是当迭 代点充分靠近精确解时。可求重根和复根。代点充分靠近精确解时。可求重根和复根。 q 牛顿的缺点 l 对重根收敛速度较慢（线性收敛）对重根收敛速度较慢（线性收敛） l 对初值的选取很敏感，要求初值相当接近真解对初值的选取很敏感，要求初值相当接近真解 在实际计算中，可以先用

50、其它方法获得真解的一个粗在实际计算中，可以先用其它方法获得真解的一个粗 糙近似，然后再用牛顿法求解。糙近似，然后再用牛顿法求解。 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.5 弦截法 牛顿迭代法虽然具有牛顿迭代法虽然具有收敛速度快收敛速度快的优点，但的优点，但 每迭代一次都要计算导数每迭代一次都要计算导数 , 当当 比较比较 复杂时复杂时, 不仅每次计算不仅每次计算 带来很多不便，带来很多不便， 而且还可能十分麻烦，如果用不计算导数的而且还可能十分麻烦，如果用不计算导数的 迭代方法，往往

51、只有线性收敛的速度。本节迭代方法，往往只有线性收敛的速度。本节 介绍的弦截法便是一种不必进行导数运算的介绍的弦截法便是一种不必进行导数运算的 求根方法。求根方法。 )( k x f )(xf)( k x f ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.5 弦截法 弦截法在迭代过程中不仅用到前一步弦截法在迭代过程中不仅用到前一步 处的处的 函数值，而且还使用函数值，而且还使用 处的函数值来构造处的函数值来构造 迭代函数，这样做能提高迭代的收敛速度。迭代函数，这样做能提高迭代的收敛速度。 称之

52、为称之为多点迭代法多点迭代法。 k x 1k x ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.5 弦截法弦截法的基本思想弦截法的基本思想 为避免计算函数的导数为避免计算函数的导数 ，使用差商，使用差商 替代牛顿公式中的导数替代牛顿公式中的导数 , ,便得到迭代公式便得到迭代公式 称为称为弦截迭代公式弦截迭代公式，相应的迭代法称为，相应的迭代法称为弦截法弦截法。 )( )()( 1 1 kk kk xx xfxf )( k x f 1 1 1 () ( ) ( )() kk kkk kk x

53、x xxf x f xf x ),2, 1(k )( k x f ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.5 弦截法弦截法的几何意义弦截法的几何意义 弦截法也称割线法弦截法也称割线法, ,其几何意义是用过曲线上两其几何意义是用过曲线上两 点点 、 的割线来代替曲线的割线来代替曲线, ,用割用割 线与线与x轴交点的横座标作为方程的近似根轴交点的横座标作为方程的近似根 再过再过 )(,( 000 xfxP)(,( 111 xfxP 2 x P1 y=f(x) x0 x2 x3 x1 x*

54、P3 P0 P2 P1点和点点和点 作割作割 线求出线求出 , ,再过再过P2点和点点和点 作割线求出作割线求出 , , 余此类推，当收敛时可求余此类推，当收敛时可求 出满足精度要求的出满足精度要求的 )(,( 222 xfxP 3 x )(,( 333 xfxP 4 x k x ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.5 弦截法 可以证明，弦截法具有超线性收敛，收敛可以证明，弦截法具有超线性收敛，收敛 的阶约为的阶约为1.618，它与前面介绍的一般迭代法，它与前面介绍的一般迭代法 一

55、样都是线性化方法，但也有区别。即一般迭一样都是线性化方法，但也有区别。即一般迭 代法在计算代法在计算 时只用到前一步的值时只用到前一步的值 ，故称，故称 之为之为单点迭代法单点迭代法；而弦截法在求；而弦截法在求 时要用到前时要用到前 两步的结果两步的结果 和和 ，使用这种方法必须给出，使用这种方法必须给出 两个初始近似根两个初始近似根 ，这种方法称为，这种方法称为多点迭多点迭 代法代法。 1k x k x 1k x 1k x k x 10 ,xx ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis ?

56、0)( 0 xf ?0)( 1 xf ?0)()( 01 xfxf 201 01 1 1 )( )()( )( xxx xfxf xf x ? 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 弦截法算法实现弦截法算法实现 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.5 弦截法 例

57、例7.5.1 用弦截法求方程用弦截法求方程 在在 初始初始 值邻近的一个根。要求值邻近的一个根。要求 解：取解：取 , , 令令 利用弦截迭代公式利用弦截迭代公式 易见取近似根易见取近似根 可满足精度要求。可满足精度要求。 x ex 5 . 0 0 x 0001. 0 1 kk xx 5 . 0 0 x6.0 1 x x exxf )( )( )()( )( 1 1 1 1 kk xx kk x k kk xx eexx ex xx kk k 56714. 0 4 x ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical

58、 Analysis 7.5 解非线性方程组的迭代解法 考虑非线性方程组 在点(x0,y0)作二元Taylor展开，并取线性部分 1 2 ( , )0 ( , )0 f x y fx y 100100 110000 200200 220000 (,)(,) ( , )(,)()()0 (,)(,) ( , )(,)()()0 f xyf xy f x yf xyxxyy xy fxyfxy fx yfxyxxyy xy ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.5 解非线性方程组的迭代解法 100100 00100 200200 00200 (,)(,) ()()(,) (,)(,) ()()(,) f xyf xy xxyyf xy xy fxyfxy xxyyfxy xy 整理得 这是关于x,y的线性方程组。 从而将非线性方程组进行了线性化。这是目前 解决非线性问题的主要方法。 ISCM 2007,Beiji ng China/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis 7.5 解非线性方程组的迭代解法 0