Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

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, Dexter
Stefansson, Kjartan
Keywords: computer science
technical 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
93-1392.pdf1.47 MBAdobe PDFView/Open
93-1392.ps410.47 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us