李洋洋， 郭清偉

（合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院，安徽合肥 230009）

0 引 言

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

1 預(yù)備知識

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

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

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

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

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

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

2 新算法的推導(dǎo)

設(shè)α是方程f（x）＝0的根，f（x）是可導(dǎo)函數(shù)，由牛頓公理顯然成立：

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

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

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

（3）式是經(jīng)典牛頓方法與Simpson公式結(jié)合得到的，這就是文獻(xiàn)［1］所給出的迭代方法，稱為Simpson牛頓方法，簡記為SN方法。

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

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

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

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

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

3.1 定理2及其證明

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

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

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

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

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

計算φ（x）在方程的根x＊處的各階導(dǎo)數(shù)值：

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

而

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

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

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

從而由泰勒展開公式得：

代入迭代函數(shù)中，整理得：

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

當(dāng)方程根的重數(shù)m已知時，改進(jìn)的XSN方法如下：

其迭代公式如下：

推論1 當(dāng)x＊是f（x）＝0的m（m≥2）重根時，當(dāng)重數(shù)m已知時，改進(jìn)的XSN方法（6）式是平方收斂的；當(dāng)重數(shù)m未知時，改進(jìn)的XSN方法（7）式是三階收斂的。

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

3.2 定理3及其證明

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

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

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

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

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

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

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

4 數(shù)值試驗比較

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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

［3］ 馬振華.現(xiàn)代應(yīng)用數(shù)學(xué)手冊：計算與數(shù)值分析卷［M］.北京：清華大學(xué)出版社，2005：163－176.

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

［5］ 蘇岐芳，李希文.一類具有五階收斂的牛頓改進(jìn)法［J］.臺州學(xué)院學(xué)報，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］ 朱 琳.關(guān)于牛頓迭代公式的改進(jìn)［J］.寧夏師范學(xué)院學(xué)報：自然科學(xué)版，2011，32（3）：88－89.

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

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

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

［11］ 劉雅妹，王 霞.一類新的求解非線性方程的七階方法［J］.數(shù)學(xué)的實踐與認(rèn)識，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.