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

伍佩鈺 張麗

（長(zhǎng)沙理工大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，長(zhǎng)沙，410004）

考慮如下非線性方程組

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

算法1 （非精確Broyden方法）

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

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

伍佩鈺 張麗

（長(zhǎng)沙理工大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，長(zhǎng)沙，410004）

本文提出了求解非線性方程組的一種非精確Broyden方法.該方法是文獻(xiàn)［8］中精確Broyden方法的推廣.在適當(dāng)?shù)臈l件下，我們證明了非精確Broyden方法具有全局收斂性和超線性收斂性.數(shù)值實(shí)驗(yàn)表明，該方法效果較好.

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

1　引言

考慮如下非線性方程組

其中F=（F1，F(xiàn)2，…，F(xiàn)n）T：Rn→Rn是連續(xù)可微的函數(shù).

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

本文提出了一種非精確Broyden方法，對(duì)子問(wèn)題進(jìn)行非精確求解，在適當(dāng)?shù)臈l件下，我們證明了算法具有全局收斂性和超線性收斂性.

2　算法

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

算法1 （非精確Broyden方法）

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

其中

步2：若

成立，則令λk=1，轉(zhuǎn)步4.

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

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

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

步6：令k=k+1，轉(zhuǎn)步1.

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

3　全局收斂性

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

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

（iii）對(duì)?x ∈Ω，F(xiàn)′（x）非奇異.

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

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

證明 由（2.6）可得，對(duì)任意的k有

由（2.3）和（2.4）可得，對(duì)任意的k有

引理4［8］設(shè)正數(shù)序列和滿足

為了后續(xù)的分析，記

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

定義

由yk=Ak+1sk，得

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

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

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

定理1 設(shè)假設(shè)A成立，則算法1產(chǎn)生的點(diǎn)列xk｛｝收斂于問(wèn)題（1.1）的唯一解.

情況一：若有無(wú)窮多個(gè)k，λk由（2.3）確定，記這無(wú)窮多個(gè)k構(gòu)成的集合為K=｛i1，i2，…｝.則當(dāng)k ∈K時(shí)，‖F(xiàn)（xk+1）‖≤ρ‖F(xiàn)（xk）‖；當(dāng)k ?K時(shí)，由（2.4）得‖F(xiàn)（xk+1）‖≤（1+ ηk）‖F(xiàn)（xk）‖；

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

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

故存在常數(shù)C1＞0，使得對(duì)?k∈K充分大時(shí)，有

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

4　超線性收斂

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

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

由（2.1）可得

從而有

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

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

由（4.2），（4.4），（4.5）可得，當(dāng)ζk≤ζ′時(shí)，

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

當(dāng)i?Ik時(shí)，取i從k′到k，則有

5　數(shù)值實(shí)驗(yàn)及結(jié)果分析

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

測(cè)試問(wèn)題如下：

問(wèn)題1 離散的兩點(diǎn)邊界值問(wèn)題［11］：

問(wèn)題2 F由下式定義［12］：

實(shí)驗(yàn)結(jié)果如下：

上表的數(shù)值結(jié)果表明，非精確Broyden方法成功求解問(wèn)題1和問(wèn)題2，當(dāng)問(wèn)題的維數(shù)較大時(shí)，需要迭代的次數(shù)和計(jì)算的時(shí)間也增加，問(wèn)題2比問(wèn)題1的數(shù)值表現(xiàn)更好.總的來(lái)說(shuō)，我們的非精確Broyden方法效果較好.

［1］袁亞湘，孫文瑜.最優(yōu)化理論與方法［M］.北京：科學(xué)出版社，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.，F(xiàn)ukushima 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.，F(xiàn)ukushima M.，Smoothing Newton and Quasi-Newton Methods for Mixed Comple-mentarity Problems［J］.Computational Optimization and Applications，2000，17：203-230.

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

［11］Li D.H.，F(xiàn)ukushima 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

湖南省自然科學(xué)基金項(xiàng)目（14JJ3084）和湖南省教育廳科學(xué)研究項(xiàng)目（13B137）資助

2016年05月30日