电子科大数值分析非线性方程求根市公开课获奖课件

1、第二章 非线性方程求根办法第1页第1页第二章 非线性方程求根办法引言方程求根二分法迭代法及其收敛性Newton迭代法第2页第2页方程是在科学研究中不可缺乏工具；方程求解是科学计算中一个主要研究对象；几百年前就已经找到了代数方程中二次至五次方程求解公式；但是，对于更高次数代数方程当前仍无有效准确解法；对于无规律非代数方程求解也无准确解法；因此，研究非线性方程数值解法成为必定。2.1引言第3页第3页非线性方程普通形式： f(x)=0代数方程： f(x)=a0+a1x+anxn （an0）超越方程 ：f(x)中含三角函数、指数函数、或其它超越函数。用数值办法求解非线性方程环节：（1）找出隔根区间；（

2、只含一个实根区间称隔根区间）（2）近似根准确化。从隔根区间内一个或多个点出发，逐次迫近，寻求满足精度根近似值。第4页第4页2.2 方程求根二分法定理1（介值定理）设函数f(x)在区间a,b连续，且f(a)f(b)0，则x*在x0右侧，令a1=x0， b1=b;（2）若f(x0)f(a)0，则x*在x0左侧，令a1=a， b1= x0。第5页第5页以a1, b1为新隔根区间，且仅为a, b二分之一，对a1, b1重复前过程，得新隔根区间a2, b2，如此二分下去，得一系列隔根区间：a, b a1, b1 a2, b2 ak, bk 其中每个区间都是前一区间二分之一，故ak, bk 长度：当k趋于

3、无穷时趋于0。即若二分过程无限继续下去，这些区间最后必收敛于一点x*，即方程根。第6页第6页二分法性质：f(an)f(bn)0;bn an = (b a)/ 2n实际计算中，若给定充足小正数0和允许误差限1，当|f(xn)| 0或bn- an 1时，均可取x* xn。 每次二分后，取有根区间中点xk= (ak+bk) /2作为根近似值，则可得一近似根序列： x0, x1, x2, 该序列必以根x*为极限。第7页第7页定理2 设x*为方程f(x)=0在a, b内唯一根，且f(x)满足f(a)f(b)0，则由二分法产生第n个区间an, bn 中点xn满足不等式证实：第8页第8页计算过程简朴，收敛性

4、可确保；对函数性质要求低，只要连续即可。收敛速度慢；不能求复根和重根；调用一次求解一个a, b间多个根无法求得。二分法求解非线性方程优缺点：第9页第9页不动点迭代法不动点存在性与迭代法收敛性迭代收敛加速办法2.3 迭代法及其收敛性第10页第10页迭代法基本思想： 迭代法是一个逐次迫近办法，用某个固定公式重复校正根近似值，使之逐步准确化，最后得到满足精度要求结果。例：求方程 x3-x-1=0 在 x=1.5 附近一个根。解：将所给方程改写成假设初值x0=1.5是其根，代入得第11页第11页x1x0，再将x1代入得x2x1，再将x2代入得如此下去，这种逐步校正过程称为迭代过程。这里用公式称为迭代公

5、式，即k=0,1,2,第12页第12页迭代结果见下表： k xk k xk012341.51.357211.330861.325881.3249456781.324761.324731.324721.32472仅取六位数字，x7与x8相同，即认为x8是方程根。x*x8=1.32472第13页第13页2.3.1 不动点迭代法将连续函数方程f(x)0改写为等价形式：x=(x)其中(x)也是连续函数，称为迭代函数。不动点：若x*满足f(x*)=0，则x*=(x*)；反之，若x*=(x*) ，则f(x*)=0 ，称x*为(x)一个不动点。不动点迭代：(k=0,1,)若对任意 x0a, b，由上述迭代得

6、序列xk，有极限则称迭代过程收敛，且x*=(x*)为(x)不动点。第14页第14页x2 x1 x0y = x几何意义：第15页第15页但迭代法并不总令人满意，如将前述方程x3-x-1=0改写为另一等价形式：此时称迭代过程发散。则有x1=2.375， x2=12.396，x3=1904,结果越来越大。仍取初值x0=1.5，建迭代公式：第16页第16页收敛 发散 第17页第17页定理3（存在性） 设(x)Ca, b且满足下列两个条件：（1）对于任意x a, b，有a(x)b；（2）若(x)在a, b一阶连续，且存在常数0L1，使得对任意x a, b，成立| (x)| L则(x)在a, b上存在唯一

7、不动点x*。2.3.2 不动点存在性与迭代法收敛性第18页第18页不动点存在性证实：证：若或显然 (x) 有不动点；不然，设则有（因a(x)b）记则有故存在x*使得即x*即为不动点。第19页第19页不动点存在唯一性证实：设有 x1* x2*, 使得则其中，介于 x1* 和 x2* 之间。由定理条件可得矛盾！故 x1* = x2*，不动点唯一存在。第20页第20页定理4（全局收敛性）设(x)C a, b且满足下列两个条件：则对任意x0 a, b，由xn+1=(xn )得到迭代序列xn 收敛到(x)不动点x *，并有误差预计：（2）若(x)在a, b一阶连续，且存在常数0L1，使得对任意x a,

8、b，成立| (x)| L（1）对于任意x a, b，有a(x)b；第21页第21页( 0L1 )故迭代格式收敛。因此证实：第22页第22页重复递推，可得误差预计式第23页第23页定义 设(x)有不动点x*，若存在x*某邻域R：|x-x*| ，对任意x0 R，迭代过程xk+1=(xk )产生序列xk R且收敛到x*，则称不动点迭代法xk+1=(xk )局部收敛。定理4给出收敛性称全局收敛性，实际应用时通常只在不动点x*邻近考察其收敛性，称局部收敛性。第24页第24页证实：依据连续函数性质，因(x)连续，存在x*某邻域R：|x-x*| ，对任意x R， |(x)| L1，且 |(x)-x*| =

9、| (x)-(x*)| = |()| | x- x*| L | x- x*| | x- x*| 即对任意x R， 总有(x) R。由全局收敛性定义知，迭代过程 xk+1=(xk )对于任意初值x0 R均收敛。定理5（局部收敛性） 设x*为(x)不动点， (x)在x*某邻域连续，且|(x*)|1时称超线性收敛。且r 越大，收敛越快。第28页第28页定理：设x*为x=(x )不动点，若(x )满足：（1） (x )在x*附近是p次连续可微(p1)；（2）则迭代过程xn+1=(xn )在点x*邻近是p阶收敛。得因此故迭代过程xn+1=(xn ) p阶收敛。证：由Taylor公式第29页第29页假定(

10、x )改变不大，近似取某个近似值L，则有2.3.3 迭代收敛加速办法一、Aitken加速收敛办法：由微分中值定理，有同理两式相比，得第30页第30页类推可得故上式即为Aitken加速收敛办法迭代格式。第31页第31页将Aitken加速技巧与不动点结合可得或将其写为二、Steffensen迭代法：第32页第32页解：由前知，迭代格式 xk+1=xk3-1 是发散。现用steffensen迭代法计算。取(x )=x3-1，结果下列： k xk yk zk0123451.51.416291.355651.328951.324801.324722.375001.840921.491401.347101

11、.3251812.39655.238882.317281.444351.32714表明即使不动点迭代法不收敛，用steffensen迭代法仍也许收敛。例：用steffensen迭代法求解方程 x3-x-1=0 。第33页第33页求方程在3,4中解。例解由取对数结构迭代格式故当x 3,4时，(x ) 3,4，且故迭代格式收敛。第34页第34页取x0=3.5，经计算可得迭代16次后x16=3.73307，有6位有效数字。若用steffensen迭代法加速，结果下列：k xk yk zk03.53.604143.6620213.734443.733813.7334723.73307阐明steffen

12、sen迭代法收敛速度比不动点迭代快得多。第35页第35页1. 不动点存在性与迭代法收敛性前一次课内容回顾2. 收敛阶鉴定3. 迭代收敛加速办法4. Steffensen迭代法第36页第36页Newton迭代法及其收敛性简化Newton迭代法（平行弦法）弦截法Newton下山法重根情形2.4 Newton迭代法第37页第37页设方程f(x)=0有近似根xk（f (xk)0），将f(x)在xk展开：（在x和xk之间）2.4.1 Newton迭代法及其收敛性基本思想：将非线性方程逐步归结为某种线性方程求解。可设第38页第38页记该线性方程根为xk+1，则故f(x)=0可近似表示为即为Newton法迭

13、代格式。（k=0,1,）第39页第39页Newton迭代法几何意义： （亦称切线法）xyx*xk+1xkPky=f(x)切线方程故第40页第40页Newton迭代法收敛性：迭代函数：定理：假设f(x)在x*某邻域内含有连续二阶导数，且设f(x*)=0， f (x*)0，则对充足靠近x*初始值x0，Newton迭代法产生序列xn至少平方收敛于x*。设f(x*)=0，f (x*)0，则 (x*)=0，故Newton迭代法在x*附近至少平方收敛。第41页第41页解： f (x)=ex+xex，故Newton迭代公式为k xk 00.51 0.5710220.5671630.56714迭代3次即可得到

14、精度为10-5近似解0.56714。若用不动点迭代，达到同一精度需17次。例：用Newton迭代法解方程 xex-1=0。即取迭代初值x0=0.5，结果下列：第42页第42页Newton迭代法缺点：1.被零除错误2.程序死循环y = arctan x方程: f(x)=x3 3x + 2 = 0在重根x*=1附近，f (x)近似为零。对 f(x) = arctan x存在 x0，Newton迭代法陷入死循环。第43页第43页若| (x)|=|1-cf (x)|1，即取0cf (x)2在x*附近成立，则收敛。若取c=1/f (x0)，则称简化Newton法。2.4.2 简化Newton法（平行弦法

15、）迭代公式：（c0,k=0,1,）迭代函数：第44页第44页在Newton迭代格式中，用差商近似导数，2.4.3 弦截法（割线法）称弦截法。得第45页第45页弦截法几何意义：xyx*xk+1xk-1Pk-1y=f(x)xkPk弦线PkPk-1方程：当y0时，第46页第46页例 用简化Newton迭代法和弦截法计算方程x3-3x+1=0根。解：设f(x)=x3-3x+1，则f (x)=3x2-3由简化Newton法，得由弦截法，得第47页第47页x0=0.5x1= 0.3333333333x2 = 0.3497942387x3 = 0.3468683325x4 = 0.3473702799x5

16、= 0.3472836048x6 = 0.3472985550 x7 = 0.3472959759x8 = 0.3472964208x9 = 0.3472963440 x10 = 0.3472963572x11 = 0.3472963553x0=0.5;x1=0.4;x2 = 0.3430962343x3 = 0.3473897274x4 = 0.3472965093x5= 0.3472963553x6 = 0.3472963553简化Newton法弦截法要达到精度10-8，简化Newton法迭代11次，弦截法迭代5次， Newton迭代法迭代4次。第48页第48页无论前面哪种迭代法：（New

17、ton迭代法、简化Newton法、弦截法）Newton迭代法x0 = 2x1 = -3.54x2 = 13.95x3 = -279.34x4 = 12是否收敛均与初值位置相关。如x0 =1x1 = -0.5708x2 = 0.1169x3 = -0.0011x4 = 7.9631e-010 x5 = 0收敛发散第49页第49页为预防Newton法发散，可增长一个条件： |f(xk+1)|f(xk)|，满足该条件算法称下山法。可用下山法确保收敛，Newton法加快速度。2.4.4 Newton下山法称Newton下山法。（01,下山因子）记即第50页第50页从=1开始，逐次减半计算。顺序，直到使

18、下降条件|f(xk+1)|f(xk)|成立为止。选取：即按第51页第51页例：求解方程要求达到精度|xn-xn-1|10-5，取x0= -0.99。解：先用Newton迭代法：f (x)=x2-1x2=21.69118 x3=15.15689 x4 = 9.70724 x5 = 6.54091 x6 = 4.46497 x7 = 3.13384x8= 2.32607 x9 = 1.90230 x10= 1.75248 x11= 1.73240 x12= 1.73205 x13= 1.73205需迭代13次才达到精度要求第52页第52页用Newton下山法，结果下列：k=0 x0 =-0.99 f(x0) =0.666567k = 1 x1 =32.505829 f(x) = 11416.4 =0.5 x1 =15.757915 f(x