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

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

?

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

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

摘要:采用一致系數(shù)求積公式近似逼近泰勒余項,得到一種新的求解非線性方程組的廣義牛頓法.給出算法的一般形式,證明算法是三階收斂的,并且在一定的溫和條件下可以達到五階收斂.最后,給出數(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分解、同倫攝動、牛頓柯特斯求積等技巧求解非線性方程組(1)的牛頓衍生算法[1-8],這些方法相較于牛頓法具有更高的收斂性.在本文中,我們提出一種新的廣義牛頓迭代算法,即采用基于一致系數(shù)求積的牛頓法求解非線性方程組(1).此廣義牛頓迭代法只需要估計f(x)以及它在不同點處的雅可比矩陣即可.數(shù)值實驗表明,這個迭代算法是三次收斂的并且在一定的溫和條件下可達到五階收斂.

1　預(yù)備知識

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

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

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

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

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

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

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

其中

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

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

以及

成立.

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

2　算法及其收斂性分析

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

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

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

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

Step 2 計算

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

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

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

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

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

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

引理1 對任意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的一個鄰域N(α)內(nèi)是充分可微的,α是非線性方程組(1)的一個解.選取充分接近解α的初始值x0并且假設(shè)J(x)在鄰域N(α)內(nèi)是連續(xù)非奇異的.那么算法1產(chǎn)生的序列{xk}是三次收斂到α的.

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

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

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

其中ejk=xjk-αjk.

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

那么

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

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

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

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

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

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

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

對方程(22)兩邊相對于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的坐標函數(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}.對式(23)兩邊相對于xl取微分,并令x=α,應(yīng)用引理2計算可得

另一方面,對式(20)兩邊相對于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}.對式(23)兩邊求二次微分,然后令x=α應(yīng)用式(7),(8),引理2和假設(shè)?2fi(α)/(?xj?xk)=0,i,j,k∈{1,2,…,n},有

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

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

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

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

3 數(shù)值實驗

下面例子1～3中,實驗停止的標準設(shè)為

其中‖·‖∞指無窮范數(shù).如文獻[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ù)、算法最后兩步迭代點之間的距離,以及算法最后迭代值的殘差.表格1～4表示新算法1與牛頓法和牛頓-柯特斯方法作比較.例子3滿足溫和條件?2fi(α)/(?xj?xk)=0,i,j,k∈{1,2},定理2保證了算法的五階收斂性.從表格中我們可以看出新算法1仍然能保持很好的收斂性質(zhì),并且相對牛頓-柯特斯方法系數(shù)要求更自由.

參考文獻:

[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

中圖分類號:O 151.23

文獻標志碼:A

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

Email:yaotengteng718@163.com

引文格式:姚騰騰.基于一致系數(shù)求積的廣義牛頓法求解非線性方程組[J].廈門大學(xué)學(xué)報(自然科學(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)

考慮如下非線性方程組: