求解非線性方程組的一種非精確Broyden方法*

伍佩鈺 張麗

（長沙理工大學數學與統計學院，長沙，410004）

考慮如下非線性方程組

基于文獻［8］中的精確Broyden方法，我們提出如下求解問題（1.1）的非精確　Broyden方法.

算法1 （非精確Broyden方法）

步1：若F（xk）=0，則算法停止.否則，按（2.1）和（2.2）非精確求解線性方程組BkP　+ F（xk）=0，得到其近似解pk：

求解非線性方程組的一種非精確Broyden方法*

伍佩鈺 張麗

（長沙理工大學數學與統計學院，長沙，410004）

本文提出了求解非線性方程組的一種非精確Broyden方法.該方法是文獻［8］中精確Broyden方法的推廣.在適當的條件下，我們證明了非精確Broyden方法具有全局收斂性和超線性收斂性.數值實驗表明，該方法效果較好.

非線性方程組 非精確Broyden方法 全局收斂 超線性收斂

1　引言

考慮如下非線性方程組

其中F=（F1，F2，…，Fn）T：Rn→Rn是連續可微的函數.

關于問題（1.1）的數值方法研究是計算數學與優化領域的重要課題［1，5，6］.對于中小型問題，牛頓法、擬牛頓法等都是行之有效的方法［10］.Broyden方法是求解方程組（1.1）的一種重要的擬牛頓方法.1965年，Broyden［2］第一次提出求解非線性方程組的擬牛頓法，因其好的局部收斂性［2，3，4］，很快受到學者們的青睞，但是對求解非線性方程組的全局收斂性的結果卻較少.Griewank［7］在1986年研究了非線性方程組的Broyden方法的全局收斂性，并提出了一種無導數的線性搜索，同時證明了Broyden方法在該線性搜索下的全局收斂.Li和Fukushima［8］構造了一個反例表明Griewank的線性搜索是不適定的.為克服此缺陷，Li和Fukushima［8］提出了一種稱為近似范數下降的無導數線性搜索，在適當的條件下，證明了求解非線性方程組Broyden方法的全局收斂性.但該方法中每一步都要精確求解一個線性方程組BkP+F（xk）=0，當方程組（1.1）的變量個數比較多時，精確求解該子問題的計算量較大.

本文提出了一種非精確Broyden方法，對子問題進行非精確求解，在適當的條件下，我們證明了算法具有全局收斂性和超線性收斂性.

2　算法

基于文獻［8］中的精確Broyden方法，我們提出如下求解問題（1.1）的非精確Broyden方法.

算法1 （非精確Broyden方法）

步1：若F（xk）=0，則算法停止.否則，按（2.1）和（2.2）非精確求解線性方程組BkP+ F（xk）=0，得到其近似解pk：

其中

步2：若

成立，則令λk=1，轉步4.

步3：按如下線性搜索計算步長因子λk，即λk=max｛1，β，β2，…｝滿足不等式

步4：令xk+1=xk+λkpk.

步5：按如下Broyden修正公式計算Bk+1：

步6：令k=k+1，轉步1.

注記 ①在步1中，若對任意k，rk=0，則算法1退化為文獻［8］中的精確Broyden方法.②不等式（2.4）對任意充分小的λ＞0恒成立，且對任意k有

3　全局收斂性

為了得到算法1的全局收斂性，做如下假設假設A

（ii）F′（x）在Ω上Lipschitz連續，即存在常數L＞0，使得

（iii）對?x ∈Ω，F′（x）非奇異.

類似于文獻［8］中的證明，我們有如下引理.

引理1［8］由算法1產生的序列｛xk｝?Ω.

證明 由（2.6）可得，對任意的k有

由（2.3）和（2.4）可得，對任意的k有

引理4［8］設正數序列和滿足

為了后續的分析，記

則yk=Ak+1sk，代入（2.5）得

定義

由yk=Ak+1sk，得

引理5［8］設假設A中（i）和（ii）成立，且xk｛｝由算法1產生.

特別地，存在｛ζk｝的一個子列收斂于0.

下面證明算法1的全局收斂性.

定理1 設假設A成立，則算法1產生的點列xk｛｝收斂于問題（1.1）的唯一解.

情況一：若有無窮多個k，λk由（2.3）確定，記這無窮多個k構成的集合為K=｛i1，i2，…｝.則當k ∈K時，‖F（xk+1）‖≤ρ‖F（xk）‖；當k ?K時，由（2.4）得‖F（xk+1）‖≤（1+ ηk）‖F（xk）‖；

情況二：設對充分大的k，λk由（2.4）確定，設Ak+1由（3.3）定義，ζk由（3.5）定義.

由（3.1）及引理5知，存在｛ζk｝的子列｛ζk｝k∈K收斂于0，因｛xk｝k∈K?Ω有界，不妨假設序列收斂于x-，又由（3.1）得sk=xk+1-xk→0，則｛Ak+1｝k∈K收斂于F′（x-），因此存在常數M1＞0，對?k ∈K充分大時‖Ak+1‖-1≤M1，由（2.1）和（3.6）知

故存在常數C1＞0，使得對?k∈K充分大時，有

又因u0＜1，得到F（x-）=0.證畢.

4　超線性收斂

下面證明超線性收斂性，為此先證明如下引理.

證明 由算法1中的步2，可得存在一個常數ζ＞0，使得當ζk≤ζ且k充分大時（4.1）成立.由定理1可得xk｛｝收斂于問題（1.1）的唯一解x*，且存在一個常數M2＞0，對充分大的k，使得‖Ak+1‖-1≤M2.類似于（3.11）的證明，存在一個常數ζ′＞0，C2＞0，當ζk≤ζ′且k充分大時，有

由（2.1）可得

從而有

其中M3＞0為在Ω中的一個上界，且第二個不等式由（3.6）推得，第三個不等式由（4.2）推得.由此可得

又由F′（x*）的非奇異性與xk→x*，則存在常數m＞0，對所有充分大的k，使得成立.

由（4.2），（4.4），（4.5）可得，當ζk≤ζ′時，

下面證明算法1的超線性收斂性.

當i?Ik時，取i從k′到k，則有

5　數值實驗及結果分析

我們對算法1進行數值實驗，檢驗其數值結果.利用MATLAB7.0編程，程序在3.2GHZ處理器，2GB內存的電腦上實現.算法終止條件為‖F（xk）‖≤10-4，問題（2.1）的求解采用Matlab中的GMRES（A，B，RESTART，TOL）計算.數值結果見下表，表中：n表示測試問題的維數，iter表示算法迭代的次數，‖F（xk）‖表示終止時剩余范數，time表示算法計算所需時間（單位為秒）.

測試問題如下：

問題1 離散的兩點邊界值問題［11］：

問題2 F由下式定義［12］：

實驗結果如下：

上表的數值結果表明，非精確Broyden方法成功求解問題1和問題2，當問題的維數較大時，需要迭代的次數和計算的時間也增加，問題2比問題1的數值表現更好.總的來說，我們的非精確Broyden方法效果較好.

［1］袁亞湘，孫文瑜.最優化理論與方法［M］.北京：科學出版社，2001，12-130.

［2］Broyden C.G.，A class of methods for solving nonlinear simultaneous equations［J］.Mathematics of Computation，1965，19（2）：57-593.

［3］Dennis J.E.，MoréJ.J.，A characterization of superlinear convergence and its application to quasi-Newton methods［J］.Mathematics of Computation，1974，8（2）：549-560.

［4］Broyden C.G.，Dennis J.E.，MoréJ.J.，On the local and superlinear convergence of quasi-Newton methods［J］.Journal of Institute of Mathematics and Applications，1973，12（1）：223-246.

［5］Dennis J.E.，Schnabel R.B.，Numerieal methods for uneonstrained Optimization and nonlinear equations［M］.Englewood Cliffs：Prentiee-Hall Press，1983，10-180.

［6］Ortega J.M.，Rheinboldt W.C.，Iterative solution of nonlinear equations in several variables［M］.Beijing：Academic Press，1970，1-200.

［7］Griewank A.，The’global’convergence of Broyden-like methods with a suitable line search.Austral［J］. Anziam Journal，1986，28（1）：75-92.

［8］Li D.H.，Fukushima M.，A Derivative-Free line Search and Global Convergence of Broyden-like Method for Nonlinear Equations［J］.Optimization Methods and Software，1999，13：181-201.

［9］Li D.H.，Fukushima M.，Smoothing Newton and Quasi-Newton Methods for Mixed Comple-mentarity Problems［J］.Computational Optimization and Applications，2000，17：203-230.

［10］周偉軍.擬牛頓法及其收斂性：［湖南大學博士學位論文］.長沙：湖南大學，2006，9-16.

［11］Li D.H.，Fukushima M.，A globally and superlinearly convergent Gauss-Newton based BFGS method for symmetric nonlinear equations.SIAM Journal on Numerical Analysis，1999，37（1）：152-172.

［12］Li Q.，Li D.，A class of derivative-free methods for large-scale nonlinear monotone equations.IMA Journal of Numerical Analysis，2011，31（4）：1625-1635.

An Inexact Broyden Method for Nonlinear Equations

Wu Peiyu Zhang Li
（School of Mathematics and Statistics，Changsha University of Science and Technology，Changsha 410004，China）

This paper introduces an inexact Broyden method for solving nonlinear equations，which is an extension of the method in［8］.Under appropriate conditions，we prove that the proposed method converges globally and superlinearly.Numerical results are given to show its efficiency.

Nonlinear equations Inexact Broyden method Global convergence Superlinear convergence

湖南省自然科學基金項目（14JJ3084）和湖南省教育廳科學研究項目（13B137）資助

2016年05月30日