Kantorovich Theorem example

Question

I need to write in C a program that finds roots of a 6th order polynomial. I was thinking of using Kantorovich Theorem convergence of Newton's method to find when can I use Newton-Rhapson method. I'm looking for an example of one varaiable polynomial how to find the domain were Newton-Rhapson can be used. Is there any conection to Sturm Sequences, where by them you can find a domain that has one root. Thanks

Answer 1

In one dimension, the Newton method converges on any interval that contains a sign change in the function value and no sign change in the first and second derivative.

The most complicated part for Newton-Kantorovich would be to find a bound of the second derivative $p''$ for some given interval. Then you can take any initial point $x_0$, compute the first Newton step $s_0$, find the maximum $L$ of the absolute value of the second derivative on $[x_0-|s_0|,\,x_0+|s_0|]$ and test the condition $L\,|p(x_0)|\,|p'(x_0)|^{-2}\le\frac12$. If it holds, then there is a unique root inside this interval.

Note however that there are better criteria for (real) roots of univariate polynomials.

---

Formulations of the Kantorovich theorem can be found in

• Ortega 1968 on the Kantorivich theorem http://www.jstor.org/stable/view/2313800
• Tapia 1971 on the same topic http://www.jstor.org/stable/view/2316909

Since the start of the 19th century there were various efforts to find methods to jump-start the Newton method for polynomials. Two such efforts were the root squaring idea of Dandelin, later named after Graeffe, which increases the separation of the magnitudes of the roots, and the approximation of the roots by continuous fractions and the simultaneous transformation of the polynomial by Möbius transforms introduced by M. Vincent. The latest accounts of both methods that I know of are an article by Malachovich-Zubelli for Dandelin-Graeffe and the work of A. Akritas on Vincent's method (largely discussing why it is not Uspensky's method and that the latter never existed).

Further approaches to root isolation in preparation or instead of Newton's method were based on the winding number theorem at the beginning of the computer age. One is the Lehmer method based on the Cohn-Schur test, another variant is the splitting circle method of Schönhage using FFT and Newton based on the Chinese remainder theorem to find factorizations corresponding to root clusters.

An approach using only the inner root radius (and Dandelin-Graeffe to better estimate it) to isolate root clusters is the bisection-exclusion method by Dedieu and Yakoubsohn http://www.sciencedirect.com/science/article/pii/S0885064X05000634

General ideas on the root determination of analytical functions using Newtons method can be found in various articles of S. Smale, see also the book Blum, Cucker, Smale: Complexity and Real Computation