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
DOI: https://doi.org/10.1090/S0025-5718-1976-0416018-3
MathSciNet review: 0416018
Full-text PDF

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] A. BEN-ISRAEL, "A Newton-Raphson method for the solution of systems of equations," J. Math. Anal. Appl., v. 15, 1966, pp. 243-252. MR 34 #5273. MR 0205445 (34:5273)
  • [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] P. T. BOGGS & J. E. DENNIS, JR., A Stability Analysis for Perturbed Nonlinear Iterative Methods, Cornell Univ. Computer Science Tech. Rep. TR 74-200; Math. Comp., v. 30, 1976, pp. 199-215. MR 0395209 (52:16007)
  • [4] K. M. BROWN & J. E. DENNIS, JR., "Derivative free analogues of the Levenberg-Marquardt and Gauss algorithms for nonlinear least squares approximation," Numer. Math., v. 18, 1971/72, pp. 289-297. MR 46 #2859. MR 0303723 (46:2859)
  • [5] P. DEUFLHARD, "A modified Newton method for the solution of ill-conditioned systems of nonlinear equations with application to multiple shooting," Numer. Math., v. 22, 1974, pp. 289-315. MR 50 #3584. MR 0351093 (50:3584)
  • [6] R. FLETCHER, "Generalized inverse methods for the best least squares solution of systems of non-linear equations," Comput. J., v. 10, 1967/68, pp. 392-399. MR 36 #4800. MR 0221748 (36:4800)
  • [7] M. K. GAVURIN, "Nonlinear functional equations and continuous analogs of iterative methods," Izv. Vysš. Učebn. Zaved. Matematika, v. 1958, no. 5(6), pp. 18-31; English transl., Technical Report 68-70, Univ. of Maryland, College Park, Md., 1968. MR 25 #1380. MR 0137932 (25:1380)
  • [8] G. H. GOLUB & V. PEREYRA, "The differentiation of pseudo-inverses and nonlinear least squares problems whose variables separate," SIAM J. Numer. Anal., v. 10, 1973, pp. 413-432. MR 49 #1753. MR 0336980 (49:1753)
  • [9] W. HAHN, "Über die Anwendung der Methode von Ljapunov auf Differenzengleichen," Math. Ann., v. 136, 1958, pp. 430-441. MR 20 #5982. MR 0099543 (20:5982)
  • [10] J. HURT, "Some stability theorems for ordinary difference equations," SIAM J. Numer. Anal., v. 4, 1967, pp. 582-596. MR 36 #4839. MR 0221787 (36:4839)
  • [11] K. LEVENBERG, "A method for the solution of certain non-linear problems in least squares," Quart. Appl. Math., v. 2, 1944, pp. 164-168. MR 6, 52. MR 0010666 (6:52a)
  • [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] D. W. MARQUARDT, "An algorithm for least-squares estimation of nonlinear parameters," SIAM J. Appl. Math., v. 11, 1963, pp. 431-441. MR 27 #3040. MR 0153071 (27:3040)
  • [14] J. M. ORTEGA, "Stability of difference equations and convergence of iterative processes," SIAM J. Numer. Anal., v. 10, 1973, pp. 268-282. MR 49 #4281. MR 0339523 (49:4281)
  • [15] J. M. ORTEGA & W. C. RHEINBOLDT, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York and London, 1970. MR 42 #8686. MR 0273810 (42:8686)
  • [16] R. C. RAO & S. K. MITRA, Generalized Inverse of Matrices and Its Applications, Wiley, New York, 1971. MR 49 #2780. MR 0338013 (49:2780)
  • [17] D. A. SÁNCHEZ, Ordinary Differential Equations and Stability Theory: An Introduction, Freeman, San Francisco, Calif., 1968. MR 37 #3076. MR 0227492 (37:3076)
  • [18] T. YOSHIZAWA, Stability Theory by Liapunov's Second Method, Publ. Math. Soc. Japan, no. 9, Math. Soc. Japan, Tokyo, 1966. MR 34 #7896. MR 0208086 (34:7896)

Similar Articles

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

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


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1976-0416018-3
Keywords: Ben-Israel iteration, generalized inverses, nonlinear least squares, Lyapunov stability for difference equations
Article copyright: © Copyright 1976 American Mathematical Society

American Mathematical Society