第二章 非线性方程的数值解法.ppt

第二章非线性方程的数值解法/*NumericalSolutionsofNonlinearEquations*/,本章主要内容：1、二分法2、不动点迭代的构造及其收敛性判定（重点）3、Newton和Steffensen迭代（重点）4、割线法5、非线性方程组的迭代解法,历史背景,求方程几何意义,基本定理,如果函数在上连续，且则至少有一个数使得，若同时的一阶导数在内存在且保持定号，即(或)则这样的在内唯一。,1二分法/*BisectionMethod*/,原理：若fCa,b，且f(a)f(b)0，则f在(a,b)上至少有一实根。,基本思想：逐步将区间分半，通过判别区间端点函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求出满足给定精度的根的近似值。,以此类推,终止法则？,x1,x2,a,b,Whentostop?,或,不能保证x的精度,二分法算法给定区间a,b，求f(x)=0在该区间上的根x.输入:a和b;容许误差TOL;最大对分次数Nmax.输出:近似根x.Step1Setk=1;Step2Computex=f(a+b)/2);Step3While(kNmax)dosteps4-6Step4If|x|TOL,STOP;Outputthesolutionx.Step5Ifx*f(a)0,Setb=x;ElseSeta=x;Step6Setk=k+1;Computex=f(a+b)/2);GoToStep3;Step7Outputthesolutionofequation:x;STOP.,3、,由二分法的过程可知：,4、对分次数的计算公式：,1、,2、,令,误差分析,解：,例1：用二分法求方程在区间上的根，误差限为，问至少需对分多少次？,简单;对f(x)要求不高(只要连续即可).,无法求复根及偶重根收敛慢,注：用二分法求根，最好先给出f(x)草图以确定根的大概位置。或用搜索程序，将a,b分为若干小区间，对每一个满足f(ak)f(bk)0的区间调用二分法程序，可找出区间a,b内的多个根，且不必要求f(a)f(b)0。,2迭代法的理论/*TheoryofIterationMethod*/,f(x)=0,x=g(x)（迭代函数）,思路,从一个初值x0出发，计算x1=g(x0),x2=g(x1),xk+1=g(xk),若收敛，即存在x*使得，且g连续，则由可知x*=g(x*)，即x*是g的不动点，也就是f的根。,看起来很简单，令人有点不相信，那么问题是什么呢？,如何判定这种方法是收敛的呢？,f(x)的根,g(x)的不动点,一、不动点迭代/*Fixed-PointIteration*/,几何意义,下面选取5种迭代格式：,法1,法4,法3,法2,法5,Lipschitz条件成立的充分条件,证明：g(x)在a,b上存在不动点？,令,有根,不动点唯一？,反证：若不然，设还有，则,而,当k时，xk收敛到x*？,L越收敛越快,可用来控制收敛精度,小,注：条件(II)可改为在a,b满足Lipschitz条件,定理结论仍然成立(定理2.3)。,算法:不动点迭代给定初始近似值x0，求x=g(x)的解.输入:初始近似值x0;容许误差TOL;最大迭代次数Nmax.输出:近似解x或失败信息.Step1Seti=1;Step2While(iNmax)dosteps3-6Step3Setx=g(x0);/*计算xi*/Step4If|xx0|TOLthenOutput(x);/*成功*/STOP;Step5Seti+;Step6Setx0=x;/*更新x0*/Step7Output(ThemethodfailedafterNmaxiterations);/*不成功*/STOP.,当x很大时，此处可改为,二、局部收敛性/*LocalConvergence*/,注解:局部收敛性特点：假定解存在，且肯定存在解的一个邻域，使得对其中所有初始值，由迭代生成的序列收敛于解。半局部收敛特点：不知道解存在，但指出要从满足一定（通常很强）条件的初始值出发，保证收敛于某一（临近）解。全局（整体）收敛：肯定在全空间或至少其中一个很大的部分中，无论从何处出发，都能保证收敛于一个解。,证明：,因为在的某邻域连续，,存在邻域,即对,则由定理2.3，迭代法(*)对收敛，即局部收敛.,注,例3：已知方程在1.5附近有根，把方程写成三种不同的等价形式(1)对应迭代格式；(2)对应迭代格式；(3)对应迭代格式;判断迭代格式在的收敛性，选一种收敛格式计算，精确到小数点后第二位。,解：,（1），迭代格式收敛；,（2），迭代格式收敛；,（3），迭代格式发散。,选择(2)计算012341.51.4811.4731.4691.467,注:（1）的大小反映了迭代法收敛的快慢，是收敛速度的一种度量;（2）设迭代函数满足收敛定理的条件，则产生的序列满足，如果在或的邻域有若取，必有，此时有,证明：,由Taylor公式：,充分性,取极限得,必要性,设迭代式（*）是阶收敛的，则有,即,且,（反证法）设结论不成立,则存在最小正整数,满足,情形一,情形二,由充分性证明知，迭代式（*）是阶收敛的,即,与阶收敛矛盾,证明方法与情形一类似（自己练习）,一、使用两个迭代值的组合方法：,3迭代收敛的加速方法/*AcceleratingMethod*/,将x=g(x)等价地改造为,当和时，有,相应的迭代公式为,或者,选取特殊的，有可能使迭代加速。,如：,迭代公式为,几何意义如图示,注：(1)这种迭代对原迭代公式(*)的各近似值在根的两侧往复地趋于时较为有效；,又如：,新的迭代函数为,根据定理2.5知，迭代法至少是二阶的.,但由于不知道，故也得不到，因此可取其的近似值，即,从而有,二、Steffensen(斯蒂芬森)加速迭代法：（三个迭代值组合）,或者,若令,Steffensen迭代法的优点：可以改进收敛速度，有时也能把不收敛的迭代法改进为收敛的二阶方法.,艾特肯（Aitken）加速方法：,下面选取3种迭代格式：,显示计算结果,证明：,设斯蒂芬森(Steffensen)的迭代为,其中,设,则,反之，设,型,洛比塔法则,由Taylor公式：,则,上式中用替换,即证,代入上述结果：,返回,4牛顿法/*Newton-RaphsonMethod*/,一、牛顿迭代公式的推导,1、待定参数法,不动点迭代的关键是构造满足收敛条件的迭代函数,一种自然的选择是令,为了加速不动点迭代的收敛过程，应尽可能使迭代函数在处有更多阶导数等于零（定理2.5）。,令,取,因此，选取迭代函数,NewtonRaphson迭代格式,称之为牛顿拉夫森方法，简称牛顿法,原理：将非线性方程线性化,取x0x*，将f(x)在x0做一阶Taylor展开:,，在x0和x之间,2、Taylor展开法/*TaylorsexpansionMethod*/,将(x*x0)2看成高阶小量，则有：,解：,等价于求方程的正根,解法一：,等价于求方程的正根,解法二：,等价于求方程的正根,证明：NewtonsMethod事实上是一种特殊的不动点迭代其中，则,收敛,由Taylor展开：,在单根/*simpleroot*/附近收敛快,只要，则令可得结论。,Th2.5,有根,根唯一,产生的序列单调有界保证收敛,证明：,因为fC2a,b，由（1）和（2）知f(x)在a,b内有唯一根,下面由条件（1）、（2）分4种情况讨论：,仅证明第一种情况，其它情况类似讨论,由中值定理，使得,由,另一方面，由Taylor展开得,介于、之间,重复以上过程，可得（归纳法）,（自己证）,因此，数列单调下降且有下界,令,由Taylor展开得,注：NewtonsMethod收敛性依赖于x0的选取。,x*,Th2.9中条件（3）的几何意义,证明仿照Th2.9,重根/*multipleroot*/加速收敛法：,Q1:若，NewtonsMethod是否仍收敛？,设x*是f的n重根，则：且。,因为NewtonsMethod事实上是一种特殊的不动点迭代，其中，则,A1:有局部收敛性，但重数n越高，收敛越慢。,Q2:如何加速重根情况时的收敛速度？,A2:将求f的重根转化为求另一函数的单根。,令，则f的重根=的单根。,求复根/*FindingComplexRoots*/Newton公式中的自变量可以是复数,记z=x+iy,z0为初值，同样有,设,代入公式，令实、虚部对应相等，可得,5弦割法与抛物线法/*SecantMethodandParabolaMethod*/,割线/*secantline*/,切线斜率割线斜率,需要2个初值x0和x1。,NewtonsMethod每一步要计算f和，为了避免计算导数值，现用f的值近似，从而得到弦割法（割线法）。,x2,一、弦割法,收敛速度介于NewtonandBisection之间,例1证明方程在区间内有唯一根，且使得对任意的初始值，由割线法产生的序列都收敛于。,证明：,令,方程存在根,方程存在唯一根,Muller方法的思想来源于弦割法:利用3个已知点构造一条抛物线,取其与x轴的交点构造下一次迭代值.,x*,二、抛物线法(Muller),几何图示,xk+1,Muller方法的具体实现:,设已知三个点,则过上述三个点的抛物线方程为:,取该抛物线与x轴的交点作为下一次迭代值,即,然后取新的相邻的三次迭代值重复上述过程,即为Muller方法.,Muller方法中抛物线根的计算方法:,首先要将抛物线化为规范形式:,引入新的变量,将上述变量代入前面的抛物线方程,得,其中,的两个零点为:,取的两个零点中靠近的那个零点,则有,Muller方法的迭代公式为:,具体计算步骤见教材P39.,算法:Muller方法给定初始近似值x0，x1，x2,求f(x)=0的根.输入:初值x0，x1，x2;容许误差TOL.输出:近似解x.Step1Seti=1;Step4If|t4(x2-x1)|TOLStep2dosteps3-7thenOutput(x);STOP;Step3Computet3=(x2x1)/(x1x0);Step5