2
$\begingroup$

I need to numerically compute polynomial coefficients from its roots. However, this seems to be numerically unstable even for a moderate number of roots. For example, computing the polynomial $z^N - 1$ from the roots of unity $e^{2j\pi k/N}$ fails in Matlab for $N = 100$.

N= 100;
poleAngles = linspace(0,2*pi,N);
poleAngles(end) = [];

poleLocations = exp(1i*poleAngles);

% should be [1 0 0 ... 0 0 -1];
characteristicPolynomial = real(poly(poleLocations));

Please note, that this is just an example. In the original problem I have about 10.000 conjugate roots on the unit circle at random positions.

I would like to learn more about this problem: Is this an inherent problem, or specific to MATLAB? Is there a numerically more stable way to do the computation? Is there a name for this problem in scientific literature?

$\endgroup$
5
  • $\begingroup$ Polynomials in standard form are wonderful for proving theorems about, but completely horrible for numerical purposes if the degree is more than about a handful. The way to avoid numerical problems is to reformulate whatever your end goal is so you don't need to compute coefficients in the first place. $\endgroup$
    – hmakholm left over Monica
    Sep 25, 2017 at 15:10
  • $\begingroup$ @HenningMakholm: Ok, I was somehow surprised that it is that horrible. So my actual problem is: I've got large polynomials with some structure and I found a way to compute the roots. Now I want to check how accurate these roots are. I underestimated that going back from roots to coefficients is problematic. But maybe I should post this as a separate question? $\endgroup$
    – Jiro
    Sep 25, 2017 at 15:18
  • $\begingroup$ x @Sebastian: Yes I think a separate question would be good for that. $\endgroup$
    – hmakholm left over Monica
    Sep 25, 2017 at 15:20
  • $\begingroup$ @HenningMakholm: Ok, I put it here. $\endgroup$
    – Jiro
    Sep 25, 2017 at 15:38
  • $\begingroup$ The roots of a polynomial and its coefficients are related by continuous functions, but the relationship may not be well-condiitioned. Probably your best approach is to increase the working precision of your calculations. $\endgroup$
    – Somos
    Sep 25, 2017 at 19:10

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .