第四章 解非线性方程的迭代法

第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].此时,再计算.2kkkbax或者有|(xk)|,或者有11002112222kkkkkkkababababx可见,k趋向无穷大时,xk收敛于.而且,若要|xk-|,只要12kab1log2abk或者此时可取近似根xk.在计算过程中,若出现|(xk)|1,或bk-ak2.则可取xk作为方程(x)=0的近似根,终止运算.例1用二分法求x3+4x-10=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.定义4.1设(x)为定义在区间I上的函数,且对任何xI,均有(x)I,则称(x)为I到自身上的映射.方程也可改写成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简单迭代法的收敛条件定义4.2设(x)为I到自身上的映射,且存在0L1,使对任何x1,x2I,有|(x2)-(x1)|L|x2-x1|,则称(x)为I上的压缩映射,L称为Lipschitz常数.若(x)为I上的压缩映射,则(x)在I上连续.定理4.2若(x)为I到自身上的映射,且(x)C1(I),|(x)|L1,则(x)为I上的压缩映射.证对任意x1,x2I,有|(x2)-(x1)|=|()||x2-x1|L|x2-x1|定义4.3若(x)为I到自身上的映射,且I满足,=(),则称为(x)的不动点.定理4.3若(x)为I上的压缩映射,则(x)在I上存在唯一的一个不动点,且对任何x0I,由迭代格式xk+1=(xk),k=0,1,2,…产生的序列{xk}收敛于(x)的不动点.定理4.1证不妨设I=[a,b],作函数(x)=(x)-x,由于xI时,(x)I,则(a)=(a)-a0,(b)=(b)-b0,由(x)的连续性,必存在I,使()=()-=0,即=(),就是(x)的不动点.若,I均为(x)的不动点,则有|-|=|()-()|L|-||-|所以只能=,即(x)在I上仅有一个不动点.对任意x0I,有x1=(x0)I,递推得{xk}I,设是(x)的不动点,则|xk+1-|=|(xk)-()|L|xk-|L2|xk-1-|…Lk+1|x0-|所以xk.若=(),而在I=[-,+]上(x)满足|(x)-()|L|x-|这里L1为Lipschitz常数,则当x0[-,+]时,有(1)由迭代xk+1=(xk)产生的迭代序列xkI;推论若(x)C1[a,b],且满足1.a(x)b,x[a,b];2.|(x)|L1,x[a,b].则迭代格式xk+1=(xk),k=0,1,2,…,x0[a,b]都收敛于方程x=(x)在区间[a,b]的唯一根.(3)是I上(x)的唯一不动点.;lim)2(kkx定理4.4实际上,由连续性知,存在0,使对任何xI=[-,+]都有|(x)|L1.§2.3简单迭代法的误差分析与收敛阶推论若=(),(x)在附近具有一阶连续导数,且|()|1,则存在0,当x0I=[-,+]时,有(1)由迭代xk+1=(xk)产生的迭代序列xkI;;lim)2(kkx(3)是I上(x)的唯一不动点.定理4.5若(x)为I上压缩映射,则x0I,由迭代xk+1=(xk),k=0,1,2,…产生的迭代序列xk满足:证|xk+1-xk|=|(xk)-(xk-1)|L|xk-xk-1||xk+1-|=|(xk)-()|L|xk-|11kkkxxLLx011xxLLxkk|xk+1-xk|=|(xk+1-)-(xk-)||xk-|-|xk+1-|(1-L)|xk-|01111111xxLLxxLLxxLxkkkkkk由误差估计式可见,对任一0,要使|xk-|,只要LxxLkln)1(ln01求方程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次.定义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)(则,序列注意,如果第k步发生zk-2yk+xk=0,就终止计算,取xk.如果记kkkkkkkxxxxxxx12212)(ˆkxˆ要比序列{xk}更快地收敛于,可构造如下的Aitken加速算法:,2,1,0,2)(21kxyzxyxxkkkkkkk)(kkxy)(kkyz例4分别用简单迭代法和Aitken加速算法求方程x=1.6+0.99cosx在x0=/2附近的根.(=1.585471802)取x0=/2,计算结果如下k简单迭