Modifying singular values: existence of solutions to sytems of nonlinear equations having a possibly singular Jacobian matrix
Author:
David Gay
Journal:
Math. Comp. 31 (1977), 962973
MSC:
Primary 65H10
Corrigendum:
Math. Comp. 33 (1979), 432433.
Corrigendum:
Math. Comp. 33 (1979), 432433.
MathSciNet review:
0443325
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We show that if a certain nondegeneracy assumption holds, it is possible to guarantee the existence of a solution to a system of nonlinear equations whose Jacobian matrix exists but may be singular. The main idea is to modify small singular values of in such a way that the modified Jacobian matrix has a continuous pseudoinverse and that a solution of may be found by determining an asymptote of the solution to the initial value problem . We briefly discuss practical (algorithmic) implications of this result. Although the nondegeneracy assumption may fail for many systems of interest (indeed, if the assumption holds and is nonsingular, then is unique), algorithms using may enjoy a larger region of convergence than those that require (an approximation to) .
 [A]
Adi
BenIsrael, A NewtonRaphson method for the solution of systems of
equations, J. Math. Anal. Appl. 15 (1966),
243–252. MR 0205445
(34 #5273)
 [P]
T. BOGGS (1970), The Solution of Nonlinear Operator Equations by AStable Integration Techniques, Doctoral thesis, Cornell University, Ithaca, New York; Report TR7072, Computer Science Dept., Cornell University, Ithaca, N. Y.
 [P]
Paul
T. Boggs, The solution of nonlinear systems of equations by
𝐴stable integration techniques, SIAM J. Numer. Anal.
8 (1971), 767–785. MR 0297121
(45 #6179)
 [P]
Paul
T. Boggs, The convergence of the BenIsrael
iteration for nonlinear least squares problems, Math. Comp. 30 (1976), no. 135, 512–522. MR 0416018
(54 #4095), http://dx.doi.org/10.1090/S00255718197604160183
 [P]
T. BOGGS (1976b), Private communication.
 [P]
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
 [E]
Earl
A. Coddington and Norman
Levinson, Theory of ordinary differential equations,
McGrawHill Book Company, Inc., New YorkTorontoLondon, 1955. MR 0069338
(16,1022b)
 [R]
R.
Fletcher, Generalized inverses for nonlinear equations and
optimization, Numerical methods for nonlinear algebraic equations
(Proc. Conf., Univ. Essex, Colchester, 1969) Gordon and Breach, London,
1970, pp. 75–85. MR 0343587
(49 #8328)
 [M]
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)
 [G]
G.
H. Golub and C.
Reinsch, Handbook Series Linear Algebra: Singular value
decomposition and least squares solutions, Numer. Math.
14 (1970), no. 5, 403–420. MR
1553974, http://dx.doi.org/10.1007/BF02163027
 [C]
Charles
L. Lawson and Richard
J. Hanson, Solving least squares problems, PrenticeHall,
Inc., Englewood Cliffs, N.J., 1974. PrenticeHall Series in Automatic
Computation. MR
0366019 (51 #2270)
 [K]
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)
 [D]
Donald
W. Marquardt, An algorithm for leastsquares estimation of
nonlinear parameters, J. Soc. Indust. Appl. Math. 11
(1963), 431–441. MR 0153071
(27 #3040)
 [W]
MURRAY (1972), "A numerically stable modified Newton method based on Cholesky factorization," §4.9 (pp. 6468) of Numerical Methods for Unconstrained Optimization (W. MURRAY, Editor), Academic Press, New York.
 [J]
J.
M. Ortega and W.
C. Rheinboldt, Iterative solution of nonlinear equations in several
variables, Academic Press, New YorkLondon, 1970. MR 0273810
(42 #8686)
 [C]
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)
 [G]
G.
W. Stewart, Introduction to matrix computations, Academic
Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New
YorkLondon, 1973. Computer Science and Applied Mathematics. MR 0458818
(56 #17018)
 [A]
 BENISRAEL (1966), "A NewtonRaphson method for the solution of systems of equations," J. Math. Anal. Appl., v. 15, pp. 243252. MR 34 #5273. MR 0205445 (34:5273)
 [P]
 T. BOGGS (1970), The Solution of Nonlinear Operator Equations by AStable Integration Techniques, Doctoral thesis, Cornell University, Ithaca, New York; Report TR7072, Computer Science Dept., Cornell University, Ithaca, N. Y.
 [P]
 T. BOGGS (1971), "The solution of nonlinear systems of equations by Astable integration techniques," SIAM J. Numer. Anal., v. 8, pp. 767785. MR 45 #6179. MR 0297121 (45:6179)
 [P]
 T. BOGGS (1976a), "The convergence of the BenIsrael iteration for nonlinear least squares problems," Math. Comp., v. 30, pp. 512522. MR 0416018 (54:4095)
 [P]
 T. BOGGS (1976b), Private communication.
 [P]
 T. BOGGS & J. E. DENNIS, JR. (1976), "A stability analysis for perturbed nonlinear iterative methods," Math. Comp., v. 30, pp. 199215. MR 52 #16007. MR 0395209 (52:16007)
 [E]
 A. CODDINGTON & N. LEVINSON (1955), Theory of Ordinary Differential Equations, McGrawHill, New York. MR 16, 1022. MR 0069338 (16:1022b)
 [R]
 FLETCHER (1970), "Generalized inverses for nonlinear equations and optimization," Numerical Methods of Nonlinear Algebraic Equations (P. RABINOWITZ, Editor), Gordon and Breach, London and New York, pp. 7585. MR 49 #8328. MR 0343587 (49:8328)
 [M]
 K. GAVURIN (1958), "Nonlinear functional equations and continuous analogues of iteration methods," Izv. Vysš. Učebn. Zaved. Matematika, no. 5 (6), pp. 1831; English transl., Report 6870, Computer Science Center, University of Maryland, College Park, Md. MR 25 #1380. MR 0137932 (25:1380)
 [G]
 H. GOLUB & C. REINSCH (1970), "Singular value decomposition and least squares solutions," Numer. Math., v. 14, pp. 403420; Also: contribution I/10 of Handbook for Automatic Computation. Vol. II, Linear Algebra (J. H. WILKINSON & C. REINSCH, Editors), SpringerVerlag, Berlin and New York, 1971. MR 1553974
 [C]
 L. LAWSON & R. J. HANSON (1974), Solving Least Squares Problems, PrenticeHall, Englewood Cliffs, N. J. MR 51 #2270. MR 0366019 (51:2270)
 [K]
 LEVENBERG (1944), "A method for the solution of certain nonlinear problems in least squares," Quart. Appl. Math., v. 2, pp. 164168. MR 6, 52. MR 0010666 (6:52a)
 [D]
 W. MARQUARDT (1963), "An algorithm for leastsquares estimation of nonlinear parameters," SIAM J. Appl. Math., v. 11, pp. 431441. MR 27 #3040. MR 0153071 (27:3040)
 [W]
 MURRAY (1972), "A numerically stable modified Newton method based on Cholesky factorization," §4.9 (pp. 6468) of Numerical Methods for Unconstrained Optimization (W. MURRAY, Editor), Academic Press, New York.
 [J]
 M. ORTEGA & W. C. RHEINBOLDT (1970), Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York and London. MR 42 #8686. MR 0273810 (42:8686)
 [C]
 R. RAO & S. K. MITRA (1971), Generalized Inverse of Matrices and Its Applications, Wiley, New York. MR 49 #2780. MR 0338013 (49:2780)
 [G]
 W. STEWART (1973), Introduction to Matrix Computations, Academic Press, New York. MR 0458818 (56:17018)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65H10
Retrieve articles in all journals
with MSC:
65H10
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197704433251
PII:
S 00255718(1977)04433251
Keywords:
Continuation methods,
eigenvalues,
nonlinear equations,
pseudoinverse,
singular value decomposition
Article copyright:
© Copyright 1977
American Mathematical Society
