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

第4章 非线性方程求根,非线性科学是当今科学发展的一个重要研究方向，而非线性方程的求根也成了一个不可缺的内容。但是，非线性方程的求根非常复杂。,通常非线性方程的根的情况非常复杂：,无穷组解,第4章 非线性方程求根 非线性科学是当今科学发,所以，只在某个区域内可能解存在唯一，而且经常很简单的形式得不到精确解：,因此，通常我们用迭代法解非线性方程,看迭代法之前，先看看一种简单直观的方法,原理：,所以，只在某个区域内可能解存在唯一，而且经常很简单的形式得不,4.1对分法,a,b,x1,x2,a,b,什么时候停止？,或,x*,4.1对分法abx1x2ab什么时候停止？或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,xEnd while,每次缩小一倍的区间，收敛速度为1/2，较慢，且只能求一个根，使用条件限制较大,算法,2,不能保证 x 的精度,While(|a-b|eps)每次缩小一倍的区间，收敛速度,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*是 g 的不动点，也就是f 的根。,4.2 迭代法f(x)=0 x=g(x)等价变换f,迭代法的基本步骤如下：,1、给出方程的局部等价形式,2、取合适的初值，产生迭代序列,3、求极限,易知，该值为方程的根,一定收敛吗？,迭代法的基本步骤如下：1、给出方程的局部等价形式2、取合适的,x*,x1,p1,x*,x1,p1,xyy=xx*y=g(x)x0p0 x1p1xyy=,若满足：,1、,2、,可导，且存在正数L1，使得对任意的x，有,则有：,1、存在唯一的点,2、,迭代收敛，且有误差估计,定理,若满足：1、2、可导，且存在正数L1，使得对任意的x，有则,存在唯一性,做辅助函数,，则有,所以，存在点,若,，则有：,又，,则,所以，任意的初值都收敛,证明：,存在唯一性做辅助函数，则有所以，存在点若，则有：又，则所,误差估计,由p的任意性，令,证毕,误差估计由p的任意性，令证毕,构造满足定理条件的等价形式一般难于做到。要构造收敛迭代格式有两个要素：,1、等价形式,2、初值选取,下面我们开始介绍若干种迭代法的构造方法,构造满足定理条件的等价形式一般难于做到。要构造收敛迭代格式有,4.3 Newton迭代法,将f(x)在初值处作Taylor展开,取线性部分作为f(x)的近似，有：,若,，则有,记为,类似，我们可以得到,x0,4.3 Newton迭代法将f(x)在初值处作Taylor展,这样一直下去，我们可以得到迭代序列,Newton迭代的等价方程为：,所以,若f(x)在a处为单根，则,所以，迭代格式收敛,这样一直下去，我们可以得到迭代序列Newton迭代的等价方程,收敛速度,函数在a处作Taylor展开,若a为p重根，取迭代格式为：,即,Newton迭代收敛速度快，格式简单，应用广泛,收敛速度函数在a处作Taylor展开若a为p重根，取迭代格式,例 用Newton迭代法求方程xex-1=0在0.5附近的根,精度要求=10-5.,解 Newton迭代格式为,例 用Newton迭代法求方程xex-1=0在0.,注：Newtons Method 收敛性依赖于x0 的选取。,x*,x0,x0,x0,注：Newtons Method 收敛性依赖于x0 的选取,4.4 弦截法,将Newton迭代中的导数，用差商代替，有格式,是2步格式。收敛速度比Newton迭代慢,x0,x1,切线,割线,4.4 弦截法将Newton迭代中的导数，用差商代替，有格式,定义设迭代 xk+1=g(xk)收敛到g(x),4.4 非线性方程组的Newton迭代法,则，直接推广Newton迭代为：,4.4 非线性方程组的Newton迭代法则，直接推广Newt,实际中，用解方程组的形式,实际中，用解方程组的形式,