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 where . This procedure takes the form where 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.

**[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)**

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