一種基于牛頓迭代法的方程求根優化方法

吳承楷

（北京交通大學數學與統計學院，北京 100044）

牛頓迭代法又稱為牛頓-拉夫遜方法，是牛頓提出的一種在實數域和復數域上近似求解方程的方法。17 世紀，航海、天文技術的日益興盛推動了科學的進步，數學發展也迎來了全新時期，因此方程的求根問題成為數學家們關注的焦點。此時，數學家們熱衷于尋找方程的嚴格按照公式給出的解（即解析解），韋達和卡爾丹等人在該領域做出了巨大貢獻。然而隨著對求根問題研究的深入，研究人員發現絕大多數方程都沒有一般的解析解，只能通過逼近的方法去求近似解（即數值解），因此尋找精度較高的數值解開始成為方程求根的主流思想，牛頓迭代法就是在該思想基礎上應運而生的。

步入現代，自然科學各領域的高速進步對方程求根問題的解答方式提出了全新要求，需要收斂速度更快的求根方法。許多中外研究人員在原牛頓迭代法的基礎上改進了牛頓迭代法，并將其應用于已有的技術中[1]。國防科技大學電子科學學院的王佳奇等人提出了基于牛頓迭代法的全球衛星導航系統（GNSS）欺騙干擾參數估計方法，將牛頓迭代法和統計方法相結合，提高了參數估計的精度[2]。

1 牛頓迭代法

原始的牛頓迭代法在幾何意義上是一個不斷求取切線的過程。對于一個形如f（x）=0 的方程，先給出一個初始的近似值x0，然后得出f（x）在x0處的導數和函數值。再以該導數為斜率，以該函數值為函數上一點構造一個一次函數，并求其零點，設其為x1。最后重復上述步驟，直到求取到符合精度條件的零點值。牛頓迭代法是早期收斂速度較快的求根手段之一，而且可以證明當方程根處的導數值不等于0 時，牛頓迭代法至少是平方收斂的，和二分法相比，其收斂速度有顯著提高。運算步驟如公式（1）所示。

式中：xk為前一次的近似迭代數值解；xk+1為在xk基礎上迭代一次后得到的數值解；f（xk）為f（x）在xk處的值；f'（xk）為f（x）在xk處的導數值。

根據迭代函數的定義xk+1=φ（xk），可得迭代函數，如公式（2）所示。

2 中點牛頓迭代法

中點牛頓迭代法利用中點，將原來牛頓迭代法中分母上的f'（xk）改進為，具有加強收斂速度的效果，其運算步驟如公式（3）所示。

式中：xk+1*為xk經過一次預迭代后得到的中間值，其值如公式（4）所示。

3 三等分點牛頓迭代法（改進后的中點牛頓法）

3.1 原理和改進方法

在仔細學習了各種數值計算方法后，考慮中點牛頓迭代法選取了xk和xk+1*兩等分點（即中點）處的導數值代替原有牛頓法中xk處的導數值，如果要使迭代步驟更精確，需要在該區間內選取更多的點，將囊括該方程的更多信息。因此，該文根據這種思路繼續外推，考慮將xk和xk+1*中間的部分三等分，得到2 個三等分點，并分別計算2 個三等分點處的導數值，并取平均值，以此來代替中點牛頓迭代法中的。即對上述中點牛頓迭代法進行改進，提出一種新方法，命名為三等分點牛頓迭代法。

其具體原理是通過xk得出xk+1*后，繼而選取xk和xk+1*之間等距離的2 個三等分點，分別求出它們的導函數，并取平均值，再帶入原來迭代函數的分母中。具體運算步驟如公式（5）所示。

化簡后如公式（6）所示。

式中：xk+1*為xk經過一次預迭代后得到的中間值；和分別為f（x）在括號內點上的導數值。

4 數值試驗和誤差分析

為了驗證改進后的迭代法的迭代收斂速度，該文以如公式（7）所示的簡單二次方程為例，以收斂法迭代求零點進行數值試驗，來比較改進前、后算法的收斂性。

表1 數值試驗一的過程

從表1 所示的數值試驗中，該文對3 種牛頓迭代法進行了比較。可以看到，經過2 次迭代后，中點牛頓法和三等分點牛頓法均達到了要求的精度，而牛頓迭代法則進行了4 次迭代才達到要求。該文進一步提高精度要求，繼續比較中點牛頓法和三等分點牛頓迭代法的收斂效果，見表2。

表2 數值試驗二的過程

上述方程是一個簡單的多項式方程，在實際生產應用中會碰到許多含有指數對數函數、三角或反三角函數的方程，這些方程統稱為超越方程，它們的解無法通過多項式方程得到，其精確解也不能簡單表示出來，只能通過如牛頓迭代法這樣的方法來求近似解。如果對一個簡單的超越方程ex+x=0 進行一個新的數值試驗，使用三等分點牛頓迭代法和中點牛頓迭代法，可以得到類似的結果。三等分點牛頓迭代方法同樣也能加快超越方程求根的收斂速度。

問卷主要由三部分構成。第一部分題為個人信息，其設置的主要內容是對問卷之后題目的填寫效果的影響因素；第二部分題為水域現狀，為獲取填寫者對平時看到的水域水質情況的直觀感受評價，實證化探究“河長制”制度實施效用；第三部分題為實施情況，目的是采集填寫者對現階段“河長制”制度實施過程中出現的具有代表性和普遍性的不足與建議的相關看法與信息。

牛頓迭代法的精髓在于選取盡可能少但包括有關函數信息最多的點，中點牛頓迭代法只選取了中點一個點，但是該點所含的函數信息過少，因此迭代過程中獲得的精確程度不夠。當選取的點數目增多時，便可以使其包括更多有關方程的信息，因此可增加迭代獲得的精確程度[3]。

5 等分點牛頓迭代法

根據上述三等分點牛頓迭代法的研究，同理還可將其迭代公式進一步推廣至n等分點牛頓迭代法。如四等分點牛頓迭代法，如公式（8）所示。

式中：xk+1*為xk經過一次預迭代后得到的中間值。

其原理和三等分點牛頓迭代法類似，得到預迭代處理的xk+1*值后，取其和xk之間3 個四等分點處的導數值，再取平均值，其對數值解的收斂速度會比三等分點牛頓迭代法有進一步提高。

類似可以得出n等分點牛頓迭代法，如公式（9）所示。

式中：xk+1*為xk經過一次預迭代后得到的中間值。

6 應用意義

通過2 次數值試驗，所得初步結論如下：1）中點牛頓迭代法和三等分點牛頓迭代法比最基本的牛頓迭代法有加速收斂的效果，在實際生產應用中可以起到一定的推動作用。2）三等分點牛頓法比中點牛頓法收斂速度更快，并可能有隨著迭代次數增加，收斂速度進一步加快的趨勢。三等分點牛頓迭代法的具體收斂速度需要根據收斂速度表達式進行進一步研究。3）將中點牛頓迭代法和三等分點牛頓迭代法的效果進行比較，可大膽猜測隨著等分點的數量增加，迭代收斂速度會進一步加快，在具體的應用中可以取更多的等分點，以得到更快的收斂速度。不過具體結論還需要在進一步的試驗中證明。另外，等分點數量每增加一個，每次迭代計算中就會增加一次求導運算，在實際應用中的反而效果不好。

改進后的牛頓迭代法能在各領域顯著提高計算效率。該文將以水利方面的2 個經典方程計算問題為例，分別闡述改進后的牛頓迭代法在多項式方程和超越方程中的應用優勢。

蓄水池和水庫一直都是防洪水、保供水的重要設施。大型蓄水設施常常修建在山谷或落差較大的河流下游處，對當地的經濟發展和生態環境具有重要的平衡作用。蓄水池的水位調整一直是非常重要的課題。水位需要根據實際情況進行調整，并始終保持在安全且合適的范圍內，調整的依據則是水庫入庫流量、蓄水量和下泄流量之間的函數關系[6]。其基本方程式如公式（10）所示。

式中：Mi+1和Mi分別代表i+1 時刻和i時刻的蓄水池水容量；iqi和oqi分別代表i時刻入池和出池水流量；Mi代表初始蓄水池水容量。

根據上述隱式方程式確定迭代區間，然后從i=1 開始進行迭代，迭代出該時間點需要進行的泄洪量。由于每個時間點的泄洪量都會影響接下來水庫的水量和后續計算，每步中累積的微小擾動都有可能在迭代次數增加后變為巨大的誤差，因此迭代求根的精確性在這個例子中尤為重要。另外，由于方程中系數比較大，因此初始的迭代區間較難選取，采用原牛頓迭代法收斂速度較慢，而采用改進的牛頓迭代法則可加快收斂速度，效果更好。

改進的牛頓迭代法同樣能顯著提高灌注樁圓形截面受彎承載力的計算效率[7]。與蓄水池下泄洪量的計算相比，圓形截面受彎承載力的計算是一個復雜的超越方程，無法求得其具體的解析解。其基本方程如公式（11）所示。

式中：K為承載力安全系數；M為轉彎扭矩設計值；fc為混凝土軸心抗壓強度設計值；A為圓形截面面積；r為圓形截面半徑；α為受壓區混凝土對應的相對圓心角；fy為鋼筋抗拉強度設計值；As為縱向鋼筋截面面積；rs為截面半徑。

通過整理公式（11）和其他確定已知的等量關系，可將方程轉換為只含α（受壓區混凝土對應的相對圓心角）的單變量方程，然后可應用改進后的牛頓迭代法求出α，其余變量也可求出。灌注樁可用于保護河岸。河岸常年受生物、波浪沖刷和船只撞擊等外力作用，侵蝕現象非常普遍，如果不加以控制，會造成大量水土流失，間接導致岸基不穩，進而威脅河岸兩邊的住房安全。而在河岸邊埋下灌注樁可以有效減少這類侵蝕的發生，起到保護河岸的作用。不同的河岸水文情況不同，需要通過試算選擇最合適的灌注樁。而該過程普遍計算量比較大，改良的牛頓迭代法可以較好地加快計算速度。

7 結語

該文在牛頓迭代法衍生方法的基礎上提出了一種改進的牛頓迭代法，能夠實現一般方程數值解的加速逼近。數值試驗的結果表明，在迭代次數較少時（小于等于3次），該迭代方法得到的數值解精度與使用中點牛頓迭代法得到的數值結果差距不大，但隨著迭代次數增加，兩者的精度開始有了明顯的差距。因此，該文提出的三等分點牛頓迭代法在迭代次數較多的計算機算法中具有良好效果。目前工程技術上的計算和求解越來越依賴計算機，進一步提高了三等分點牛頓迭代法在實際應用中的有效性。