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.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Are you saying that this is independent of algorithm??? $\endgroup$– Igor RivinCommented Nov 2, 2017 at 23:00
-
$\begingroup$ Yes, it is stated as a fact about about the conditioning of the problem, independently of an algorithm. $\endgroup$– user49097Commented Nov 2, 2017 at 23:18
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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.
answered Nov 2, 2017 at 23:21
-
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$ Commented Nov 2, 2017 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$ Commented Nov 3, 2017 at 4:36
-
1$\begingroup$ @user, the references section of that article would be pretty good further reading. $\endgroup$ Commented Nov 3, 2017 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$ Commented Nov 3, 2017 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$ Commented Nov 3, 2017 at 4:49