第4章-非线性方程求根课件

数 学 系,University of Science and Technology of China,DEPARTMENT OF MATHEMATICS,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,4,章 非线性方程求根,非线性科学是当今科学发展的一个重要研究方向，而非线性方程的求根也成了一个不可缺的内容。但是，非线性方程的求根非常复杂。,通常非线性方程的根的情况非常复杂：,无穷组解,无解,一个解,两个解,四个解,所以，只在某个区域内可能解存在唯一，而且经常很简单的形式得不到精确解：,因此，通常我们用迭代法解非线性方程,看迭代法之前，先看看一种简单直观的方法,原理：,4.1,对分法,a,b,x,1,x,2,a,b,什么时候停止？,或,x*,While(|a-b,|,eps,),x=(a+b)/2,f(x,),若,(|,f(x,)|,eps,)x,为解,若,f(x,)*,f(b,)0,修正区间为,x,b,若,f(a,)*,f(x,)0,修正区间为,a,x,End while,每次缩小一倍的区间，收敛速度为,1/2,，较慢，且只能求一个根，使用条件限制较大,算法,2,x,x*,不能保证,x,的精度,4.2,迭代法,f,(,x,)=0,x,=,g,(,x,),等价变换,f,(,x,),的根,g,(,x,),的不动点,思路,从一个初值,x,0,出发，计算,x,1,=,g,(,x,0,),x,2,=,g,(,x,1,),x,k,+1,=,g,(,x,k,),若 收敛，即存在,x,*,使得,，且,g,连续，则由 可知,x,*=,g,(,x,*),，即,x,*,是,g,的,不动点，也就是,f,的根。,迭代法的基本步骤如下：,1,、给出方程的局部等价形式,2,、取合适的初值，产生迭代序列,3,、求极限,易知，该值为方程的根,一定收敛吗？,x,y,y=x,x*,y=g,(,x,),x,0,p,0,x,1,p,1,x,y,y=x,x*,y=g,(,x,),x,0,p,0,x,1,p,1,若满足：,1,、,2,、,可导，且存在正数,L1,，使得对任意的,x,，有,则有：,1,、存在唯一的点,2,、,迭代收敛，且有误差估计,定理,存在唯一性,做辅助函数,，则有,所以，存在点,若,，则有：,又，,则,所以，任意的初值都收敛,证明：,误差估计,由,p,的任意性，令,证毕,构造满足定理条件的等价形式一般难于做到。要构造收敛迭代格式有两个要素：,1,、等价形式,2,、初值选取,下面我们开始介绍若干种迭代法的构造方法,4.3 Newton,迭代法,将,f(x,),在初值处作,Taylor,展开,取线性部分作为,f(x,),的近似，有：,若,，则有,记为,类似，我们可以得到,x,y,x*,x,0,这样一直下去，我们可以得到迭代序列,Newton,迭代的等价方程为：,所以,若,f(x,),在,a,处为单根，则,所以，迭代格式收敛,收敛速度,函数在,a,处作,Taylor,展开,若,a,为,p,重根，取迭代格式为：,即,Newton,迭代收敛速度快，格式简单，应用广泛,例,用,Newton,迭代法求方程,xe,x,-1=0,在,0.5,附近的根,精度要求,=10,-5,.,解,Newton,迭代格式为,k,x,k,(x,k,),|x,k,-x,k-1,|,0,1,2,3,4,0.5,0.57102044,0.56715557,0.56714329,0.56714329,-0.17563936,0.01074751,0.00003393,0.0000000003,0.0000000003,0.07102044,0.00386487,0.00001228,0.00000000,注：,Newtons Method,收敛性依赖于,x,0,的选取。,x,*,x,0,x,0,x,0,4.4,弦截法,将,Newton,迭代中的导数，用差商代替，有格式,是,2,步格式。收敛速度比,Newton,迭代慢,x,0,x,1,切线,割线,定义,设迭代,x,k,+1,=,g,(,x,k,),收敛到,g,(,x,),的,不动点,x,*,。,设,e,k,=,x,k,x,*,，,若，则称该迭代为,p,阶收敛,，其中,C,称为,渐进误差常数,。,4.4,非线性方程组的,Newton,迭代法,则，直接推广,Newton,迭代为：,实际中，用解方程组的形式,