解非線性方程的一種新的全局快速算法

倪 健， 馬昌鳳

(1.南京榮飛科技有限公司，江蘇南京 210009;2.桂林電子科技大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣西桂林 541004;3.福建師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建福州 350007)

工程實(shí)際與科學(xué)計(jì)算中都遇到大量求解非線性方程f(x)=0的問(wèn)題。對(duì)于這類問(wèn)題，常常不能用解析方法求其精確解，而只能利用數(shù)值方法求其近似解。有關(guān)學(xué)者已提出求解非線性方程的許多數(shù)值方法[1-5]，牛頓法是最流行的一種解法[6]。但對(duì)于某些非線性方程，用牛頓法進(jìn)行迭代求根需迭代多次。本文提出了解非線性方程的一種新方法，該方法通過(guò)對(duì)一些參數(shù)的選取，不僅比牛頓法收斂更快，而且具有全局收斂性。

1 解非線性方程新算法的描述

1.1 收斂性分析

設(shè)非線性方程為f(x)=0，其中f(x)為連續(xù)

其中，y=x-αf(x)/f′(x)，0＜α≤1。

假設(shè)函數(shù) f:R→R存在零點(diǎn)x*，且初始點(diǎn)x0在U(x*)內(nèi)。欲使該迭代函數(shù)收斂，則需滿足|Ψ′(x)|＜1，因此，本文首先計(jì)算Ψ′(x)，即可微的非線性函數(shù)。

考慮迭代函數(shù):

易知f(x*)=0，則有以下極限存在:

由此可得:

綜上所述，可得:利用拉格朗日定理得:

即Ψ(a)-Ψ(b)=Ψ′(ξ)(a-b)，ξ∈(a，b)。所以|。

1.2 收斂效率分析

為簡(jiǎn)單起見(jiàn)，假設(shè) f(x)＞0，f′(z)＞0，f″(z)＞0，z∈U(x*)。要使該方法的收斂速度優(yōu)于牛頓法，則需在假設(shè)情況下，此方法一步收斂結(jié)果比牛頓法一步收斂結(jié)果更接近零點(diǎn)，即

x*≤Ψ(x)≤x-f(x)/f′(x)。

考慮:

當(dāng)x→x*時(shí)，對(duì)兩邊取極限，有?？紤]:

當(dāng)x→x*時(shí)，對(duì)兩邊取極限，則有:

綜上所述，(β-1+α)-1=α-1?β=1，代入(2)式有:

由此可得迭代函數(shù):

其中，y=x-αf(x)/f′(x)，0＜α≤1。所以此迭代函數(shù)較牛頓法有更快收斂速度。

2 全局參數(shù)描述

其中，y=x-αf(x)/f′(x)，0＜α≤1。

假設(shè)f(x)＞0，f′(z)＞0，f″(z)＞0，z∈U(x*)，在類似的情況下，其它情況同理可得。

為了使γ滿足x*≤Ψ(x)≤y，考慮

上述迭代函數(shù)不滿足全局收斂。為了得到一個(gè)全局收斂的迭代函數(shù)，本文考慮以下迭代格式:

考慮:

當(dāng)x→x*時(shí)，對(duì)右邊取極限，則有:

當(dāng)γ=-1時(shí)，所考慮的迭代函數(shù)即為(1)式所示函數(shù)。

如果x0?U(x*)，可以考慮

若f′(y)≈[f(y)-f(x)]/(y-x)，則有:

實(shí)際上，常用

總結(jié)上述結(jié)果得到滿足全局收斂的迭代格式為:

當(dāng)|f(xk)|≤η，γ=-1。

3 算 法

(4)計(jì)算 xk+1=xk+(yk-xk)f(xk)]/ [f(xk)+γf(yk)]。

(5)如果k＞n，停止;如果|f(xk)|＜ε，停止。

(6)k→k+1，返回步驟(2)。

根據(jù)上述論證，可得本文算法步驟如下:

(1)選取初始值x0∈R，α∈(0，1]，ε＞0，η＞0，n∈N，令k=0。

(2)計(jì)算yk=xk-αf(xk)/f′(xk)。

(3)如果|f(xk)|＞η，則

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

為了驗(yàn)證本文算法的有效性，本文選取比較典型的代數(shù)方程和超越方程，在Matlab環(huán)境下進(jìn)行數(shù)值模擬。

先將本文算法與牛頓法作比較，驗(yàn)證本文算法較牛頓法有更快收斂速度。實(shí)驗(yàn)方程如下:

例1 f(x)=(x-6)5-10(x-6)4+38(x-

6)3-68(x-6)2-57(x-6)-8=0;

例2 f(x)=1-exp(x2-3x-4);

例3 f(x)=x2-sin x;

例4 f(x)=exp(-x2)-ln(x+1)。

為了便于處理，設(shè)定參數(shù)分別為:容許誤差ε=1.0E-11，n=1 000，η=0.1，α=1。實(shí)驗(yàn)結(jié)果見(jiàn)表1所列。

表1 數(shù)值實(shí)驗(yàn)結(jié)果

數(shù)值實(shí)驗(yàn)表明，本文算法的收斂速度明顯快于牛頓法，平均減少1/2的迭代次數(shù)，且本文算法的全局收斂效果良好。

以上述例1和例3為算例，初始值x0分別取-10、-2.9，結(jié)果見(jiàn)表2所列。

表2 不同算例的收斂效率

數(shù)值實(shí)驗(yàn)表明，當(dāng)α=1時(shí)，本文算法的迭代效果最佳。

5 結(jié)束語(yǔ)

本文介紹的新算法具有收斂速度快、計(jì)算精度高、計(jì)算精度可控、收斂性不依賴初始值的選擇等特點(diǎn)，因此，本文算法不僅是有效的，而且是高效的。

[1] He JH.Improvement of New ton iteration method[J].Int J Non linear Sci Numer Simulation，2000，1(2):239-240.

[2] U jevic＇N.A m ethod for solving nonlinear equations[J].Appl M ath Comput，2006，174(2):1416-1426.

[3] 李聲鋒.求解方程的一類迭代方法及應(yīng)用[D].合肥:合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院，2007.

[4] 林 洋，楊利華，詹棠森.預(yù)測(cè)校正磨光算法及應(yīng)用[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2010，33(8):1274-1276.

[5] 王能超.算法演化論[M].北京:高等教育出版社，2008: 35-59.

[6] Yamamoto T.Historicaldevelopment in convergence analysis for New ton's and New ton-like methods[J].JCom put ApplM ath，2000，124:1-23.