3
$\begingroup$

Given the coefficients of a polynomial of high degree, i.e. n > 10.000. The polynomials have some nice structure such that I was able to find a way to compute its roots. Now I would like to evaluate how accurate these computed roots actually are. What is the best way to do this?

Initially, I tried to compute the coefficients from the roots, but this turns out to be numerically unstable. For more details here.

$\endgroup$
4
  • $\begingroup$ How did you manage the roots? Which method? (Newton, bisection...) $\endgroup$
    – Raffaele
    Sep 25, 2017 at 15:46
  • $\begingroup$ @Raffaele: The strongest property of the polynomials $p$ are that the roots are on the unit circle. So, having $p$ as the denominator of a transfer function, its impulse response consists of sinusoids with angles corresponding to the root location. (Hope this makes sense) In the end I refine with Newton. $\endgroup$
    – Jiro
    Sep 25, 2017 at 15:56
  • $\begingroup$ I find it difficult to believe that the structure which allowed you to find the roots would not be helpful when trying to evaluate their quality. Consider writing a few words about the structure. Also add a few words about the desired properties of a "more collective evaluation of the roots". Error estimates can be derived from successive iterates of Newton's method. at little extra cost. Why would a SIMD/OpenMP implementation of this not be good enough? $\endgroup$
    – Carl Christian
    Sep 25, 2017 at 17:38
  • $\begingroup$ @CarlChristian Sorry, my idea for a "more collective evaluation of the roots" was pointless. $\endgroup$
    – Jiro
    Sep 25, 2017 at 17:56

1 Answer 1

Reset to default
2
$\begingroup$

Easiest way I think is to plug in the computed root into the polynomial, using Horner's rule to save computation time. The polynomial should evaluate to zero, and the actual value of the evaluation will be the measure of the error involved.

$\endgroup$
3
  • $\begingroup$ Well, this is of course true, but as the number of roots is that high, I would appreciate a more collective evaluation instead of the accuracy of the individual roots. So, how does the error of all roots add up? $\endgroup$
    – Jiro
    Sep 25, 2017 at 16:00
  • $\begingroup$ To get less numerical errors, this can be improved by using a compensated Horner Scheme, e.g. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.81.2979 and you get some error estimates. $\endgroup$
    – gammatester
    Sep 25, 2017 at 16:04
  • $\begingroup$ @gammatester Thank you for the link. This looks helpful for the individual root accuracy. $\endgroup$
    – Jiro
    Sep 25, 2017 at 16:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .