The convergence of the Ben-Israel iteration for nonlinear least squares problems
HTML articles powered by AMS MathViewer
- by Paul T. Boggs PDF
- Math. Comp. 30 (1976), 512-522 Request permission
Abstract:
Ben-Israel [1] proposed a method for the solution of the nonlinear least squares problem ${\min _{x \in D}}{\left \| {F(x)} \right \|_2}$ where $F:D \subset {R^n} \to {R^m}$. This procedure takes the form ${x_{k + 1}} = {x_k} - F’{({x_k})^ + }F({x_k})$ where $F’{({x_k})^ + }$ denotes the Moore-Penrose generalized inverse of the Fréchet derivative of F. We give a general convergence theorem for the method based on Lyapunov stability theory for ordinary difference equations. In the case where there is a connected set of solution points, it is often of interest to determine the minimum norm least squares solution. We show that the Ben-Israel iteration has no predisposition toward the minimum norm solution, but that any limit point of the sequence generated by the Ben-Israel iteration is a least squares solution.References
- Adi Ben-Israel, A Newton-Raphson method for the solution of systems of equations, J. Math. Anal. Appl. 15 (1966), 243–252. MR 205445, DOI 10.1016/0022-247X(66)90115-6 P. T. BOGGS, "On the use of Lyapunov theory for the analysis of nonlinear iterative methods," Proc. of 1975 Conference on Information Sciences and Systems, April 2-4, 1975.
- Paul T. Boggs and J. E. Dennis Jr., A stability analysis for perturbed nonlinear iterative methods, Math. Comp. 30 (1976), 199–215. MR 395209, DOI 10.1090/S0025-5718-1976-0395209-4
- Kenneth M. Brown and J. E. Dennis Jr., Derivative free analogues of the Levenberg-Marquardt and Gauss algorithms for nonlinear least squares approximation, Numer. Math. 18 (1971/72), 289–297. MR 303723, DOI 10.1007/BF01404679
- P. Deuflhard, A modified Newton method for the solution of ill-conditioned systems of nonlinear equations with application to multiple shooting, Numer. Math. 22 (1974), 289–315. MR 351093, DOI 10.1007/BF01406969
- R. Fletcher, Generalized inverse methods for the best least squares solution of systems of non-linear equations, Comput. J. 10 (1967/68), 392–399. MR 221748, DOI 10.1093/comjnl/10.4.392
- M. K. Gavurin, Nonlinear functional equations and continuous analogues of iteration methods, Izv. Vysš. Učebn. Zaved. Mattmatika 1958 (1958), no. 5 (6), 18–31 (Russian). MR 0137932
- G. H. Golub and V. Pereyra, The differentiation of pseudo-inverses and nonlinear least squares problems whose variables separate, SIAM J. Numer. Anal. 10 (1973), 413–432. MR 336980, DOI 10.1137/0710036
- Wolfgang Hahn, Über die Anwendung der Methode von Ljapunov auf Differenzengleichungen, Math. Ann. 136 (1958), 430–441 (German). MR 99543, DOI 10.1007/BF01347793
- James Hurt, Some stability theorems for ordinary difference equations, SIAM J. Numer. Anal. 4 (1967), 582–596. MR 221787, DOI 10.1137/0704053
- Kenneth Levenberg, A method for the solution of certain non-linear problems in least squares, Quart. Appl. Math. 2 (1944), 164–168. MR 10666, DOI 10.1090/S0033-569X-1944-10666-0 A. M. LYAPUNOV, "Problème générale de la stabilité du mouvement," Kharkov, 1892; French transl., Ann. Fac. Sci. Univ. Toulouse, v. (2) 9, 1907, pp. 203-474; reprint, Ann. of Math. Studies, no. 17, Princeton Univ. Press, Princeton, N. J., 1949. MR 9, 34.
- Donald W. Marquardt, An algorithm for least-squares estimation of nonlinear parameters, J. Soc. Indust. Appl. Math. 11 (1963), 431–441. MR 153071
- James M. Ortega, Stability of difference equations and convergence of iterative processes, SIAM J. Numer. Anal. 10 (1973), 268–282. MR 339523, DOI 10.1137/0710026
- J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
- C. Radhakrishna Rao and Sujit Kumar Mitra, Generalized inverse of matrices and its applications, John Wiley & Sons, Inc., New York-London-Sydney, 1971. MR 0338013
- David A. Sánchez, Ordinary differential equations and stability theory: An introduction, W. H. Freeman and Co., San Francisco, Calif.-London, 1968. MR 0227492
- Taro Yoshizawa, Stability theory by Liapunov’s second method, Publications of the Mathematical Society of Japan, vol. 9, Mathematical Society of Japan, Tokyo, 1966. MR 0208086
Additional Information
- © Copyright 1976 American Mathematical Society
- Journal: Math. Comp. 30 (1976), 512-522
- MSC: Primary 65K05; Secondary 34D20
- DOI: https://doi.org/10.1090/S0025-5718-1976-0416018-3
- MathSciNet review: 0416018