NROOTS attempts to find all the roots of a real/complex polynomial. It uses a two-step algorithm: a first-approximation to a root is found via the companion matrix method (as per the built-in function ROOTS) and then this approximation is refined (polished) via a Newton-Raphson iteration scheme. The Newton-Raphson refinement will be rejected if it does not represent an improvement over the original root OR if the refined root actually corresponds to a different ("incorrect") root.
The algorithm is about an order of magnitude slower though generally more accurate (see figure for illustration) than ROOTS.
---------------------------------------
Note: NROOTS' goal is basically to polish output from ROOTS. In the (hopefully rare) situations where ROOTS fails to compute one or more roots accurately, NROOTS will be similarly unlikely to succeed. However, NROOTS seems to work very well in "non-pathological" cases. An algorithm such as e.g. MULTROOT by Z. Zeng (2004) would be more suitable for problems involving, say, degenerate roots (although the accuracy comes at the expense of speed and simplicity).
Further note: I wrote this algorithm for the purpose of finding accurately non-degenerate roots of degree-5 complex polynomials, for which purpose it works well. However, suggestions as to how the algorithm might be made more robust, versatile or efficient would be appreciated. |