Computing the Newtonian graph (Q1368688)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Computing the Newtonian graph |
scientific article |
Statements
Computing the Newtonian graph (English)
0 references
20 April 1998
0 references
In his study of Newton's root approximation method, \textit{S. Smale} [Bull. Am. Math. Sco., New Ser. 13, 87-121 (1985; Zbl 0592.65032)] defined the Newtonian graph of a complex univariate polynomial \(f\). The vertices of this graph are the roots of \(f\) and \(f'\) and the edges are the degenerate curves of flow of the Newtonian vector field \(N_f(z)= -f(z)/f'(z)\). The embedded edges of this graph form the boundaries of the basins of the roots with respect, to Newton's vector field. The paper is concerned with an algebraic algorithm based on cell decomposition to compute the graph. The answer to the question whether two points belong to the same basin is related to the question whether one crosses the boundary of a basin during Newton's iteration. \{Remark: A lemma which is cited as being due to Shub (1988) was actually published in [Numer. Math. 29, 123-132 (1977; Zbl 0363.65033)] by the reviewer\}.
0 references
Shub's lemma
0 references
Newton's root approximation method
0 references
Newtonian graph
0 references
Newton's vector field
0 references
algebraic algorithm
0 references
Newton's iteration
0 references