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), 962-973

MSC:
Primary 65H10

DOI:
https://doi.org/10.1090/S0025-5718-1977-0443325-1

Corrigendum:
Math. Comp. **33** (1979), 432-433.

Corrigendum:
Math. Comp. **33** (1979), 432-433.

MathSciNet review:
0443325

Full-text PDF

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]**BEN-ISRAEL (1966), "A Newton-Raphson method for the solution of systems of equations,"*J. Math. Anal. Appl.*, v. 15, pp. 243-252. MR**34**#5273. MR**0205445 (34:5273)****[P]**T. BOGGS (1970),*The Solution of Nonlinear Operator Equations by A-Stable Integration Techniques*, Doctoral thesis, Cornell University, Ithaca, New York; Report TR70-72, Computer Science Dept., Cornell University, Ithaca, N. Y.**[P]**T. BOGGS (1971), "The solution of nonlinear systems of equations by*A*-stable integration techniques,"*SIAM J. Numer. Anal.*, v. 8, pp. 767-785. MR**45**#6179. MR**0297121 (45:6179)****[P]**T. BOGGS (1976a), "The convergence of the Ben-Israel iteration for nonlinear least squares problems,"*Math. Comp.*, v. 30, pp. 512-522. 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. 199-215. MR**52**#16007. MR**0395209 (52:16007)****[E]**A. CODDINGTON & N. LEVINSON (1955),*Theory of Ordinary Differential Equations*, McGraw-Hill, 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. 75-85. 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. 18-31; English transl., Report 68-70, 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. 403-420; Also: contribution I/10 of*Handbook for Automatic Computation*. Vol. II,*Linear Algebra*(J. H. WILKINSON & C. REINSCH, Editors), Springer-Verlag, Berlin and New York, 1971. MR**1553974****[C]**L. LAWSON & R. J. HANSON (1974),*Solving Least Squares Problems*, Prentice-Hall, Englewood Cliffs, N. J. MR**51**#2270. MR**0366019 (51:2270)****[K]**LEVENBERG (1944), "A method for the solution of certain non-linear problems in least squares,"*Quart. Appl. Math.*, v. 2, pp. 164-168. MR**6**, 52. MR**0010666 (6:52a)****[D]**W. MARQUARDT (1963), "An algorithm for least-squares estimation of nonlinear parameters,"*SIAM J. Appl. Math.*, v. 11, pp. 431-441. MR**27**#3040. MR**0153071 (27:3040)****[W]**MURRAY (1972), "A numerically stable modified Newton method based on Cholesky factorization," §4.9 (pp. 64-68) 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)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65H10

Retrieve articles in all journals with MSC: 65H10

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1977-0443325-1

Keywords:
Continuation methods,
eigenvalues,
nonlinear equations,
pseudoinverse,
singular value decomposition

Article copyright:
© Copyright 1977
American Mathematical Society