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

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