数值分析第7章—非线性方程与方程组的数值解法.ppt

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

1、7.1 7.1 方程求根与二分法方程求根与二分法设非线性方程为设非线性方程为 f(x)=0 (7-1)方程方程(2-1)的解的解 称为称为方程的根方程的根或或函数函数 f(x)的零点。的零点。其中其中m为大于为大于1 1的整数的整数,且且g(x)0,称称 为方程为方程(7-1)的的m重根重根,或或函数函数 f(x)的的m重零点重零点.若若 f(x)为为n 次多项式次多项式,则称则称 f(x)=0为为n 次代数方程次代数方程.若若 f(x)为超越函数为超越函数,则称则称f(x)=0 为为超越方程超越方程 。若若 f(x)可表示为可表示为第第7章章 非线性方程求根非线性方程求根1一、求有根区间的一

2、般方法一、求有根区间的一般方法若若 f(x)满足条件满足条件:(1)在在a,b内连续内连续,(2)f(a)f(b)0,f(0)=10,f(3)=-260f (x)在此三区间的符号分别为在此三区间的符号分别为“-”、“-”、“+”由由 f (x)=4 x2(x-3)=0 得驻点得驻点 x1=0,x2=3。5以上分析可用下表表示以上分析可用下表表示x(-,0)0(0,3)3(3,4)4(4,+)f (x)f(x)-0+-0-+隔根区间隔根区间(0,3)(3,4)可见可见 f(x)仅有两个实根仅有两个实根,分别位于分别位于(0,3),(3,+),又又 f(4)=10,所以第二根的隔根区间可缩小为所以

3、第二根的隔根区间可缩小为(3,4)。62.逐步搜索法逐步搜索法(增值寻根法增值寻根法)搜索过程搜索过程,可从可从a 开始开始,也可从也可从 b 开始开始,这时应取步长这时应取步长 h 0。增值寻根法的基本思想是增值寻根法的基本思想是:从初值从初值 开始开始,按规按规定的一个初始步长定的一个初始步长h 来增值。来增值。同时计算同时计算 .可能遇到三种情形：可能遇到三种情形：此时此时 即为方程的根即为方程的根说明区间说明区间 内无根内无根 说明区间说明区间 内有根内有根 7图图2-1图图2-28三、三、二分法二分法设设方程方程f(x)=0 在区间在区间a,b 内有且只有一个实根内有且只有一个实根x

4、*。即即 f(x)满足条件满足条件:(1)在在a,b内连续内连续,(2)f(a)f(b)0,(3)f(x)在在a,b内严格单调。内严格单调。9 二分法的步骤：二分法的步骤：(2)若若 则则 令令 a2=a,b2=x1 ;(3)若若 则则 ,令令 a2=x1,b2=b。记记a,b=a1,b1,中点中点 计算计算f(x1),(1)若若 f(x1)=0,则则 x1 就是方程的根就是方程的根x*,计算结束计算结束;对压缩了的有根区间对压缩了的有根区间 a2,b2,实行同样的步骤实行同样的步骤.若每次二分时所取区间中点都不是根，则上述过程若每次二分时所取区间中点都不是根，则上述过程将无限进行下去。将无限

5、进行下去。10如此反复进行如此反复进行,可得一系列有根区间套可得一系列有根区间套由于每一区间都是前一区间的一半，因此区间由于每一区间都是前一区间的一半，因此区间 an,bn 的长度为的长度为当当 n 时时,区间必将最终收缩为一点区间必将最终收缩为一点x*,显然显然x*就就是所求的根是所求的根。11只要只要n 足够大足够大,即区间二分次数足够多即区间二分次数足够多,误差就可足误差就可足够小。够小。若取区间若取区间 的中点的中点作为作为 的近似值，则有下述误差估计式的近似值，则有下述误差估计式12 由于在偶重根附近曲线由于在偶重根附近曲线 y=f(x)为上凹或下凸为上凹或下凸,即即 f(a)与与

6、f(b)的符号相同的符号相同,因此不能用二分法求偶重根因此不能用二分法求偶重根.解解 可知可知 要想满足题意，要想满足题意，即即：例例 2 用二分法求方程用二分法求方程 f(x)=x3-x-1=0在在 上的上的实根实根,要求误差不超过要求误差不超过0.005。13为所求之近似根。即为所求之近似根。即 x*1.3242(1)f(a)0(2)根据精根据精 度要求度要求,取到小数取到小数 点后四位点后四位 即可即可.-+-+-1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.32421.5 1.5 1.375 1.375 1.3438 1.3281 1.32811.0

7、 1.25 1.25 1.3125 1.3125 1.3125 1.32031 2 3 4 5 6 7 ann14例例 3用二分法求用二分法求 在在 内的一内的一个实根，且要求满足精度个实根，且要求满足精度解解用二分法计算结果如表用二分法计算结果如表2-1：150.0000721.3647460941.36718751.363281259-0.032151.3642578131.36718751.35937580.032361.363281251.3751.3593757-0.096411.3593751.3751.343756-0.350981.343751.3751.31255-0.848

8、391.31251.3751.2540.162111.3751.51.253-1.798671.251.51.022.3751.52.01.01n16-0.007991.3647460941.3652343751.36425781311-0.016051.3642578131.3652343751.3632812510n接上图接上图迭代迭代11 次，次，近似根近似根即为所求，即为所求，其误差其误差177.2 不动点迭代法及其收敛性不动点迭代法及其收敛性一、迭代法的基本思想一、迭代法的基本思想 迭代法是一种重要的逐次逼近法迭代法是一种重要的逐次逼近法,其其基本思想基本思想是：是：将方程将方程 f

9、(x)=0 化为等价方程化为等价方程然后在隔根区间内取一点然后在隔根区间内取一点 x0，按下式计算按下式计算计算结果生成数列计算结果生成数列如果这个数列有极限如果这个数列有极限18这种求根方法称为这种求根方法称为不动点迭代法不动点迭代法。如果迭代序列收敛如果迭代序列收敛,则称则称迭代格式收敛迭代格式收敛,否则称为否则称为发发散散。当当(x)连续时连续时,显然显然 就是方程就是方程 x=(x)之根。之根。于是于是可以从数列可以从数列 中求得满足精度要求的近似根。中求得满足精度要求的近似根。称为称为迭代格式迭代格式,(x)称为称为迭代函数迭代函数,x0 称为称为迭代初值迭代初值,数列数列 称为称为

10、迭代序列迭代序列。19 对方程进行如下三种变形：对方程进行如下三种变形：用迭代法求方程用迭代法求方程 x4+2x2-x-3=0 在区间在区间1,1.2内内的的 实根实根。解解例例120分别按以上三种形式建立迭代格式，并取分别按以上三种形式建立迭代格式，并取x0=1进行进行迭代计算，结果如下：迭代计算，结果如下：21第二种格式比第一种格式收敛快得多第二种格式比第一种格式收敛快得多,而第三种格式而第三种格式不收敛。不收敛。可见迭代格式不同可见迭代格式不同,收敛情况也不同。收敛情况也不同。准确根准确根 =1.124123029。22例例2 用迭代法求方程用迭代法求方程在在内的一个近似根，取初始近似值

11、内的一个近似根，取初始近似值解解原方程的等价方程可以有以下不同形式原方程的等价方程可以有以下不同形式23对应的迭代公式有：对应的迭代公式有：取取列表计算如下列表计算如下241.365230021.3659167381.365229941.3638870071.3652230581.3678469761.365225591.3600941951.365264751.3751702541.364957011.34545838-469.731.367376371.402540802.99696.73221.348399731.286953770.8165-0.87511.51.51.51.50(4)

12、(3)(2)(1)n表表2-225二、二、迭代法的几何意义迭代法的几何意义一般来说从一般来说从构造构造不止一种，有的不止一种，有的收敛，有的不收敛，这收敛，有的不收敛，这取决于取决于 的性态的性态。方程方程 的根，在几何上就是直线的根，在几何上就是直线与曲线与曲线 交点的横坐标交点的横坐标如图如图2-3所示所示26272829三、不动点的存在性与迭代法的收敛性三、不动点的存在性与迭代法的收敛性定理定理 1(1)当当xa,b时时，(2)存在正数存在正数L1，使对任意的使对任意的 xa,b,方程方程在在a,b存在唯一根存在唯一根,且满足条件且满足条件：设设 则则 30 证方程证方程之解存在且唯一之

13、解存在且唯一.由于由于在在 a,b上存在上存在,f(x)在在a,b上连续。上连续。作函数作函数由条件由条件连续连续。所以所以证证使使 即即则则(1)f(a)0,f(b)0,故存在故存在 ,31则由微分中值定理及条件值定理及条件则由微分中值定理及条件值定理及条件(2)(2)有有此式仅当此式仅当才能成立才能成立，因此因此则由微分中值定理及条件则由微分中值定理及条件(2)有有设方程设方程还有一不动点还有一不动点32定理定理 2(1)当当xa,b时时，(2)存在正数存在正数L1，使对任意的使对任意的 xa,b,对任意迭代初值对任意迭代初值 x0a,b,迭代序列迭代序列,且满足条件且满足条件：设设收敛于

14、收敛于 。则则 且有下列误差估计式且有下列误差估计式 33即迭代过程收敛，即迭代过程收敛，且且反复用此不等式，并注意反复用此不等式，并注意 0 L 1,因此因此先证迭代格式先证迭代格式收敛收敛任取任取 x0 a,b，由微分中值定理，有由微分中值定理，有34提示提示：定理的证明利用定理定理的证明利用定理1 1以及微分中值定理。以及微分中值定理。3536则任取则任取 x0 U,迭代格式迭代格式均收敛于均收敛于 ,定理定理 3 若方程若方程之根的某邻域之根的某邻域 L 1时称为时称为超线性收敛超线性收敛.利用微分中值定理及泰勒展式可得下面的定理利用微分中值定理及泰勒展式可得下面的定理3.显然显然,收

15、敛阶越大收敛阶越大,收敛越快收敛越快.p=2 时称为时称为二阶二阶(平方平方)收敛收敛,特别地特别地,令令若若43则迭代过程在则迭代过程在 的邻近为的邻近为 p 阶收敛阶收敛。(1)若若为线性收敛为线性收敛；则迭代过程在则迭代过程在 的邻近的邻近(2)若若定理定理 4之根之根,在在 的邻域的邻域 U内内有连续的有连续的 p 阶导数，阶导数，则则 设设 为为4445由泰勒展式可得由泰勒展式可得解解的三阶方法。假设的三阶方法。假设 x0 充分靠近充分靠近 ,求求证明迭代公式证明迭代公式 xk+1=xk(xk2+3a)/(3xk2+a)，试求试求例例 246加速迭代法加速迭代法松弛法迭代公式：松弛法

16、迭代公式：为松弛因子为松弛因子7.3 7.3 迭代收敛的加速方迭代收敛的加速方法法47称为称为斯蒂芬森斯蒂芬森(Steffensen)加速法加速法.则埃特金法为则埃特金法为平方收敛平方收敛；若若为为 p(p 1)阶收敛阶收敛，导数连续导数连续,的的 p 阶阶可以证明可以证明:若若为线性收敛为线性收敛,则埃特金法为则埃特金法为 2p 1 阶收敛阶收敛。迭代格式迭代格式48 求方程求方程 x=e x 在在 x=0.5 附近的根附近的根.x25=x26=0.5671433 若对此格式用若对此格式用斯蒂芬森斯蒂芬森法法,则则 取取 x0=0.5,迭代格式迭代格式 得得解解例例349仍取仍取 x0=0.

17、5,得得由此可见由此可见,斯蒂芬森斯蒂芬森法加速收敛效果是相当显著法加速收敛效果是相当显著的的.50例例4分别用松弛法、分别用松弛法、斯蒂芬森斯蒂芬森法求方程法求方程 在初值在初值 附近的一个根，取迭代格式附近的一个根，取迭代格式解解 用松弛法计算，取用松弛法计算，取51因此松弛法的迭代公式为因此松弛法的迭代公式为列表计算如下：列表计算如下：1.3652300131.3652300121.3649539161.50.8871308690.8871308690.890803686 3 2 1 0n52用用斯蒂芬森斯蒂芬森方法计算，迭代格式为：方法计算，迭代格式为：53列表计算如下：列表计算如下：

18、1.3652305831.3673763721.3652255341.3483997251.3652300131.3652652241.5 2 1 0 n547.4 7.4 牛顿法牛顿法一、牛顿法的基本思想一、牛顿法的基本思想 设已知方程设已知方程 f(x)=0 的近似根的近似根 x0，且在且在 x0附近附近 可用一阶泰勒多项式近似，表示为可用一阶泰勒多项式近似，表示为方程方程 f(x)=0 可用线性方程近似代替，即可用线性方程近似代替，即55解此线性方程得解此线性方程得取此取此 x 作为原方程的新近似根作为原方程的新近似根 x1，重复以上步骤重复以上步骤，得迭代公式得迭代公式此式称为此式称为

19、牛顿牛顿(Newton)迭代公式迭代公式。56例例 1用牛顿法求方程用牛顿法求方程在在 内一个实根，取初始近似值内一个实根，取初始近似值解解所以迭代公式为：所以迭代公式为：列表计算如下：列表计算如下：1.365230011.365262011.37333331.5 3 2 10n57二、牛顿法的几何意义二、牛顿法的几何意义方程方程 的根就是曲线的根就是曲线 与与 轴交点的横轴交点的横坐标坐标 ，当初始值，当初始值 选取后，过选取后，过 作切线，其切线方程为：作切线，其切线方程为：它与它与x轴交点的横坐标为：轴交点的横坐标为：58一般地，设一般地，设 是是 的第的第n 次近似值，过次近似值，过

20、作作 的切线，其切线与的切线，其切线与x 轴交点的横坐标为：轴交点的横坐标为：即用切线与即用切线与 x 轴交点的横坐标近似代替曲线轴交点的横坐标近似代替曲线 与与x 轴交点的横坐标，如图轴交点的横坐标，如图2-4。59若过曲线若过曲线 y=f(x)上的点上的点 P(xk,f(xk)引切线，引切线，该切线与该切线与 x 轴交点的横坐标即为由牛顿迭代公式轴交点的横坐标即为由牛顿迭代公式求得的求得的 xk+1,因此因此牛顿迭代法也称牛顿切线法牛顿迭代法也称牛顿切线法。图图2-460将原方程化为将原方程化为 x e x=0，则则牛顿迭代格式为牛顿迭代格式为取取 x0=0.5，迭代得迭代得x1=0.56

21、6311,x2=0.5671431,x3=0.5671433 f(x)=x e x，f (x)=1+e x,用牛顿迭代法求方程用牛顿迭代法求方程 x=e x 在在 x=0.5 附近的根。附近的根。例例4 4 解解 61三、牛顿迭代法的收敛速度三、牛顿迭代法的收敛速度牛顿迭代法的迭代函数为牛顿迭代法的迭代函数为不为不为 0由于由于 所以当所以当 时时,62只是收敛速度将大大减慢只是收敛速度将大大减慢。1、当当 为单根时，牛顿迭代法在为单根时，牛顿迭代法在根根 的附近的附近 是二阶收敛的是二阶收敛的；2、当当 为重根时，设为为重根时，设为m重根，则重根，则 f(x)可表为可表为其中其中 此时用牛顿

22、迭代法求此时用牛顿迭代法求 仍然收敛仍然收敛，63事实上，因为事实上，因为令令 则则64可见用牛顿法求方程的重根时仅为线性收敛。可见用牛顿法求方程的重根时仅为线性收敛。653、计算重根的牛顿迭代法计算重根的牛顿迭代法有两种方法可以提高求重根的收敛速度：有两种方法可以提高求重根的收敛速度：1）采用如下迭代格式采用如下迭代格式662）将求重根问题化为求单根问题，注意函数将求重根问题化为求单根问题，注意函数所以化为求所以化为求 u(x)=0的单根是平方收敛的。的单根是平方收敛的。格式为格式为67 用牛顿迭代法求用牛顿迭代法求 f(x)=(x-1)sin(x-1)+3x-x3+1=0 在在0.95 附

23、近之根附近之根。取取 x0=0.95 用牛顿迭代用牛顿迭代法求得的法求得的 xk 见右表见右表。解解例例 5k xk k m0 1 2 3 4 5 60.95 0.9744279 0.9870583 0.9934878 0.9967328 0.9983576 0.99919010.5090 0.5047 0.5007 0.51252.0369 2.0190 2.0028 2.0511可见可见 xk 收敛很慢。收敛很慢。68由重根数由重根数 m 为为 2,用加速法用加速法 x0=0.95 x1=0.9988559 x2=x3=1收敛速度大大加快于直接用牛顿迭代公式收敛速度大大加快于直接用牛顿迭代

24、公式.求得求得694、简化牛顿迭代法简化牛顿迭代法此式称为此式称为简化牛顿迭代公式简化牛顿迭代公式。只要只要 M 选择得当选择得当，上式总是线性收敛的。上式总是线性收敛的。在牛顿迭代公式中用一常数在牛顿迭代公式中用一常数 M 代替代替 得得7071牛顿下山法牛顿下山法72用常数用常数 M 来代替来代替 f (xk)虽然简单，但没充分虽然简单，但没充分利用利用 f(x)本身的特性本身的特性，因此收敛较慢。因此收敛较慢。若在牛顿迭代公式中改用差商若在牛顿迭代公式中改用差商代替导数代替导数 f (xk)，得迭代公式得迭代公式1、割线（弦截）法割线（弦截）法7.5 7.5 弦截法与抛物线法弦截法与抛物

25、线法73每步只用一新点，此格式为每步只用一新点，此格式为弦截法（双点割线法）弦截法（双点割线法）。可以证明它的收敛阶为可以证明它的收敛阶为确实比式确实比式收敛快。收敛快。7475将式将式每步只用一新点，此格式为每步只用一新点，此格式为单点割线法。单点割线法。中的中的 xk-1 改为改为 x0，即即763、割线法的几何意义、割线法的几何意义双点割线法是用过点双点割线法是用过点 和和 两点的两点的割线与割线与 x 轴交点的横坐标轴交点的横坐标 作为作为 的新近似值。的新近似值。重复此过程，用过点重复此过程，用过点 和和 的两点的割线法与的两点的割线法与x 轴交点的横坐标轴交点的横坐标 来作为来作为

26、 的下一新的近似值。的下一新的近似值。如图表如图表2-577图图2-5图图2-6单点割线法则是用过点单点割线法则是用过点 和和 的两点的割线与的两点的割线与x 轴交点的横坐标轴交点的横坐标 来作为来作为 的近似值，如图的近似值，如图2-6。78 用牛顿迭代法和弦截法求方程用牛顿迭代法和弦截法求方程 f(x)=x4+2x2 x 3=0 在区间在区间（1,1.5）内之根（误差为内之根（误差为 10-9）。）。取取x0=1.5,用牛顿法用牛顿法,可得可得 x6=1.12412303030；而采用单点割线法，则迭代而采用单点割线法，则迭代18 次得次得x18=1.124123029.例例6解解取取 x

27、0=1.5,x1=1,用双点割线法用双点割线法,迭代迭代6 次得到同样次得到同样的结果，的结果，79例例7用弦截法求用弦截法求 在在0.5附近的根。附近的根。精确到小数点后第六位。精确到小数点后第六位。解解令令即即80取取 列表计算如下：列表计算如下：0.3472960.3472950.3477310.3563220.20.3476950.3477310.3563220.20.5 54 3 2 1 n814、割线法收敛的速度、割线法收敛的速度定理定理这说明它是线性收敛的这说明它是线性收敛的(p=1.6181)。而单而单点割线法在单根附近是线性收敛的。点割线法在单根附近是线性收敛的。设设 的根为的根为 。若。若 在在 附近有连续附近有连续的二阶导数，的二阶导数，而初值，而初值 充分接近充分接近 ，则双点割线法的迭代过，则双点割线法的迭代过程收敛，收敛速度为程收敛，收敛速度为825。抛物线法。抛物线法8384857.67.6解非线性方程组的牛顿迭代法解非线性方程组的牛顿迭代法 8687迭代格式迭代格式8889