数值分析非线性方程的数值解法.ppt

第二章 非线性方程的数值解法,简介（Introduction）,我们知道在实际应用中有许多非线性方程的例子，例如（1）在光的衍射理论（the theory of diffraction of light)中,我们需要求x-tanx=0的根（2）在行星轨道（planetary orbits）的计算中,对任意的a和b，我们需要求x-asinx=b的根（3）在数学中，需要求n次多项式xn+a1 xn-1+.+an-1 x+an 0的根,求f(x)=0的根,2.1 对分区间法(Bisection Method),原理：若 f(x)Ca,b，且 f(a)f(b)0，则f(x)在(a,b)上必有一根。,x1,x2,a1,b2,x*,b1,a2,误差 分析：,第 k 步产生的 xk 有误差,对于给定的精度,可估计二分法所需的步数 k：,例1 用二分法求 在(1,2)内的根，要求绝对误差不超过 解：f(1)=-50-(1,2)+f(1.25)0(1.25,1.375)f(1.313)0(1.360,1.368),f(1.5)0(1,1.5),12,例2，求方程f(x)=x 3 e-x=0的一个实根。因为 f(0)0。故f(x)在(0,1)内有根用二分法解之，(a,b）=（0,1)计算结果如表：ka bk xk f(xk)符号00 1 0.5000 10.5000 0.7500 20.7500 0.8750 3 0.87500.8125 4 0.81250.7812 5 0.7812 0.7656 60.7656 0.7734 7 0.7734 0.7695 8 0.7695 0.7714 90.7714 0.7724 100.7724 0.7729 取x10=0.7729，误差为|x*-x10|=1/211。,Remark1：求奇数个根,Find solutions to the equation,on the intervals 0,4，Use the bisection method to compute a solution with an accuracy of 107.Determine the number of iterations to use.,0,1,1.5,2.5 and 3,4，利用前面的公式可计算迭代次数为k=23.,Remark2:要区别根与奇异点,Consider f(x)=tan(x)on the interval(0,3).Use the 20 iterations of the bisection method and see what happens.Explain the results that you obtained.（如下图）,Remark3:二分发不能用来求重根,f(x)=0,x=g(x),f(x)的根,g(x)的不动点,2.2 单个方程的迭代法,f(x)=0化为等价方程x=g(x)的方式是不唯一的,有的收敛,有的发散 For example：2x3-x-1=0,(1)如果将原方程化为等价方程,由此可见，这种迭代格式是发散的,取初值,(2)如果将原方程化为等价方程,仍取初值,依此类推,得 x3=0.9940 x4=0.9990 x5=0.9998 x6=1.0000 x7=1.0000,已经收敛,故原方程的解为 x=1.0000,同样的方程 不同的迭代格式 有不同的结果,什么形式的迭代法能够收敛呢?,收敛性分析,定义2 若存在常数(0 1),使得对一切x1,x2a,b,成立不等式|g(x1)-g(x2)|x1-x2|，（1）则称g(x)是a,b上的一个压缩映射，称为压缩系数,考虑方程 x=g(x),g(x)Ca,b,若(I)当 xa,b 时，g(x)a,b(II)在a,b上成立不等式：|g(x1)-g(x2)|x1-x2|（1）则（1）g在a,b上存在惟一不动点x*（2）任取 x0a,b，由 xk+1=g(xk)得到的序列 xk（a,b】）收敛于x*。（3）k次迭代所得到的近似不动点xk与精确不动点x*有有误差估计式：（2）（3）,3 Fixed-Point Iteration,证明：g(x)在a,b上存在不动点？,不动点唯一？,当k 时，xk 收敛到 x*？,|x*-x|=|g(x*)-g(x)|x*-x|.因0 1，故必有 x=x*,若有xa,b,满足g(x)=x，则,|xk-x*|=|g(xk-1)-g(x*)|x k-1-x*|2|xk-2-x*|k|x0-x*|0,令G(x)=g(x)-x,xa,b，由条件知G(a)=g(a)-a0,G(b)=g(b)-b0.,由条件知G(x)在a,b上连续，又由介值定理知存在x*a,b，使G(x*)=0，即x*=g(x*).,3 Fixed-Point Iteration,可用 来控制收敛精度,越小，收敛越快,(4)|xk-x*|=|g(xk-1)-g(x*)|x k-1-x*|（|xk-xk-1|+|xk-x*|）,故有|xk-x*|/(1-)|xk-xk-1|.这就证明了估计式(2).,(5)|xk-xk-1|=|g(xk-1)-g(xk-2)|x k-1-xk-2|k-1|x1-x0|,联系估计式(6)可得|xk-x*|k-1/(1-)|x1-x0|.即估计式(3)成立,Remark：,定理条件非必要条件，而且定理2.2.1中的压缩条件不好验证，一般来讲，若知道迭代函数g(x)C1a,b,并且满足|g(x)|1,对任意的xa,b,则g（x)是a,b上的压缩映射,例题,已知方程2x-7-lgx0，求方程的含根区间，考查用迭代法解此方程的收敛性。,在这里我们考查在区间3.5,4的迭代法的收敛性,很容易验证：f(3.5)0将方程变形成等价形式：x(lgx+7)/2,由定理2.2.1知，迭代格式xk+1(lgxk+7)/2在3.5,4内收敛,局部收敛性定理,设x*为g的不动点，g(x)与g(x)在包含x*的某邻域U(x*)(即开区间)内连续，且|g(x*)|0，当x0 x*-，x*+时，迭代法(3)产生的序列xk x*-，x*+且收敛于x*.证明略（作为练习）,We dont know x*,how do we estimate the inequality？,举例,用一般迭代法求x3-x-1=0的正实根x*,容易得到：g(x)在包含x*的某邻域U(x*)内连续，且|g(x*)|1,例题,用一般迭代法求方程x-lnx2在区间（2，）内的根，要求|xk-xk-1|/|xk|=10-8,解：令f(x)=x-lnx-2,f(2)0,故方程在（2,4）内至少有一个根,将方程化为等价方程：x2lnx,因此，x0（2，），xk+12lnxk产生的序列 xk 收敛于X*,取初值x03.0,计算结果如下：,7 3.1461436118 3.146177452 9 3.14618820910 3.14619162811 3.14619271412 3.14619306013 3.14619316914 3.146193204,k xi0 3.000000000 1 3.098612289 2 3.130954362 3 3.141337866 4 3.144648781 5 3.145702209 6 3.146037143,另一种迭代格式：,0 3.000000000 1 3.147918433 2 3.146193441 3 3.146193221,程序演示,由此可见，对同一个非线性方程的迭代格式，在收敛的情形下，有的收敛快，有的收敛慢。,定义1.:设序列xk收敛于x*，若存在p1和正数c，使得成立,则称xk为 p 阶收敛的,特别,p=1，要求c1,称线性收敛;1p2,称超线性收敛 p=2,称平方收敛。,迭代法的收敛阶(收敛速度),设x*为g的不动点，p2为正整数，g在x*的某邻域(x*)内p阶连续可微，且g(x*)=g(x*)=g(p-1)(x*)=0，而g(p)(x*)0，则存在0，当x0 x*-，x*+(x0 x*)时，由迭代法(3)产生的序列xk以p阶收敛速度收敛于x*.,Prove:,(1)由g(x*)=0必存在0，当x0 x*-，x*+U(x)时，由迭代格式(3)产生的序列xk收敛于x*,并有xk x*-，x*+(2)由泰勒公式有xk+1=g(xk)=g(x*）g(x*)(xk-x*)+g(p-1)(x*)(xk-x*)p-1/(p-1)!+g(p)(x*+(xk-x*)(xk-x*)p/p!，01.利用g在x*的各阶导数条件及g(x*)=x*,上式可改写成,(11),(3)由于g在x*处p阶连续可微且g(p)(x*)0，知必存在x*的某邻域(x*)，当xU(x*)时，有g(p)(x)0.由于x*+(xk-x*)x*-，x*+U(x*)，故g(p)(x*+(xk-x*)0，k=0，1,2,.可见，当初值x0 x*时，由(11)式可推出诸xkx*于是由(11)式有,上式令k取极限.,即xk有p阶收敛速度.,Newton Iterative Method,牛顿法及其几何意义 收敛性及其收敛速度 计算实例及其程序演示,取x0作为初始近似值，将f(x)在x0做Taylor展开:,重复上述过程,作为第一次近似值,一、牛顿法及其几何意义,Newton迭代公式,基本思路：将非线性方程f(x)=0 线性化,牛顿法的几何意义,x 1,x 2,牛顿法也称为切线法,（局部收敛性定理）设 f(x)C2a,b，若 x*为 f(x)在a,b上的根,且 f(x*)0，则存在 x*的邻域 使得任取初始值，Newton 法产生的序列 xk 收敛到 x*，且满足,至少平方收敛,二、牛顿法的收敛性与收敛速度,在x*的附近收敛,由Taylor 展开：,令k，由 f(x*)0，即可得结论。,证明：Newton法实际上是一种特殊的迭代法,设 x*是 f 的 m 重根，则令：且,Answer1:有局部收敛性,Answer2:线性收敛,结论：Newton法的收敛性依赖于x0 的选取。,x*,有根,根唯一,全局收敛性定理(定理2.3.1)：设 f(x)C2a,b，若f(a)f(b)0；则由Newton法产生的序列 xk 单调地收敛到f(x)=0 在 a,b 的唯一根x*,且收敛速度至少是二阶的,保证Newton迭代函数将a,b映射于自身,将f(x*)在 xk 处作Taylor展开,对迭代公式两边取极限，得,说明数列xk有下界,故xk单调递减,从而xk收敛.令,？,三、计算实例及其程序演示,辅助工具:VC程序设计语言Matlab数学软件,(1)选定初值x0,计算f(x0),f(x0),计算步骤,(2)按公式 迭代 得新的近似值xk+1,(3)对于给定的允许精度，如果 则终止迭代，取;否则k=k+1，再转 步骤(2)计算,允许精度,最大迭代次数,迭代信息,例题1,用Newton法求方程 的根,要求,取初值x00.0,计算如下：,对迭代格式一:the iterative number is 27,the numerical solution is 0.442852706对迭代格式二:the iterative number is 3,the numerical solution is 0.442854401,例题2,求函数 的正实根精度要求：,从图形中我们可以看出：在x=7和x=8 之间有一单根；在x=1和x=2 之间有一重根。,用Matlab画图，查看根的分布情形,初值x08.0 时,计算的是单根,The iterative number is 28,The numerical solution is 7.600001481初值x01.0,计算的是重根,The iterative number is 1356,The numerical solution is 1.198631981,迭代过程的收敛速度,一种迭代法要具有实用价值，不但要肯定它是收敛的，还要求它收敛的比较快。所谓迭代过程的收敛速度，是指在接近收敛时迭代误差的下降速度,具体地说,如果迭代误差 当 时成立(常数)则称迭代过程是 阶收敛的。特别地，时称线性收敛，时称平方收敛。,迭代过程的收敛速度,迭代过程的加速,设 是根 的某个近似值，用迭代公式校正一次得假设 在所考察的范围内改变不大，其估计值为，则有据此可导出如下加速公式：其一步分为两个环节：迭代:改进:,埃特金算法,前面加速方案有个缺点是其中含有导数 的有关信息而不便于实际应用。设将迭代值 再迭代一次，可得 据此构造出不含导数信息的加速公式：迭代:迭代:改进:这一加速方法称为埃特金算法。,埃特金算法,开方公式,对于给定正数 应用牛顿迭代法解二次方程可导出求开方值 的计算公式设 是 的某个近似值，则 自然也是一个近似值，上式表明，它们两者的算术平均值将是更好的近似值。定理 开方公式对于任意给定的初值 均为平方收敛。,开方公式,牛顿下山法,一般地说，牛顿法的收敛性依赖于初值 的选取，如果 偏离 较远，则牛顿法可能发散。为了防止发散，通常对迭代过程再附加一项要求，即保证函数值单调下降：满足这项要求的算法称为下山法。牛顿下山法采用以下迭代公式：其中 称为下山因子。,弦截法,用差商 替代牛顿公式中的导数可得到以下离散化形式：从几何图形上看，上面的公式求得的实际上是弦线与 轴的交点，因此称这种方法为弦截法。改用差商 代替牛顿法中的导数有以下快速弦截法迭代公式：,弦截法,弦截法,小结,(1)当f(x)充分光滑且 x*是f(x)=0的单根时，牛顿法在x*的附近至少是平方收敛的。(2)当f(x)充分光滑且 x*是f(x)=0的重根时，牛顿法在x*的附近是线性收敛的。(3)Newton法在区间a,b上的收敛性依赖于初值x0 的选取。,解非线性方程组的牛顿法,将非线性方程组线性化，得到：,其中F(xk)为F(x)在xk处的Jacobi矩阵：,例：用牛顿法解方程组,取初始值（1，1，1），计算如下,N x y z0 1.0000000 1.0000000 1.000000002.1893260 1.5984751 1.39390061.8505896 1.4442514 1.27822401.7801611 1.4244359 1.23929241.7776747 1.4239609 1.23747381.7776719 1.4239605 1.23747111.7776719 1.4239605 1.2374711,练习：,3.Newton 迭代法是如何推出的?它若在单根附近收敛,是几阶收敛?在重根附近是几阶收敛？求方程重根时,能达到2阶收敛的改进 Newton 迭代公式是什么,用牛顿法求方程 在区间 1，2 内的一个实根，要求,2.导出求立方根 的迭代公式，并讨论其收敛性。,首先导出求根方程，再对 使用牛顿法得迭代公式,用全局收敛性定理或局部收敛性定理讨论其收敛性。,Newton 迭代法的收敛性,简单迭代法,下山迭代法,弦截法,弦截法,弦截法的几何表示,弦截法收敛性定理,用弦截法给出埃特金算法的几何解释,二、抛物线法,抛物线法计算公式,