常用数值分析方法1非线性方程求根.ppt

第一章,材料科学研究中的常用数值分析方法,主 要 内 容,1 非线性方程求解2 线性方程组的数值解法3 插值法与曲线拟合4 有限差分法与有限单元法,1 非线性方程求解,1.1 概 述1.2 对分法1.3 迭代法1.4 Newton法1.5 弦截法其他方法：Aitken加速法、Steffensen加速法、重根加速收敛法、抛物线法、牛顿下山法、劈因子法等。,1.1 非线性方程求解概述,很多科学计算问题常常归结为求解方程：,非线性方程求解概述(续）,例如，从曲线y=x和y=lg x的简单草图可看出方程lg x+x=0有唯一的正根x*，但是没有求x*的准确值的已知方法，即使是对代数方程，要求其精确解也是困难的。对于二次方程ax2+bx+c=0，我们可以用熟悉的求根公式：,对于三、四次代数方程，尽管存在求解公式，但并不实用。而对于大于等于五次的代数方程，它的根不能用方程系数的解析式表示，至于一般的超越方程，更没有求根公式。因此，为求解一个非线性方程，我们必须依靠某种数值方法来求其近似解。,对于方程（1-1）要求得其准确解一般来说是不可能的。,求方程根近似解的几个问题：,设函数f(x)在区间a,b上连续，严格单调，且f(a)f(b)0，则在a,b内方程f(x)=0有且仅有一个实根。,根据此结论，我们可以采用如下两种方法求出根的隔离区间。,1.根的存在性：方程是否有根？如果有根，有几个根？2.根的隔离：确定根所在的区间，使方程在这个小区间内有且仅有一个根，这一过程称为根的隔离，完成根的隔离，就可得到方程的各个根的近似值。3.根的精确化：已知一个根的粗略近似值后，建立计算方法将近似解逐步精确化，直到满足给定精度为止。,关于根的存在性是纯数学问题，不详细介绍，可查阅有关代数学内容。,根的隔离主要依据如下结论：,求根的隔离区间的两种方法,1.描图法：,画出y=f(x)的草图，由f(x)与x轴交点的大概位置来确定有根区间。也可利用导函数f(x)的正、负与函数f(x)的单调性的关系来确定根的大概位置。,例1 求f(x)=3x 1 cos x=0的有根区间,解：将方程变形为3x 1=cos x绘出曲线 y=3x1及 y=cos x，由图1-1可知，方程只有一个实根：,解：令f(x)=4x312x2=0，可得驻点x1=0,x2=3,由此而得到三个区间(,0)(0,3),(3,),f(x)在此三个区间上的正负号分别为“”，“”，“+”，由此可见，函数f(x)在此三个区间上为“减”，“减”，“增”，并且因为f()0,f(0)=10,f(3)=260所以仅有二个实根，分别位于(0,3),(3,)内。又因f(4)=10,所以，二个隔根区间确定为(0,3),(3,4)。,例2,从区间a,b的左端点a出发，按选定的步长h一步步向右搜索，若:,则：区间 a+jh,a+(j+1)h内必有根。搜索过程也可以从 b开始，这时应取步长h0。,求出根的隔离区间后，就可采用适当的方 法，使其进一步精确化。下面介绍几种常用的精确化根的方法（非线性方程求解的方法）,2.逐步搜索法：,1.2 对分法（二分法）,设f(x)在区间a,b上连续，严格单调，且f(a)f(b)0，则方程f(x)=0在a,b内存在唯一实根，对分法的基本思想是：用对分区间的方法，通过判别函数f(x)在每个对分区间中点的符号，逐步将有根区间缩小，最终求得一个具有相当精确程度的近似根。具体步骤为:,对分法（续）,若每次对分区间时所取区间中点都不是根，则上述过程将无限地进行下去，当n时，区间将最终收缩为一点x*，显然x*就是所求方程的根。,x1,x2,a,b,When to stop?,或,不能保证 x 的精度,x*,2,对分法的几何意义,对分法的误差估计,作为x*的近似值，则误差为：,只要n足够大（即区间对分次数足够多），xn的误差就可足够小，且只要f(x)连续，对分区间总是收敛的。,式（1-2）不仅可以估计对分区间法的误差，而且可以用给定的误差限 估计出对分区间的次数，因为由式（1-2）有：,若取区间an,bn的中点：,对分法举例,例3,解：因为：f(x)连续且f(x)=3x2+10 0(x(,)，故：f(x)在(,)上单调增加 而：f(1)=9 0 所以：原方程在（1，2）内有唯一实根。,表12,对分法的优缺点,优点：计算简单，方法可靠，容易估计误差。缺点：但它收敛较慢，不能求偶次重根，也不能求复根。因此，一般在求方程近似根时，很少单独使用，常用于为其他高速收敛算法（如牛顿法）提供初值。,1.3 迭代法,迭代法是求解方程f(x)=0的根的一种主要方法。它是利用同一个迭代公式，逐次逼近方程的根，使其得到满足预先给定精度要求的近似值。,迭代法的基本思想,迭代法是一种重要的逐次逼近法，其基本思想是：设方程f(x)=0在区间a,b内有一根x*，将方程化为等价方程x=(x)，并在a,b内任取一点x0作为初始近似值，然后按迭代公式计算：,产生迭代序列x0,x1,xn,显然，若xn收敛于x*，(x)在x*处连续，就有:,这种求根方法称为迭代法，式（1-3）称为迭代格式，(x)称为迭代函数，x0称为迭代初值，xn称为迭代序列 如果迭代序列收敛，则称迭代格式（1-3）收敛，否则称为发散。,即：x*是方程f(x)=0的解。,故：当n充分大时，可取xn作为方程的近似解。,迭代法举例,例4,解：容易验证，方程在1,2内有根，取x0=1.5,例4（续）,表1-2,迭代法举例（续）,例5,解：对方程进行变换，可得如下三种等价形式：,分别按以上三种形式建立迭代格式，并取x0=1进行迭代计算，结果如下：,例5的计算结果表明：将一方程化为等价方程的方法很多，由此可构造许多不同的迭代函数，得到多种迭代格式。而它们所产生的迭代序列则可能收敛，也可能发散，可能收敛很快，也可能收敛很慢。迭代法的收敛性取决于迭代函数在方程的根的邻近的性态。,迭代法的几何含义,从几何上看，迭代法是将求曲线y=f(x)的零点问题化为求曲线y=(x)与直线y=x的交点，迭代过程如图1-2所示，从初始点x0出发，沿直线x=x0走到曲线y=(x)，得点(x0,(x0)，再沿直线y=(x0)走到直线y=x，交点为(x1,(x1)，如此继续下去，越来越接近点(x*,x*)。,y,当然，迭代过程也可能出现图1-3所示的情况，此时点(xn,xn)越来越远离交点(x*,x*)，迭代序列发散。,由此可见，使用迭代法必须解决两个问题：一是迭代格式满足什么条件才能保证收敛；二是如何判别迭代收敛的速度，建立收敛快的迭代格式。,迭代法的几何含义（续）,迭代法的收敛条件（三大定理）,定理1.1（压缩映象原理）,设函数(x)在区间a,b上满足条件：,则：方程x=(x)在a,b内有唯一的根x*，且对任意初值x0 a,b，迭代序列：,证明略,两个重要误差公式,1.式（1-2）说明，在正常情况下，即L不太接近于1（若L接近于1，则收敛速度很慢），可用相邻两次迭代值之差的绝对值来估计误差，控制迭代次数。,就停止计算，取xn作为方程的近似根。这种用相邻两次计算结果来估计误差的方法，称为事后估计法。,即当给定精度时，如果有：,1,2,2.而式（1-3）的误差估计，称为事前估计法，因为用它可以估计出要达到给定精度 所需次数n,事实上，由,两个重要误差公式（续）,迭代法的收敛条件(之二),定理1.2,（1）对任意的x a,b，有(x)a,b；（2）存在常数0 L 1，使得对任意x a,b，都有：,则:方程x=(x)在a,b上有唯一的根x*，且对任意初值 x0 a,b，迭代序列：,均收敛于x*，并有：,证明略,设函数(x)在区间a,b上满足条件：,定理2.2应用举例,在隔根区间（1,1.2）内可以采用三种迭代格式：,用定理1.2判别简单迭代法的收敛性比定理1.1方便,如对例题5：,第一种迭代格式发散，第二、三种迭代格式收敛且第三种迭代格式比第二种迭代格式中的L要小，因而收敛要快得多，这与实际迭代结果完全吻合。,故可取n=7，只需迭代7次就可达到所要求的精度。,定理2.2应用举例（续）,根据定理1.2可知，,对第三种迭代格式，为使与方程近似根的误差不超过10-6，可估计迭代次数：,迭代法的收敛条件(之三),定理1.3,如果：,则：,定理1.3强调迭代初值x0应取在根x*的邻域中。如果对任意给定的x0，迭代格式均收敛，则称此格式具有全局收敛性，但这样的格式是极其稀少的。如果对根x*的某邻域内的任一点x0，迭代格式均收敛，则此格式具有局部收敛性。,即可保证对其中任取的一点x0迭代收敛。事实上，在用迭代法求解方程（1-1）时，常常先用对分区间求得较好的初值，然后再进行迭代。,本定理给出的就是局部收敛性条件。具体解题时，虽然无法判别隔根区间是否为以x*为中心的邻域，但只要它足够小，且在邻域中满足：,定理1.3（续）,1.4 Newton法,将非线性方程线性化，以线性方程的解逐步逼近非线性方程的解，这就是Newton法的基本思想。,设已知方程f(x)=0的近似根x0，f(x)在其零点x*邻近一阶连续可微，且 f(x)0，当 x0充分接近 x*时，f(x)可用Taylor公式近似表示为：,则方程f(x)=0可用线性方程近似代替，即：,Newton法（续）,解此线性方程得：,取此x作为原方程的新近似值x1，重复以上步骤，于是得迭代公式：,按式（1-6）求方程f(x)=0近似解称为Newton法。,Newton法的几何意义,如此继续下去，xn+1为曲线上点(xn,f(xn)处的切线与x轴的交点。因此Newton法是用曲线的切线与x轴的交点作为曲线与x轴交点的近似，故Newton法又称为切线法。,Newton迭代法有着明显的几何意义,如图1-4所示:,过点(x0,f(x0)作曲线y=f(x)的切线，切线方程为：y=f(x0)+f(x)(xx0)该切线与x轴的交点的横坐标即为新的近似值x1，而x2则是曲线上点(x1,f(x1)处的切线与x轴的交点。,Newton法举例,例7,解：因为f(x)=3x2+10，故Newton迭代公式为：,x1=1.5970149，x2=1.5945637，x3=1.5945621=x4迭代三次所得近似解就准确到8位有效数字。,代入初值x0得：,可见Newton法收敛很快。,一般地，有如下屏定理1.4：,Newton法收敛定理,定理1.4,设函数f(x)在其零点x*邻近二阶连续可微，且f(x*)0，则存在 0，使得对任意x0 x*,x*+，Newton法所产生的序列xn至少二阶收敛于x*。,定理1.4表明，当初值x0充分接近x*时，Newton法的收敛速度较快，但当初值不够好时，可能会不收敛或收敛于别的根，这可从Newton法的几何意义看到：,注：Newtons Method 收敛性依赖于x0 的选取。,x*,Newton法的优缺点,优点：Newton法具有收敛快，稳定性好，精度高等优点，它是求解非线性方程的有效方法之一。缺点：每次迭代均需要计算函数值与导数值，故计算量较大。而且当导数值提供有困难时，Newton法无法进行。,1.5 弦截法,不 足 之 处：需要计算导数值，较难；,这就是弦截法迭代公式,Newton法优点：收敛快（平方阶），固定格式；,修 正：以差商代替导数（微商）,弦截法迭代公式的几何解释,与x轴相交，即y=0，解出x得：,即以割线代替曲线f(x)，以割线与x轴的交点去近似曲线与x轴的交点，又称为割线法。,弦截法的几点说明,1、需要两个点x0，x1才能开始进行迭代：（1）若只给定x0，则须利用其他方法，如对分法，求 x1，然后再利用弦截法，求x2，x3，；（2）若给定一有根区间，可直接用两端点作 x0，x1。,xn收敛，收敛阶为1.618，超线性收敛。,3.上述弦截法又称为变端点弦截法（双点），,该法称为：定端点弦截法（单点），几何意义如右图：,弦截法的几点说明(续）,其实还可固定一端点x0写为：,弦截法举例,例9,用定端点，变端点截线法求方程：f(x)=x32x5在区间2,3内的一个实根（有12位有效数字的实根为=2.09455148514）。,解：取x0=2,x1=3，用两种方法计算结果如下：（见表1-4）,表1-3,可见：变端点比定端点收敛速度快。变端点的x6已达精确值，而定端点x6只有7位有效数字。,