Skip to Main content Skip to Navigation
Conference papers

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
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-02405752
Contributor : Guillaume Moroz <>
Submitted on : Wednesday, December 11, 2019 - 7:02:01 PM
Last modification on : Tuesday, September 22, 2020 - 3:53:28 AM
Long-term archiving on: : Thursday, March 12, 2020 - 10:23:45 PM

Files

macis2019_chebyshev.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02405752, version 1
  • ARXIV : 1912.05843

Citation

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⟩

Share

Metrics

Record views

76

Files downloads

409