Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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 $ f(x) = 0$ whose Jacobian matrix $ J(x)$ exists but may be singular. The main idea is to modify small singular values of $ J(x)$ in such a way that the modified Jacobian matrix $ \hat J(x)$ has a continuous pseudoinverse $ {\hat J^ + }(x)$ and that a solution $ {x^\ast}$ of $ f(x) = 0$ may be found by determining an asymptote of the solution to the initial value problem $ x(0) = {x_0},x\prime (t) = - {\hat J^ + }(x)f(x)$. 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 $ J({x^\ast})$ is nonsingular, then $ {x^\ast}$ is unique), algorithms using $ {\hat J^ + }(x)$ may enjoy a larger region of convergence than those that require (an approximation to) $ {J^{ - 1}}(x)$.


References [Enhancements On Off] (What's this?)

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

Similar Articles

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

American Mathematical Society