作者：祝强1, 李少康1, 徐臻2
作者单位：1. 西安工业大学测试与控制技术研究所, 陕西 西安 710021;
2. 西安共达精密机器有限公司, 陕西 西安 710075
关键词：LM算法;高斯牛顿法;最小二乘;残差
摘要：
针对传统LM算法求解大残差非线性最小二乘问题时存在算法失效的现象,分析Hessian矩阵与其近似矩阵的相似度对LM算法有效性的影响,提出一种依据残差变化方向搜索信赖域区间的自寻优LM算法。优化阻尼系数的更新算法,引入大残差引起的局部不收敛判断条件,以最速下降法结束当前迭代。迭代过程均以目标函数值的减小作为接受条件,算法稳定可靠。圆拟合测试结果证明:自寻优LM算法对待求参数初始值的选取不敏感,在15夹角短圆弧、大残差等极端条件下仍可获得较快的收敛速度和良好拟合效果。自寻优LM算法具有较强的鲁棒性和稳定性,性能明显优于传统LM算法。
Study of solving nonlinear least squares under large residual based on Levenberg-Marquardt algorithm
ZHU Qiang1, LI Shaokang1, XU Zhen2
1. Institute of Measurement and Control Technology, Xi'an Technological University, Xi'an 710021, China;
2. Xi'an GongDa Precision Machine Co., Ltd., Xi'an 710075, China
Abstract: The traditional Levenberg-Marquardt algorithm (LM algorithm) is always invalid in solving large residual nonlinear least squares problems. Thus, how the similarity between Hessian matrix and its approximate matrix influences the effectiveness of the traditional LM algorithm is analyzed. And a self-optimizing LM algorithm that the residual changing direction is used to search for trust-region intervals is proposed. The updating algorithm of damping coefficient is improved; A judging condition is introduced to solve the local divergence caused by large residual; and the LM algorithm is substituted by the steepest descent method. It is the unique accepting condition that the objective function value is decreased continuously in the iterative process. The self-optimizing LM algorithm is stable and reliable. Circle fitting tests show that the self-optimizing LM algorithm is insensitive to the initial value of searching parameters. Under the extreme conditions such as large residual and the short arc of 15° included angle, the convergence is fast and the fitting results are good, which proves that this new algorithm is robust and stable and its performance is superior to the traditional LM algorithm.
Keywords: Levenberg-Marquardt algorithm;Gauss-Newton algorithm;least squares;residual
2016, 42(3): 12-16 收稿日期: 2015-07-30;收到修改稿日期: 2015-09-11
基金项目: 国家自然科学基金(51475351);陕西省科学技术研究发展计划项目(2013K08-12);陕西省协同创新计划项目(2015XT-32);西安工业大学校长基金(XAGDXJJ1006)
作者简介: 祝强(1972-),男,湖北襄阳市人,副教授,博士,研究方向为精密测量与控制技术。
参考文献
[1] WANG X H, LI C. Convergence of newton's method and uniqueness of the solution of equations in banach space II[J]. Acta Mathematica Sinica,2003,19(2):405-412.
[2] PROINOV P D. General local convergence theory for a class of iterative processes and its applications to newton's method[J]. Journal of Complexity,2009,25(1):38-62.
[3] MARQUARDT D W. An algorithm for the least-squares estimation of nonlinear parameters[J]. Journal of the Society for Industrial and Applied Mathematics,1963,11(2):431-441.
[4] LEVENBERG K. A method for the solution of certain non-linear problems in least squares[J]. Quarterly Journal of Applied Mathmatics,1944,2(2):164-168.
[5] 魏荣,卢俊国,王执铨. 基于Levenberg-Marquardt算法和最小二乘方法的小波网络混合学习算法[J]. 信息与控制,2001,30(5):440-442.
[6] TRANSTRUM M K, MACHTA B B, SETHNA J P, Why are nonlinear fits to data so challenging[J]. Phys Rev Lett,2010(104):060201.
[7] TRANSTRUMA M K, SETHNA J P. Improvements to the Levenberg-Marquardt algorithm for nonlinear least-squares minimization[J]. Journal of Computational Physics, 2012,11(1):1-32.
[8] RENKA R J. Nonlinear least squares and Sobolev gradients[J]. Applied Numerical Mathematics,2013(65):91-104.
[9] KAZEMI P, RENKA R J. A Levenberg-Marquardt method based on sobolev gradients[J]. Nonlinear Analysis:Theory,Methods & Applications,2012,75(16):6170-6179.
[10] LAMPTON M. Damping-undamping strategies for the Levenberg-Marquardt nonlinear Least-Squares method[J]. Computers in Physics Journal,1997,11(1):110-115.
[11] 张鸿燕,耿征. Levenberg-Marquardt算法的一种新解释[J].计算机工程与应用,2009,45(3):5-8.
[12] UMBACH D, JONES K N. A few methods for fitting circles to data[J]. IEEE Trans on Instrumentation and Measurement,2003,52(6):1181-1885.
[13] KANATANI K, SUGAYA Y. Performance evaluation of iterative geometric fitting algorithms[J]. Computational Statistics & Data Analysis,2007,52(2):1208-1222.
[14] ALSHARADQAH A, CHERNOV N. Error analysis for circle fitting algorithms[J]. Electronic Journal of Statistics, 2009,21(3):886-911.
[15] CHERNOV N, LESORT C. Statistical efficiency of curve fitting algorithms[J]. Computational Statistics and Data Analysis,2004,47(4):713-728.
