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

第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.0abyxy=(x)记a0=a,b0=b,计算,2000bax若|(x0)|,则取x0;否则,若(a0)(x0)0,取a1=a0,b1=x0;若(a0)(x0)0,取a1=x0,b1=b0而且有根区间[a1,b1]长度是有根区间[a0,b0]长度的一半,x0再对有根区间[a1,b1]重复上面运算,即:计算,2111bax若|(x1)|,则取x1;否则,若(a1)(x1)0,取a2=a1,b2=x1;若(a1)(x1)0,取a2=x1,b2=b1,得到新的有根区间[a2,b2].x1而且有根区间[a2,b2]长度是有根区间[a1,b1]长度的一半.一直进行下去,直到求出有根区间[ak,bk].或者有|(xk)|,或者有此时,再计算.2kkkbax11002112222kkkkkkkababababx可见,k趋向无穷大时,xk收敛于.而且,若要|xk-|,只要12kab1log2abk或者此时可取近似根xk.在计算过程中,若出现|(xk)|1,或bk-ak2.则可取xk作为方程(x)=0的近似根,终止运算.例1用二分法求x3+4x-7=0在区间[1,2]内根的近似值,并估计误差.解这里(x)=x3+4x-7，(1)(2)=-180,而且(x)=3x2+40,所以(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作为方程根的近似值,且有00049.02254882813.1255859375.12||101010abx只需k5ln210-115.61.即需取x16.如果取精度=10-5,则要使51110212||kkkabx二分法要求函数在区间[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]内的根.例2332xx,建立迭代格式,2,1,0,3231kxxkk如果取初值x0=1.9,计算得kxkkxk0123451.91.894536471.893521141.893332331.893297221.89329069678910…1.893289471.893289251.893289211.893289201.89328920……由计算结果有，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产生的序列{xk}[a,b],即(x)的值域落在定义域内.另外,从几何上看:xoyy=xy=(x)x0x1x2xoyy=xy=(x)x0x1x2xoyy=xy=(x)x0x1x2xoyy=xy=(x)x0x1x2x4x31.a(x)b,x[a,b];2.|(x)|L1,x[a,b]定理4.1设迭代函数(x)C1[a,b],且满足则迭代格式xk+1=(xk),k=0,1,2,…,x0[a,b]都收敛于方程x=(x)在区间[a,b]的唯一根，且11kkkxxLLx011xxLLxkkLxxLkln)1(ln01可见,|xk-xk-1|充分小可保证|xk-|充分小,而且对任一0,要使|xk-|,只要证记(x)=(x)-x,则(a)=(a)-a0,(b)=(b)-b0,由(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-|01111111xxLLxxLLxxLxkkkkkk求方程xex-1=0在0.5附近的根,精度要求=10-3.解可以验证方程xex-1=0在区间[0.5,0.6]内仅有一个根.例3改写方程为x=e-x,建立迭代格式,2,1,0,1kexkxk由于(x)=e-x,在[0.5,0.6]上有|(x)|e-0.50.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.002030.001150.00065所以,取近似根x10=0.56691满足精度要求.如果精度要求为=10-5,则由LxxLkln)1(ln0195.196.0ln10653.0104.0ln5可知,需要迭代20次.实际上,方程在区间[0.55,0.6]上有唯一根，而在区间[0.55,0.6]上有|(x)|e-0.550.581。若取L=0.58，则有注意：这里迭代次数20是充分的但不是必要的。LxxLkln)1(ln0150.4210lnln0.5818.60.10653可知,需要迭代19次.推论若=(),(x)在附近具有一阶连续导数,且|()|1，则存在0，当x0I=[-，+]时，迭代格式xk+1=(xk),k=0,1,2,…都收敛于方程x=(x)在区间I上的唯一根。实际上，由连续性可知,存在L0，0，使对任何xI=[-，+]都有|(x)|L1.而且，对任何xI=[-，+]，都有|(x)-|=|(x)-()|=|()(x-)|L|x-|即(x)I=[-，+]。由定理4-1可见，结论成立。这时的迭代方法称为局部收敛的。定义4.4设迭代序列xk收敛于,记误差ek=xk-,如果存在正实数p和非零常数C,使得或Ceepkkk1lim|xk+1-|C|xk-|p,k1则称序列xk是p阶收敛的,称p是收敛阶,C是渐近误差常数.p=1称为线性收敛;p1称超线性收敛;p=2称平方收敛.设(x)充分光滑,由于|ek+1|=|xk+1-|=|(xk)-()|=|(k)||ek|所以,当()0时,有0|)(|)(limlim1kkkkkee于是此时,迭代法是m阶收敛的.所以,当()0时,简单迭代法只具有线性收敛.设()=()=…=(m-1)()=0,但(m)()0,由于|ek+1|=|xk+1-|=|(xk)-()|mkkmem)(!1)(0|)(|!1)(!1limlim)()(1mkmkmkkkmmee所以mkkmmkmkkkxmxmxxx))((!1))(()!1(1))((21))(()()()(1)1(2下面介绍Aitken加速算法，此方法可对线性收敛的简单迭代法起到加速作用，而且可应用于其它数值方法中。假设(1)(2)，则有由于xk+1-=(1)(xk-)xk+2-=(2)(xk+1-)121kkkkxxxx即(xk+1-)2(xk-)(xk+2-)xk+12-2xk+1+2xkxk+2-(xk+xk+2)+2解得kkkkkkxxxxxx122122kkkkkkxxxxxx12212)(要比序列{xk}更快地收敛于,可构造如下的Aitken加速算法:则,序列注意,如果第k步发生zk-2yk+xk=0,就终止计算,取xk.如果记kkkkkkkxxxxxxx12212)(ˆkxˆ,2,1,0,2)(21kxyzxyxxkkkkkkk)(kkxy)(kkyz例4分别用简单迭代法和Aitken加速算法求方程x=1.6+0.99cosx在x0=/2附近的根.(=1.585471802)取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.00000078Newton迭代法是求方程根的重要方法之一,其最大优点是在方程的单根附近具有平方收敛,而且Newton迭代法还可用来求方程的重根、复根及非线性方程组.§3Newton迭代法§3.1Newton迭代公式设(x)在有根区间[a,b]上二阶连续可微,x0是根的某个近似值,因为200000)(2)())(()()(xxfxxxfxfxf取(x)(x0)+(x0)(x-x0),方程(x)=0近似为(x0)+(x0)(x-x0)=0若(x0)0,其解