全局收斂L-M迭代法的非線性參數平差

王利朋，劉成龍

(1.西南交通大學 地球科學與環境工程學院，四川 成都 611756；

2.西南交通大學 高速鐵路運營安全空間信息技術國家地方聯合工程實驗室，四川 成都 611756)

?

全局收斂L-M迭代法的非線性參數平差

王利朋1,2，劉成龍1,2

(1.西南交通大學 地球科學與環境工程學院，四川 成都 611756；

2.西南交通大學 高速鐵路運營安全空間信息技術國家地方聯合工程實驗室，四川 成都 611756)

摘要:采用全局收斂的L-M非線性迭代算法，可以較大程度減弱非線性模型線性化的模型誤差，在雅可比矩陣近似奇異或壞條件時，L-M迭代仍然可以收斂；同時，該算法具有全局收斂特性，大大降低了平差對迭代初值的要求，可以在初值受誤差影響較大的情況下得到精確解。通過與幾種不同的非線性規劃算法的比較，證明了全局收斂的L-M迭代算法無論是解算精度還是收斂范圍均具有相對優勢。

關鍵詞：全局收斂；L-M迭代；非線性參數平差；模型誤差

間接平差的函數模型既有線性的，也有非線性的。針對不同類型的函數模型，眾多學者和研究人員提出了不同的平差方法，實踐證明，相關的數據處理方法均是行之有效的。常見的平差方法包括：經典的最小二乘解法(Least Squares，簡稱LS)；線性化后的牛頓迭代法[1]；非線性整體最小二乘(Nonlinear Total Least Squares，簡稱NTLS)[2]；非線性模型的高斯-牛頓(Gauss-Newton，簡稱G-N)迭代法[3]等。經典最小二乘解法的實質是，對非線性的觀測方程進行線性化，按照泰勒展開公式在參數的近似值處展開并保留一次項，從而得到線性化之后的模型，再利用線性最小二乘法(Linear Least Squares)解算。但是，LS參數的近似值必須充分接近其真實值，否則會產生無法忽略的模型誤差(Modal Error)，對最終的結果產生嚴重影響。鄧興升等[1]將線性化與牛頓迭代結合在一起，雖然通過牛頓迭代可以以較高的精度收斂，但其前提是函數模型應為線性模型或非線性程度很弱，同時對參數初值的選取依賴性較強，當初值選取接近真實值時，可以線性收斂甚至二次收斂，但牛頓迭代法仍然是局部收斂的，即參數初值選取偏差較大時，無法收斂至真值。胡川等[2]提出的NTLS算法降低了對參數初值的要求并提高了解算的精度。吳玲等[3]提出了非線性模型的G-N迭代法，該方法不需要對非線性函數進行線性化，避免了模型誤差，選取適當的初值即可，但仍然存在收斂區間較窄的缺點。無論是經典的最小二乘解法、線性化后的牛頓迭代法或G-N迭代法，對初值的選取都比較敏感，其處理效率及解算結果的好壞都強烈依賴于所選取的初值。為了解決這個問題，本文將一種全局收斂的萊文伯格-馬夸特(Globally Convergent Levenberg-Marquardt)迭代算法應用于平差，簡稱GCLM。該方法由Levenberg提出，并由Marquardt重新發現[5-6]。本文將該方法應用于平差，引入依靠信賴域技巧而不斷變化的參數αk，并以此來確定迭代參數μk，確保迭代能夠正常進行，解決了G-N迭代中Jk矩陣(第k次迭代的Jacobi矩陣)幾乎奇異或壞條件時迭代不收斂的問題。通過實驗數據證明，相對于經典的最小二乘法和文獻[1]~[3]中的方法，GCLM迭代法具有解算精度較高和收斂范圍更大的特點。

1GCLM迭代算法

設非線性方程組為：

F(x)=0

(1)

為了求解該方程組，利用以下線性方程組的迭代解dk來確定真實解的搜索方向，對近似解xk進行糾正：

(JkTJk+μkI)dk=-JkTFk

(2)

式(2)中，k為迭代次數；Jk為第k次迭代的Jacobi矩陣；dk為迭代解的修正值；I為單位矩陣；μk為正則化參數，可以保證JkTJk+μkI對稱正定，即式(2)的解dk是適定的。

在G-N迭代法中，要求JkTJk始終保持列滿秩，這就限制了該方法的適用范圍，當Jk矩陣幾乎奇異或壞條件時，給G-N迭代法中的牛頓步帶來困難，下式為牛頓步：

dkN=-Jk-1Fk

(3)

dkN為G-N迭代法中的修正值，當Jk壞條件或幾乎奇異時，dk會變得很大，影響迭代解的準確性。式(2)中引入非負迭代參數μk，即使JkTJk處于壞條件狀態，仍然可以保證JkTJk+μkI具有較小的條件數，可以避免牛頓步中Jk幾乎奇異或壞條件時產生的問題，μk可以按照以下公式計算：

μk=αk(θ‖Fk‖+(1-θ)‖JkTFk‖)，θ∈(0，1)

(4)

式(4)中：αk可以依據信賴域技巧不斷修正[7]，||Fk||代表該向量的2-范數。于是可以得到第k步迭代的實際下降量Aredk和預估下降量Predk：

(5)

設置參數Tk=Aredk/Predk，以Tk來探測近似解xk和參數αk，根據Tk的大小確定是否對xk和參數αk進行修正。GCLM迭代算法步驟如下：

1)設定，x1∈Rn，ε>0，α1>m>0，0

2)判斷，如果‖JkTFk‖≤ε，停止計算；否則，依次計算式(4)和(2)，得到修正值dk，并執行第3步、第4步和第5步；

3)計算，按照式(5)計算實際下降量Aredk和預估下降量Predk，得到參數Tk；

4)修正，

(6)

(7)

5)迭代，k=k+1，轉第2步(2)。

該算法由于引入了正則化參數μk而保證了迭代的順利進行，同時具有全局收斂的優勢，其解算結果不依賴于迭代初值的選取，下面對GCLM算法的全局收斂特性進行簡述。

2GCLM的全局收斂特性

設文獻[4]中的假定成立，則GCLM算法經過有限次迭代后會終止，或k次迭代后滿足

(8)

此時，若算法(8)迭代不收斂，則存在常數τ> 0，使得無數個k滿足

‖JkTFk‖≥τ

(9)

設K與T分別為指標集：K={k||JkTFk||≥τ}，T={k|xk+1≠xk，k∈K}，由上述GCLM算法可知，當k≥1時

Predk=‖Fk‖2-‖Fk+Jkdk‖2≥

(10)

從而

(11)

同樣由上述GCLM算法可知

(12)

根據式(11)與(12)可知

(13)

(14)

αk→+

(15)

由式(9)和(14)以及(10)可得

(16)

因此，由GCLM算法中αk的取值可知存在常數M>m，使得當k充分大時有

αk

(17)

式(15)與式(17)矛盾，從而GCLM算法全局收斂得到驗證。

GCLM算法不僅具有全局收斂的特性，同時避免了非線性問題線性化時產生的模型誤差，其不依賴于迭代初值的特點使得GCLM算法具有較高的解算精度，下文對GCLM算法的應用以及實例計算的數據進行分析和討論。

3算例

為了驗證GCLM算法的實用性及有效性，以邊角網平差為例，簡述該算法應用于邊角網平差的原理，下文的數據分析選擇一個邊角觀測的單三角形為例按照不同的方法進行平差。如圖1所示為邊角網中的一條邊，SAB為觀測邊，αAB為方位角，

圖1　觀測邊的邊長及方位角Fig.1 Length and azimuth of the observed side

按照GCLM算法可得該觀測邊的非線性方程組

(18)

(19)

解的糾正方程為

(JkTPJk+μkI)dk=-JkTPVk

(20)

其平差準則為

‖JkTPVk‖ε

(21)

m代表觀測值個數；P為觀測值的權陣；Vk為第k次迭代所有觀測值的改正數；ε為迭代終止條件。

根據上述的函數模型和平差準則利用GCLM算法進行解算，按照GCLM算法的迭代步驟求出式(19)滿足準則(21)的最終解，并對坐標平差值進行精度評定

(22)

式(22)中，σ0為驗后單位權中誤差，Dxx為坐標平差值的方差-協方差陣。

4數據分析

按照GCLM算法在邊角網中的應用，以一個單三角形為例，如圖2所示，觀測了2個內角L1，L2和2條邊長S1，S2，各觀測值如下：L1=40°23'17.8"，L2=93°59'58.7"，S1=1 786.372m，S2=2 493.721m，已知A點坐標為(0，0)，AB方位角為0。

圖2　邊角觀測的單三角形Fig.2 Triangulateration triangle

可以求得B點和C點較準確的坐標近似值為：XB0=1 786.372m，XC0=1 899.374m，YC0=1 615.841m，稱為第1類近似值。以第1類近似值為基礎，分別采用幾種不同的算法對該單三角形進行平差，將不同算法的結果做了對比，如表1所示。為了對比不同的非線性算法的收斂特性及其平差結果對初值選取的依賴性，更改B和C2點的坐標近似值如表2所示，稱為第2類近似值，表2為G-N法與GCLM法基于第2類坐標近似值的解算平差結果對比。

表1　不同算法基于第1類近似值的平差數據對比

表2　G-N法與GCLM法基于第二類近似值的平差數據對比

從表1中可以看出，無論是NTLS算法、G-N算法還是本文的GCLM算法，均可以獲得較高精度的坐標平差值，這3種方法的驗后單位權中誤差均優于傳統的LS法和線性化后的牛頓迭代法，且3種方法的驗后單位權中誤差較差不超過0.1"。從表2可以看出，當坐標近似值較為接近準確值或偏差不大時，G-N算法仍然可以正常進行且驗后精度與表1中驗后精度相同，即初值選取較為恰當時不會影響G-N算法解算結果的有效性，此時G-N算法與本文的GCLM算法驗后精度相差0.02"，可以認為2種方法解算精度相當。當B和C 2點坐標近似值偏差很大時，G-N算法無法收斂至坐標真值，而本文的GCLM算法仍然可以順利進行且精度與表1中精度相當，即初值選取偏差較大時，GCLM算法獲得的坐標平差值及驗后精度與基于第一類坐標近似值的坐標平差值和驗后精度相同。

筆者對模擬的100個單三角形進行了同樣的計算，統計結果顯示：NTLS算法、G-N算法以及GCLM算法優于傳統的LS算法和牛頓迭代法的比例為97%；筆者在這100個單三角形中按照表2中初始值選取的方法對G-N算法和GCLM算法的結果作了統計，當初始值選取偏差很大時G-N算法無法收斂；當初始值選取偏差不大時，GCLM算法解算結果與G-N算法解算結果的比較如表3所示。δ為2種方法的驗后單位權中誤差較差，P(Δσ0)=P(σGCLM-σG-N)，表示驗后單位權中誤差較差屬于不同區間的比例。

表3　GCLM算法與G-N算法的統計結果

從表3可以看出，在待求點坐標迭代初值較為理想的情況下，GCLM算法總體上略優于G-N算法，由于GCLM算法具有一定的收斂優勢，因此可以認為在非線性平差問題中GCLM算法略優于傳統算法和G-N法，且與NTLS算法相差不大。

5結論

1)GCLM算法優于傳統的線性化方法，可以得到更加準確的平差結果，且驗后精度明顯提高；與G-N等非線性算法相比，GCLM算法可以保證迭代計算全局收斂，克服了G-N法局部收斂的缺點，一定程度上降低了對迭代初值的要求，具有較大的收斂范圍，其驗后精度與NTLS精度相當。

2)GCLM算法從理論上降低了非線性模型線性化后的模型誤差，無論是收斂特性還是驗后精度均具有相對優勢，是一種有效的非線性參數平差算法。

參考文獻:

[1] 鄧興升,孫虹虹,湯仲安.高斯牛頓迭代法解算非線性Bursa-Wolf模型的精度分析[J].測繪科學,2014，39(5)：93-95.

DENG Xingsheng, SUN Honghong, TANG Zhongan.Accuracy analysis of gauss newton iteration method for solution of nonlinear Bursa-Wolf Model[J].Science of Surveying and Mapping, 2014，39(5):93-95.

[2] 胡川,陳義.非線性整體最小平差迭代算法[J]．測繪學報,2014,43(7):668-674.

HU Chuan, CHEN Yi.An iterative for nonlinear total least squares adjustment[J].Acta Geodaetica et Cartographica Sinica,2014,43(7):668-674.

[3] 吳玲,劉忠,盧發興.全局收斂高斯-牛頓法.解非線性最小二乘定位問題[J].火控雷達技術,2003，32(3)：75-80.

WU Ling, LIU Zhong, LU Faxing.Global convergence Gauss-Newton Method applied to nonlinear least square estimation in target location[J].Fire Control Radar Technology, 2003，32(3)：75-80.

[4] Yamashita N, Fukushima M.On the rate of convergence of the Levenberg-Marquardt Method[J].Computing,2001(15):239-249.

[5] Levenberg K.A method for the solution of certain nonlinear problems in least squares[J].Quart APPL Math,1944：164-166.

[6] Marquardt D W.An algorithm for least-squares estimation of nonlinear inequalities[J].SIAM J Appl Math,1963,11:431-441.

[7] Fan Jinyan.A modified Levenberg-Marquardt method for singular system of nonlinear equa-Tions[J].Journal of Computational Mathematics,2003,21(5):625-636.

[8] 何葉丹,馬昌鳳.求解非線性方程組的一個修正非單調L-M算法[J].福建師范大學學報(自然科學版),2013(4):21-28.

HE Yedan, MA Changfeng.A modified nonmonotone L-M method for solving nonlinear system of equations[J].Journal of Fujian Normal University(Natural Science Edition),2013(4):21-28.

[9] 范東明.非線性最小二乘參數平差的非線性規劃算法研究[J].西南交通大學學報,2001，36(5)：476-480.

FAN Dongming.Nonlinear programming algorithms for nonlinear least squares adjustment by parameters[J].Journal of Southwest Jiaotong University ,2001，36(5)：476-480.

[10] 劉國林,姜巖,陶華學.非線性最小二乘參數平差[J].測繪學報,1998，27(3)：224-230.

LIU Guolin, JIANG Yan, TAO Huaxue.Nonlinear least souares adjustment by parameters[J].Acta Geodaetica et Cartographica Sinica,1998，27(3)：224-230.

[11] 游為,范東明.基于改進同倫算法的非線性最小二乘平差[J].西南交通大學學報,2009，44(2)：181-185.

YOU Wei, FAN Dongming.Nonlinear least squares adjustment based on improved homotopy algorithm[J].Journal of Southwest Jiaotong University ,2009，44(2)：181-185.

[12] Ma Changfeng,Jiang Lihua.Some research on Levenberg-Marquardt method for the nonlinear equations[J].Applied Mathematics and Computation,2007,184:1032-1040.

[13] 宋韜,劉成龍,楊雪峰.工程平面控制網置平平差的方法研究[J].鐵道科學與工程學報，2013,10(3)：82-86.

SONG Tao, LIU Cheng Long, YANG Xue Feng.The research for the method of plane control network adjustment[J].Journal of Railway Science and Engineering，2013,10(3)：82-86.

[14] 王穗輝.誤差理論與測量平差[M].上海：同濟大學出版社, 2010.

WANG Suihui.Error Theory and Surveying Adjustment[M].Shanghai: Tongji University Press, 2010.

[15] 宋力杰.測量平差程序設計[M].北京：國防工業出版社, 2009.

SONG Lijie.Program design of surveying adjustment[M].Beijing: National Defense Industry Press,2009.

[16] 徐士良.數值分析與算法[M].北京：機械工業出版社,2003.

XU Shiliang.Numerical analysis and algorithm[M].Beijing: China Machine Press, 2003.

(編輯陽麗霞)

Globally convergent levenberg-marquardt method for nonlinear parameter adjustment

WANG Lipeng1,2，LIU Chenglong1,2

(1.Faculty of Geosciences and Environmental Engineering, Southwest Jiaotong University, Chengdu 611756, China;

2.State-Province Joint Engineering Laboratory of Spatial Information Technology of High-Speed Rail Safety, Chengdu 611756, China)

Abstract:Adopting iterated algorithm of globally convergent levenberg-marquardt could weaken the model error greatly while non-linear model is linearized.Beside, the L-M iterated algorithm is still convergent even Jacobian matrix is approximatively singular.Meanwhile,the algorithm is globally convergent which would weaken the requirement greatly for iterative initial value.This algorithm could gain exact solution even the iterative initial value has a serious error.Through the comparison of different non-linear programming algorithm,it has been proved that iterated algorithm of globally convergent levenberg-marquardt has comparative advanage in accuracy and the range of convergence.

Key words:globally convergent;L-M iteration;non-linear parameter adjustment;model error

收稿日期：2015-04-15基金項目：長江學者和創新團隊發展計劃資助項目(IRT13092)

通訊作者：劉成龍(1962 - )，男，福建莆田人，教授，從事精密工程測量與變形監測；E-mail：wanglpswjtu@sina.com

中圖分類號：P207

文獻標志碼：A

文章編號：1672-7029(2015)06-1452-06