改進的布洛依登算法

李福祥+黃佳玥

摘 要：提出了一種改進的布洛依登算法，證明了新方法的收斂性，通過進行數值實驗驗證了改進布洛依登算法的收斂階數及有效性，并通過與牛頓法以及擬牛頓法的比較體現了改進的布洛依登算法的優越性。

關鍵詞：

非線性方程組；擬牛頓迭代法；改進擬牛頓迭代法

DOI：10.15938/j.jhust.2017.06.024

中圖分類號： O22

文獻標志碼： A

文章編號： 1007-2683（2017）06-0127-04

Abstract：A Modified Broyden algorithm is presented to solve nonlinear equations in this paper. The convergence of the new algorithml is proved. The convergent order and effectiveness of improved Broyden method can be verified by numerical experiments. Through comparing with Newton′s method and quasinewton method， the advantages of the improvement Broyden method are showed.

Keywords：nonlinear equations； quasi Newton iteration method； improved quasi newton iteration method

0 引 言

求解非線性方程組的牛頓法是一個最基本而且十分重要的方法，目前很多有效的迭代法都是以牛頓法為基礎改進的。求解非線性方程組的牛頓法是求解非線性方程的牛頓法的推廣[1-7]。

擬牛頓算法與牛頓法相比，擬牛頓法降低了導數值的運算量，收斂速度比牛頓法快，但每一步迭代都要計算新的矩陣的逆矩陣，在一定程度上也會增加計算的難度，改進擬牛頓算法就是基于這個缺點改進的，通過改進布洛依登秩1校正公式，降低逆矩陣的計算量。

3 改進的布洛依登算法

利用Mathematica軟件進行編程計算，分別用牛頓法、擬牛頓法和改進擬牛頓法對上面的六個方程組進行迭代求解，以真解X與最后一次迭代得到的X-之間的差（ε=X-X-）為指標進行比較。

由于計算機不能顯示出過小的數，因此分別選取迭代次數為2、3、4。為了使表格簡潔明了，在不影響結果真實性、準確性的前提下，表格中只記錄了ε的指數。

計算例1可得比較結果如表1；例2的結果比較見表2；例3的結果比較見表3。

由表1、表2、表3可以看出，在收斂階數方面：牛頓迭代法為2階收斂；擬牛頓迭代法與改擬牛頓迭代法均為3階收斂。從效率指數方面看：牛頓迭代法的效率指數為212n，擬牛頓迭代法的效率指數為313n，改擬牛頓迭代法的效率指數均為313n，即擬牛頓迭代法與改擬牛頓迭代法的計算效率高于牛頓迭代法，而改擬牛頓迭代法的計算效率與擬牛頓迭代法的計算效率是一樣的。但是，改進擬牛頓算法比擬牛頓算法少算了一個矩陣的逆，因此對擬牛頓迭代法的修改是有一定意義的。

6 結 論

本文主要介紹了改進擬牛頓迭代法的形式，證明了該方法的收斂性，利用數值實驗證明了改進擬牛頓迭代法的收斂階數為3階，進行了三種迭代法的比較，說明了改進擬牛頓迭代法的有效性。

參 考 文 獻：

[1] HALLEY E. A New. Exact and Easy Method for Finding the Roots of Equations Generally and without Any Previous Reduction[J]. Philos. Trans. R. Soc.Lond.， 1694（18）： 136-148.

[2] KOU J， LI Y. Modified Chebyshev′s Method Free from Second Derivative for Nonlinear Equations[J]. J. Appl. Math. Comput.， 2007， 187（2）： 1027-1032.

[3] GUTIERREZ J M， HERNANDEZ M A. An Acceleration of Newton′s Method： Super Halley Method[J]. J. Appl. Math. Comput.， 2001， 117（2）： 223-239.

[4] KING R F. A Family of Fourth Order Methods for Nonlinear Equations[J]. SI AMJ. Numer. Anal.， 1973（10）： 876-879.

[5] LIU Z， ZHENG Q， ZHAO P. A Variant of Ste Ensens Method of Fourthorder Convergence and Its Applications[J]. Applied Mathematics and Computation， 2010， 216（7）： 1978-1983.

[6] OSTROWSKI A M. Solutions of Equations and Systems of Equations[M]. New York： Academic Press， 1966.

[7] KUNG H T， TRAUB J F. Optimal Order of Onepoint and Multipoint Iteration[J]. J. Assoc. Comput. Mach.， 1974（21）： 643-651.

[8] 黃象鼎， 曾鐘鋼， 馬亞南. 非線性數值分析的理論與方法[M]. 武漢： 武漢大學出版社， 2004.

[9] 李慶楊， 莫孜中， 祁力群. 非線性方程組的數值解法[M]. 北京： 科學出版社，1999.

（編輯：關 毅）endprint