The convergence of the BenIsrael iteration for nonlinear least squares problems
Author:
Paul T. Boggs
Journal:
Math. Comp. 30 (1976), 512522
MSC:
Primary 65K05; Secondary 34D20
MathSciNet review:
0416018
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: BenIsrael [1] proposed a method for the solution of the nonlinear least squares problem where . This procedure takes the form where denotes the MoorePenrose 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 BenIsrael iteration has no predisposition toward the minimum norm solution, but that any limit point of the sequence generated by the BenIsrael iteration is a least squares solution.
 [1]
Adi
BenIsrael, A NewtonRaphson method for the solution of systems of
equations, J. Math. Anal. Appl. 15 (1966),
243–252. 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 24, 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 (52 #16007), http://dx.doi.org/10.1090/S00255718197603952094
 [4]
Kenneth
M. Brown and J.
E. Dennis Jr., Derivative free analogues of the LevenbergMarquardt
and Gauss algorithms for nonlinear least squares approximation, Numer.
Math. 18 (1971/72), 289–297. MR 0303723
(46 #2859)
 [5]
P.
Deuflhard, A modified Newton method for the solution of
illconditioned systems of nonlinear equations with application to multiple
shooting, Numer. Math. 22 (1974), 289–315. MR 0351093
(50 #3584)
 [6]
R.
Fletcher, Generalized inverse methods for the best least squares
solution of systems of nonlinear equations, Comput. J.
10 (1967/1968), 392–399. MR 0221748
(36 #4800)
 [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 (25 #1380)
 [8]
G.
H. Golub and V.
Pereyra, The differentiation of pseudoinverses 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
(49 #1753)
 [9]
Wolfgang
Hahn, Über die Anwendung der Methode von Ljapunov auf
Differenzengleichungen, Math. Ann. 136 (1958),
430–441 (German). MR 0099543
(20 #5982)
 [10]
James
Hurt, Some stability theorems for ordinary difference
equations, SIAM J. Numer. Anal. 4 (1967),
582–596. MR 0221787
(36 #4839)
 [11]
Kenneth
Levenberg, A method for the solution of certain nonlinear problems
in least squares, Quart. Appl. Math. 2 (1944),
164–168. 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. 203474; reprint, Ann. of Math. Studies, no. 17, Princeton Univ. Press, Princeton, N. J., 1949. MR 9, 34.
 [13]
Donald
W. Marquardt, An algorithm for leastsquares estimation of
nonlinear parameters, J. Soc. Indust. Appl. Math. 11
(1963), 431–441. MR 0153071
(27 #3040)
 [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 (49 #4281)
 [15]
J.
M. Ortega and W.
C. Rheinboldt, Iterative solution of nonlinear equations in several
variables, Academic Press, New YorkLondon, 1970. MR 0273810
(42 #8686)
 [16]
C.
Radhakrishna Rao and Sujit
Kumar Mitra, Generalized inverse of matrices and its
applications, John Wiley\thinspace&\thinspace Sons, Inc., New
YorkLondonSydney, 1971. MR 0338013
(49 #2780)
 [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
(37 #3076)
 [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
(34 #7896)
 [1]
 A. BENISRAEL, "A NewtonRaphson method for the solution of systems of equations," J. Math. Anal. Appl., v. 15, 1966, pp. 243252. 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 24, 1975.
 [3]
 P. T. BOGGS & J. E. DENNIS, JR., A Stability Analysis for Perturbed Nonlinear Iterative Methods, Cornell Univ. Computer Science Tech. Rep. TR 74200; Math. Comp., v. 30, 1976, pp. 199215. MR 0395209 (52:16007)
 [4]
 K. M. BROWN & J. E. DENNIS, JR., "Derivative free analogues of the LevenbergMarquardt and Gauss algorithms for nonlinear least squares approximation," Numer. Math., v. 18, 1971/72, pp. 289297. MR 46 #2859. MR 0303723 (46:2859)
 [5]
 P. DEUFLHARD, "A modified Newton method for the solution of illconditioned systems of nonlinear equations with application to multiple shooting," Numer. Math., v. 22, 1974, pp. 289315. MR 50 #3584. MR 0351093 (50:3584)
 [6]
 R. FLETCHER, "Generalized inverse methods for the best least squares solution of systems of nonlinear equations," Comput. J., v. 10, 1967/68, pp. 392399. 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. 1831; English transl., Technical Report 6870, Univ. of Maryland, College Park, Md., 1968. MR 25 #1380. MR 0137932 (25:1380)
 [8]
 G. H. GOLUB & V. PEREYRA, "The differentiation of pseudoinverses and nonlinear least squares problems whose variables separate," SIAM J. Numer. Anal., v. 10, 1973, pp. 413432. 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. 430441. 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. 582596. MR 36 #4839. MR 0221787 (36:4839)
 [11]
 K. LEVENBERG, "A method for the solution of certain nonlinear problems in least squares," Quart. Appl. Math., v. 2, 1944, pp. 164168. 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. 203474; reprint, Ann. of Math. Studies, no. 17, Princeton Univ. Press, Princeton, N. J., 1949. MR 9, 34.
 [13]
 D. W. MARQUARDT, "An algorithm for leastsquares estimation of nonlinear parameters," SIAM J. Appl. Math., v. 11, 1963, pp. 431441. 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. 268282. 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:
http://dx.doi.org/10.1090/S00255718197604160183
PII:
S 00255718(1976)04160183
Keywords:
BenIsrael iteration,
generalized inverses,
nonlinear least squares,
Lyapunov stability for difference equations
Article copyright:
© Copyright 1976
American Mathematical Society
