非线性方程求根课件.ppt

1、数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS第4章 非线性方程求根 非线性科学是当今科学发展的一个重要研究方向，而非线性方程的求根也成了一个不可缺的内容。但是，非线性方程的求根非常复杂。通常非线性方程的根的情况非常复杂：21)2sin(yyx无穷组解1041122aaaaayxaxy无解一个解两个解四个解数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS所以，只在某个区域内可能解存在唯一，而

2、且经常很简单的形式得不到精确解：因此，通常我们用迭代法解非线性方程看迭代法之前，先看看一种简单直观的方法原理：原理：0)(.,.,0)()(xftsxbfaf0)cos(xex数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS4.1对分法对分法abx1x2ab什么时候停止？11xxkk 2)(xf 或或x*数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSWhile(|a-b|eps)x=(a+b

3、)/2 f(x)若(|f(x)|eps)x为解 若f(x)*f(b)0 修正区间为x,b 若f(a)*f(x)0 修正区间为a,xEnd while每次缩小一倍的区间，收敛速度为1/2，较慢，且只能求一个根，使用条件限制较大算法 2xx*不能保证 x 的精度数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS4.2 迭代法迭代法f(x)=0 x=g(x)等价变换等价变换f(x)的根的根g(x)的不动点的不动点思思路路从一个初值从一个初值 x0 出发，计算出发，计算 x1=g(x0),x2=g(x1

4、),xk+1=g(xk),若若 收敛，即存在收敛，即存在 x*使得使得 ，且，且 g 连续，则由连续，则由 可可知知 x*=g(x*)，即，即x*是是 g 的不动点，也就是的不动点，也就是f 的根。的根。0kkx*limxxkk kkkkxgx limlim1数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS迭代法的基本步骤如下：1、给出方程的局部等价形式)(0)(xxxf2、取合适的初值，产生迭代序列)(,10iixxx3、求极限nnxx lim*易知，该值为方程的根一定收敛吗？数 学 系Un

5、iversity of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSxyy=xx*y=g(x)x0p0 x1p1 xyy=xx*y=g(x)x0p0 x1p1数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS,),(baxx若满足：1、,)(baxbxa2、)(x可导，且存在正数L1，使得对任意的x，有Lx)(则有：1、存在唯一的点*)(*,xxx2、bax,0迭代收敛，且有误差估计011*xxLLxxkk定理定理数 学 系Un

6、iversity of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS存在唯一性做辅助函数)()(xxx，则有0)(,0)(ba所以，存在点*)(*0*)(.,.*,xxxtsx若*)*(*xx，则有：*)*)(*)*(*)(*xxLxxxxxx又，1L*xx,0bax 则*)(*)()(*1xxxxxxkkk*011xxLxxLxxkkk所以，任意的初值都收敛证明：数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS误差估计011

7、11)()(xxLxxLxxxxkkkkkkkkkpkpkkpkxxxxxx11011xxLLkpk0101111xxLLxxLLLkpk由p的任意性，令011*xxLLxxkkp证毕数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS构造满足定理条件的等价形式一般难于做到。要构造收敛迭代格式有两个要素：1、等价形式2、初值选取下面我们开始介绍若干种迭代法的构造方法数 学 系University of Science and Technology of ChinaDEPARTMENT OF MAT

8、HEMATICS4.3 Newton迭代法迭代法将f(x)在初值处作Taylor展开200000)(!2)()()()(xxxfxxxfxfxf取线性部分作为f(x)的近似，有：0)()(000 xxxfxf若0)(0 xf，则有)()(000 xfxfxx记为1x类似，我们可以得到)()(1112xfxfxxxyx*x0数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS这样一直下去，我们可以得到迭代序列)()(1kkkkxfxfxxNewton迭代的等价方程为：)()()(0)(xfxfxxx

9、xf所以2)()()()()()(xfxfxfxfxfxx若f(x)在a处为单根，则0)(,0)(,0)(aafaf所以，迭代格式收敛数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS收敛速度收敛速度)(2)()()()()(21nnnnnaxaaxaxax)(2)()(2)(22aaxaxnnn函数在a处作Taylor展开若a为p重根，取迭代格式为：)()(1kkkkxfxfpxx即Meenn21Newton迭代收敛速度快，格式简单，应用广泛数 学 系University of Science

10、 and Technology of ChinaDEPARTMENT OF MATHEMATICS 例例 用Newton迭代法求方程xex-1=0在0.5附近的根,精度要求=10-5.解解 Newton迭代格式为,2,1,0,111kxexxexeexxxkxkkxkxxkkkkkkkkxk(xk)|xk-xk-1|012340.50.571020440.567155570.567143290.56714329-0.175639360.010747510.000033930.00000000030.00000000030.071020440.003864870.000012280.000000

11、00数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSNewtons Method 收敛性依赖于收敛性依赖于x0 的选取。的选取。x*x0 x0 x0数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS4.4 弦截法弦截法将Newton迭代中的导数，用差商代替，有格式)()()(111kkkkkkkxfxfxxxfxx是2步格式。收敛速度比Newton迭代慢Meenn618.11x0 x1切线切线

12、割线割线 数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS定义定义设迭代设迭代 xk+1=g(xk)收敛到收敛到g(x)的不动点的不动点 x*。设设 ek=xk x*，若，则称该迭代为若，则称该迭代为p 阶收敛阶收敛，其中其中 C 称为称为渐进误差常数渐进误差常数。0|lim1 Ceepkkk数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS4.4 非线性方程组的非线性方程组的Newton迭代法迭代法)()()()(11kkkkkkkXFXJXxFxFXXTnTnxxxXfffFXF),(,),(,0)(2121则，直接推广Newton迭代为：nnnnxfxfxfxfXJ1111)(数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS实际中，用解方程组的形式)()(1kkkkXFXXXJ