Seminars & Colloquia Calendar

Download as iCal file

Experimental Mathematics Seminar

A Globally Convergent Newton Method for Polynomials

Bahman Kalantari, Rutgers (CS).

Location:  Hill 705
Date & time: Thursday, 06 February 2020 at 5:00PM - 6:00PM

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.


Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.