第二章 非线性方程.ppt

1,第2章非线性方程求根,2,科学研究及生产实践中的许多问题常常归结为非线性方程求解。非线性方程的根即使存在，也往往不能用公式表示，或者求出了根的表达式，却因为比较复杂而难以用它来计算根的近似值。所以，当根存在时，研究求根的数值方法，很有必要。,本章主要研究求非线性方程的搜索法、二分法、迭代法、Newton迭代法、变形Newton迭代法。,3,2.1根的搜索与二分法,1.1根的搜索,理论基础,4,根的逐步搜索法,5,为了用搜索法求出非线性方程的足够精确的近似解，步长必须取得非常小，从而需要计算很多次函数值。因此搜索法是效率很底的一种方法，通常用来求根的粗略近似，把它作为后面要讨论的迭代法的初始值。,另一方面，搜索法只适用于一元非线性方程的奇重实根，并且不能推广到多元的情形。,6,所以是方程的根的一个区间。,非线性方程根的搜索法还有：图解法、近似方程法、理论分析法。,例1对于方程，利用根的搜索法确定根的一个有限区间。,解：,7,1.2二分法,x1,x2,a,b,什么时候停止？,或,x*,数学基础,8,求的数值解的二分法如下：,9,10,While(|a-b|>eps)x=(a+b)/2f(x)若(|f(x)|<eps)x为解若f(x)*f(b)<0修正区间为x,b若f(a)*f(x)<0修正区间为a,xEndwhile,每次缩小一倍的区间，收敛速度为1/2，较慢，且只能求一个根，,使用条件限制较大不能保证x的精度.,算法,11,二分法的优缺点,1、二分法收敛速度不快，其收敛速度仅与一个以1/2为比值的等比级数相同。,二分法计算过程简单，程序容易实现。可在大范围内求根，但该方法收敛较慢，且不能求偶数重根和复根，一般用于求根的初始近似值,而后在使用其它的求根方法。,2、二分法只能用于求实函数的实根，不能用于求复根及偶数重根。,12,解：,13,计算如下表：,所以近似根：,14,从一个初值x0出发，计算x1=g(x0),x2=g(x1),xk+1=g(xk),。,f(x)=0,x=g(x),f(x)的根,g(x)的不动点,思路,若收敛，即存在x*使得，且,g连续，则由可知x*=g(x*)，,2.2迭代法,即x*是g的不动点，也就是f的根。,15,迭代法的基本步骤如下：,1、给出方程的局部等价形式;,2、取合适的初值，产生迭代序列;,3、求极限,易知，该值为方程的根。,一定收敛吗？,16,17,设有方程形如：,对于给定的初值,由公式,得到一个迭代序列:,这样的算法称为迭代法，称为迭代,迭代法需要一个初值，才能开始运算,定义:如果对给定的初值,则称迭代格式(2.2)收敛，否则称为发散,函数，迭代函数确定了迭代序列的性质,18,19,2.1迭代过程的收敛性,20,21,证明：,22,即得（3）证毕,23,24,评注,25,26,解：,27,28,29,2.2迭代法的局部收敛性,例3中，我们看到，迭代法的收敛性不仅与迭代函数有关,初值的取值范围也是很重要的实际上使用迭代法时通常初值是在根的附近的，所以,应用中常用局部收敛性来决定迭代法的取舍,30,关于局部收敛性，有如下定理,证明：,31,证明：,32,解：,33,选用1）计算如下：,所以：,34,2.3迭代过程的收敛速度,迭代法要有实用价值不仅要是收敛的，还要求它的收敛速度快。迭代过程的收敛速度是指迭代误差的下降速度。,显然越大,收敛越快,相同的收敛阶时,较小的迭代法收敛较快,证明：,36,（2）由泰勒公式：,37,2.4迭代法的算法,开始,读入,输出迭代失败标志,结束,输出,是,是,否,否,38,2.3Newton迭代法,用简单迭代法求方程的根的困难在于建立收敛速度快的迭代公式，牛顿迭代方法是建立快速收敛的迭代法的一般方法,39,3.1牛顿迭代公式的建立,将f(x)在初值处作Taylor展开,取线性部分作为f(x)的近似，有：,若,，则有,记为,类似，可以得到,40,这样一直下去，我们可以得到迭代序列,Newton迭代的等价方程为：,所以,若f(x)在a处为单根，则,所以，迭代格式收敛。,牛顿迭代公式,41,评注：,牛顿迭代法迭代函数为；,42,切线法的几何意义如下图：,切线,43,例5用Newton迭代法求方程在0.5附近的根,精度要求,解,Newton迭代格式为,44,注：Newton迭代法收敛性依赖于x0的选取。,x*,45,3.2牛顿法的收敛性,证明：,46,47,定理2.5对于的多重根，牛顿迭代法仅为线性收敛的。,关于重根的情形，我们不加证明地指出如下定理。,48,解,49,50,中，每步计算都要求,2.4牛顿方法的变形方法,牛顿迭代法是一种重要而基本的方法，非线性方程,从处理出发。,的各种常用的迭代法都与牛顿法有一些关系。下面针对,牛顿迭代格式,的值，导致计算过程烦琐，介绍两种变形方法，都可以,51,4.1简化牛顿法,52,53,4.2弦截法,称为弦截法。,54,切线,割线,55,解,本例中交点横坐标就是弦截法的迭代公式,56,解,取，计算如下：,57,所以：。,58,59,4.3重根的修正方法,60,61,解,迭代公式,62,在MATLAB中提供了一个fzero函数，可以用求单变量非线性方程的根。该函数的调用格式为：z=fzero(fname,x0,tol,trace)其中fname是待求根的函数文件名，x0为搜索的起点。一个函数可能有多个根,但fzero函数只给出离x0最近的那个根。tol控制结果的相对精度，缺省时取tol=eps，trace指定迭代信息是否在运算中显示,为1时显示，为0时不显示，缺省时取trace=0。,非线性方程数值求解,eps：系统的浮点（Floating-point）精确度,63,步骤如下：(1)建立函数文件funx.m。functionfx=funx(x)fx=x-10.x+2;(2)调用fzero函数求根。z=fzero(funx,0.5)z=0.3758,例求在附近的根。,