数值分析非线性方程的数值解法.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)计算结果如表： k a bk xk f(xk)符号 0 0 1 0.5000 1 0.5000 0.7500 2 0.7500 0.8750 3 0.8750 0.8125 4 0.8125 0.7812 5 0.7812 0.7656 6 0.7656 0.7734 7 0.7734 0.7695 8 0.7695 0.7714 9 0.7714 0.7724 10 0.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）,定理2.2.1,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内收敛,局部收敛性定理,定理2.2.2设x*为g的不动点，g(x)与g(x)在包含x*的某邻域U(x*) (即开区间)内连续，且|g(x*)|0，当x0x* - ，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.146143611 8 3.146177452 9 3.146188209 10 3.146191628 11 3.146192714 12 3.146193060 13 3.146193169 14 3.146193204,k xi 0 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,称平方收敛。,迭代法的收敛阶(收敛速度),定理2.2.3,设x*为g的不动点，p2为正整数，g在x*的某邻域(x*)内p阶连续可微，且 g(x*)=g(x*)=g (p-1)(x*)=0，而g(p)(x*)0， 则存在0，当x0 x* - ，x*+ (x0x*)时，由迭代法(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,. 可见，当初值x0x*时，由(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*的附近至少是平方收敛