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

《数值分析非线性方程的数值解法.ppt》由会员分享，可在线阅读，更多相关《数值分析非线性方程的数值解法.ppt（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章 非线性方程的数值解法非线性方程的数值解法 简介（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)=0f(x)=0的根的根2.1 对分区间法对分区间法 (Bisection Method)原理：原理：若若 f(x)Ca,b，且且

2、f(a)f(b)0，则则f(x)在在(a,b)上必有一根。上必有一根。abx1x2a1b2x*b1a2停机条件（termination condition）：或或误差误差 分析：分析：第第1步产生的步产生的有误差有误差第第 k 步产生的步产生的 xk 有误差有误差对于给定的精度对于给定的精度 ,可估计二分法所需的步可估计二分法所需的步数数 k：例例例例1 1 1 1 用二分法求用二分法求 在在(1,2)(1,2)内的根，要求绝对误差不超过内的根，要求绝对误差不超过 解解解解：f(1)=-50 -(1,2)+f(1.25)0 (1.25,1.375)f(1.313)0 (1.313,1.375)

3、f(1.344)0 (1.344,1.375)f(1.360)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.7

4、724 100.7724 0.7729 取x10=0.7729，误差为|x*-x10|=1/211。Remark1：求奇数个根 Find solutions to the equationon 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)=ta

5、n(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 2.2 单个方程的迭代法 f(x)=0 f(x)=0化为等价方程化为等价方程x=g(x)x=g(x)的方式是不唯一的方式是不唯一的的,有的收敛有的收敛,有的发散有的发散 For example For e

6、xample：2x2x3 3-x-1=0-x-1=0(1)(1)(1)(1)如果将原方程化为等价方程如果将原方程化为等价方程由此可见，这种迭代格式是发散的由此可见，这种迭代格式是发散的 取初值取初值(2)(2)(2)(2)如果将原方程化为等价方程如果将原方程化为等价方程仍取初值仍取初值依此类推依此类推,得得 x x3 3=0.9940=0.9940 x x4 4=0.9990=0.9990 x x5 5=0.9998=0.9998 x x6 6=1.0000=1.0000 x x7 7=1.0000=1.0000已经收敛已经收敛,故原方程的解为故原方程的解为 x=1.0000 x=1.0000

7、 同样的方程同样的方程 不同的迭代格式不同的迭代格式 有不同的结果有不同的结果什么形式的迭代什么形式的迭代法能够收敛呢法能够收敛呢?收敛性分析定义定义2 若存在常数若存在常数(0 1),使得对一使得对一切切x x1 1,x,x2 2a,ba,b,成立不等式成立不等式|g(x|g(x1 1)-g(x)-g(x2 2)|)|x|x1 1-x-x2 2|，（1 1）则称则称g(x)g(x)是是a,ba,b上的一个压缩映射上的一个压缩映射，称为压缩系数称为压缩系数 考虑方程考虑方程 x=g(x),g(x)Ca,b,若若(I)当当 x a,b 时，时，g(x)a,b(II)在在a,ba,b上成立不等式：

8、上成立不等式：|g(x|g(x1 1)-g(x)-g(x2 2)|)|x|x1 1-x-x2 2|（1 1）则则（1）g g在在a,ba,b上存在惟一不动点上存在惟一不动点x x*（2）任取）任取 x0 a,b，由由 xk+1=g(xk)得到的序列得到的序列 x xk k（a,ba,b】）】）收敛于收敛于x x*。（3）k k次迭代所得到的近似不动点次迭代所得到的近似不动点x xk k与精确不动点与精确不动点x x*有有有误差估计式：有误差估计式：（2）（3）定理定理2.2.13 Fixed-Point Iteration证明：证明：g(x)在在a,b上存在不动点？上存在不动点？不动点唯一？不

9、动点唯一？当当k 时，时，xk 收敛到收敛到 x*？|x x*-x|=|g(x-x|=|g(x*)-g(x)|)-g(x)|x|x*-x|.-x|.因因0 0 1 1，故必有，故必有 x=xx=x*若有若有xxa,ba,b,满足满足g(x)=xg(x)=x，则则|x xk k-x-x*|=|g(x|=|g(xk-1k-1)-g(x)-g(x*)|)|x k-1k-1-x-x*|2 2|x|xk-2k-2-x-x*|k k|x|x0 0-x-x*|0 0,令令G(x)=g(x)-x,xG(x)=g(x)-x,xa,ba,b，由条件由条件知知G(a)=g(a)-a0,G(b)=g(b)-b0.G(

10、a)=g(a)-a0,G(b)=g(b)-b0.由条件由条件知知G(x)G(x)在在a,ba,b上连续，又由介值定理知上连续，又由介值定理知存在存在x x*a,ba,b，使使G(xG(x*)=0)=0，即即x x*=g(x=g(x*).).3 Fixed-Point Iteration 可用可用 来控来控制收敛精度制收敛精度 越小，收敛越快越小，收敛越快(4)|(4)|x xk k-x-x*|=|g(x|=|g(xk-1k-1)-g(x)-g(x*)|)|x k-1k-1-x-x*|（|x|xk k-x-xk-1k-1|+|x|+|xk k-x-x*|）,故有故有|x xk k-x-x*|/(

11、1-/(1-)|x|xk k-x-xk-1k-1|.|.这就证明了估计式这就证明了估计式(2).(2).(5)(5)|x|xk k-x-xk-1k-1|=|g(x=|g(xk-1k-1)-g(x)-g(xk-2k-2)|)|x k-1k-1-x-xk-2k-2|k-1k-1|x|x1 1-x-x0 0|联系估计式联系估计式(6)(6)可得可得|x xk k-x-x*|k-1k-1/(1-/(1-)|x|x1 1-x-x0 0|.|.即估计式即估计式(3)(3)成立成立Remark：定理条件非必要条件，而且定理定理条件非必要条件，而且定理2.2.12.2.1中中的压缩条件不好验证，一般来讲的压缩

12、条件不好验证，一般来讲，若知道迭代函数若知道迭代函数g(x)Cg(x)C1 1a,ba,b,并且并且满足满足|g(x)|g(x)|1,1,对任意的对任意的xxa,ba,b,则则g g（x)x)是是a,ba,b上的压缩映射上的压缩映射例题已知方程2x-7-lgx0，求方程的含根区间，考查用迭代法解此方程的收敛性。在这里我们考查在区间3.5,4的迭代法的收敛性很容易验证：f(3.5)0将方程变形成等价形式：x(lgx+7)/2由定理由定理2.2.1知，迭代格式知，迭代格式x xk+1k+1(lgx(lgxk k+7)/2+7)/2在在3.5,43.5,4内收敛内收敛局部收敛性定理局部收敛性定理定理

13、定理2.2.22.2.2设设x x*为为g g的不动点，的不动点，g(x)g(x)与与g(x)g(x)在包含在包含x x*的某邻域的某邻域U(xU(x*)()(即开区间即开区间)内连续，内连续，且且|g(xg(x*)|1)|0 0，当，当x x0 0 x x*-，x x*+时，迭代法时，迭代法(3)(3)产生的序列产生的序列 x xk k x x*-，x x*+且收敛于且收敛于x x*.证明略（作为练习）证明略（作为练习）We donWe dont know t know x x*,how do we,how do we estimate the estimate the inequality

14、inequality？举例用一般迭代法求x3-x-1=0的正实根x*容易得到：容易得到：g(x)g(x)在包含在包含x x*的某邻域的某邻域U(xU(x*)内内连续，且连续，且|g(xg(x*)|1)|1例题用一般迭代法求方程x-lnx2在区间（2，）内的根，要求|xk-xk-1|/|xk|=10-8解：令f(x)=x-lnx-2f(2)0,故方程在（2,4）内至少有一个根将方程化为等价方程：x2lnx因此，x0（2，），xk+12lnxk产生的序列 xk 收敛于X*取初值x03.0,计算结果如下：7 3.1461436118 3.146177452 9 3.14618820910 3.146

15、19162811 3.14619271412 3.14619306013 3.14619316914 3.146193204k 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*，若存在若存在

16、p1和正数和正数c，使得成立使得成立则称则称xk为为 p 阶收敛的阶收敛的特别特别,p=1，要求要求c1,称线性收敛称线性收敛;1p 0，当，当x x0 0 x x*-，x x*+(x(x0 0 xx*)时，由迭代法时，由迭代法(3)(3)产生的序列产生的序列x xk k以以p p阶收敛速度收敛于阶收敛速度收敛于x x*.Prove:(1)(1)由由g(g(x x*)=0)=0必存在必存在 0，当，当x x0 0 x x*-，x x*+U(x)U(x)时，由迭代格式时，由迭代格式(3)(3)产生的序列产生的序列 x xk k 收敛于收敛于x*,x*,并有并有x xk k x x*-，x x*+

17、(2)(2)由泰勒公式有由泰勒公式有x xk+1k+1=g(x=g(xk k)=)=g(x*g(x*）g(x*)(xg(x*)(xk k-x x*)+)+g+g(p-1)(p-1)(x(x*)(x)(xk k-x-x*)p-1p-1/(p-1)!/(p-1)!+g +g(p)(p)(x(x*+(x(xk k-x-x*)(x)(xk k-x-x*)p/p/p!p!，00 1.利用利用g g在在x x*的各阶导数条件及的各阶导数条件及g(xg(x*)=x)=x*,上式可改写成上式可改写成(11)(3)(3)由于由于g g在在x x*处处p p阶连续可微且阶连续可微且g g(p)(p)(x(x*)0

18、)0，知必存在知必存在x x*的的某邻域某邻域(x x*)，当当xU(xxU(x*)时，有时，有g g(p)(p)(x)0.(x)0.由于由于x x*+(x(xk k-x-x*)x x*-，x x*+U(xU(x*)，故故g g(p)(p)(x(x*+(x(xk k-x-x*)0)0，k=0k=0，1,2,1,2,.可见，当初值可见，当初值x x0 0 xx*时，由时，由(11)(11)式可推出诸式可推出诸x xk kxx*于是由于是由(11)(11)式有式有上式令上式令kk取极限取极限.即即 x xk k 有有p p阶收敛速度阶收敛速度.Newton Iterative Method 牛顿法

19、及其几何意义牛顿法及其几何意义 收敛性及其收敛速度收敛性及其收敛速度 计算实例及其程序演示计算实例及其程序演示取取x0 0作为初始近似值作为初始近似值，将将f(x)在在x x0 0做做TaylorTaylor展开展开:重复上述过程重复上述过程 作为第一次近似值作为第一次近似值一、牛顿法及其几何意义一、牛顿法及其几何意义Newton迭代公式迭代公式基本思路：基本思路：将非线性方程将非线性方程f(x)=0 线性化线性化牛顿法的几何意义牛顿法的几何意义xyx*x0 x 1x 2牛顿法也称为切线法牛顿法也称为切线法（局部收敛性定理局部收敛性定理）设设 f(x)C2a,b，若若 x*为为 f(x)在在a

20、,b上的根上的根,且且 f (x*)0，则存在则存在 x*的邻域的邻域 使得任取初始值使得任取初始值 ，Newton 法产生的序列法产生的序列 xk 收敛到收敛到 x*，且满足且满足至少平方收敛至少平方收敛二、牛顿法的收敛性与收敛速度二、牛顿法的收敛性与收敛速度在在x*的附近的附近收敛收敛由由Taylor 展开：展开：令令k，由由 f (x*)0，即可得结论。即可得结论。证明：证明：Newton法法实际上是一种特殊的迭代法实际上是一种特殊的迭代法思考题思考题1 若若 ，Newton法法是否仍收敛？是否仍收敛？设设 x*是是 f 的的 m 重根，则令：重根，则令：且且Answer1:有局部收敛性

21、有局部收敛性Answer2:线性收敛线性收敛思考题思考题2当当x*是是 f(x)=0的的m重根重根,是否平方收敛？是否平方收敛？结论：结论：结论：结论：Newton法的收敛性依赖于法的收敛性依赖于x0 的选取。的选取。x*x0 x0 x0 有根有根根唯一根唯一全局收敛性定理全局收敛性定理(定理定理2.3.1)：设设 f(x)C2a,b，若若(1)f(a)f(b)0；则由则由Newton法产生的序列法产生的序列 xk 单调地收敛到单调地收敛到f(x)=0 在在 a,b 的唯一根的唯一根x*,且收敛速度至少是二阶且收敛速度至少是二阶的的保证保证产生的序列产生的序列xk单调有界单调有界保证保证New

22、ton迭迭代函数代函数将将a,b映映射于自身射于自身将将f(x*)在在 xk 处作处作TaylorTaylor展开展开对迭代公式两边取极限，得对迭代公式两边取极限，得证明：证明：证明：证明：以以为例证明为例证明 说明数列说明数列 xk 有下界有下界故故 xk 单调递减单调递减,从而从而 xk 收敛收敛.令令？三、计算实例及其程序演示计算实例及其程序演示辅助工具辅助工具:VCVC程序设计语言程序设计语言MatlabMatlab数学软件数学软件(1)(1)选定初值选定初值x0,计算计算f(x0),f (x0)计算步骤计算步骤(2)(2)按公式按公式 迭代迭代 得新的近似值得新的近似值xk+1 (3

23、)(3)对于给定的允许精度对于给定的允许精度，如果如果 则终止迭代，取则终止迭代，取 ;否则否则k=k+1，再转再转 步骤步骤(2)(2)计算计算允许精度允许精度最大迭代最大迭代次数次数迭代信息迭代信息例题1用用NewtonNewton法求方程法求方程 的根的根,要求要求迭代格式一：迭代格式一：迭代格式二：迭代格式二：取初值取初值x x0 00.00.0,计算如下：计算如下：对迭代格式一对迭代格式一:the iterative number is 27,the numerical solution is 0.442852706对迭代格式二对迭代格式二:the iterative number

24、is 3,the numerical solution is 0.442854401例题2求函数求函数 的正实根的正实根精度要求：精度要求：从图形中我们可以从图形中我们可以看出：看出：在在x=7和和x=8 之之间有一单根；间有一单根；在在x=1和和x=2 之之间有一重根。间有一重根。用用MatlabMatlab画图，查看根的分布情形画图，查看根的分布情形初值初值x08.0 时,计算的是单根计算的是单根,The iterative number is 28,The numerical solution is 7.600001481初值初值x01.0,计算的是重根计算的是重根,The iterat

25、ive number is 1356,The numerical solution is 1.198631981取初值取初值x x0 08.08.0,用牛顿迭代公式计算如下：用牛顿迭代公式计算如下：取初值取初值x x0 01.01.0,用牛顿迭代公式计算如下：用牛顿迭代公式计算如下：迭代过程的收敛速度迭代过程的收敛速度 一种迭代法要具有实用价值，不但要肯定它是收敛的，还要求它收敛的比较快。所谓迭代过程的收敛速度，是指在接近收敛时迭代误差的下降速度,具体地说,如果迭代误差 当 时成立 (常数)则称迭代过程是 阶收敛收敛的。特别地，时称线性收敛线性收敛，时称平方收敛平方收敛。迭代过程的收敛速度迭代

26、过程的收敛速度迭代过程的加速迭代过程的加速 设 是根 的某个近似值，用迭代公式校正一次得假设 在所考察的范围内改变不大，其估计值为 ，则有据此可导出如下加速公式：其一步分为两个环节：迭代:改进:埃特金算法埃特金算法前面加速方案有个缺点是其中含有导数 的有关信息而不便于实际应用。设将迭代值 再迭代一次，可得 据此构造出不含导数信息的加速公式：迭代:迭代:改进:这一加速方法称为埃特金算法埃特金算法。埃特金算法埃特金算法开方公式开方公式对于给定正数 应用牛顿迭代法解二次方程可导出求开方值 的计算公式设 是 的某个近似值，则 自然也是一个近似值，上式表明，它们两者的算术平均值将是更好的近似值。定理定理

27、 开方公式对于任意给定的初值 均为平方收敛。开方公式开方公式牛顿下山法牛顿下山法一般地说，牛顿法的收敛性依赖于初值 的选取，如果 偏离 较远，则牛顿法可能发散。为了防止发散，通常对迭代过程再附加一项要求，即保证函数值单调下降：满足这项要求的算法称为下山法下山法。牛顿下山法牛顿下山法采用以下迭代公式：其中 称为下山因子。弦截法弦截法用差商 替代牛顿公式中的导数可得到以下离散化形式：从几何图形上看，上面的公式求得的实际上是弦线与 轴的交点，因此称这种方法为弦截法弦截法。改用差商 代替牛顿法中的导数有以下快速弦截法迭代公式：弦截法弦截法弦截法弦截法小结(1)当f(x)充分光滑且 x*是f(x)=0的

28、单根时，牛顿法在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.0000000012.1893260 1.5984751 1.393900621.8505896 1.4442514 1.278224031.7801611

29、1.4244359 1.239292441.7776747 1.4239609 1.237473851.7776719 1.4239605 1.237471161.7776719 1.4239605 1.2374711练习：练习：3.3.Newton Newton 迭代法是如何推出的迭代法是如何推出的?它若在单根附近收它若在单根附近收敛敛,是几阶收敛是几阶收敛?在重根附近是几阶收敛？求方程重根在重根附近是几阶收敛？求方程重根时时,能达到能达到2 2阶收敛的改进阶收敛的改进 Newton Newton 迭代公式是什么迭代公式是什么1.1.用牛顿法求方程用牛顿法求方程 在区间在区间 1 1，2 2 内内的一个实根，要求的一个实根，要求2.2.导出求立方根导出求立方根 的迭代公式，并讨论其收敛性。的迭代公式，并讨论其收敛性。首先导出求根方程首先导出求根方程 ，再对，再对 使用牛顿法使用牛顿法得迭代公式得迭代公式 ,用全局收敛性定理或局部收用全局收敛性定理或局部收敛性定理讨论其收敛性。敛性定理讨论其收敛性。Newton 迭代法的收敛性简单迭代法下山迭代法弦截法弦截法弦截法弦截法弦截法的几何表示x0Xx*x1 x2 x3Y f(x)0P0P2 P1弦截法收敛性定理弦截法收敛性定理用弦截法给出埃特金算法的几何解释 二、抛物线法抛物线法计算公式