姚騰騰(廈門大學(xué)數(shù)學(xué)科學(xué)學(xué)院,福建廈門361005)

?

基于一致系數(shù)求積的廣義牛頓法求解非線性方程組

姚騰騰
(廈門大學(xué)數(shù)學(xué)科學(xué)學(xué)院,福建廈門361005)

摘要:采用一致系數(shù)求積公式近似逼近泰勒余項(xiàng),得到一種新的求解非線性方程組的廣義牛頓法.給出算法的一般形式,證明算法是三階收斂的,并且在一定的溫和條件下可以達(dá)到五階收斂.最后,給出數(shù)值例子說明算法的有效性和穩(wěn)定性.

關(guān)鍵詞:一致系數(shù)求積;廣義牛頓法;非線性方程組;三階收斂

其中x=(x1,x2,…,xn)T∈Rn,f:K?Rn→Rn在凸集K中是充分Fréchet可微的.眾所周知,牛頓法是求解非線性方程組(1)的經(jīng)典迭代法.而近幾年,出現(xiàn)了許多利用Adomian分解、同倫攝動(dòng)、牛頓柯特斯求積等技巧求解非線性方程組(1)的牛頓衍生算法[1-8],這些方法相較于牛頓法具有更高的收斂性.在本文中,我們提出一種新的廣義牛頓迭代算法,即采用基于一致系數(shù)求積的牛頓法求解非線性方程組(1).此廣義牛頓迭代法只需要估計(jì)f(x)以及它在不同點(diǎn)處的雅可比矩陣即可.數(shù)值實(shí)驗(yàn)表明,這個(gè)迭代算法是三次收斂的并且在一定的溫和條件下可達(dá)到五階收斂.

1　預(yù)備知識(shí)

一致系數(shù)求積公式[9]定義如下形式的積分

這里ρ(x)是權(quán)函數(shù),通常式(2)的不定積分無法求解,為此我們需要定義能夠近似I(f)的數(shù)值積分公式.典型的數(shù)值積分公式具有如下形式:

其中xk稱為求積公式的節(jié)點(diǎn),Ak稱為求積系數(shù).假設(shè)ρ(x)=1,則n個(gè)節(jié)點(diǎn)的一致系數(shù)求積公式具有如下簡單形式

由文獻(xiàn)[10]知,節(jié)點(diǎn)xk是關(guān)于積分區(qū)間的中點(diǎn)對(duì)稱的.

對(duì)任意的x,xs∈K,由泰勒定理[10]得

其中f'(x)為函數(shù)f在點(diǎn)x∈Rn處的雅克比矩陣.通過積分變換有

應(yīng)用M個(gè)節(jié)點(diǎn)的一致系數(shù)求積公式,得到如下的數(shù)值積分逼近:

其中

節(jié)點(diǎn)wM,k表示M個(gè)節(jié)點(diǎn)中的第k個(gè)節(jié)點(diǎn),則由節(jié)點(diǎn)關(guān)于原點(diǎn)對(duì)稱,滿足

注1 我們知道M個(gè)節(jié)點(diǎn)的一致系數(shù)公式具有至少M(fèi)次代數(shù)精度,并且M為偶數(shù)時(shí),代數(shù)精度為M+1.因此,當(dāng)M≥2時(shí),有

以及

成立.

注2 如果能建立求積公式(3),那么必須要求式(4)中的節(jié)點(diǎn)xk,k=1,2,…,n為不同的實(shí)數(shù),而當(dāng)n =8以及n≥10時(shí),解得式(4)中總會(huì)出現(xiàn)一對(duì)復(fù)共軛節(jié)點(diǎn).因此,在這些情形下無法構(gòu)造一致系數(shù)公式.

2　算法及其收斂性分析

基于以上討論,我們給出一種新的基于一致系數(shù)求積公式求解非線性方程組(1)的廣義牛頓迭代算法.

算法1 (基于一致系數(shù)求積公式的廣義牛頓法)

Step 0 給定初值x0∈Rn以及正整數(shù)M.s∶=0.

Step 1 計(jì)算ys=xs-f'(xs)-1f(xs).

Step 2 計(jì)算

Step 3 s∶=s+1返回到Step 1.

由于節(jié)點(diǎn){wM,k}是關(guān)于原點(diǎn)對(duì)稱的,并且當(dāng)M為奇數(shù)時(shí),原點(diǎn)必是節(jié)點(diǎn),加上系數(shù)θM,k的取法,可得如下關(guān)系式

下面證明,上述建立的求解非線性方程組(1)的算法1是局部三次收斂的.假設(shè)α∈Rn是非線性方程組(1)的一個(gè)解,f在α的一個(gè)鄰域N(α)內(nèi)是充分連續(xù)可微的.對(duì)任意的x∈N(α),J(x)∈Rn×n為f在點(diǎn)x處的雅克比矩陣,即

這里假設(shè)J(x)對(duì)任意x∈N(α)都是非奇異的,并且定義H(x)為J(x)的逆矩陣.那么得到

其中δik是克羅內(nèi)克符號(hào)函數(shù).對(duì)等式(11)兩邊相對(duì)于xl求微分,可以得到

下面我們給出所需的兩個(gè)引理,類似于文獻(xiàn)[3]的證明過程,引理可以很容易地得到.

引理1 對(duì)任意x∈N(α),定義y(x)=(y1(x), …,yn(x))∈Rn為經(jīng)典牛頓法的迭代函數(shù):

有

和

成立.特殊的有

其中uMi(x)=(uMi1(x),uMi2(x),…,uMin(x))T∈Rn.那么有等式

和

成立.

接下來,我們給出算法1的局部三次收斂性定理.

定理1 函數(shù)f:N(α)?Rn→Rn在α∈Rn的一個(gè)鄰域N(α)內(nèi)是充分可微的,α是非線性方程組(1)的一個(gè)解.選取充分接近解α的初始值x0并且假設(shè)J(x)在鄰域N(α)內(nèi)是連續(xù)非奇異的.那么算法1產(chǎn)生的序列{xk}是三次收斂到α的.

證明 任意給定x∈N(α),我們定義W(x)= Z-1(x),這里

對(duì)每一個(gè)x∈Rn,定義g(x)∶=(g1(x),…,gn(x))T,其中

對(duì)每一個(gè)j∈{1,…,n},gj(x)在點(diǎn)α處泰勒展開

其中ejk=xjk-αjk.

首先,我們證明?gj(α)/?xk=0,j,k∈{1,2,…, n}.式(15)兩邊同時(shí)左乘Zij(x),

那么

應(yīng)用W(x)=Z-1(x),等式簡化為

對(duì)式(17)兩邊相對(duì)于xk求微分,應(yīng)用式(11)和引理1可得

上式中令x=α,應(yīng)用式(10)得

由假設(shè)J(x)對(duì)所有x∈N(α)都是非奇異的,所以有

接下來,我們證明?2gj(α)/(?xk?xl)=0,j,k,l ∈{1,2,…,n}.對(duì)式(18)兩邊相對(duì)于xl取微分,應(yīng)用式(11)和引理1,得到

令x=α并將式(19)代入到式(20)得,

另一方面,根據(jù)式(14),有

對(duì)方程(22)兩邊相對(duì)于xk取微分得到,

令x=α并應(yīng)用引理2,式(23)為

由于函數(shù)fi(x)是充分可微的,將式(24)代入到式(21)滿足

結(jié)合式(9),有

由假設(shè)J(α)是非奇異的,所以有

因此,由式(16),(19)和(25)可知算法1是三次收斂的.

定理2 如果定理1中的假設(shè)成立,M≥2并且f的坐標(biāo)函數(shù){fi}滿足?2fi(α)/(?xj?xk)=0,i,j,k ∈{1,2,…,n},那么算法1產(chǎn)生的序列{xk}是五階收斂到α的.

證明 我們首先證明?3gj(α)/(?xk?xl?xm)= 0,j,k,l,m∈{1,2,…,n}.對(duì)式(23)兩邊相對(duì)于xl取微分,并令x=α,應(yīng)用引理2計(jì)算可得

另一方面,對(duì)式(20)兩邊相對(duì)于xm取微分,然后令x=α由式(11),(19)和(25)和引理1得到

將式(26)代入到式(27)有

由假設(shè)M≥2,?2fi(α)/(?xj?xk)=0,i,j,k∈{1,2,…,n},通過式(7),(9)和(28)有

由J(α)的非奇異性,可得

類似的,我們證明?4gj(α)/(?xk?xl?xm?xr)= 0,j,k,l,m,r∈{1,2,…,n}.對(duì)式(23)兩邊求二次微分,然后令x=α應(yīng)用式(7),(8),引理2和假設(shè)?2fi(α)/(?xj?xk)=0,i,j,k∈{1,2,…,n},有

另一方面,對(duì)式(20)兩邊求二次微分,并令x=α應(yīng)用式(19),(25),(29)和引理1有

我們將式(30)代入到式(31)中,可得

由J(α)的非奇異性,有

由式(16),(19),(25),(29)和(32)可得算法1是五階收斂的.

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

下面例子1～3中,實(shí)驗(yàn)停止的標(biāo)準(zhǔn)設(shè)為

其中‖·‖∞指無窮范數(shù).如文獻(xiàn)[3]中一樣,方法的收斂階p由如下的近似值給出

例子1[3]考慮如下非線性方程組:

非線性方程組的解為α=(0.577 350,0.577 350, 0.577 350,-0.288 675)T.這里我們給出初始值為x0=(0.6,0.6,0.6,-0.2)T.

例子2[11]考慮如下非線性方程組:

非線性方程組的解為α=(1.478 489;2.386 312)T.這里我們給出初始值為x0=(1.2,2.0)T.

例子3[3]考慮如下非線性方程組:

非線性方程組的解為α=(0,0)T.這里我們給出初始值為x0=(0.4,0.4)T.

例子4[11]考慮如下非線性方程組:

非線性方程組的解為α=(0,0)T.這里我們給出初始值為x0=(0.5,1)T.

表1　例子1的數(shù)值結(jié)果(ε=10-11)Tab.1 Numerical result of example 1(ε=10-11)

表2　例子2的數(shù)值結(jié)果(ε=10-11)Tab.2 Numerical result of example 2(ε=10-11)

表3　例子3的數(shù)值結(jié)果(ε=10-11)Tab.3 Numerical result of example 3(ε=10-11)

表4　例子4的數(shù)值結(jié)果(ε=10-11)Tab.4 Numerical result of example 4(ε=10-11)

表1～4中IT.,‖xs+1-xs‖∞,和‖f(xs)‖∞分別表示算法迭代步數(shù)、算法最后兩步迭代點(diǎn)之間的距離,以及算法最后迭代值的殘差.表格1～4表示新算法1與牛頓法和牛頓-柯特斯方法作比較.例子3滿足溫和條件?2fi(α)/(?xj?xk)=0,i,j,k∈{1,2},定理2保證了算法的五階收斂性.從表格中我們可以看出新算法1仍然能保持很好的收斂性質(zhì),并且相對(duì)牛頓-柯特斯方法系數(shù)要求更自由.

參考文獻(xiàn):

[1] BABAJEE D K R,DAUHOO M Z,DARVISHI M T.et al.A note on the local convergence of iterative methods based on Adomian decomposition method and 3-node quadrature rule[J].Appl Math Comput,2008,200: 452-458.

[2] CORDERO A,TORREGROSA J R.Variants of Newton' s method for functions of several variables[J].Appl Math Comput,2006,183:199-208.

[3] CORDERO A,TORREGROSA J R.Variants of Newton' s method using fifth-order quadrature formulas[J].Appl Math Comput,2007,190:686-698.

[4] DARVISHI M T,BARATI A.A third-order Newton-type method to solve systems of nonlinear equations[J].Appl Math Comput,2007,187:630-635.

[5] GOLBABAI A,JAVIDI M.A new family of iterative methods for solving system of nonlinear algebric equations[J].Appl Math Comput,2007,190:1717-1722.

[6] NOOR M A.Some applications of Newton-Cotes formula for solving nonlinear equations[J].Int J Appl Math Eng Sci,2010,4:43-52.

[7] NOOR M A,WASEEM M.Variant of Newton method using fifth-order quadrature formula:revisited[J].J Appl Math&Inform,2009,27:1195-1209.

[8] SáNCHEZ M G,PERIS J M,GUTIéRREZ J M.Accelerated iterative methods for finding solutions of a system of nonlinear equations[J].Appl Math Comput,2007,190: 1815-1823.

[9] 蔣爾雄,趙風(fēng)光,蘇仰鋒.數(shù)值逼近[M].2版.上海:復(fù)旦大學(xué)出版社,2008:153-156.

[10] ORTEGA J M,RHEINBOLDT W C.Iterative solution of nonlinear equations in several variables[M].New York:Academic Press,1970:181-239.

[11] WANG H.New third-order method for solving systems of nonlinear equations[J].Numer Algor,2009,50(3): 271-282.

Uniform-coefficient Quadrature-based Iterative Methods for Solving Nonlinear Equations

YAO Tengteng
(School of Mathematical Sciences,Xiamen University,Xiamen 361005,China)

Abstract:In this paper,we present a new variant of Newton's method for solving nonlinear equations based on uniform-coefficient quadrature formulas.The cubic convergence of the proposed algorithm is established.Moreover,the fifth-order convergence is proved under some mild conditions.Some numerical experiments are reported to illustrate the effectiveness and the flexibility of our algorithm.

Key words:uniform coefficient quadrature;newton-type method;nonlinear equations;cubic convergence

收稿日期:2015-05-27 錄用日期:2015-11-24

doi:10.6043/j.issn.0438-0479.2016.02.013

中圖分類號(hào):O 151.23

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):0438-0479(2016)02-0221-06

Email:yaotengteng718@163.com

引文格式:姚騰騰.基于一致系數(shù)求積的廣義牛頓法求解非線性方程組[J].廈門大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,55(2):221-226.

Citation:YAO T T.Uniform-coefficient quadrature-based iterative methods for solving nonlinear equations[J].Journal of Xiamen University(Natural Science),2016,55(2):221-226.(in Chinese)

考慮如下非線性方程組: