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

第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的有根区间.,得到新的有根区间a1,b1,设(x)在区间a,b上连续且(a)(b)0 .,0,a,b,y,x,y=(x),记a0=a,b0=b,计算,若|(x0)|0,取a1=x0,b1=b0,而且有根区间a1,b1长度是有根区间a0,b0长度的一半,x0,再对有根区间a1,b1重复上面运算, 即: 计算,若|(x1)|0, 取a2=x1 ,b2=b1,得到新的有根区间a2,b2.,x1,而且有根区间a2,b2长度是有根区间a1,b1长度的一半.一直进行下去,直到求出有根区间ak,bk.,或者有|(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)=-180,所以(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作为方程根的近似值,且有,只需k5ln210-115.61.即需取x16.,如果取精度=10-5,则要使,二分法要求函数在区间a，b上连续，且在区间两端点函数值符号相反，二分法运算简便、可靠、易于在计算机上实现。但是，若方程(x)=0在区间a，b上根多于1个时，也只能求出其中的一个根。另外，若方程(x)=0在区间a，b有重根时，也未必满足(a)(b)0. 而且由于二分法收敛的速度不是很快,一般不单独使用,而多用于为其他方法提供一个比较好的初始近似值.,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 收敛 , 则称简单迭代法是收敛的.,解 改写原方程为等价方程,求方程x3-2x-3=0在1,2内的根.,例2,建立迭代格式,如果取初值x0=1.9 ,计算得,由计算结果有，x10=x9，因此可取x10=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)的值域落在定义域内.,另外,从几何上看:,x0,x1,x2,x0,x1,x2,x0,x1,x2,x0,x1,x2,x4,x3,1.a(x)b, xa,b; 2.|(x)| L1, xa,b,定理4.1,设迭代函数(x)C1a,b,且满足,则迭代格式xk+1=(xk),k=0,1,2,x0a,b都收敛于方程x=(x)在区间a,b的唯一根，且,可见,|xk-xk-1|充分小可保证|xk-|充分小,而且对任一0,要使|xk-|, 只要,证 记(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-|,求方程xex-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,计算得,所以,取近似根x10=0.56691满足精度要求.,如果精度要求为=10-5, 则由,可知,需要迭代20次.,实际上,方程在区间0.55,0.6上有唯一根，而在区间0.55,0.6上有|(x)|e-0.550.581。若取L=0.58，则有,注意：这里迭代次数20是充分的但不是必要的。,可知,需要迭代19次.,推论 若=(),(x)在附近具有一阶连续导数,且|()|0，当x0I=-， +时，迭代格式xk+1=(xk),k=0,1,2,都收敛于方程x=(x)在区间I上的唯一根。,实际上，由连续性可知,存在L0，0，使对任何xI=-，+都有|(x)| L1.,而且，对任何xI=-，+，都有,|(x)-|=|(x)-()|=|()(x-)|L|x-|,即(x)I=-，+。,由定理4-1可见，结论成立。,这时的迭代方法称为局部收敛的。,定义4.4 设迭代序列xk收敛于,记误差ek=xk-,如果存在正实数p和非零常数C, 使得,或,|xk+1-|C|xk-|p , k1,则称序列xk是p阶收敛的, 称p是收敛阶,C是渐近误差常数.,=1称为线性收敛;p1称超线性收敛;p=2称平方收敛.,设(x)充分光滑, 由于,|ek+1|=|xk+1-|=|(xk)-()|=|(k)|ek|,所以,当()0时,有,于是,此时,迭代法是m阶收敛的.,所以,当()0时,简单迭代法只具有线性收敛.,设()=()=(m-1)()=0,但(m)()0, 由于,|ek+1|=|xk+1-|=|(xk)-()|,所以,下面介绍Aitken加速算法，此方法可对线性收敛的简单迭代法起到加速作用，而且可应用于其它数值方法中。,假设 (1)(2)，则有,由于,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),取x0= /2,计算结果如下,Newton迭代法是求方程根的重要方法之一,其最大优点是在方程的单根附近具有平方收敛,而且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-xk)=0,设(xk)0, 其解为,迭代格式(4.4)称为 Newton迭代法.,x,y,o,x0,y=(x),x1,x2,直线 y=(x0)+(x0)(x-x0),就是 y-(x0)=(x0)(x-x0),Newton迭代法也叫切线法.,Newton迭代法相当于取迭代函数,3.2 Newton迭代法的收敛性,的简单迭代法. 因为,如果是(x)=0的单根, 即()=0, 但()0, 则有()=0, 从而可知Newton迭代法在根附近是收敛的.,因为,所以,于是有,可见, 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-|2m1/M2 时,Newton迭代法是收敛的.,设(x)在单根附近具有二阶连续导数, 则对充分接近的初值x0,Newton迭代法产生的序列xk收敛于, 并且,定理4.6,取x0=0.5,计算结果如下:,例5 用Newton迭代法求方程xex-1=0在0.5附近的根,精度要求=10-5.,解 Newton迭代格式为,的近似值,要求=10-5.,从结果可见 ,Newton迭代法迭代3次已获得精确到小数点后五位的近似解,迭代4次已获得精确到小数点后八位的近似解.与例3比较可见Newton迭代法收敛的确实快.,例6 用Newton迭代法求,解 对方程x2-3=0应用Newton迭代法：,取x0=1.7，计算得：,3.3 Newton迭代法的变形,1. 简化Newton迭代法,所以取x3=1.732050808,为了简化计算(xk),采用迭代格式,称为简化Newton迭代法.,o,x,y,y=(x),x0,x1,x2,x3,在区间I=-,+上,取M与(x)同号,且M1/2max|(x)|,时,简化Newton迭代法对x0I收敛.通常取M=(x0).,简化Newton迭代法一般只具有线性收敛.,2.割线法,因为,o,x,y,y=(x),x0,x1,x2,x3,为了简化计算(xk),采用迭代格式,称为割线法.,若(x)在根附近二次连续可微,且()0,可以证明割线法是收敛的,且有,割线法收敛的阶为,3.计算重根的Newton迭代法,称是方程(x)=0的m重根,是指(x)=(x-)m h(x),其中h(x)在x=处连续且h()0,若h(x)在处充分可微,则 ()=()=(m-1)()=0,(m)()0,由于,可见,恰是方程,的单根.应用Newton迭代法可得:,称之为带参数m的Newton迭代法, 它是求方程(x)=0m重根的具有平方收敛的迭代法.,再看函数:,可见,恰是方程u(x)=0的单根, 应用Newton迭代法有,这是求方程(x)=0重根的具有平方收敛的迭代法,而且不需知道根的重数.,例7 利用Newton迭代法求方程 (x)=x4-8.6x3-35.51x2+464.4x-998.46=0的正实根.,o,x,y,2,4,6,8,10,y=f(x),解 y=(x)的图形为,可见,方程在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,然而若用一般的Newton迭代法(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,课间休息,