求解對稱非線性方程組的兩種修正MHS無導(dǎo)數(shù)型共軛梯度法

沈冬梅，楊忠選

(1.南昌工學(xué)院 教育學(xué)院，江西 南昌 330108;2.華東交通大學(xué) 理學(xué)院，江西 南昌 330108)

考慮對稱非線性方程組(1)的求解問題

F(x)=0，

(1)

式中：F:Rn→Rn為連續(xù)可微函數(shù)，其雅克比矩陣是對稱的，即J(x)=J(x)T。

對稱非線性方程組(1)的求解已被廣泛研究。Li和Fukushima[1]提出了利用Gauss-Newton-based BFGS的Derivative-Free(無導(dǎo)數(shù))線性搜索求解對稱非線性方程組，并證明了算法的全局收斂性。文獻(xiàn)[2-5]分別利用無導(dǎo)數(shù)修正FR算法、無導(dǎo)數(shù)修正PRP算法、無導(dǎo)數(shù)修正CD算法、無導(dǎo)數(shù)修正HS算法求解對稱非線性方程組，并證明了算法的全局收斂性。Zhou和Shen[6]提出了兩種近似PRP型無導(dǎo)數(shù)方法，并用于求解該問題，同時證明其具有全局收斂性。徐瑞昌[7]利用修正的BFGS算法求解對稱非線性方程組，并指出算法具有全局收斂性和超線性收斂速度。沈冬梅等[8]證明了近似PRP算法具有超線性收斂速度。Abubakar等[9]提出了一個修正的Dai-Liao共軛梯度法用于求解對稱非線性方程組，并證明了該算法的全局收斂性。Zhou[10]提出了求解對稱線性方程組的無導(dǎo)數(shù)MBFGS擬牛頓法，并證明該算法的全局收斂性。Sabi’u等[11]構(gòu)造了一個修正的PRP共軛梯度法求解大規(guī)模的非線性對稱方程組，并證明了其全局收斂性。

本文繼續(xù)研究求解對稱非線性方程組的下降無導(dǎo)數(shù)共軛梯度算法。這里首先回顧文獻(xiàn)[12]提出的兩種修正的HS算法，分別為修正的MHS共軛梯度法算法(簡稱為MTTHS算法)和保守的MHS共軛梯度法算法(簡稱為CTTHS):

xk+1=xk+λkdk

(2)

(3)

式中：?f(xk)為f(x)在xk處的梯度，sk=xk+1-xk=λkdk，yk-1=?f(xk)-?f(xk-1)，

(4)

式中：r≥0及t>0均為常數(shù)。

這兩種算法的顯著特點(diǎn)是在不依賴于任何線性搜索的條件下均能產(chǎn)生下降方向，即

1 修正的MHS無導(dǎo)數(shù)型共軛梯度算法

對稱非線性方程組(1)的求解可轉(zhuǎn)化為如下無約束極小化問題：

(5)

然而，由(5)式定義的f(x)的梯度為?f(x)=J(x)TF(x)=J(x)F(x)，其雅克比矩陣的計(jì)算量較大，顯然不適合計(jì)算大規(guī)模問題。為避免計(jì)算復(fù)雜的梯度，文獻(xiàn)[1]提出了一種近似梯度，即

(6)

顯然，

(7)

本文利用近似梯度函數(shù)gk的計(jì)算方式，建立求解對稱非線性方程組的MTTHS和CTTHS無導(dǎo)數(shù)型共軛梯度法。這里我們通過以下兩個過程確定MTTHS無導(dǎo)數(shù)型共軛梯度法的搜索方向和搜索步長。

過程1 確定MTTHS無導(dǎo)數(shù)型共軛梯度法搜索方向：

將(6)式運(yùn)用到MTTHS共軛梯度法中，把最速下降方向-?f(xk-1)、-?f(xk)對應(yīng)的替換為-gk-1、-gk，得到MTTHS無導(dǎo)數(shù)型共軛梯度法的搜索方向，即

(8)

這表明當(dāng)λ充分小時，dk(λ)是問題(5)中函數(shù)f(x)在xk處的下降方向。

過程2 確定MTTHS無導(dǎo)數(shù)型共軛梯度法的步長因子：

對于搜索方向dk(λ)中的步長λ，借用文獻(xiàn)[13] 的方式，令λ=max{ρj，j=0， 1， 2 …}滿足下列不等式:

(9)

基于搜索方向和步長的確定，建立求解(5)的MTTHS型無導(dǎo)數(shù)算法，步驟如下：

算法1 (MTTHS無導(dǎo)數(shù)型共軛梯度法)

步驟1 給定初始點(diǎn)x0∈Rn，參數(shù)0<ρ<1，σ1>0和σ2>0，令k:=0；

步驟2 利用(8)式計(jì)算搜索方向dk；

步驟3 通過(9)式計(jì)算步長因子λk；

步驟4 令xk+1=xk+λkdk；

步驟5 令k:=k+1，轉(zhuǎn)步驟2。

類似于MTTHS型無導(dǎo)數(shù)共軛梯度法搜索方向和步長的確定方式，可得到CTTHS型無導(dǎo)數(shù)共軛梯度法算法。

算法2 (CTTHS無導(dǎo)數(shù)型共軛梯度法)

步驟1 給定初始點(diǎn)x0∈Rn，參數(shù)0<ρ<1，σ1>0和σ2>0，ε1>0，r>0，令k:=0；

步驟2 按照下式計(jì)算搜索方向dk：

(10)

步驟3 利用(9)式計(jì)算搜索步長λk；

步驟4 令xk+1=xk+λkdk；

步驟5 令k:=k+1，轉(zhuǎn)步驟2。

2 算法的全局收斂性

假設(shè)A

2)F(x)=0為對稱非線性方程組；

由假設(shè)A知，對x，y∈N有，

引理2[13]設(shè)序列{xk}由MTTHS無導(dǎo)數(shù)型共軛梯度法或CTTHS無導(dǎo)數(shù)型共軛梯度法產(chǎn)生，則

引理3[13]設(shè)假設(shè)A 的條件成立，序列{xk}由MTTHS無導(dǎo)數(shù)型共軛梯度法或CTTHS無導(dǎo)數(shù)型共軛梯度法產(chǎn)生，則有

(11)

L2F(xk)≤γ1L2=L。

由zk的定義得

因此，我們有

下面的引理表明搜索方向dk有界。

(12)

證明由dk的定義易有

下面的定理表明MTTHS無導(dǎo)數(shù)型共軛梯度算法具有全局收斂性。

(13)

證明(反證法) 假設(shè)(13)式不成立，則存在一個正常數(shù)τ使得

(14)

由?f(xk)=F′(xk)TF(xk)和(14)式知，存在常數(shù)τ1>0，使得

這意味著

(15)

另一方面，由中值定理，存在一個常數(shù)tk∈(0，1)，使得

(16)

(17)

(18)

又因?yàn)閧xk}?Ω有界，不妨假設(shè)xk→x*，由(6)、(8)和(17)、(18)式，我們有

(19)

(20)

下面的定理表明CTTHS無導(dǎo)數(shù)型共軛梯度算法具有全局收斂性。

這意味著

(21)

另一方面，由中值定理，存在一個常數(shù)

(22)

(23)

另一方面，我們有

(24)

由(21)-(24)式，我們得到

故假設(shè)不成立，原命題成立，即證。

3 數(shù)值試驗(yàn)

為考察MTTHS無導(dǎo)數(shù)型共軛梯度法和CTTHS無導(dǎo)數(shù)型共軛梯度法的數(shù)值表現(xiàn)，用Matlab編程如下對稱非線性方程組問題進(jìn)行測試，見表1。數(shù)值結(jié)果表明，本文提出的MTTHS無導(dǎo)數(shù)型共軛梯度法與CTTHS無導(dǎo)數(shù)型共軛梯度法均具有良好的數(shù)值效果，主要表現(xiàn)在搜索方向是下降方向，且一如既往的具有占用內(nèi)存低、迭代次數(shù)少，計(jì)算速度快的優(yōu)勢，同時也反映出修正的MHS方法的計(jì)算表現(xiàn)與近似PRP算法1很類似(該算法的搜索方向不一定均為下降方向)，是求解大規(guī)模對稱非線性方程組的有效算法。

測試問題1：F(x)=Ax+f(x)，其f(x)=(ex1-1，…，exn-1)T，矩陣A由文獻(xiàn)[13]給出。

4 結(jié)束語

針對求解對稱非線性方程組問題，本文利用近似梯度代替精確梯度，構(gòu)造了MTTHS無導(dǎo)數(shù)型和CTTHS無導(dǎo)數(shù)型的共軛梯度法。這兩個算法的搜索方向均為下降方向，且由于利用近似梯度代替精確梯度，避免了梯度的復(fù)雜計(jì)算，從而適用于大規(guī)模對稱非線性方程組問題。在適當(dāng)?shù)臈l件下，證明了這兩種算法的全局收斂性，這兩種算法的搜索方向均為下降方向，且具有較好的數(shù)值表現(xiàn)。

表1 算法的數(shù)值結(jié)果