Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Newton's method for overdetermined
systems of equations

Authors: J. P. Dedieu and M. Shub
Journal: Math. Comp. 69 (2000), 1099-1115
MSC (1991): Primary 65, 15
Published electronically: May 19, 1999
MathSciNet review: 1651750
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Complexity theoretic aspects of continuation methods for the solution of square or underdetermined systems of polynomial equations have been studied by various authors. In this paper we consider overdetermined systems where there are more equations than unknowns. We study Newton's method for such a system.

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

  • 1. Allgower, E., and K. Georg, Continuation and Path Following, Acta Numerica, 1-64 (1993) MR 94k:65076.
  • 2. Blum, L., F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, Springer, New York (1997). MR 99a:68070
  • 3. Dedieu, J. P., Condition Number Analysis for Sparse Polynomial Systems, in: Foundations of Computational Mathematics, (F. Cucker and M. Shub, eds.), Springer, Heidelberg (1997).
  • 4. Dedieu, J. P. and M. Shub, Multihomogeneous Newton Methods, Math. Comp. (to appear).
  • 5. Dennis, J., and R. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice Hall (1983). MR 85j:65001
  • 6. Lang, S., Real Analysis, Addison-Wesley, Reading, Mass. (1983). MR 87b:00001
  • 7. Li, T. Y., Numerical Solution of Multivariate Polynomial Systems by Homotopy Continuation Methods, Acta Numerica, 6, 399-436 (1997). CMP 98:06
  • 8. Malajovich, G., On Generalized Newton Algorithms, Theoretical Computer Science 133, 65-84 (1994). MR 95g:65073
  • 9. Ortega, J., and W. Rheinboldt (editors), Studies in Numerical Analysis. Vol. 2: Numerical Solutions of Nonlinear Problems, SIAM, Philadelphia (1968). MR 42:1302
  • 10. Ostrowski, A., Solutions of Equations in Euclidean and Banach Spaces, Academic Press, New York, (1973). MR 50:11760
  • 11. Renegar, J., On the Efficiency of Newton's Method in Approximating All Zeros of Systems of Complex Polynomials, Math. of Oper. Research 12, 121-148 (1987). MR 88j:65112
  • 12. Royden, H., Newton's Method, Preprint, (1986).
  • 13. Seber, G., and C. Wild, Nonlinear Regression, John Wiley (1989). MR 90j:62004
  • 14. Shub, M., Some Remarks on Dynamical Systems and Numerical Analysis, in: Dynamical Systems and Partial Differential Equations: Proceedings of the VII ELAM (L. Lara-Carrero and J. Lewowicz, eds.), Universidad Simon Bolivar, Editoricil Equinoccio, pp. 69-92 (1986). MR 88j:58005
  • 15. Shub, M. and S. Smale, Complexity of Bézout's Theorem I: Geometric Aspects, J. Am. Math. Soc. 6, 459-501 (1993a). MR 93k:65054
  • 16. Shub, M. and S. Smale, Complexity of Bézout's Theorem II: Volumes and Probabilities, in: Computational Algebraic Geometry, Progress in Mathematics (F. Eyssette and A. Galligo, eds.), vol. 109, Birkhäuser, 267-285 (1993b). MR 94m:68086
  • 17. Shub, M. and S. Smale, Complexity of Bézout's Theorem III: Condition Number and Packing, J. of Complexity 9, 4-14 (1993c). MR 94g:65152
  • 18. Shub, M. and S. Smale, Complexity of Bézout's Theorem IV: Probability of Success, Extensions, SIAM J. Numer. Anal. 33, 128-148 (1996). MR 97k:65310
  • 19. Shub, M. and S. Smale, Complexity of Bézout's Theorem V: Polynomial Time, Theoretical Computer Science 133, 141-164 (1994). MR 96d:65091
  • 20. Smale, S., On the Efficiency of Algorithms of Analysis, Bull. A.M.S. 13, 87-121 (1985). MR 86m:65061
  • 21. Smale, S., Algorithms for Solving Equations, in: Proceedings of the International Congress of Mathematicians, A.M.S., pp. 172-195 (1986a). MR 89d:65060
  • 22. Smale, S., Newton's Method Estimates from Data at One Point, in: The Merging of Disciplines: New Directions in Pure, Applied and Computational Mathematics (R. Ewing, K. Gross, and C. Martin, eds.), Springer (1986b), 185-196. MR 88e:65076
  • 23. Smith, S., Optimization Techniques on Riemannian Manifolds, Fields Institute Communications 3, 113-136 (1994). MR 95g:58062
  • 24. Stewart, G. and J. Sun, Matrix Perturbation Theory, Academic Press (1990). MR 92a:65017
  • 25. Wang, X, Some Results Relevant to Smale's Reports, in: Proceedings of the Smalefest (M. V. Hirsch, J. E. Marsden, and M. Shub, eds.), Springer, pp. 456-465 (1993). CMP 94:03

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (1991): 65, 15

Retrieve articles in all journals with MSC (1991): 65, 15

Additional Information

J. P. Dedieu
Affiliation: LAO, Université Paul Sabatier, 31062 Toulouse, Cedex 04, France

M. Shub
Affiliation: Department of Mathematical Sciences, IBM Research Division, T.J. Watson Research Center, Yorktown Heights, NY 10598

Received by editor(s): February 19, 1998
Received by editor(s) in revised form: August 17, 1998
Published electronically: May 19, 1999
Additional Notes: The second author was partially supported by an NSF grant
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society