一個具有二階收斂速度的迭代法

吳江

摘要：Newton迭代法和弦截法是對非線性方程求根問題的常用方法。Newton迭代法需要計算一階導數值，具有二階收斂速度。弦截法只需要計算函數值，但它的收斂速度沒有Newton迭代法快。本文將給出一個不需要計算導數值且具有二階收斂速度的迭代法（新迭代法），并用數值實驗來驗證其有效性。

關鍵詞：迭代法；非線性方程；收斂速度

0引言

Newton迭代法具有二階收斂速度.具有收斂速度快且形式簡單等特點，具體有關Newton迭代法的內容可以參考文獻。Helley迭代和Chebyshev迭代具有三階收斂速度.并且它們只需要計算一階導數值。而弦截法可以避免計算一階導數值，而它是超線性收斂的，所以它的收斂速度沒有Newton迭代法快。具體有關弦截法的內容可以參考文獻。文獻考慮到牛頓迭代法需要計算函數的導數值，而有些函數的導數值計算復雜，于是提出了一種可以避免計算導數值并且具有二階收斂速度的迭代算法。本文從牛頓迭代法和文獻的迭代算法出發，構造一個簡單的迭代公式，該迭代法不必計算一階導數值，且與Newton迭代法一樣可以達到二階的收斂速度。

1新迭代法及證明

Newton迭代法是求解非線性方程最為經典的迭代法，許多專家和學者在構造新的迭代法時，都會以Newton迭代法為基礎。本文構造新的迭代法的依據是將Newton迭代法中用到的導數值用函數值的差商來替換，從而得到新的迭代法。Newton迭代公式為

從牛頓迭代公式可以看到.在迭代過程中.每一步迭代都需要計算函數值f（x）和導數值f（x），所以如果f（x）本身是較為復雜的函數，那么計算f（x）的計算也會相當復雜。于是文獻為了避免計算函數的導數值，提出了下面的迭代公式。

文獻迭代公式為其中A，B為任意實數。從該迭代公式可以看出，它在迭代過程中不涉及到f（x）的導數值，而該迭代法在實際的使用中，需要確定A，B的值，而文獻[5]在最后說明當A取1，B取0時計算效果較好。

考慮到文獻[5]迭代公式有待定參數，并且沒有一種方法可以確定最佳參數值，所以本考慮用不帶參數的來代替Newton迭代公式中的f（x）。這樣可以得到下面新的迭代公式。

本文新的迭代公式為

在迭代公式（1）中，只需要計算函數值，不需要計算導數值。

定理1方程f（x）=0的根為xo，函數f（x）在包含‰的某個開區間內有連續的二階導數，且廣（x）=0，則迭代公式（1）在此開區間至少以二階收斂速度收斂于xo。

證明設迭代誤差en=xn-xo.用泰勒公式將f（xn）在xo處展開，并且注意到.f（xo）=0，得

2數值實驗

下面將給出兩個非線性方程求根的數值實驗，來驗證新的迭代法的有效性。首先大致確定非線性方程實數根所在的區間范圍.然后在這個已確定的區間中，任取一個值作為迭代的初始值。輸出的控制條件設定為[Xk-k-1]≤0（10-15）。

例1

求方程f（x）=e3-1=0在區間[-1，1]上的根（精確根xo=0）。例1的數值實驗結果如表1所示。

例2求方程g（x）=x-e2=0在區間[0，1]上的根（精確根xo=0.56714329…）。例2的數值實驗結果如表2所示。

運用新的迭代法，即式（1）迭代來求解非線性方程的根具有收斂速度快的特點。在例1中新的迭代法只需要5次迭代就達到了所要求的精度：例2中只需6次迭代就達到了所要求的精度。所以可以看出，新的迭代法快速穩定地收斂到非線性方程的實數根.且在迭代過程中只需要計算函數值，不需要計算導數值，從上面兩個數值試驗結果可以看出新的代法是非常有效的。

3結束語

本文新的迭代法具有簡單有效的特點.從式（1）可以看出新的迭代法的迭代公式簡潔明了，而且沒有待定參數.所以在使用時不需要考慮參數的選擇。另一方面，它具有和牛頓迭代法一樣的二階收斂速度.而且無需考慮導數值的計算.這就說明本文迭代法在計算復雜函數的根時.要明顯優于牛頓迭代法。與此同時，迭代公式簡單且無需計算導數也大大提高了計算機的使用效率，降低了編程的復雜度，體現出快速、有效、使用方便的特點。