HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Wednesday, December 11, 2019 - 7:02:01 PM
Last modification on : Thursday, March 17, 2022 - 10:08:41 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

71

Files downloads

470