Modifying singular values: existence of solutions to sytems of nonlinear equations having a possibly singular Jacobian matrix
HTML articles powered by AMS MathViewer
- by David Gay PDF
- Math. Comp. 31 (1977), 962-973 Request permission
Corrigendum: Math. Comp. 33 (1979), 432-433.
Corrigendum: Math. Comp. 33 (1979), 432-433.
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
- Adi Ben-Israel, A Newton-Raphson method for the solution of systems of equations, J. Math. Anal. Appl. 15 (1966), 243–252. MR 205445, DOI 10.1016/0022-247X(66)90115-6 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.
- Paul T. Boggs, The solution of nonlinear systems of equations by $A$-stable integration techniques, SIAM J. Numer. Anal. 8 (1971), 767–785. MR 297121, DOI 10.1137/0708071
- Paul T. Boggs, The convergence of the Ben-Israel iteration for nonlinear least squares problems, Math. Comp. 30 (1976), no. 135, 512–522. MR 416018, DOI 10.1090/S0025-5718-1976-0416018-3 T. BOGGS (1976b), Private communication.
- Paul T. Boggs and J. E. Dennis Jr., A stability analysis for perturbed nonlinear iterative methods, Math. Comp. 30 (1976), 199–215. MR 395209, DOI 10.1090/S0025-5718-1976-0395209-4
- Earl A. Coddington and Norman Levinson, Theory of ordinary differential equations, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1955. MR 0069338
- 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. 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. 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, DOI 10.1007/BF02163027
- Charles L. Lawson and Richard J. Hanson, Solving least squares problems, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1974. MR 0366019
- Kenneth Levenberg, A method for the solution of certain non-linear problems in least squares, Quart. Appl. Math. 2 (1944), 164–168. MR 10666, DOI 10.1090/S0033-569X-1944-10666-0
- Donald W. Marquardt, An algorithm for least-squares estimation of nonlinear parameters, J. Soc. Indust. Appl. Math. 11 (1963), 431–441. MR 153071, DOI 10.1137/0111030 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 and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
- 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. W. Stewart, Introduction to matrix computations, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. MR 0458818
Additional Information
- © Copyright 1977 American Mathematical Society
- Journal: Math. Comp. 31 (1977), 962-973
- MSC: Primary 65H10
- DOI: https://doi.org/10.1090/S0025-5718-1977-0443325-1
- MathSciNet review: 0443325