數值計算方法【非線性方程】（2/7）

目錄

方程的根

二分法

疊代法

疊代原理

疊代法的收斂性

 疊代過程的收斂速度

疊代的加速

權重法

埃特金加速法和斯蒂芬森加速法

牛頓疊代法

牛頓疊代法的收斂情況

牛頓下山法

重根修正

雙點弦法

方程的根

若函數為代數多項式，則稱其為代數方程，否則為超越方程。超越方程包括指數、對數、三角方程等。使函數f(x)值為0的x的值稱為方程的根或解，也稱x為函數f(x)的零點或根。若函數f(x)可分解為

，則稱

為方程的m重根。

重根還有一個判斷條件：

即直到對x*第m次求導不為0以前，m-1階導均為0。

設函數f(x)在區間[a,b]上連續，且f(a)f(b)<0，則方程f(x)=0在區間[a,b]上至少有一個根。

設函數f(x)在區間[a,b]上是單調連續函數，且f(a)f(b)<0，則方程在區間内有且僅有一個根。

二分法

根據上行粗體字的原理，用計算機進行二分法的思想和過程如下：

1. 找出根的存在區間[a,b]，給出允許誤差

   

   。
2. 計算中值

   

   。
3. 若

   

   ，則根位于

   

   中，以

   

   代替a。否則

   

   代替b。
4. 若b-a<

   

   ，計算終止，輸出x=

   

   ，否則轉向第二步。

 可見，每進行一次區間二分，區間長度減小一半。二分k次後的有根區間

的長度為

，取

中點為根的近似值，此時誤差為

,滿足允許誤差即可停止計算。

二分法的優點是簡單，局限性是隻能求單根，不能求重根。

二分法的前提是函數f(x)在區間[a,b]上是單調連續函數。

疊代法

疊代原理

疊代是将方程f(x)=0轉化為x=g(x)，利用y=x自變量和因變量相等的特點，在自變量和因變量也就是x和g(x)之間來回切換，進而得到收斂根的數值計算方法。

形象地表示，圖像如下：

文字分析一個圖a，其它請自行分析。首先我取一個x0作為初值，畫豎直線得到g(x)的值，由疊代公式y=x=g(x)，可以畫水準線得到因變量y的值，而y又等于自變量x的值，可以畫豎直線再次得到g(x)的值，重複這個步驟，每次得到x的值，都更加趨近于y=x和g(x)的交點的橫坐标，而這個橫坐标就是方程的根。

來看一個例子。求解方程： f(x) =x^3-x-1=0  在區間 （1，1.5）内的根。

将方程改寫為

。取初值x0=1.5，代入得到

。繼續疊代得到

，

……繼續下去。

取六位有效數字時，

，滿足了x=g(x)這個式子，即認為這是方程的根。

如果疊代值有極限，則稱疊代收斂。如上面這道題的解法。如果上面這道題的疊代方程改為

,它就不收斂。它的了解與誤差的逐級放大異曲同工（參考上一篇博文）。

疊代法的收斂性

初值

與經過疊代後得到的

處于同一區間内，則稱疊代格式映内。

g(x)在某區間上有連續一階導數，對區間的所有x值g(x)映内，且存在0<L<1，使得所有x有：

，則x=g(x)在區間上有唯一解。對任意初值疊代過程都收斂。L值越小，收斂得越快。而對任意初值，

時，疊代一定發散。

證明省略，如果有必要，我會把所有的證明統一放在一個文章中發表出來。

雖然不證明，但是可以了解一下。g'(x)表示g(x)的變化率，當導數大于1的時候，變化的速率越來越快，類似二次函數抛物線；當導數小于1的時候，變化速率越來越慢，類似函數

。導數小于1的時候顯然更容易收斂，而這個數值比1小的程度越大，變化就越緩慢，會更快抵達極限值。

誤差估計式:

證明并不複雜，用到絕對值三角不等式，同樣省略證明。

對于上述定理，映内性不易驗證，且對較大範圍内的有根區間條件不一定成立。是以可以減弱條件，使其在根的鄰域内成立，即局部收斂性。

g(x)在根x*的鄰域上有連續一階導數，且

，則疊代過程局部收斂。

 疊代過程的收斂速度

定義：設疊代過程

收斂于x*，疊代誤差

，

，則稱

是p階收斂的。

和重根類似，如果有：

疊代的加速

權重法

權重法是最常用的加速方法。疊代到

後用疊代公式校正一次得

，由于

比

更加精确，是以給它更多權重。改進後的疊代公式為

埃特金加速法和斯蒂芬森加速法

埃特金加速法和斯蒂芬森加速法的原理證明不寫出來，感興趣的可以自己查一查，這兩個加速方法用到了二階差分和三個臨近點，不是很常用。

其中

是

的一階差分，

是

的二階差分。

把不動點法和埃特金加速法結合起來就是斯蒂芬森疊代法。

牛頓疊代法

，

和前面疊代法相比，牛頓疊代規定了具體的疊代方程，且它的圖像了解不再是畫豎直水準線，而是用切線代替，這說明了牛頓疊代的收斂更快些。

牛頓疊代法的收斂情況

對牛頓疊代函數求導

，根據收斂條件可知，此導數的絕對值<1時，疊代收斂。這是充分條件，不是必要條件，不滿足時也可能收斂。

f(x*)=0,f'(x*)

0,f''(x)在x*的鄰域連續，則牛頓疊代法至少局部二階收斂，且有

牛頓下山法

牛頓疊代法的突出特點是收斂速度快，但缺點是每次要計算導數，計算量大。初值在單根x*附近時，牛頓疊代法具有平方收斂速度，如果初值偏離較遠，則牛頓疊代法可能發散或收斂很慢。牛頓下山法是擴大初值範圍的修正方法。為了防止初值的選取造成疊代發散或疊代值偏離，要求疊代過程對所選的初值能使函數值下降。即要滿足下山條件：

可以利用權重的方法。如前所述。

下山因子

的選擇是逐漸探索的，從

=1開始反複将

的值減半進行試算，一旦單調下降條件成立，則稱“下山成功”；反之，如果在上述過程中找不到使單調下降條件成立的下山因子

，則稱“下山失敗”，此時需要另選初值。

重根修正

牛頓疊代法具有平方收斂速度是指單根時的情況，當不是單根時，就沒有平方收斂速度。

當重根數已知時，牛頓疊代過程是線性收斂的。此時修正的牛頓疊代法為

仍然是平方收斂的，但這種修正方法需要預知重根數m的值。

當重根數未知時，省略過程得到疊代格式（不需要知道重根數，但複雜）

雙點弦法

又稱割線法。用割線代替牛頓疊代的切線，簡化運算。

用

代替牛頓疊代公式中的導數f'(x)，得到

雙點弦法的收斂速度僅稍慢于牛頓法，計算前必須提供兩個開始值

。

關于本小節的計算機實作方法和代碼，容我寫完以後想想再發。