求解非線性方程的一類改進型牛頓迭代法

陳 偉，蔡 靜，高壽蘭

(湖州師范學院 理學院, 浙江 湖州 313000)

0 引 言

牛頓迭代法是求解非線性方程f(x)=0最常用的數值方法之一.牛頓迭代法的幾何意義鮮明、形式簡單，并在單根附近具有二階收斂速度.但牛頓迭代法的計算過程需要調用導數值，這對函數的可導性要求很高，同時需要較大的計算量，且其局部收斂性還要求迭代的初值與精確根很靠近，這極大地限制了它的應用范圍.

近年來，很多文獻對牛頓迭代法做了進一步的修改與推廣.文獻[1]給出了經典牛頓迭代法的兩種修正形式，并證明它們具有三階收斂速度.文獻[2]和[3]利用先用牛頓迭代法預估后校正的方法對牛頓迭代法進行改進，并證明其在一定條件下至少具有三階收斂速度.文獻[4]利用動力系統的李雅普諾夫方法，克服了f(x)的單調性和特殊情況f′(x)=0.文獻[5]通過差商和局部指數逼近類似，構造了一類不需要計算導數值的超線性收斂指數下降迭代法.文獻[6]提出一種新的二階收斂迭代法，解決了非線性方程f(x)=0在某區間的求根和某些常微分方程的初值問題.文獻[7]將Liapunov方法與指數逼近法結合，構造了一種新的二階收斂指數迭代法.文獻[8]利用割線代替切線的方法，得到了不帶導數項的具有線性收斂的單點割線法和具有超線性收斂的雙點割線法.文獻[9]給出一種以割線代替導數，從而避免導數運算的二階收斂迭代公式.文獻[10]利用微分中值定理的漸進性和線性插值構造了一個四階的迭代公式.文獻[11]利用差商構建了一種避免導數運算的二階收斂牛頓迭代法.文獻[12]基于切比雪夫正交多項式零點插值誤差的極小化性質,構造了非線性方程求根的一類迭代算法,其具有超線性收斂速度.

本文通過添加兩個參數，同時對牛頓迭代法進行先預估再矯正，構造一種具有雙參數的改進型牛頓迭代法.通過調整兩個參數的值可以有效提高迭代法的收斂速度，且在一般情況下比牛頓迭代法具有更快的收斂速度.

1 算法構造

參照文獻[4]和[8],引入一個動力系統：

(1)

其中，U(x*)為x*的某領域，μ為參數.顯然，方程f(x)=0的根x*是動力系統(1)的平衡點，反之相同.

由此可見，動力系統(1)給求解方程f(x)=0提供了各種各樣的可能性，采用不一樣的數值方程求解動力系統(1)就能得到不一樣的求解方程f(x)=0的迭代方法.

由泰勒公式(麥克勞林公式)可對函數進行如下展開：

本文將用到此公式k=-1的形式：

若利用Euler法，則可得：

xn+1=xn-hnf(xn)/[μf(xn)+f′(xn)].

(2)

在式(2)中，如果取hn=1，則可得到迭代公式：

xn+1=φ(xn),φ(x)=x-f(x)/[μf(x)+f′(x)].

(3)

當f(x)在U(x*)內有二階連續導數時，容易得到φ(x*)=0，φ′(x*)≠0，則迭代公式(3)是平方收斂的.

在式(3)中，如果取μ=0，則可得到經典的牛頓迭代法：

(4)

文獻[11]對式(4)進行了修改，構造了一種避免導數運算的迭代法：

(5)

參考上述文獻的構造思想，本文對牛頓迭代法進行如下改進：

首先，利用式(3)進行預估：

最后，得到如下具有雙參數的改進牛頓迭代法：

(6)

2 收斂性分析

由Euler法和傳統牛頓迭代法的一些相關結論，不難證明根據式(6)改進的迭代公式在一定條件下是收斂的.因此，下面只需對迭代公式進行收斂階的證明.

定理2設f(x)：I→R在開區間I內充分光滑.如果a∈I是f(x)=0的單根，且x0充分靠近a，則由式(6)構造的具有參數的改進牛頓迭代法至少具有二階收斂速度.

證明令

en=xn-a,ck=f(k)(a)/[k!f′(a)],k=2,3,4.

將f(x)在a處進行泰勒展開，得：

(7)

(8)

將式(7)和式(8)代入式(6)，得：

整理后得：

(9)

利用泰勒公式對式(9)進行展開，只需展開到第4項，得：

即

則

(10)

由式(8)得：

(11)

將式(7)和式(11)代入式(6)，得：

a+

(12)

利用泰勒公式對式(12)進行展開，只需展開到第3項，得：

即

3 數值實驗

下面通過求解非線性方程f(x)=0在區間[a,b]的解，將迭代公式(3)、牛頓迭代法(4)、迭代公式(5)與本文迭代公式(6)進行比較.

例1求f(x)=4x7+x6-5x5+3x4+x3-7x2+7x-2=0在區間[0,1]內的根.

初始值取x0=0.5,終止條件為|xn+1-xn|<10-6.迭代公式(3)取μ=-1，迭代公式(5)取A=1,B=0，迭代公式(6)取λ=0.5，μ=-1.例1中4類迭代法的收斂速度比較見表1.

表1 例1中4類迭代法的收斂速度比較

例2求f(x)=2cosx-3x+3=0在區間[1,2]內的根.

初始值取x0=1.5,迭代公式(3)取μ=-1，迭代公式(5)取A=1,B=0,迭代公式(6)取λ=0.5，μ=-1，終止條件為|xn+1-xn|<10-6.例2中4類迭代法的收斂速度比較見表2.

表2 例2中4類迭代法的收斂速度比較

從例1和例2的數值結果可以看出，本文給出的迭代公式(6)的迭代結果精度明顯優于其他各類修正的牛頓迭代法，且收斂速度更快.