arXiv
Open Access
2019
Evaluation of Chebyshev polynomials on intervals and application to root finding
Viviane Ledoux
Guillaume Moroz
Abstrak
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.
Topik & Kata Kunci
Penulis (2)
V
Viviane Ledoux
G
Guillaume Moroz
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2019
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓