數(shù)值分析第八章非線性方程解法

其中f(x)

為非線性函數(shù).如求

f(x)=0的根第八章非線性方程求根1例若干年以前,美國原子能委員會(huì)準(zhǔn)備將濃縮的放射性廢料裝入密封的圓桶內(nèi)沉至海底.但是,當(dāng)時(shí)一些科學(xué)家與生態(tài)學(xué)家都反對這種作法.科學(xué)家用實(shí)驗(yàn)測定出圓桶能夠承受的最大撞擊速度為v=12.2m/s,如果圓桶到達(dá)海底時(shí)的速度超過這個(gè)速度,將會(huì)因撞擊海底而破裂,從而引起嚴(yán)重的核污染.然而原子能委員會(huì)卻認(rèn)為不存在這種可能性.根據(jù)圓桶的質(zhì)量,體積以及海水的密度與海底的深度,通過建立數(shù)學(xué)模型得知圓桶到達(dá)海底時(shí)的速度v(m/s)滿足如下方程:那么圓桶到達(dá)海底時(shí)的速度究竟會(huì)不會(huì)超過12.2m/s呢?2§1對分區(qū)間法(二分法)原理:若f

C[a,b]，且f(a)·f(b)<0，則f在(a,b)上必有一根.[a,b]

稱為f(x)=0的有根區(qū)間.下文中,設(shè)x*是方程f(x)=0的根.3取不妨設(shè)f(a)<0,f(b)>0.①若則②若?、廴羧∫宰鳛樾碌挠懈鶇^(qū)間繼續(xù)迭代,得有根區(qū)間序列取為的第n個(gè)近似值.4abx0x1ab停機(jī)準(zhǔn)則或不能保證

x

的精度x*2xx*5誤差分析：第0步產(chǎn)生的有誤差第k步產(chǎn)生的xk

有誤差對于給定的精度,可估計(jì)二分法所需的步數(shù)k：①簡單;②對f(x)

要求不高(只要連續(xù)即可).①無法求復(fù)根及偶重根②收斂慢6例1試用二分法求方程的唯一實(shí)根,要求誤差不超過解[1,2]為有根區(qū)間;f(x)單調(diào)增加,方程有唯一根.對分區(qū)間次數(shù)取n=14.7計(jì)算結(jié)果如下表:0121.51.6..1.752.8..2...............121.59448251.59472661.59460460.0007...131.59448251.59460461.59454360.0003...141.59454361.59460461.59457411.5211.51.751.6250.54..8f(x)=0x=g(x)等價(jià)變換f(x)的根g(x)的不動(dòng)點(diǎn)思路從一個(gè)初值x0

出發(fā),計(jì)算x1=g(x0),x2=g(x1),…,xk+1=g(xk),…若收斂,即存在x*使得且g連續(xù),則由可知x*=g(x*),即x*是g的不動(dòng)點(diǎn)，也就是f的根.§2迭代法9例2用簡單迭代法求方程的根,要求精確到0.510-6.解法一：迭代格式:取初值計(jì)算得顯然此迭代序列發(fā)散.10例2用簡單迭代法求方程的根,要求精確到0.510-6.解法二：迭代格式:初值故計(jì)算得

11例2用簡單迭代法求方程的根,要求精確到0.510-6.解法三：迭代格式:初值計(jì)算得12例2用簡單迭代法求方程的根,要求精確到0.510-6.解法四：迭代格式:初值計(jì)算得13上例表明,對同一方程可構(gòu)造不同的迭代格式，產(chǎn)生的迭代序列收斂性也不同.

迭代法的收斂性與什么有關(guān)？

怎樣構(gòu)造具有收斂性的迭代法？14xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p115定理考慮方程x=g(x),g(x)C[a,b],若(I)當(dāng)x[a,b]時(shí)，g(x)[a,b]；(II)0L<1使得|g(x)|L

對x[a,b]成立.則任取x0[a,b]，由xk+1=g(xk)得到的序列收斂于g(x)在[a,b]上的唯一不動(dòng)點(diǎn).并且有誤差估計(jì)式：(k=1,2,…)且存在極限k16證明：①g(x)在[a,b]上存在不動(dòng)點(diǎn)？令有根②不動(dòng)點(diǎn)唯一？反證：若不然，設(shè)還有，則在和之間而17③當(dāng)k

時(shí)，

xk收斂到x*？④可用來控制收斂精度18⑤⑥L越收斂越快小19例2用簡單迭代法求方程的根,要求精確到六位小數(shù).解法一：迭代函數(shù)解法二：迭代函數(shù)對故迭代法收斂.20局部收斂定理如果函數(shù)g(x)在x*的某鄰域B*={x||xx*|

*}內(nèi)連續(xù)可微，且x*=g(x*)，|g(x*)|<1，則存在正數(shù)，

*，由x0B開始的迭代收斂.該定理表明，若|g(x*)|<1，只要初值x0選得離x*足夠近，迭代法一定收斂.21xyy=g(x)x*y=x

Aitken加速：x0P(x0,x1)x1x2P(x1,x2)一般地，有：比收斂得快.

Steffensen加速：22取迭代函數(shù)按公式計(jì)算得n01.51.63265311.579085811.59449471.59458951.594551021.59456211.59456211.5945621例用Steffensen加速方法求的根,取x0=1.5,=106.解一.23例用Steffensen加速方法求的根,取x0=1.5,=106.解二.取迭代函數(shù)按公式計(jì)算得n01.5-0.125-21.37695311.63454082.346989118.74493721.60218081.73675934.342997031.59485311.59998351.695691141.59456251.59457011.594710651.594562124

收斂速度定義設(shè)數(shù)列收斂于如果存在正數(shù)r和a,使得則稱數(shù)列是r階收斂的，或稱的收斂階為r.r=1,稱數(shù)列為線性收斂的；r>1,稱數(shù)列為超線性收斂的；r=2,稱數(shù)列為平方收斂的.收斂階r的大小刻劃了數(shù)列的收斂速度，r越大，收斂越快.25定理設(shè)迭代函數(shù)g(x)在x*鄰近有r階連續(xù)導(dǎo)數(shù)，且則迭代公式xk+1=g(xk)所產(chǎn)生的迭代數(shù)列是r階收斂的.證明：0故26Aitken加速有超線性收斂.Steffensen加速有r=2，條件是平方收斂.對于簡單迭代法,若

則有

線性收斂.27Newton-RaphsonMethod28原理：將非線性方程線性化(Taylor展開)設(shè)xn是

x*的第n個(gè)近似值,將f(x)在xn做Taylor展開線性

/*linear*/xyx*xn只要f

C1，每一步迭代都有f(xn)0，而且若則

x*就是f的根.令xn+1§3牛頓法29例用牛頓法求方程的根,取x0=1.5.解：迭代公式為代入初值得：可見牛頓法收斂很快.30定理（收斂的充分條件）設(shè)f

C2[a,b]，若(1)f(a)f(b)<0；(2)在整個(gè)[a,b]上f不變號且

f(x)0；(3)選取x0

[a,b]使得f(x0)f(x0)>0；則Newton’sMethod產(chǎn)生的序列{xk}收斂到f(x)在[a,b]的唯一根.有根根唯一產(chǎn)生的序列單調(diào)有界，保證收斂.31（局部收斂性）設(shè)f

C2[a,b]，若x*

為f(x)在[a,b]上的根，且f(x*)0，則存在x*的鄰域使得任取初值Newton’sMethod產(chǎn)生的序列{xk}收斂到x*，且滿足定理證明：Newton’sMethod事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代其中則收斂32由Taylor展開：只要f(x*)0,則令可得結(jié)論.在單根附近收斂快再證：33注：Newton’sMethod收斂性依賴于x0的選取.x*x0x0x034當(dāng)x*是方程的m重根時(shí),牛頓迭代法是線性收斂的,且則稱x*為方程f(x)=0的m重根.設(shè)35求重根的改進(jìn)Newton法此時(shí)迭代函數(shù)則迭代法具有2階收斂，但要知道x*的重?cái)?shù)m.其中m為f(x)=0的根的重?cái)?shù).36構(gòu)造求重根的另一迭代法則故x*是(x)=0的單根.對它用牛頓法，其迭代函數(shù)為從而可構(gòu)造迭代法它是二階收斂的.37例方程的根是二重根，用上述三種方法求根.解先求出三種方法的迭代公式(3)方法3取初值x0=1.5,計(jì)算結(jié)果見下表(1)牛頓