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
DOI: https://doi.org/10.1090/S0025-5718-99-01115-1
Published electronically: May 19, 1999
MathSciNet review: 1651750
Full-text PDF Free Access

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. Eugene L. Allgower and Kurt Georg, Continuation and path following, Acta numerica, 1993, Acta Numer., Cambridge Univ. Press, Cambridge, 1993, pp. 1–64. MR 1224680
  • 2. Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale, Complexity and real computation, Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. MR 1479636
  • 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. John E. Dennis Jr. and Robert B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice Hall Series in Computational Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983. MR 702023
  • 6. Serge Lang, Real analysis, 2nd ed., Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. MR 783635
  • 7. Li, T. Y., Numerical Solution of Multivariate Polynomial Systems by Homotopy Continuation Methods, Acta Numerica, 6, 399-436 (1997). CMP 98:06
  • 8. Gregorio Malajovich, On generalized Newton algorithms: quadratic convergence, path-following and error analysis, Theoret. Comput. Sci. 133 (1994), no. 1, 65–84. Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993). MR 1294426, https://doi.org/10.1016/0304-3975(94)00065-4
  • 9. Studies in numerical analysis, 2: Numerical solutions of nonlinear problems, A collection of papers presented at Symposia in Numerical Solution of Nonlinear Problems sponsored by the Office of Naval Research at the Fall meeting of the Society for Industrial and Applied Mathematics held at Philadelphia, Pennsylvania, October 21-23, vol. 1968, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1970. MR 0266396
  • 10. A. M. Ostrowski, Solution of equations in Euclidean and Banach spaces, Academic Press [A Subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Third edition of Solution of equations and systems of equations; Pure and Applied Mathematics, Vol. 9. MR 0359306
  • 11. J. Renegar, On the efficiency of Newton’s method in approximating all zeros of a system of complex polynomials, Math. Oper. Res. 12 (1987), no. 1, 121–148. MR 882846, https://doi.org/10.1287/moor.12.1.121
  • 12. Royden, H., Newton's Method, Preprint, (1986).
  • 13. G. A. F. Seber and C. J. Wild, Nonlinear regression, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1989. MR 986070
  • 14. Yu. S. Baranov and Yu. E. Gliklikh, A nonintegrable distribution on an infinite-dimensional manifold of diffeomorphisms, Differentsial′naya Geom. Mnogoobraz. Figur 17 (1986), 11–17, 121 (Russian). MR 904777
  • 15. I. D. Coope, Circle fitting by linear and nonlinear least squares, J. Optim. Theory Appl. 76 (1993), no. 2, 381–388. MR 1203908, https://doi.org/10.1007/BF00939613
  • 16. M. Shub and S. Smale, Complexity of Bezout’s theorem. II. Volumes and probabilities, Computational algebraic geometry (Nice, 1992) Progr. Math., vol. 109, Birkhäuser Boston, Boston, MA, 1993, pp. 267–285. MR 1230872, https://doi.org/10.1007/978-1-4612-2752-6_19
  • 17. Michael Shub and Steve Smale, Complexity of Bezout’s theorem. III. Condition number and packing, J. Complexity 9 (1993), no. 1, 4–14. Festschrift for Joseph F. Traub, Part I. MR 1213484, https://doi.org/10.1006/jcom.1993.1002
  • 18. Michael Shub and Steve Smale, Complexity of Bezout’s theorem. IV. Probability of success; extensions, SIAM J. Numer. Anal. 33 (1996), no. 1, 128–148. MR 1377247, https://doi.org/10.1137/0733008
  • 19. M. Shub and S. Smale, Complexity of Bezout’s theorem. V. Polynomial time, Theoret. Comput. Sci. 133 (1994), no. 1, 141–164. Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993). MR 1294430, https://doi.org/10.1016/0304-3975(94)90122-8
  • 20. Steve Smale, On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. (N.S.) 13 (1985), no. 2, 87–121. MR 799791, https://doi.org/10.1090/S0273-0979-1985-15391-1
  • 21. Steve Smale, Algorithms for solving equations, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Berkeley, Calif., 1986) Amer. Math. Soc., Providence, RI, 1987, pp. 172–195. MR 934223
  • 22. Steve Smale, Newton’s method estimates from data at one point, The merging of disciplines: new directions in pure, applied, and computational mathematics (Laramie, Wyo., 1985) Springer, New York, 1986, pp. 185–196. MR 870648
  • 23. Steven T. Smith, Optimization techniques on Riemannian manifolds, Hamiltonian and gradient flows, algorithms and control, Fields Inst. Commun., vol. 3, Amer. Math. Soc., Providence, RI, 1994, pp. 113–136. MR 1297990
  • 24. G. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154
  • 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 of the American Mathematical Society 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
Email: dedieu@cict.fr

M. Shub
Affiliation: Department of Mathematical Sciences, IBM Research Division, T.J. Watson Research Center, Yorktown Heights, NY 10598
Email: mshub@us.ibm.com

DOI: https://doi.org/10.1090/S0025-5718-99-01115-1
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