一種基于牛頓迭代法的方程求根優(yōu)化方法

吳承楷

（北京交通大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，北京 100044）

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

步入現(xiàn)代，自然科學(xué)各領(lǐng)域的高速進(jìn)步對(duì)方程求根問題的解答方式提出了全新要求，需要收斂速度更快的求根方法。許多中外研究人員在原牛頓迭代法的基礎(chǔ)上改進(jìn)了牛頓迭代法，并將其應(yīng)用于已有的技術(shù)中[1]。國防科技大學(xué)電子科學(xué)學(xué)院的王佳奇等人提出了基于牛頓迭代法的全球衛(wèi)星導(dǎo)航系統(tǒng)（GNSS）欺騙干擾參數(shù)估計(jì)方法，將牛頓迭代法和統(tǒng)計(jì)方法相結(jié)合，提高了參數(shù)估計(jì)的精度[2]。

1 牛頓迭代法

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

式中：xk為前一次的近似迭代數(shù)值解；xk+1為在xk基礎(chǔ)上迭代一次后得到的數(shù)值解；f（xk）為f（x）在xk處的值；f'（xk）為f（x）在xk處的導(dǎo)數(shù)值。

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

2 中點(diǎn)牛頓迭代法

中點(diǎn)牛頓迭代法利用中點(diǎn)，將原來牛頓迭代法中分母上的f'（xk）改進(jìn)為，具有加強(qiáng)收斂速度的效果，其運(yùn)算步驟如公式（3）所示。

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

3 三等分點(diǎn)牛頓迭代法（改進(jìn)后的中點(diǎn)牛頓法）

3.1 原理和改進(jìn)方法

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

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

化簡(jiǎn)后如公式（6）所示。

式中：xk+1*為xk經(jīng)過一次預(yù)迭代后得到的中間值；和分別為f（x）在括號(hào)內(nèi)點(diǎn)上的導(dǎo)數(shù)值。

4 數(shù)值試驗(yàn)和誤差分析

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

表1 數(shù)值試驗(yàn)一的過程

從表1 所示的數(shù)值試驗(yàn)中，該文對(duì)3 種牛頓迭代法進(jìn)行了比較?？梢钥吹剑?jīng)過2 次迭代后，中點(diǎn)牛頓法和三等分點(diǎn)牛頓法均達(dá)到了要求的精度，而牛頓迭代法則進(jìn)行了4 次迭代才達(dá)到要求。該文進(jìn)一步提高精度要求，繼續(xù)比較中點(diǎn)牛頓法和三等分點(diǎn)牛頓迭代法的收斂效果，見表2。

表2 數(shù)值試驗(yàn)二的過程

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

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

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

5 等分點(diǎn)牛頓迭代法

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

式中：xk+1*為xk經(jīng)過一次預(yù)迭代后得到的中間值。

其原理和三等分點(diǎn)牛頓迭代法類似，得到預(yù)迭代處理的xk+1*值后，取其和xk之間3 個(gè)四等分點(diǎn)處的導(dǎo)數(shù)值，再取平均值，其對(duì)數(shù)值解的收斂速度會(huì)比三等分點(diǎn)牛頓迭代法有進(jìn)一步提高。

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

式中：xk+1*為xk經(jīng)過一次預(yù)迭代后得到的中間值。

6 應(yīng)用意義

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

改進(jìn)后的牛頓迭代法能在各領(lǐng)域顯著提高計(jì)算效率。該文將以水利方面的2 個(gè)經(jīng)典方程計(jì)算問題為例，分別闡述改進(jìn)后的牛頓迭代法在多項(xiàng)式方程和超越方程中的應(yīng)用優(yōu)勢(shì)。

蓄水池和水庫一直都是防洪水、保供水的重要設(shè)施。大型蓄水設(shè)施常常修建在山谷或落差較大的河流下游處，對(duì)當(dāng)?shù)氐慕?jīng)濟(jì)發(fā)展和生態(tài)環(huán)境具有重要的平衡作用。蓄水池的水位調(diào)整一直是非常重要的課題。水位需要根據(jù)實(shí)際情況進(jìn)行調(diào)整，并始終保持在安全且合適的范圍內(nèi)，調(diào)整的依據(jù)則是水庫入庫流量、蓄水量和下泄流量之間的函數(shù)關(guān)系[6]。其基本方程式如公式（10）所示。

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

根據(jù)上述隱式方程式確定迭代區(qū)間，然后從i=1 開始進(jìn)行迭代，迭代出該時(shí)間點(diǎn)需要進(jìn)行的泄洪量。由于每個(gè)時(shí)間點(diǎn)的泄洪量都會(huì)影響接下來水庫的水量和后續(xù)計(jì)算，每步中累積的微小擾動(dòng)都有可能在迭代次數(shù)增加后變?yōu)榫薮蟮恼`差，因此迭代求根的精確性在這個(gè)例子中尤為重要。另外，由于方程中系數(shù)比較大，因此初始的迭代區(qū)間較難選取，采用原牛頓迭代法收斂速度較慢，而采用改進(jìn)的牛頓迭代法則可加快收斂速度，效果更好。

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

式中：K為承載力安全系數(shù)；M為轉(zhuǎn)彎扭矩設(shè)計(jì)值；fc為混凝土軸心抗壓強(qiáng)度設(shè)計(jì)值；A為圓形截面面積；r為圓形截面半徑；α為受壓區(qū)混凝土對(duì)應(yīng)的相對(duì)圓心角；fy為鋼筋抗拉強(qiáng)度設(shè)計(jì)值；As為縱向鋼筋截面面積；rs為截面半徑。

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

7 結(jié)語

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