A study of accelerated Newton methods for multiple polynomial roots (Q973853): Difference between revisions

Given a univariate, complex polynomial \(f(z)\) of degree \(d \geq 2\), Newton's method has local quadratic convergence for simple zeros, but only linear convergence for multiple zeros. Numerous variations of Newton's method have been proposed to try to accelerate the convergence at multiple zeros. Critical to their success is the accuracy of their `built in' multiplicity estimates. In order to unify various methods of estimating the multiplicity of a root and determining the neighborhood of convergence, the authors introduce the concept of an indicator function: Definition: As usual, let \(f^{(j)}(x)\) be the \(j^{th}\) derivative of \(f\). The functions \[ \text{Ind}_j(f(x)) = f^{(j-1)}(x)*f^{(j+1)}(x)/(f^{(j)}(x))^2 \] will be called \textit{indicator functions} of \(f\). They note that the indicator functions can be seen as generalizations of Crouse and Putt's derivative ratios [Roots of Polynomials by Ratio of Successive Derivatives. Technical Report, NASA TN D-6793, NASA, Washington (1972)], and \(\text{Ind}_1(f(x))\) is \textit{M. A. Hernández Verón}'s [Numer. Math. 59, No. 3, 273--276 (1991; Zbl 0712.65035)] degree of logarithmic convexity. Additionally, they note that if, in a particular domain, \(\text{Ind}_j(f)\) returns values in the range of \([0,2]\), then one may expect a zero or pole of \(f(x)\) in that domain. Moreover, the indicator function also estimates the order of the zero or pole in that domain. However, they caution that if \(f\) has a cluster of \(j\) roots relatively close to each other, then far enough away, these distinct roots will `seem as a multiple root', and a Newton iteration results in a value somewhere near the center of the cluster. The authors discuss the algorithm of Crouse and Putt for polynomial roots in detail, giving, in addition, a simple variant. They also discuss \textit{E. Schröder}'s [Clebsch. Ann. II. 317--365 (1870; JFM 02.0042.02)] multiplicity estimate, noting that it can be reformulated as \(1/(1-\text{Ind}_1(f))\). They compare several other multiplicity estimates to Schröder's estimate, including those of Ostrowski, Aitken-Steffensen and Rall. The authors end with computational experiments comparing: Newton-Schröder, Newton-Schröder rounded to nearest integer, Newton-Rall, Newton-Rall rounded to nearest integer, Newton-Traub, Newton-Traub rounded to nearest integer, Newton-Aitken-Steffensen, Newton-Ostrowski, Newton-Madsen, Newton-Hansen-Patrick, and Crouse-Putt-Newton. They conclude that, on average, Newton-Madsen generally takes the fewest iterations. Assigning unique scores from 1 to 11 (1 being best, 11 being worst) and summing the individual scores for each of the comparisons, Newton-Schröder rounded and Netwon-Madsen tie for first place, with Newton-Schröder (not rounded) coming in a not-too-distant third. The appendix lists the polynomials used in the tests.