1、第4章 非线性方程求根 非线性科学是当今科学发展的一个重要研究方向,而非线性方程的求根也成了一个不可缺的内容。但是,非线性方程的求根非常复杂。通常非线性方程的根的情况非常复杂:21)2sin(yyx无穷组解1041122aaaaayxaxy无解一个解两个解四个解所以,只在某个区域内可能解存在唯一,而且经常很简单的形式得不到精确解:因此,通常我们用迭代法解非线性方程看迭代法之前,先看看一种简单直观的方法原理:原理:0)(.,.,0)()(xftsxbfaf0)cos(xex4.1对分法对分法abx1x2ab什么时候停止?11xxkk 2)(xf 或或x*While(|a-b|eps)x=(a+b
2、)/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 的精度4.2 迭代法迭代法f(x)=0 x=g(x)等价变换等价变换f(x)的根的根g(x)的不动点的不动点思思路路从一个初值从一个初值 x0 出发,计算出发,计算 x1=g(x0),x2=g(x1),xk+1=g(xk),若若 收敛,即存在收敛,即存在 x*使得使得 ,且,且 g 连续,则由连续,则由 可可知知 x*=g(x*),即,即x*是是
3、 g 的不动点,也就是的不动点,也就是f 的根。的根。0kkx*limxxkk kkkkxgx limlim1迭代法的基本步骤如下:1、给出方程的局部等价形式)(0)(xxxf2、取合适的初值,产生迭代序列)(,10iixxx3、求极限nnxx lim*易知,该值为方程的根一定收敛吗?xyy=xx*y=g(x)x0p0 x1p1 xyy=xx*y=g(x)x0p0 x1p1,),(baxx若满足:1、,)(baxbxa2、)(x可导,且存在正数L1,使得对任意的x,有Lx)(则有:1、存在唯一的点*)(*,xxx2、bax,0迭代收敛,且有误差估计011*xxLLxxkk定理定理存在唯一性做辅
4、助函数)()(xxx,则有0)(,0)(ba所以,存在点*)(*0*)(.,.*,xxxtsx若*)*(*xx,则有:*)*)(*)*(*)(*xxLxxxxxx又,1L*xx,0bax 则*)(*)()(*1xxxxxxkkk*011xxLxxLxxkkk所以,任意的初值都收敛证明:误差估计01111)()(xxLxxLxxxxkkkkkkkkkpkpkkpkxxxxxx11011xxLLkpk0101111xxLLxxLLLkpk由p的任意性,令011*xxLLxxkkp证毕构造满足定理条件的等价形式一般难于做到。要构造收敛迭代格式有两个要素:1、等价形式2、初值选取下面我们开始介绍若干种
5、迭代法的构造方法4.3 Newton迭代法迭代法将f(x)在初值处作Taylor展开200000)(!2)()()()(xxxfxxxfxfxf取线性部分作为f(x)的近似,有:0)()(000 xxxfxf若0)(0 xf,则有)()(000 xfxfxx记为1x类似,我们可以得到)()(1112xfxfxxxyx*x0这样一直下去,我们可以得到迭代序列)()(1kkkkxfxfxxNewton迭代的等价方程为:)()()(0)(xfxfxxxxf所以2)()()()()()(xfxfxfxfxfxx若f(x)在a处为单根,则0)(,0)(,0)(aafaf所以,迭代格式收敛收敛速度收敛速度
6、)(2)()()()()(21nnnnnaxaaxaxax)(2)()(2)(22aaxaxnnn函数在a处作Taylor展开若a为p重根,取迭代格式为:)()(1kkkkxfxfpxx即Meenn21Newton迭代收敛速度快,格式简单,应用广泛 例例 用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.01074
7、7510.000033930.00000000030.00000000030.071020440.003864870.000012280.00000000Newtons Method 收敛性依赖于收敛性依赖于x0 的选取。的选取。x*x0 x0 x04.4 弦截法弦截法将Newton迭代中的导数,用差商代替,有格式)()()(111kkkkkkkxfxfxxxfxx是2步格式。收敛速度比Newton迭代慢Meenn618.11x0 x1切线切线 割线割线 定义定义设迭代设迭代 xk+1=g(xk)收敛到收敛到g(x)的不动点的不动点 x*。设设 ek=xk x*,若,则称该迭代为若,则称该迭代为p 阶收敛阶收敛,其中其中 C 称为称为渐进误差常数渐进误差常数。0|lim1 Ceepkkk4.4 非线性方程组的非线性方程组的Newton迭代法迭代法)()()()(11kkkkkkkXFXJXxFxFXXTnTnxxxXfffFXF),(,),(,0)(2121则,直接推广Newton迭代为:nnnnxfxfxfxfXJ1111)(实际中,用解方程组的形式)()(1kkkkXFXXXJ