Code covered by the BSD License  

Highlights from
NROOTS: complex polynomial root finder

5.0

5.0 | 1 rating Rate this file 21 Downloads (last 30 days) File Size: 2.6 KB File ID: #30696
image thumbnail

NROOTS: complex polynomial root finder

by

 

NROOTS finds all the roots of real/complex polynomials. Accuracy is better than with ROOTS.

| Watch this File

File Information
Description

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.

MATLAB release MATLAB 7.6 (R2008a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (1)
25 Dec 2012 Huang xin

good work

Contact us