Newton’s method for overdetermined systems of equations

Dedieu, J.; Shub, M.

doi:10.1090/S0025-5718-99-01115-1

Newton’s method for overdetermined systems of equations
HTML articles powered by AMS MathViewer

by J. P. Dedieu and M. Shub PDF

Math. Comp. 69 (2000), 1099-1115 Request permission

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

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, DOI 10.1017/s0962492900002336
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, DOI 10.1007/978-1-4612-0701-6
Dedieu, J. P., Condition Number Analysis for Sparse Polynomial Systems, in: Foundations of Computational Mathematics, (F. Cucker and M. Shub, eds.), Springer, Heidelberg (1997).
Dedieu, J. P. and M. Shub, Multihomogeneous Newton Methods, Math. Comp. (to appear).
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
Serge Lang, Real analysis, 2nd ed., Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. MR 783635
Li, T. Y., Numerical Solution of Multivariate Polynomial Systems by Homotopy Continuation Methods, Acta Numerica, 6, 399–436 (1997).
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, DOI 10.1016/0304-3975(94)00065-4
James M. Ortega and Werner C. Rheinboldt (eds.), Studies in numerical analysis, 2: Numerical solutions of nonlinear problems, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1970. 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, 1968. MR 0266396
A. M. Ostrowski, Solution of equations in Euclidean and Banach spaces, Pure and Applied Mathematics, Vol. 9, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Third edition of Solution of equations and systems of equations. MR 0359306
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, DOI 10.1287/moor.12.1.121
Royden, H., Newton’s Method, Preprint, (1986).
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, DOI 10.1002/0471725315
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
I. D. Coope, Circle fitting by linear and nonlinear least squares, J. Optim. Theory Appl. 76 (1993), no. 2, 381–388. MR 1203908, DOI 10.1007/BF00939613
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, DOI 10.1007/978-1-4612-2752-6_{1}9
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, DOI 10.1006/jcom.1993.1002
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, DOI 10.1137/0733008
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, DOI 10.1016/0304-3975(94)90122-8
Steve Smale, On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. (N.S.) 13 (1985), no. 2, 87–121. MR 799791, DOI 10.1090/S0273-0979-1985-15391-1
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
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
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
G. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154
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).