Simpson牛頓公式的一種改進

李洋洋， 郭清偉

（合肥工業大學數學學院，安徽合肥 230009）

0 引 言

迭代法是求解非線性方程的最為常用的方法之一，主要有簡單迭代法、弦截法、拋物線法、牛頓法及其各種變形的迭代方法。文獻［1］提出Simpson牛頓方法和幾何平均方法，且證明其三階收斂到單根；文獻［2］利用反函數的求導法則，提出了Homeier－Simpson牛頓方法，且證明其三階收斂到單根；文獻［3－4］講述了關于非線性方程求根的一些基礎知識；文獻［5］中介紹了一類具有五階收斂的牛頓方法；文獻［6－7］提出調和平均牛頓方法和中點牛頓方法及改進牛頓法，且證明其三階收斂到單根；文獻［8］介紹了一類四階牛頓變形方法；文獻［9］討論了平方收斂公式的一個5階加速方法；文獻［10］介紹了科茨求積公式與牛頓公理相結合得出的各種迭代格式，至少三階收斂到單根。在已有的迭代法中，有的收斂階雖高但計算效率低下，有的2個方面都不理想。考慮到收斂階和計算效能問題，本文基于文獻［1，2，5］和文獻［10－12］，提出了一種新的迭代格式，稱為改進的Simpson牛頓方法，簡記為XSN方法；證明了該方法對單根而言具有三階收斂性，對非單根而言具有線性收斂性，與同類方法相比，在計算效率方面有了一定的改善。

1 預備知識

為研究迭代序列的收斂速度和收斂效率，先給出效率指數的定義、收斂階定義及收斂定理。

定義1 設迭代序列｛xn｝∞0的收斂階為p≥1，每步迭代的計算量為ω，則稱e為迭代序列的效率指數［1］，即

定義2 設迭代過程xn＋1＝φ（xn）收斂于方程x＝φ（x）的根x＊，如果迭代誤差en＝xn－x＊，當n→∞時，成立下列漸進關系式：

則稱該迭代過程是p階收斂的［2］。

定理1 對于迭代過程xn＋1＝φ（xn），如果φ（p）（x）在所求根x＊的鄰近連續，并且有：

則該迭代過程在點x＊鄰近是p階收斂的［3］。

2 新算法的推導

設α是方程f（x）＝0的根，f（x）是可導函數，由牛頓公理顯然成立：

將（1）式中右端積分用數值積分Simpson公式近似代替，并令x＝α，則

其中，用xn＋1近似代替α，整理得到迭代格式：

（2）式中關于xn＋1是隱式的，給求解帶來很多麻煩，為避免隱式求解，提出組合格式，即

（3）式是經典牛頓方法與Simpson公式結合得到的，這就是文獻［1］所給出的迭代方法，稱為Simpson牛頓方法，簡記為SN方法。

衡量一個迭代法的優劣除了考察其收斂階外，還要考慮算法的效率指數。從（3）式可以明顯看出，迭代一次需要計算1次函數值和3次導數值，考慮到迭代的計算效率，如果收斂階不變，能減少函數值或導數值的計算次數，提高計算的效能。由此將和在xn泰勒展開，可得：

將（4）式代入（3）式，得到本文的迭代公式：

其中，n＝0，1，2，…。

顯然，（5）式迭代一次需要計算1次函數值和2次導數值。如果將函數與其各階導數的計算量看作相同，每迭代一次，（5）式就比（3）式減少1次計算量，然而它們的收斂階相同，根據定義1可知（5）式的計算效率要高于（3）式。為了方便，把本文的迭代公式（5）式簡記為XSN方法。

3 收斂性分析及計算效能比較

3.1 定理2及其證明

定理2 若方程f（x）＝0在某一區間存在實根x＊，且f″（x）在x＊某一鄰域內連續，則有：

（1）當x＊是f（x）＝0的單根時，XSN方法是三階收斂的。

（2）當x＊是f（x）＝0的m（m≥2）重根時，XSN方法是線性收斂的。

下面證明當f′（x＊）和f″（x＊）均不為零時，迭代格式三階收斂于f（x）＝0的根x＊。

證明 （1）由（5）式知XSN方法的迭代函數為：

計算φ（x）在方程的根x＊處的各階導數值：

而f（x＊）＝0，代入整理得φ′（x＊）＝。當f（x＊）＝0時，有

而

根據定理1可得XSN方法是三階收斂，其收斂階高于牛頓迭代法。

（2）設x＊是f（x）＝0的m（m≥2）重根，則

f（x＊）＝0， f′（x＊）＝0，…，f（m－1）（x＊）＝0， f（m）（x＊）≠0。

從而由泰勒展開公式得：

代入迭代函數中，整理得：

故由定理1得XSN方法在重根附近是線性收斂的，從而定理2證畢。

當方程根的重數m已知時，改進的XSN方法如下：

其迭代公式如下：

推論1 當x＊是f（x）＝0的m（m≥2）重根時，當重數m已知時，改進的XSN方法（6）式是平方收斂的；當重數m未知時，改進的XSN方法（7）式是三階收斂的。

由定理2的證明過程即可得到該推論。

3.2 定理3及其證明

定理3 XSN方法的效率指數高于文獻［1］的SN方法、文獻［5］的五階牛頓方法及文獻［8］的四階牛頓方法。

證明 （1）XSN的收斂階為3，每次迭代的計算量為3n，所以效率指數為：

（2）文獻［1］中SN方法的收斂階為3，每次迭代的計算量為4n，所以效率指數為：

（3）文獻［5］中的迭代方法收斂階為5，每次迭代的計算量為5n，所以效率指數為：

（4）文獻［8］中的迭代方法收斂階為4，每次迭代的計算量為4n，所以效率指數為：

則有eSN＜e［5］＜e［8］＜eXSN，至此，定理3得證。

定理3也表明，雖然有些迭代方法收斂階提高了，但并沒有真正提高計算的效能。

4 數值試驗比較

（1）算例1。求方程f（x）＝sin2（x）－x2＋1的根，取初值x＝1.5。

反復使用本文方法（XSN法）與正割法迭代，令｜xn＋1－xn｜≤10－5時終止迭代，得到xn序列，見表1所列。

表1 使用XSN法與正割法迭代得到的xn序列

（2）算例2。求方程f（x）＝x3－x－1的根，取初值x0＝0。

反復使用本文方法（XSN法）與經典牛頓法，令｜xn＋1－xn｜≤10－5時終止迭代，得到xn序列，見表2所列。

表2 使用XSN法與經典牛頓法迭代得到的x n序列

明顯地，牛頓法用20次才達到精度，而XSN方法只4次就達到了很好的收斂效果。

（3）算例3。求方程f（x）＝x3＋4x2－10的根，取初值x0＝1。

反復使用本文方法（XSN法）與經典牛頓－Cauchy法，令｜xn＋1－xn｜≤10－5時終止迭代，得到xn序列，見表3所列。

表3 使用XSN法與經典牛頓－Cauchy法迭代得到的x n序列

通過表1～表3的迭代結果可以看出，XSN方法具有較快的收斂速度和較高的數值精度。

5 結束語

目前有很多迭代公式，但主要都是對經典牛頓法的各種變形，雖然收斂階有所提高，但是計算效能并沒有真正提高。本文基于收斂階和計算效率2個方面考慮，對Simpson－牛頓法進行改進，數值驗證非常有效，所以該方法在非線性方程求根中具有很高的實用價值。

［1］ 王 霞，趙玲玲，李飛敏.牛頓方法的兩個新格式［J］.數學的實踐與認識，2007，37（1）：72－76.

［2］ 王 霞，張銀銀.一個三階牛頓變形方法［J］.數學的實踐與認識，2009，39（14）：14－18.

［3］ 馬振華.現代應用數學手冊：計算與數值分析卷［M］.北京：清華大學出版社，2005：163－176.

［4］ Cautschi W.Numerical analysis：an introduction［M］.Boston：Birkhauser，1997：50－100.

［5］ 蘇岐芳，李希文.一類具有五階收斂的牛頓改進法［J］.臺州學院學報，2008，30（6）：1－4.

［6］ Ozban A Y.Some variants of Newton’s methods［J］.Applied Mathematics Letters，2004，17（9）：677－682.

［7］ 朱 琳.關于牛頓迭代公式的改進［J］.寧夏師范學院學報：自然科學版，2011，32（3）：88－89.

［8］ 趙玲玲，王 霞.一類四階牛頓變形方法［J］.數學的實踐與認識，2008，38（9）：102－106.

［9］ 林開勇，陶芳寬，江 平，等.平方收斂公式的一個5階加速方法［J］.合肥工業大學學報：自然科學版，2009，32（11）：1763－1765.

［10］ 薛雅萍，吳開謖，劉曉晶.基于等距節點積分公式的牛頓迭代法及其收斂階［J］.數學的實踐與認識，2007，37（24）：34－38.

［11］ 劉雅妹，王 霞.一類新的求解非線性方程的七階方法［J］.數學的實踐與認識，2011，41（14）：239－245.

［12］ Chun C B.Some fourth－order iterative methods for solving nonlinear equations［J］.Appl Math Comput，2008，195：454－459.