5
$\begingroup$

It is stated in several sources on numerical analysis that the general problem of polynomial root-finding is ill-conditioned, but that it is well-conditioned if the roots are near the unit circle. (e.g. see page 133 of Approximation Theory and Approximation Practice by Trefethen.) What is the underlying reason for this? Thank you very much.

$\endgroup$
  • $\begingroup$ Are you saying that this is independent of algorithm??? $\endgroup$ – Igor Rivin Nov 2 '17 at 23:00
  • $\begingroup$ Yes, it is stated as a fact about about the conditioning of the problem, independently of an algorithm. $\endgroup$ – user49097 Nov 2 '17 at 23:18
8
$\begingroup$

The issue is explained nicely in Six Myths of Polynomial Interpolation and Quadrature. It is not a stability problem of polynomial root finding, but a problem of finding the proper representation of the polynomial. If the roots are on or near the unit circle, you want to express the polynomial in an orthogonal basis on the unit circle, which is the basis of monomials $x^k$. If the roots are near the real axis, close to the interval $[-1,1]$, you want instead to use a basis that is orthogonal on that interval (Chebyshev polynomials). If you use the wrong basis the algorithm is unstable, but that is not a problem with the algorithm per se, but with the choice of basis.

The cited reference gives an example how root finding in the interval $[-1,1]$ is highly robust if you represent the polynomial in terms of the orthogonal Chebyshev polynomials [using the Chebfun algorithm], while a representation in terms of monomials is highly sensitive to small errors in the coefficients.

$\endgroup$
  • 1
    $\begingroup$ Since the standard basis is not very orthogonal on the interval, then, presumably, rewriting your polynomial in the Chebyshev basis might be unstable in and of itself. $\endgroup$ – Igor Rivin Nov 2 '17 at 23:27
  • 2
    $\begingroup$ @Igor, correct; the map from monomial coefficients to Chebyshev coefficients is a possible source of inaccuracy. I made a Mathematica demo of the conditioning of the basis conversion matrix here. $\endgroup$ – J. M. isn't a mathematician Nov 3 '17 at 4:36
  • 1
    $\begingroup$ @user, the references section of that article would be pretty good further reading. $\endgroup$ – J. M. isn't a mathematician Nov 3 '17 at 4:36
  • 2
    $\begingroup$ @J.M.isnotamathematician Thanks! That lends credence to the OP's claim that it is the problem which is unstable (given that the polynomial is presented in the usual way - if the polynomial is given by values at points, presumably there might be a more stable way of finding a chebyshev representation) $\endgroup$ – Igor Rivin Nov 3 '17 at 4:45
  • 1
    $\begingroup$ @Igor, indeed, it is that the problem is ill-conditioned, and not that the algorithms are unstable. For the "polynomial is given by values at points" case, Trefethen and others have recommended the "barycentric Lagrange form" for good stability. $\endgroup$ – J. M. isn't a mathematician Nov 3 '17 at 4:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.