Anna Broms: Three Myths on Polynomial Interpolation and Root Finding

Abstract

Weierstrass approximation theorem states that every continuous function can be approximated arbitrarily well by a polynomial. Can such a polynomial be found via interpolation and does it hold numerically that an interpolatory polynomial of higher and higher degree converges to the function it tries to approximate? If equidistant points and a monomial basis is used, the answer is most certainly no for an arbitrary Lipschitz continuous function. This fact has given rise to the common misbelief that interpolation is not to be trusted: it’s neither numerically stable, nor a well-conditioned problem. If Chebyshev nodes and a Chebyshev basis is used, combined with barycentric interpolation, the story is different and interpolation to very high polynomial degrees is both stable and efficient. The key ideas are outlined in the talk. We will also explore the ill-conditioned problem of finding the roots of a polynomial given its coefficients. Surprisingly, this can be transformed into a stable global method for finding roots of a general function. If time allows we will explain the well-known Runge phenomenon near the end-points on an equidistant grid by applying potential theory.