Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6170
 Title: Computing the Newtonian Graph (Extended abstract) Authors: Kozen, DexterStefansson, Kjartan Keywords: computer sciencetechnical report Issue Date: Oct-1993 Publisher: Cornell University Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1392 Abstract: A polynomial $f\in \complex[z]$ defines a vector field $N_f(z) = -f(z)/f'(z)$ on $\complex$. Certain degenerate curves of flow in $N_f$ give the edges of the Newtonian graph, as defined by \cite{Sma85}. These give a relation between the roots of $f$ and $f'$, much similar to the linear order, when $f$ has real roots only. We give a purely algebraic algorithm to compute the Newtonian graph and the basins of attraction in the Newtonian field. The resulting structure can be used to query whether two points in $\complex$ are within the same basin of attraction. This gives us an algebraic approach to root-finding using Newton's method. This method extends to rational functions and more generally to any functions on $\complex$ whose flow is algebraic over $\complex(e)$. URI: http://hdl.handle.net/1813/6170 Appears in Collections: Computer Science Technical Reports

Files in This Item:

File Description SizeFormat