Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The convergence of the Ben-Israel iteration for nonlinear least squares problems

Author: Paul T. Boggs
Journal: Math. Comp. 30 (1976), 512-522
MSC: Primary 65K05; Secondary 34D20
MathSciNet review: 0416018
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Ben-Israel [1] proposed a method for the solution of the nonlinear least squares problem $ {\min _{x \in D}}{\left\Vert {F(x)} \right\Vert _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 [Enhancements On Off] (What's this?)

  • [1] Adi Ben-Israel, A Newton-Raphson method for the solution of systems of equations, J. Math. Anal. Appl. 15 (1966), 243–252. MR 0205445
  • [2] 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.
  • [3] Paul T. Boggs and J. E. Dennis Jr., A stability analysis for perturbed nonlinear iterative methods, Math. Comp. 30 (1976), 199–215. MR 0395209, 10.1090/S0025-5718-1976-0395209-4
  • [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 0303723
  • [5] 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 0351093
  • [6] R. Fletcher, Generalized inverse methods for the best least squares solution of systems of non-linear equations, Comput. J. 10 (1967/1968), 392–399. MR 0221748
  • [7] 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
  • [8] 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. Collection of articles dedicated to the memory of George E. Forsythe. MR 0336980
  • [9] Wolfgang Hahn, Über die Anwendung der Methode von Ljapunov auf Differenzengleichungen, Math. Ann. 136 (1958), 430–441 (German). MR 0099543
  • [10] James Hurt, Some stability theorems for ordinary difference equations, SIAM J. Numer. Anal. 4 (1967), 582–596. MR 0221787
  • [11] Kenneth Levenberg, A method for the solution of certain non-linear problems in least squares, Quart. Appl. Math. 2 (1944), 164–168. MR 0010666
  • [12] 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.
  • [13] Donald W. Marquardt, An algorithm for least-squares estimation of nonlinear parameters, J. Soc. Indust. Appl. Math. 11 (1963), 431–441. MR 0153071
  • [14] James M. Ortega, Stability of difference equations and convergence of iterative processes, SIAM J. Numer. Anal. 10 (1973), 268–282. Collection of articles dedicated to the memory of George E. Forsythe. MR 0339523
  • [15] J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
  • [16] 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
  • [17] David A. Sánchez, Ordinary differential equations and stability theory: An introduction, W. H. Freeman and Co., San Francisco, Calif.-London, 1968. MR 0227492
  • [18] Taro Yoshizawa, Stability theory by Liapunov’s second method, Publications of the Mathematical Society of Japan, No. 9, The Mathematical Society of Japan, Tokyo, 1966. MR 0208086

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65K05, 34D20

Retrieve articles in all journals with MSC: 65K05, 34D20

Additional Information

Keywords: Ben-Israel iteration, generalized inverses, nonlinear least squares, Lyapunov stability for difference equations
Article copyright: © Copyright 1976 American Mathematical Society