Title: A Globally Convergent Newton Method for Polynomials
Speaker: Bahman Kalantari, Department of Computer Science, Rutgers University (NB)
Abstract: Newton's method for polynomial root finding is one of mathematics' most well-known algorithms. The method also has its shortcomings: it is undefined at critical points, it could exhibit chaotic behavior and is only guaranteed to converge locally. Based on the Geometric Modulus Principle for a complex polynomial p(z), together with a Modulus Reduction Theorem , we develop the Robust Newton's method (RNM), defined everywhere with a step-size that guarantees an a priori reduction in polynomial modulus in each iteration. Furthermore, we prove RNM iterates converge globally, either to a root or a critical point. Specifically, given epsilon and any seed z_0, in t=O(1/epsilon^2) iterations of RNM, independent of degree of p(z), either |p(z_t)| < epsilon or |p(z_t) p'(z_t)| < epsilon. By adjusting the iterates at near-critical points, we describe a modified RNM that necessarily convergence to a root. In combination with Smale's point estimation, RNM results in a globally convergent Newton's method having a locally quadratic rate. We present sample polynomiographs that demonstrate how in contrast with Newton's method RNM smooths out the fractal boundaries of basins of attraction of roots. RNM also finds potentials in computing all roots of arbitrary degree polynomials. A particular consequence of RNM is a simple algorithm for solving cubic equations.