# Stability of root-finding near the unit circle

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.

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

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.