數(shù)值計(jì)算方法2

1、第二章 非線性方程的數(shù)值解法 2.1 二分法 2.2 一般迭代法 2.3 牛頓迭代法 2.4 弦截法 （1）確定初始含根區(qū)間 數(shù)值計(jì)算方法主要分為兩大類。第一類是區(qū)間收縮法區(qū)間收縮法。 0)(:xf求解問題（2）收縮含根區(qū)間第二類是迭代法迭代法。 （1）選定根的初始近似值（2）按某種原則生成收斂于根的近似點(diǎn)列2.1 二分法二分法 基本假設(shè) : 2.1.1 二分法的計(jì)算步驟二分法的計(jì)算步驟 常用終止原則為: 0)()()(,bfafxfba連續(xù)且上在閉區(qū)間kkkkbaxab21,2取時(shí)終止計(jì)算當(dāng)計(jì)算到2.1.2 二分法的收斂性與事前誤差估計(jì)二分法的收斂性與事前誤差估計(jì) 時(shí)因?yàn)閗abababkkk

2、kk0212111所以，二分法總是收斂的 )(21)(21|),(21,1*ababxxbaxkkkkk我們得由進(jìn)一步數(shù)為預(yù)先估計(jì)出所需迭代步故對(duì)給定的精度要求,|* xx2lglgabK2lglg,10mabKm時(shí)特別當(dāng)例例 2.1 試用二分法求 052)(3xxxf的一個(gè)正根，使誤差小于10-3,16)3(, 1)2(6)1 (,5)0(ffff因?yàn)楣士扇〕跏紖^(qū)間 3 , 2,00ba即為所求近似值這時(shí)9921997. 92lg323lgabxK解解2.1.3 二分法評(píng)述二分法評(píng)述優(yōu)點(diǎn)優(yōu)點(diǎn)：簡(jiǎn)單可靠，易于編程實(shí)現(xiàn)，它對(duì)函數(shù)要求低，適 用于的奇數(shù)重根情形。缺點(diǎn)：不能直接用于求偶重根，不能用于

3、求復(fù)根，也難 以向方程組推廣使用，收斂速度慢。2.2 一般迭代法一般迭代法) 22(0)(xf對(duì)迭代法的算法思想為： (1) 把（2-2）等價(jià)變換為如下形式 ) 22()(xgx的不動(dòng)點(diǎn)稱為從而)(,)(*xgxxgx (2) 建立迭代格式 )32()(1kkxgx或更一般地建立迭代格式 ) 32() 1(),(11mxxxgxmkkkk (3) 適當(dāng)選取初始值，遞推計(jì)算出所需的解。 2.2.1 迭代法的算法思想迭代法的算法思想 2.2.2 迭代法的收斂性迭代法的收斂性則稱在 內(nèi) 李普希茲連續(xù)李普希茲連續(xù)。 )(xg 定義定義2.1 設(shè)在某個(gè)區(qū)間 內(nèi)，函數(shù) 滿足下述李普希茲條件李普希茲條件：

4、)10,(| )()(|為常數(shù)LyxyxLygxg則 在 內(nèi)李普希茲連續(xù)。 )(xg命題命題2.1 若 在閉區(qū)間 內(nèi)連續(xù)且 )(xg)(1| )(|xLxg)()()()(yxgygxg|)(| )()(|yxLyxgygxg命題得證。 證證 定理定理2.1 設(shè) x*= g(x*), g(x) 在閉區(qū)間 ： 內(nèi)李普希茲連續(xù)，則對(duì)任何初值 由迭代格式 xk+1= g(xk) 計(jì)算得到的解序列 收斂于 x* ( 這時(shí)我們稱迭代格式 xk+1= g(xk)在 x* 的鄰域 上局部收斂局部收斂）。|xx0 x kx（1）首先用數(shù)學(xué)歸納法證明： , 2 , 1 , 0kxk由假設(shè)知 0 x又設(shè) ，則 k

5、x|kxx| )()(|*1kkkkxxxxLxgxgxx所以1kx即綜上，由歸納法原理知，結(jié)論成立。 證證)(0|01時(shí)kxxLxxLxxkkk因此， ，定理得證。 xxkklim 反設(shè)存在 )(, 0)(,xgxxfxxx即且| )()(|0 xxxxLxgxgxx則矛盾。所以結(jié)論成立。 2) 迭代函數(shù)在 x* 附近李普希茲連續(xù)從而收斂的迭代格式統(tǒng)稱為皮卡（皮卡（Picard）迭代）迭代 (2) 由（1）的結(jié)論和 g(x) 在 內(nèi)李普希茲連續(xù)的假設(shè)，可遞推得到 注注 1) g(x) 在內(nèi)李普希茲連續(xù)的條件保證了x* 為 f (x)=0 在 內(nèi)的唯一根。 證證推論推論 設(shè) x*= g(x*)

6、 ， 若 g(x) 在 x* 附近連續(xù)可微且 ，則迭代格式 xk+1= g(xk) 在 x* 附近局部收斂。 1| )(|* xg 注注 由于 x* 事先未知，故實(shí)際應(yīng)用時(shí)，代之以近似判則 。 但需注意，這實(shí)際上是假設(shè)了x0充分接近 x* ，若 x0 離 x* 較遠(yuǎn)，迭代格式可能不收斂。 1| )(|0 xg 定理定理2.2 （非局部收斂定理）（非局部收斂定理）如果 在 上連續(xù)可微且以下條件滿足： )(xg,ba,)(, ,) 1 (baxgbax則若1)(, ,)2(Lxgbax對(duì).)(, ,*1xxxgxbaxkkk收斂于的解序列對(duì)那么注注 雖然定理2.1的條件是充分條件，但其條件并不很強(qiáng)

7、，實(shí)際上，我們易證如下命題。 命題命題2.2 若在區(qū)間 內(nèi) ，則對(duì)任何 ，迭代格式 不收斂。 ,ba1 xg)(1kkxgx,0bax 2.2.3 迭代法的誤差估計(jì)迭代法的誤差估計(jì) )42(), 2 , 1(|11kxxLxxkkkk), 2 , 1(|1211sxxLxxLxxkkssksksksk故對(duì)正整數(shù) p，有 | )1 (1| )(|1111211kkpkkppkkpkpkpkpkkpkxxLLLxxLLLxxxxxxxx取極限得令p)52()(1|1kkkxxLLxx|1|01xxLLxxkk1ln1|ln|ln|101LxxLK|11kkxxLL （2）事后誤差估計(jì)）事后誤差估計(jì)

8、 由此，對(duì)給定的精度 可進(jìn)行 |*xx(1) 事前誤差估計(jì)事前誤差估計(jì)簡(jiǎn)單地代之以|1kkxx)2/1(|1nkkaaxx或 例例 2.2 試建立收斂的迭代格式求解在區(qū)間(2,3)內(nèi)滿足精度要求 的根。 052)(3xxxf810 首先可簡(jiǎn)單的把 等價(jià)化為 253xx0523 xx由此建立迭代格式 25)(),(31xxgxgxkk1| )(|3 , 2,23)(2xgxxg內(nèi)在知由所以該迭代格式在內(nèi)不收斂，不可取。 為建立收斂的迭代格式，我們把 等價(jià)化為0523 xx352 xx 從而建立迭代格式3152)(, )(xxgxgxkk解解易知在 x 0時(shí) g(x) 單調(diào)增，故有 2 g(2)

9、g(x) g(3) 31392)2()(00)52(132)(332gxgxxg在內(nèi)單調(diào)減得又由故由定理2.2得：任取x0 2,3，該迭代格式收斂。取 x0=2 計(jì)算，結(jié)果見表 2-2（書17頁）。 2.2.4 迭代法的收斂速度與加速收斂技巧迭代法的收斂速度與加速收斂技巧 則稱該迭代格式是p 階收斂階收斂的。特別地，p=1時(shí)稱為線線性收斂性收斂， 1p2 時(shí)稱為超線性收斂超線性收斂，p=2 時(shí)稱為平方平方收斂收斂。 )112()0(1為常數(shù)CCeepkk 定義定義2.2 設(shè)迭代格式 的解序列 收斂于 的根 ，如果迭代誤差 當(dāng) 時(shí)滿足漸近關(guān)系式)(1kkxgx kxxxekkk)(xgx *x

10、對(duì)于線性收斂的計(jì)算格式，可采用以下介紹的埃特肯（Aitken）加速技巧來提高收斂速度。 設(shè)序列 線性收斂于 ，即有 ，則近似地有 kxCeekkk1lim*x)()(1201xxCxxxxCxx 兩式相除得 xxxxxxxx102102)(0122122xxxxxxx解得 把埃特肯加速技巧應(yīng)用于單步迭代法 便構(gòu)成了Steffensen算法算法。 )(1kkxgx 據(jù)此，我們可取修正值 作為 的新近似值以提高精度。這一技巧便稱為埃特肯埃特肯加速技巧加速技巧。 012212222)(xxxxxxx*x 例例 2.3 試用Steffensen算法求解 在區(qū)間（2，3）內(nèi)滿足精度要求 的根。 052)

11、(3xxxf810 對(duì)例2.2 的迭代格式 取 用算法計(jì)算，結(jié)果見表 2-3 。 3152kkxx20 x解解 2.3 牛頓迭代法牛頓迭代法 2.3.1 牛頓迭代公式的構(gòu)造牛頓迭代公式的構(gòu)造 設(shè) f (x) 在其零點(diǎn) 附近連續(xù)可微，已知 為的第k次近似值，則 *xkx)()()()()()()(12xPxxxfxfxxOxxxfxfxfkkkkkkk取 的根作為 的第k+1次近似值 0)(1xPx1kx)122()()(1kkkkxfxfxx解得其迭代函數(shù)為 )132()()()(xfxfxxg牛頓迭代法牛頓迭代法幾何意義幾何意義：過點(diǎn) 作函數(shù) y= f (x) 的切線 l： )(,kkxfx

12、P)()(kkkxxxfxfy以切線 l 與 x 軸的交點(diǎn) 作為 的新近似值 1kx*x 2.3.2 牛頓迭代法的收斂性與收斂速度牛頓迭代法的收斂性與收斂速度 定理定理 2.3 給定 f (x)=0，如果在根 附近 f (x)二階連續(xù)，且 為 f (x)=0的單根，則牛頓迭代法在 附近至少是平方收斂的。 *x*x*x2)()()()(xfxfxfxg 對(duì)牛頓迭代法首先證明牛頓迭代法的收斂性： 而單根條件保證了 0)(xf0)(*xg因此由定理2.1知，牛頓迭代法局部收斂。 證證其次證明牛頓迭代法的收斂速度：之間與介于由kkkkkxxxxfxxxfxfxf )(21)()()(0整理得 212)

13、()()(21)()()(21)()(kkkkkkkkxxxffxxxxffxfxfxx )()(21)()(2121 xfxfxffeekkk所以 可見，當(dāng) 時(shí)，牛頓迭代法為平方收斂；當(dāng) 時(shí)，牛頓迭代法超平方收斂。 0)( xf0)( xf例例 2.4 試用牛頓迭代法求解 在區(qū)間 (2,3) 內(nèi)滿足精度要求 的根。 052)(3xxxf810相應(yīng)于該方程的牛頓迭代公式為 2352231kkkkkxxxxx取 x0 = 2 ，計(jì)算結(jié)果見表2-4。 解解牛頓迭代法評(píng)述牛頓迭代法評(píng)述 優(yōu)點(diǎn)優(yōu)點(diǎn)：是收斂速度比較快 缺點(diǎn)缺點(diǎn)：(1) 局部收斂，對(duì)初始值的要求比較高。為解決這一問題，可采用二分法來提供足

14、夠“好”的近似值作為迭代初值，或通過增加“下山”限制來放寬對(duì)初值的要求，即把牛頓迭代法修改為 01)()(xxfxfxxkkkkk其中 的選取使得 （這稱為“下山”限制）。該方法稱為牛頓下山法牛頓下山法。 )()(1kkxfxfk （2）當(dāng) 為 重根時(shí)，牛頓迭代法僅僅線性收斂。 )2(0)(mxf的*x （3）由于涉及 的計(jì)算，導(dǎo)致了對(duì)函數(shù)的要求高，并增加了每一迭代步的計(jì)算量，這在一定程度上減弱了該迭代法收斂快的優(yōu)越性，而且在向非線性方程組推廣時(shí)，使計(jì)算量和對(duì)函數(shù)的要求大大增加。因此，人們致力于研究建立牛頓迭代法的修改格式以回避對(duì)函數(shù)導(dǎo)數(shù)值的計(jì)算。本章僅對(duì)非線性方程介紹一種較為有效的修改算法弦

15、截法。 )(xf 2.4 2.4 弦截法弦截法 , 1 , 0,)()()()(10111kxxxxxfxfxfxxkkkkkkk 計(jì)算思想是：若已知 x* 的兩個(gè)近似值 xk 和 xk-1，則以 f (x) 在 xk 與 xk-1 之間的平均變化率(差商) 近似代替 ，據(jù)此把牛頓迭代法修改為 11)()(kkkkxxxfxf)(kxf 幾何意義幾何意義是以過 和 兩點(diǎn)做曲線 的弦線 l ： )(,kkxfxP)(,11kkxfxQ)(xfy )()()()(11kkkkkkxxxxxfxfxfy以 l 與 x 軸的交點(diǎn) 作為的新近似值（如圖2-3所示） 1kx弦截法弦截法 定理定理 2.4

16、設(shè) f (x) 在其零點(diǎn) x* 的鄰域 內(nèi)二階連續(xù)，且對(duì) ，則對(duì) ，相應(yīng)的弦截法是 階收斂的。 |xxx0)(,xfx10, xx618. 1251p 該定理說明弦截法是超線性收斂的算法，也是局部收斂的方法，其迭代初始值亦可用二分法提供。 例例 2.5 試用弦截法求解 在區(qū)間內(nèi)滿足精度要求 的根。 052)(3xxxf810相應(yīng)于該方程的弦截法公式為 )()52()52(521131331kkkkkkkkkkxxxxxxxxxx取 計(jì)算，結(jié)果見表2-5。 3,210 xx解解 例例 2.6 試討論函數(shù)方程 的根的分布情況， 分別用牛頓迭代法和弦截法求其最小正根， 使誤差小于 ，并比較它們的工作量 02s