求解對稱非線性方程組的兩種修正MHS無導數型共軛梯度法

沈冬梅，楊忠選

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

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

F(x)=0，

(1)

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

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

本文繼續研究求解對稱非線性方程組的下降無導數共軛梯度算法。這里首先回顧文獻[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均為常數。

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

1 修正的MHS無導數型共軛梯度算法

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

(5)

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

(6)

顯然，

(7)

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

過程1 確定MTTHS無導數型共軛梯度法搜索方向：

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

(8)

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

過程2 確定MTTHS無導數型共軛梯度法的步長因子：

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

(9)

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

算法1 (MTTHS無導數型共軛梯度法)

步驟1 給定初始點x0∈Rn，參數0<ρ<1，σ1>0和σ2>0，令k:=0；

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

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

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

步驟5 令k:=k+1，轉步驟2。

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

算法2 (CTTHS無導數型共軛梯度法)

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

步驟2 按照下式計算搜索方向dk：

(10)

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

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

步驟5 令k:=k+1，轉步驟2。

2 算法的全局收斂性

假設A

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

由假設A知，對x，y∈N有，

引理2[13]設序列{xk}由MTTHS無導數型共軛梯度法或CTTHS無導數型共軛梯度法產生，則

引理3[13]設假設A 的條件成立，序列{xk}由MTTHS無導數型共軛梯度法或CTTHS無導數型共軛梯度法產生，則有

(11)

L2F(xk)≤γ1L2=L。

由zk的定義得

因此，我們有

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

(12)

證明由dk的定義易有

下面的定理表明MTTHS無導數型共軛梯度算法具有全局收斂性。

(13)

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

(14)

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

這意味著

(15)

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

(16)

(17)

(18)

又因為{xk}?Ω有界，不妨假設xk→x*，由(6)、(8)和(17)、(18)式，我們有

(19)

(20)

下面的定理表明CTTHS無導數型共軛梯度算法具有全局收斂性。

這意味著

(21)

另一方面，由中值定理，存在一個常數

(22)

(23)

另一方面，我們有

(24)

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

故假設不成立，原命題成立，即證。

3 數值試驗

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

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

4 結束語

針對求解對稱非線性方程組問題，本文利用近似梯度代替精確梯度，構造了MTTHS無導數型和CTTHS無導數型的共軛梯度法。這兩個算法的搜索方向均為下降方向，且由于利用近似梯度代替精確梯度，避免了梯度的復雜計算，從而適用于大規模對稱非線性方程組問題。在適當的條件下，證明了這兩種算法的全局收斂性，這兩種算法的搜索方向均為下降方向，且具有較好的數值表現。

表1 算法的數值結果