基于牛頓迭代法的一類新預(yù)估-校正算法

常丑娥，孟國艷

（忻州師范學(xué)院數(shù)學(xué)系,山西忻州 034000）

在科學(xué)研究和工程技術(shù)領(lǐng)域中，經(jīng)常將實(shí)際問題進(jìn)行建模，轉(zhuǎn)化為非線性方程f(x)=0 進(jìn)行處理。其中非線性函f(x)可為高階多項式或超越函數(shù)。在文獻(xiàn)[1]中介紹了非線性方程求根公式的演變歷史，發(fā)現(xiàn)大部分n(n≥5) 次及以上的方程無求根公式可言。在實(shí)際問題中，常采用迭代法求解滿足精度要求的近似根。在計算過程中若能將迭代收斂速度提高，顯而易見，該研究具有重要的現(xiàn)實(shí)意義。

文獻(xiàn)[2-3]中給出Newton-Raphson method（NR法），簡稱牛頓法，該方法是一個經(jīng)典的迭代法，結(jié)構(gòu)簡單，收斂速度也較快，至少為二階收斂。很多學(xué)者對其進(jìn)行改進(jìn)研究，提出各種改進(jìn)修正的算法。其中龍愛芳從牛頓迭代公式xk+1=xk-中的導(dǎo)數(shù)f'(xk)入手研究，嘗試避免計算導(dǎo)數(shù)，來減少計算量[4]。WEERAKOON S 等學(xué)者從數(shù)值積分入手，利用梯形公式近似定積分進(jìn)行改進(jìn)，提出算術(shù)平均牛頓法（TN 法）[5]。王霞等利用Simpson 公式代替梯形公式，提出Simpson（SN 法）[6]。之后，許多學(xué)者利用不同的數(shù)值積分給出不同的牛頓迭代格式。陳偉等以先預(yù)估后校正的思想提出含雙參數(shù)的改進(jìn)型牛頓迭代法[7]。姚夢媛等將牛頓法與數(shù)值積分結(jié)合，采用高斯公式，提出高斯-勒讓德牛頓法（GN 法）[8]。

受牛頓法的啟發(fā)，結(jié)合預(yù)估-校正思想，對牛頓法經(jīng)過變形加速修正處理，提出了一種新的預(yù)估-校正算法。

1 理論基礎(chǔ)

收斂階定義[9]設(shè)由迭代格式xk+1=φ(xk)產(chǎn)生的迭代序列為{xk}，記誤差ek=x*-xk。若?p,c∈R，且p≥1,c＞0時，有，則稱迭代序列{xk}按漸進(jìn)誤差常數(shù)c,p階收斂到x*。當(dāng)p=1 且0 ＜c＜1 時為線性收斂；當(dāng)p=2 時，為平方收斂；當(dāng)p＞1時，為超線性收斂。收斂階定理[9]設(shè)x*=φ(x*)，整數(shù)p＞1,φ(p)(x) 在U(x*) 連 續(xù)，且φ'(x*)=…=φ(p-1)(x*)=0，而φ(p)(x*)≠0，則由xk+1=φ(xk)產(chǎn)生的序列{xk} 在U(x*)內(nèi)p階收斂。

2 新預(yù)估-校正算法的構(gòu)造

由牛頓迭代法

可知，若牛頓法收斂，則迭代收斂階為二階，收斂速度較快，每一次迭代后的‖xk-xk-1‖越來越小。因此受啟發(fā)，再結(jié)合雙牛頓迭代法[10]，有

此時由（1）、（2）進(jìn)行了兩次循環(huán)迭代。對（2）進(jìn)行移項后，變形可得

由于（6）為隱格式，不易求解，于是進(jìn)行修正，得到新的迭代算法為

其中：yk為預(yù)估步；zk為加速步；xk +1為校正步。

可見，得到的迭代格式（7）為牛頓迭代法的一種新的預(yù)估-校正格式，該格式通過加速步起到了加速的作用。

3 理論分析

設(shè)f(x)及各階導(dǎo)數(shù)在根x*的U(x*)內(nèi)連續(xù)，初值x0充分接近x*時，有下列結(jié)論：

結(jié)論1對于f(x)=0，當(dāng)x*為單根時，有f(x*)=0,f'(x*)≠0，從迭代格式（7）可知，當(dāng)xk取x*時，=x*，所以f(yk)=f(x*)=0，同理f(zk)=0。

對于迭代格式（7）的迭代函數(shù)可取為

結(jié)合收斂階定理可得

由收斂階定理知，當(dāng)x*是f(x)=0 的單根時，構(gòu)造的新算法（7）二階收斂。

結(jié)論2對于f(x)=0，當(dāng)x*是m(m≥2)重根時，令f(x)=(x-x*)mg(x) 且g(x*)≠0，有f(x*)=f'(x*)=…=f(m-1)(x*)=0，但f(m)(x*)≠0。從迭代格式（7）可知

于是由收斂階定理知，當(dāng)x*是f(x)=0 的重根時，構(gòu)造的新算法（7）線性收斂。

4 數(shù)值實(shí)驗(yàn)與分析

實(shí)驗(yàn)1通過6 個不同的方程[8]來驗(yàn)證新的預(yù)估-校正算法的收斂速度，并與GN、SN、TN、NR 法進(jìn)行比較。程序在同一環(huán)境MATLAB R2018a 下編寫，設(shè)置ε=10-10作為終止條件。這6個方程[8]分別為：

（1）(x-2)3(x+2)4=0 該方程有多個根，均為重根；

（2）x5-10=0 該方程有單根和多重根；

（3）(x-1)6-1=0 該方程有多個根，僅有一個根為重根；

（4）(x-1)e-x=0 該方程有單根（涉及指數(shù)函數(shù)）；

（5）sin(x-1) +x-1=0 該方程有單根（涉及三角函數(shù)）；

（6）x2-ex-3x+2=0 該方程有多個根，均為單根；

由于方程的根的情況各異，所以測試方程具有代表性。測試結(jié)果見表1。

表1 不同方程求根時迭代格式所需的迭代次數(shù)

通過數(shù)值計算發(fā)現(xiàn)，對于同一方程，在不同的初始條件和相同的終止條件下，新算法的迭代次數(shù)較雙牛頓、GN、SN、TN、NR 的迭代次數(shù)少，收斂速度快。當(dāng)初始值選取較好時，新算法的迭代次數(shù)略比其他算法的迭代次數(shù)少；當(dāng)初始值選取的不是較好時，新算法的迭代次數(shù)明顯比其他算法的迭代次數(shù)少。

實(shí)驗(yàn)2通過3 個不同的方程[9]來驗(yàn)證新的預(yù)估-校正算法的收斂速度，并與雙牛頓、GN、SN、TN、NR法進(jìn)行比較。程序同樣在MATLAB R2018a 下編寫，設(shè)置ε=10-10作為終止條件。這3個方程[9]分別為：

測試結(jié)果見表2。

表2 不同方程求根時迭代格式所需的迭代次數(shù)

通過高次代數(shù)多項式方程和超越方程的計算，結(jié)果表明：對于同一方程，在不同的初始條件和相同的終止條件下，新算法的迭代次數(shù)比雙牛頓、GN、SN、TN、NR 的迭代次數(shù)少，至多相等，可見新算法在收斂速度上占優(yōu)勢。

從表2 可看出，當(dāng)初始值選取較好時，新算法的收斂速度從迭代次數(shù)上分析略占優(yōu)勢；當(dāng)初始值選取的不是較好時，新算法的收斂速度明顯比其他算法快。

5 結(jié)束語

基于雙牛頓迭代法，結(jié)合預(yù)估校正思想，構(gòu)造出的新的預(yù)估-校正迭代格式，結(jié)構(gòu)緊湊，收斂階至少為二階收斂，計算過程相對有些復(fù)雜，效率指數(shù)也不是很高，但迭代次數(shù)較少，能起到提高收斂速度的效果。通過不同的算例分析可知，對于同一方程在同一終止條件下，當(dāng)初始值不同時，迭代次數(shù)不同。經(jīng)過與其他幾種迭代法比較，發(fā)現(xiàn)該迭代法的收斂速度快，迭代次數(shù)少，具有一定的可行性和應(yīng)用性。