I've implemented the Jenkins Traub algorithm in c++ (Github repo). While the majority of the solutions work well, it seems that a small portion of the roots are unstable. Here is a figure showing polynomials evaluated at the computed roots (termed "residual"). This value should always be close to zero since we are finding polynomial roots, however, sometimes the value is unstable.
My intuition is that these unstable roots occur in polynomials with poor conditioning, and that it could be fixed by rescaling the polynomial somehow. Methods exist for balancing and scaling companion matrices, but does anything exist for the polynomial itself?
Thanks very much for the feedback, I realized a flaw in my experiments. For evaluating the Jenkins-Traub method I was taking the real value of all roots whereas for the companion matrix I was only consider roots where the imaginary component was 0. This has a large effect on the residuals. After correcting this error here are my updated results that I am now very happy with:
When the histogram starts on the y-axis it means that portion of roots evaluated to 0 within machine precision.