TOPICS
Search

Newtonian Graph


Newton's method for finding roots of a complex polynomial f entails iterating the function z-[f(z)/f^'(z)], which can be viewed as applying the Euler backward method with step size unity to the so-called Newtonian vector field N_f(z)=-f(z)/f^'(z). The rescaled and desingularized vector field V_f(z)=-f(z)f^'(z)^_ then has sinks at roots of f and has saddle points at roots of f^' that are not also roots of f. The union of the closures of the unstable manifolds of the saddles of V_f defines a directed graph whose vertices are the roots of f and of f^', and whose edges are the unstable curves oriented by the flow direction. This graph, along with the labelling of each vertex w with the multiplicity m(w)>=0 of w as a root of f, is defined to be the Newtonian graph of f (Smale 1985, Shub et al. 1988, Kozen and Stefánsson 1997).


See also

Newton's Method, Newtonian Vector Field, Vector Field

Explore with Wolfram|Alpha

References

Airapetyan, R. "Continuous Newton Method and Its Modification." Appl. Anal. 73, 463-484, 1999.Airapetyan, R.; Ramm, A. G.; and Smirnova, A. "Continuous Analog of the Gauss-Newton Method." Math. Models Methods Appl. Sci. 9, 463-474, 1999.Diener, I. "Trajectory Methods in Global Optimization." In Handbook of Global Optimization, 2 (Ed. R. Horst and P. M. Pardalos). Dordrecht, Netherlands: Kluwer, pp. 649-668, 1995.Jongen, H. T.; Jonker, P.; and Twilt, F. "The Continuous Newton-Method for Meromorphic Functions." In Geometrical Approaches to Differential Equations (Proc. Fourth Scheveningen Conf., Scheveningen, 1979) (Ed. R. Martini). Berlin: Springer-Verlag, pp. 181-239, 1980.Jongen, H. T.; Jonker, P.; and Twilt, F. "The Continuous, Desingularized Newton Method for Meromorphic Functions." Acta Appl. Math. 13, 81-121, 1988.Kozen, D. and Stefánsson, K. "Computing the Newtonian Graph." J. Symb. Comput. 24, 125-136, 1997.Shub, M.; Tischler, D.; Williams, R. F. "The Newtonian Graph of a Complex Polynomial." SIAM J. Math. Anal. 19, 246-256, 1988.Smale, S. "On the Efficiency of Algorithms of Analysis." Bull. Amer. Math. Soc. 13, 87-121, 1985.

Referenced on Wolfram|Alpha

Newtonian Graph

Cite this as:

Weisstein, Eric W. "Newtonian Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NewtonianGraph.html

Subject classifications