Evaluation of Chebyshev polynomials on intervals and application to root finding

Viviane Ledoux (1, 2) , Guillaume Moroz (1)

1 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
2 ENS-PSL - École normale supérieure - Paris

In approximation theory, it is standard to approximate functions by polynomials expressed in the Chebyshev basis. Evaluating a polynomial $f$ of degree n given in the Chebyshev basis can be done in $O(n)$ arithmetic operations using the Clenshaw algorithm. Unfortunately, the evaluation of $f$ on an interval $I$ using the Clenshaw algorithm with interval arithmetic returns an interval of width exponential in $n$. We describe a variant of the Clenshaw algorithm based on ball arithmetic that returns an interval of width quadratic in $n$ for an interval of small enough width. As an application, our variant of the Clenshaw algorithm can be used to design an efficient root finding algorithm.

Mots clés: Chebyshev polynomials; Clenshaw algorithm; Root finding; Ball arithmetic; Interval arithmetic.

Domaines: Calcul formel [cs.SC]

Viviane Ledoux, Guillaume Moroz. Evaluation of Chebyshev polynomials on intervals and application to root finding. Mathematical Aspects of Computer and Information Sciences 2019, Nov 2019, Gebze, Turkey. ⟨hal-02405752⟩