|
Newton's method for overdetermined systems of equations
Author(s):
J.
P.
Dedieu;
M.
Shub.
Journal:
Math. Comp.
69
(2000),
1099-1115.
MSC (1991):
Primary 65, 15
Posted:
May 19, 1999
Retrieve article in:
PDF DVI PostScript
This article is available free of charge
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:
- 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
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:
10.1090/S0025-5718-99-01115-1
PII:
S 0025-5718(99)01115-1
Received by editor(s):
February 19, 1998
Received by editor(s) in revised form:
August 17, 1998
Posted:
May 19, 1999
Additional Notes:
The second author was partially supported by an NSF grant
Copyright of article:
Copyright
2000,
American Mathematical Society
|
Comments: webmaster@ams.org