《数值分析》第四章--解非线性方程的迭代法ppt课件.ppt

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

1、经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第第4 4章章 解非线性方程的迭代法解非线性方程的迭代法 本章讨论求非线性方程 (x)=0 (4.1)的根的问题.其中(x)是高次多项式函数或超越函数.如 (x)=3x5-2x4+8x2-7x+1 (x)=e2x+1-xln(sinx)-2等等.1 二二 分分 法法 设(x)在区间a,b上连续且(a)(b)0,根据连续函数的介值定理,区间a,b上必有方程(x)=0的根,称a,b为方程(x)=0的有根区间.经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔

2、偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 ,得到新的有根区间a1,b1,设(x)在区间a,b上连续且(a)(b)0.0abyxy=(x)记a0=a,b0=b,计算若|(x0)|,则取x0;否则,若(a0)(x0)0,取a1=x0,b1=b0 而且有根区间a1,b1长度是有根区间a0,b0长度的一半,x0再对有根区间a1,b1重复上面运算,即:计算若|(x1)|,则取x1;否则,若(a1)(x1)0,取a2=x1,b2=b1,得到新的有根区间a2,b2.x1 而且有根区间a2,b2长度是有根区间a1,b1长度的一半.一直进行下去,直到求出有根区间ak,bk.经营者提供

3、商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 或者有|(xk)|,或者有此时,再计算可见,k趋向无穷大时,xk收敛于.而且,若要|xk-|,只要此时可取近似根xk.在计算过程中,若出现|(xk)|1,或bk-ak2.则可取xk作为方程(x)=0的近似根,终止运算.例例1 用二分法求x3+4x-7=0在区间1,2内根的近似值,并估计误差.经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 解解 这里(x)=x3+4x-7，(1)(2)=-18

4、0,所以(x)=0在1,2区间有唯一根.取x0=1.5,由于(x0)=2.375,得新有根区间1,1.5,x1=1.25,由于(x1)=-0.0468,得新有根区间1.25,1.5,x2=1.375,由于(x2)=1.0996,得新有根区间1.25,1.375,x3=1.3125,由于(x3)=0.511,得新有根区间1.25,1.3125,.x9=1.254882813,得有根区间1.254882813,1.255859375,x10=1.255371094,(x10)=-0.000105285取x10=1.255371094作为方程根的近似值,且有 经营者提供商品或者服务有欺诈行为的，应当

5、按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用只需k5ln210-115.61.即需取x16.如果取精度=10-5,则要使 二分法要求函数在区间a，b上连续，且在区间两端点函数值符号相反，二分法运算简便、可靠、易于在计算机上实现。但是，若方程(x)=0在区间a，b上根多于1个时，也只能求出其中的一个根。另外，若方程(x)=0在区间a，b有重根时，也未必满足(a)(b)0.而且由于二分法收敛的速度不是很快,一般不单独使用,而多用于为其他方法提供一个比较好的初始近似值.经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿

6、的金额为消费者购买商品的价款或接受服务的费用 2.1 简单迭代法的一般形式简单迭代法的一般形式2 简简 单单 迭迭 代代 法法 首先把方程(x)=0改写成等价(同解)形式 x=(x)(4.2)得到迭代序列xk,如果xk,则有=(),即是方程(x)=0的根.取一个合适的初始值x0,然后作迭代 xk+1=(xk),k=0,1,2,(4.3)这种求方程根的方法称为简单迭代法简单迭代法,或逐逐次逼近法次逼近法.其中(x)称为迭代函数迭代函数,式(4.3)称为迭代格式迭代格式.若迭代序列xk 收敛,则称简单迭代法是收敛的简单迭代法是收敛的.经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿

7、其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 解解 改写原方程为等价方程 求方程x3-2x-3=0在1,2内的根.例例2 ,建立迭代格式如果取初值x0=1.9,计算得kxkkxk0123451.91.894536471.893521141.893332331.893297221.893290696789101.893289471.893289251.893289211.893289201.89328920经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 由计算结果有，x10=x9，因此可取x

8、10=1.89328920.方程也可改写成x=(x3-3)/2,建立迭代格式 xk+1=(xk3-3)/2 ,k=0,1,2,仍取初值x0=1.9,则有 x1=1.9295,x2=2.0917,x3=3.0760,x4=13.0529可见,xk,此迭代格式是发散的.2.2 简单迭代法的收敛条件及收敛阶简单迭代法的收敛条件及收敛阶 首先，(x)应使初值 x0 产生的序列xka,b,即(x)的值域落在定义域内.另外,从几何上看:经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用x xo oy yy=xy=xy=(x)x

9、 x0 0 x x1 1x x2 2 x xo oy yy=xy=xy=(x)x x0 0 x x1 1x x2 2x xo oy yy=xy=xy=(x)x x0 0 x x1 1x x2 2x xo oy yy=xy=xy=(x)x x0 0 x x1 1x x2 2 x x4 4x x3 3经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 1.a(x)b,xa,b;2.|(x)|L0,要使|xk-|,只要经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买

10、商品的价款或接受服务的费用 证证 记(x)=(x)-x,则(a)=(a)-a0,(b)=(b)-b0,由(x)的连续性,必存在I,使()=()-=0,即=(),又(x)=(x)-10,所以(x)=0的根唯一.|xk+1-xk|=|(xk)-(xk-1)|=|()(xk-xk-1)|L|xk-xk-1|xk+1-|=|(xk)-()|=|()(xk-)|L|xk-|xk+1-xk|=|(xk+1-)-(xk-)|xk-|-|xk+1-|(1-L)|xk-|经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 求方程xe

11、x-1=0在0.5附近的根,精度要求=10-3.解解 可以验证方程xex-1=0在区间0.5,0.6内仅有一个根.例例3 改写方程为x=e-x,建立迭代格式 由于(x)=e-x,在0.5,0.6上有|(x)|e-0.50.61.所以迭代法收敛.取初值x0=0.5,计算得kxk|xk-xk-1|kxk|xk-xk-1|0123450.50.606530.545240.579700.560060.571170.106530.061290.034460.019640.011116789100.564860.568440.566410.567560.566910.006310.003580.00203

12、0.001150.00065经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 所以,取近似根x10=0.56691满足精度要求.如果精度要求为=10-5,则由可知,需要迭代20次.实际上,方程在区间0.55,0.6上有唯一根，而在区间0.55,0.6上有|(x)|e-0.550.581。若取L=0.58，则有 注意：这里迭代次数20是充分的但不是必要的。可知,需要迭代19次.经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 推论推论

13、 若=(),(x)在附近具有一阶连续导数,且|()|0，当x0I=-，+时，迭代格式xk+1=(xk),k=0,1,2,都收敛于方程x=(x)在区间I上的唯一根。实际上，由连续性可知,存在L0，0，使对任何xI=-，+都有|(x)|L1.而且，对任何xI=-，+，都有|(x)-|=|(x)-()|=|()(x-)|L|x-|1则称序列xk是p p阶收敛的阶收敛的,称p是收敛阶收敛阶,C是渐近误差常渐近误差常数数.p=1称为线性收敛线性收敛;p1称超线性收敛超线性收敛;p=2称平方收敛平方收敛.设(x)充分光滑,由于|ek+1|=|xk+1-|=|(xk)-()|=|(k)|ek|所以,当()0

14、时,有经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用于是此时,迭代法是m阶收敛的.所以,当()0时,简单迭代法只具有线性收敛.设()=()=(m-1)()=0,但(m)()0,由于|ek+1|=|xk+1-|=|(xk)-()|所以 下面介绍AitkenAitken加速算法加速算法，此方法可对线性收敛的简单迭代法起到加速作用，而且可应用于其它数值方法中。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用假设(1)(2)，则有 由于

15、xk+1-=(1)(xk-)xk+2-=(2)(xk+1-)即 (xk+1-)2(xk-)(xk+2-)xk+12-2xk+1+2xkxk+2-(xk+xk+2)+2 解得 经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 要比序列x k更快地收敛于,可构造如下的Aitken加速算法:则,序列注意,如果第k步发生zk-2yk+xk=0,就终止计算,取xk.如果记 例例4 分别用简单迭代法和Aitken加速算法求方程x=1.6+0.99cosx在x0=/2附近的根.(=1.585471802)经营者提供商品或者服务

16、有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用取x0=/2,计算结果如下k简单迭代法kAitken算法xk|xk-xk-1|xk|xk-xk-1|012341.570801.61.571091.599711.571380.02920.028910.028620.028330121.57079631.585472581.585471800.014676280.00000078经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 NewtonNewton迭代法

17、迭代法是求方程根的重要方法之一,其最大优点是在方程的单根附近具有平方收敛,而且Newton迭代法还可用来求方程的重根、复根及非线性方程组.3 Newton 迭代法迭代法 3.1 Newton迭代公式迭代公式 设(x)在有根区间a,b上二阶连续可微,x0是根的某个近似值,因为取(x)(x0)+(x0)(x-x0),方程(x)=0近似为 (x0)+(x0)(x-x0)=0若(x0)0,其解为经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用得到根的新的近似值x1,一般地,在xk附近线性化方程为 (xk)+(xk)(x-

18、xk)=0设(xk)0,其解为迭代格式(4.4)称为 NewtonNewton迭代法迭代法.xyox0y=(x)x1x2直线 y=(x0)+(x0)(x-x0)就是 y-(x0)=(x0)(x-x0)Newton迭代法也叫切线法切线法.经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 Newton迭代法相当于取迭代函数3.2 Newton迭代法的收敛性迭代法的收敛性的简单迭代法.因为 如果是(x)=0的单根,即()=0,但()0,则有()=0,从而可知Newton迭代法在根附近是收敛的.因为所以经营者提供商品或者

19、服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用于是有可见,Newton迭代法至少是平方收敛的.若记M2=max|(x)|,m1=min|(x)|.则有|xk+1-|C|xk-|2因此 C|xk+1-|(C|xk-|)2 (C|xk-1-|)4 可见,当C|x0-|1,即|x0-|1/2max|(x)|时,简化Newton迭代法对x0I收敛.通常取M=(x0).简化Newton迭代法一般只具有线性收敛.2.2.割线法割线法 因为经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买

20、商品的价款或接受服务的费用oxyy=(x)x0 x1x2x3 为了简化计算(xk),采用迭代格式称为割线割线法法.若(x)在根附近二次连续可微,且()0,可以证明割线法是收敛的,且有割线法收敛的阶为 3.3.计算重根的计算重根的NewtonNewton迭代法迭代法经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 称是方程(x)=0的m重根,是指(x)=(x-)m h(x),其中h(x)在x=处连续且h()0,若h(x)在处充分可微,则 ()=()=(m-1)()=0,(m)()0由于可见,恰是方程 的单根.应用N

21、ewton迭代法可得:称之为带参数带参数m m的的NewtonNewton迭代法迭代法,它是求方程(x)=0m重根的具有平方收敛的迭代法.再看函数:经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用可见,恰是方程u(x)=0的单根,应用Newton迭代法有这是求方程(x)=0重根的具有平方收敛的迭代法,而且不需知道根的重数.例例7 7 利用Newton迭代法求方程 (x)=x4-8.6x3-35.51x2+464.4x-998.46=0的正实根.o ox xy2 24 46 68 81010y=f(x)解 y=(x

22、)的图形为可见,方程在x=4附近有一个重根,在x=7附近有一单根.经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用利用Newton迭代法求方程的单根,取初值x0=7,精度=10-6,计算可得:x4=7.34846923,x5=7.348469229,|x5-x4|=0.000000001可见,迭代5次就得到满足精度的解x5=7.348469229利用求重根的Newton迭代法(4.5)求重根,取x0=4,可得 x3=4.300000,x4=4.300000,|x4-x3|=0.000000006然而若用一般的Ne

23、wton迭代法(4.4)求重根,取x0=4,虽然也收敛,却需要迭代19次才能得到满足精度要求的解.可见,迭代4次就得到满足精度的解x4=4.300000.利用带参数2的Newton迭代法,取x0=4可得x2=4.2999898.经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用练习题练习题第第102页页 习题习题44-1,4-3,4-4,4-5,4-7,4-8,经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用练习题练习题第第102页页 习题习题44-10，4-12,4-13,经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用课间休息课间休息