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]**Adi Ben-Israel,*A Newton-Raphson method for the solution of systems of equations*, J. Math. Anal. Appl.**15**(1966), 243–252. MR**0205445**, https://doi.org/10.1016/0022-247X(66)90115-6**[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]**Paul T. Boggs,*The solution of nonlinear systems of equations by 𝐴-stable integration techniques*, SIAM J. Numer. Anal.**8**(1971), 767–785. MR**0297121**, https://doi.org/10.1137/0708071**[P]**Paul T. Boggs,*The convergence of the Ben-Israel iteration for nonlinear least squares problems*, Math. Comp.**30**(1976), no. 135, 512–522. MR**0416018**, https://doi.org/10.1090/S0025-5718-1976-0416018-3**[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**, https://doi.org/10.1090/S0025-5718-1976-0395209-4**[E]**Earl A. Coddington and Norman Levinson,*Theory of ordinary differential equations*, McGraw-Hill Book Company, Inc., New York-Toronto-London, 1955. MR**0069338****[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****[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****[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**, https://doi.org/10.1007/BF02163027**[C]**Charles L. Lawson and Richard J. Hanson,*Solving least squares problems*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1974. Prentice-Hall Series in Automatic Computation. MR**0366019****[K]**Kenneth Levenberg,*A method for the solution of certain non-linear problems in least squares*, Quart. Appl. Math.**2**(1944), 164–168. MR**0010666**, https://doi.org/10.1090/qam/10666**[D]**Donald W. Marquardt,*An algorithm for least-squares estimation of nonlinear parameters*, J. Soc. Indust. Appl. Math.**11**(1963), 431–441. MR**0153071****[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]**J. M. Ortega and W. C. Rheinboldt,*Iterative solution of nonlinear equations in several variables*, Academic Press, New York-London, 1970. MR**0273810****[C]**C. Radhakrishna Rao and Sujit Kumar Mitra,*Generalized inverse of matrices and its applications*, John Wiley & Sons, Inc., New York-London-Sydney, 1971. MR**0338013****[G]**G. W. Stewart,*Introduction to matrix computations*, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Computer Science and Applied Mathematics. MR**0458818**

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