數(shù)值計算方法2

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

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

3、求復根，也難 以向方程組推廣使用，收斂速度慢。2.2 一般迭代法一般迭代法) 22(0)(xf對迭代法的算法思想為： (1) 把（2-2）等價變換為如下形式 ) 22()(xgx的不動點稱為從而)(,)(*xgxxgx (2) 建立迭代格式 )32()(1kkxgx或更一般地建立迭代格式 ) 32() 1(),(11mxxxgxmkkkk (3) 適當選取初始值，遞推計算出所需的解。 2.2.1 迭代法的算法思想迭代法的算法思想 2.2.2 迭代法的收斂性迭代法的收斂性則稱在 內(nèi) 李普希茲連續(xù)李普希茲連續(xù)。 )(xg 定義定義2.1 設在某個區(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 設 x*= g(x*), g(x) 在閉區(qū)間 ： 內(nèi)李普希茲連續(xù)，則對任何初值 由迭代格式 xk+1= g(xk) 計算得到的解序列 收斂于 x* ( 這時我們稱迭代格式 xk+1= g(xk)在 x* 的鄰域 上局部收斂局部收斂）。|xx0 x kx（1）首先用數(shù)學歸納法證明： , 2 , 1 , 0kxk由假設知 0 x又設 ，則 k

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

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

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

8、 由此，對給定的精度 可進行 |*xx(1) 事前誤差估計事前誤差估計簡單地代之以|1kkxx)2/1(|1nkkaaxx或 例例 2.2 試建立收斂的迭代格式求解在區(qū)間(2,3)內(nèi)滿足精度要求 的根。 052)(3xxxf810 首先可簡單的把 等價化為 253xx0523 xx由此建立迭代格式 25)(),(31xxgxgxkk1| )(|3 , 2,23)(2xgxxg內(nèi)在知由所以該迭代格式在內(nèi)不收斂，不可取。 為建立收斂的迭代格式，我們把 等價化為0523 xx352 xx 從而建立迭代格式3152)(, )(xxgxgxkk解解易知在 x 0時 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 計算，結(jié)果見表 2-2（書17頁）。 2.2.4 迭代法的收斂速度與加速收斂技巧迭代法的收斂速度與加速收斂技巧 則稱該迭代格式是p 階收斂階收斂的。特別地，p=1時稱為線線性收斂性收斂， 1p2 時稱為超線性收斂超線性收斂，p=2 時稱為平方平方收斂收斂。 )112()0(1為常數(shù)CCeepkk 定義定義2.2 設迭代格式 的解序列 收斂于 的根 ，如果迭代誤差 當 時滿足漸近關系式)(1kkxgx kxxxekkk)(xgx *x

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

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

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

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

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

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

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