周 童，陳 亮，伍珍香

（淮北師范大學 數(shù)學科學學院，安徽 淮北235000）

0 引言

本文主要討論非線性方程組

的解的問題，其中F( x ):Rn→Rn是連續(xù)可微函數(shù). 由于F(x)是非線性函數(shù)，方程組（1）可能會沒有解，因此本文假設方程組（1）解集非空并設其為X*.

Levenberg-Marquardt 方法（LM）［1-3］是求解方程組（1）的經(jīng)典方法之一，LM方法通過如下公式給出搜索方向

其中：Fk=F( xk),Jk=F′( xk),μk≥0. 由于是正定矩陣，因此式（2）有唯一解dk，而且搜索方向dk是優(yōu)化函數(shù)

的下降方向，其中φ( x ):Rn→R. 可以證明由LM方法產(chǎn)生的序列的任意聚點是φ 的穩(wěn)定點，即

因此如果F′( x*)是非奇異的，則x*是方程組（1）的解. 然而對于收斂性來說，F(xiàn)′( x*)是非奇異這一條件過強，因此本文使用局部誤差界這一弱條件代替非奇異. 局部誤差界定義如下.

定義1設N 是Rn的子集且X*∩N ≠0，如果存在c ≥0，有

成立，則稱‖F(xiàn)( x)‖ 為方程組（1）提供了一個在N 上的局部誤差界.

對于式（2）參數(shù)μk有不同的選擇，如當時，Dennis 等［4］給予證明，當μk=‖F(xiàn)( x )‖時，F(xiàn)an等［5］證明LM的二階收斂，同時在皆為局部誤差界的條件下，也有一些結果，如當μk=αk‖ Fk‖時，F(xiàn)an［6］證明了局部二階收斂；當時，楊柳等［7］證明局部二階收斂；當（0 ≤θ ≤1）時，Ma［8］證明局部二階收斂；當時，張華仁等［9］證明局部二階收斂；當μk=‖ Fk‖2時，Yamashita等［10］很好地證明LM二階收斂，由于參數(shù)的選擇使算法的迭代次數(shù)過多，因此，本文對參數(shù)進行了改進，使其迭代次數(shù)減少. 在本文中設

與文獻［10］相比，由于考慮了‖ Fk‖的取值情形，使參數(shù)總是小于等于1，避免迭代步過大，提高計算效率，數(shù)值實驗也顯示了迭代次數(shù)減少.

1 LMM的收斂速率

本節(jié)研究LM方法的局部收斂性，公式為

其中dk是線性方程（2）的解.

定義一個二次函數(shù)

其中：θk:Rn→R，F(xiàn)k=F(xk),Jk=F′( xk). 由于函數(shù)（8）是嚴格凸的，所以無約束最小值問題

等價于線性方程（2）. 為證明LM方法的收斂性，先給出一些假設條件.

假設1對于x*∈X*，以下條件［11］（i）和（ii）成立：

（i）存在b ∈( 0,1),c1∈(0,∞)，有

（ii）如果存在一個常數(shù)c2∈(0,∞)，使得

則稱對于式（1），‖F(xiàn)( x )‖在N( x*,b) 上提供一個局部誤差界.

當F 是連續(xù)可微的且J 是Lipschitz連續(xù)的，由假設1（i），存在一個常數(shù)L，使得

在上述假設和LM參數(shù)的設定下，證明以下引理.

引理1設假設1成立，則存在常數(shù)p,q，使得

證明下面分2種情況討論.

第1 種 情 況：當‖ Fk‖≤1 時，μk=‖ Fk‖δ. 由 假 設1（ii）知，c2dist(x,X*)≤‖ F( x )‖，所 以，又由式（12）知，‖ F( x )-F( y )‖≤L‖x-y ‖，因為μk=‖ Fk‖δ，所以有μk≤Lδdist(xk,X*)δ.

第2種情況：當‖ Fk‖＞1時，μk=‖ Fk‖-δ＜1. 由上式可得，μk≥L-δdist(xk,X*)-δ.

引理2設假設1成立且參數(shù)μk由上述給出，如果，則式（2）的解dk滿足

證明由于dk是式（9）的解，所以有

假設{ xk} 收斂到x*，秩［12］(J(x*))=r，將J(x*)進行SVD分解

由于‖ Fk‖的不同，下面將分成2種情況討論.

1.1 第1種情況：‖ Fk ‖≤1

引理3假設F(x)是連續(xù)可微的，J(x)和F(x)是Lipschitz連續(xù)的，則

證明證明過程與文獻［13］引理4.1的證明類似，這里不予證明.

引理4假設F(x)是連續(xù)可微，J(x)和F(x)是Lipschitz連續(xù)的，則

證明通過Jk的SVD分解，有，并且有

因為假設{ xk} 收斂到x*，假設，因此當‖ Fk‖≤1時，

引理5如果，則有

證明由條件知,，且xk=xk-1+dk-1，因此由假設1（i）（ii）和引理2可以得到

由引理4知，存在常數(shù)c4＞0，有，所以

引理6如果x0∈N(X*,r1) ，則對于所有的k，有

證明由數(shù)學歸納法知，當k=0 時，由引理2有

所以有xk+1，引理得證.

下面將給出LM方法的二階收斂性定理.

定理1若假設1成立，x0∈N( X*,r1) ，且{ xk} 是由LM方法產(chǎn)生的一組序列，則{dist(xk,X*)} 二次收斂到0，同時序列{ xk} 收斂到解

證明引理3和引理4已經(jīng)證明定理的第1部分. 接下來只需要證明定理的第2部分，即序列{xk} 收斂到解. 因為收斂到0且對于所有的k，有，足以說明{xk}收斂. 因為對于所有k ≥1,有，所以任意i,j ∈N+,i ≥j，有

這意味著序列{ xk} 是Cauchy序列，因此{ xk} 收斂.

1.2 第2種情況：‖ Fk ‖＞1

引理7如果xk,xk-1，dist(xk-1,X*)≤r2＜1，則有

證明由條件知，，且xk=xk-1+dk-1，由假設1（i）（ii）和引理2可以得到

又因為

所以當‖ Fk‖＞1時，

故

所以dist(xk,X*)≤c5dist(xk-1,X*)，其中，引理得證.

引理8如果，則對于所有的k，有

證明由數(shù)學歸納法知，當k=0 時，由引理2有

則

定理2設假設1成立，且是由LM方法產(chǎn)生的序列，則線性收斂到0，同時序列{ xk} 收斂到解

證明證明過程與定理1證明類似，省略.

2 數(shù)值結果

在本節(jié)中，本文要進行數(shù)值實驗用來驗證文章中所提出的自適應性Levenberg-Marquardt方法，LM方法的算法在文獻［9］給出，它選擇參數(shù)μk=‖ Fk‖2很好地證明了二階收斂，但迭代次數(shù)過多，因此本文進行改進，使迭代次數(shù)減少.

考慮由非奇異問題［14-15］改編的非線性方程組，其中：F( x )是標 準的非奇異測試 函 數(shù)，x*是其 根，A ∈Rn×k是列 滿 秩，1 ≤k ≤n. 很容易看出，且的秩為n-k. 問題的不足之處是使的解可能不是F(x )=0 的解. 現(xiàn)在考慮的秩為n-1的奇異問題.

下面給出相關矩陣，A ∈Rn,AT=(1 ,1,…,1) .

根據(jù)在LM 方法和ALM（Adaptive Levenberg-Marquardt,ALM）方法中定義的δ 的不同，本文將在LM方法中取δ 為2，ALM 方法分別取δ 為1，1.5 和2. 2 個算法終止條件是相同的，都是，或者迭代次數(shù)不超過100（n+1），則對于秩為n-1 的數(shù)值結果為表1. 在第3 列中的1，10 和100 與起始點x0，10 x0和100 x0相聯(lián)系，其中x0被建議使用［14］. 如果相應的方法在規(guī)定的最大迭代次數(shù)內(nèi)失敗于達到所需的精度，則用“-”表示. 為保障數(shù)值的穩(wěn)定性，需要使用MATLAB中的pcg函數(shù)來解決式（2）的問題.

從2個算法的直觀結果來看，在LM方法中x0=1 或10時迭代次數(shù)較少，但當x0=100 時算法收斂但迭代次數(shù)較多，而ALM方法將參數(shù)重新選擇，則在所需的最大迭代次數(shù)內(nèi)收斂時的迭代次數(shù)要少于LM方法的迭代次數(shù)，尤其是指數(shù)同為2時，可以得到ALM方法的有效性.

表1 Rank( J( x* ))=n-1

3 總結

本文主要介紹用具有自適應性參數(shù)的Levenberg-Marquardt方法解非線性方程組問題，研究它的收斂性，證明出在局部誤差界的條件下當‖F(xiàn)k‖≤1 時其二次收斂，當‖F(xiàn)k‖＞1 時其線性收斂，最后也通過數(shù)值試驗驗證出方法的有效性.