logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-10032019-113459


Tipo di tesi
Tesi di laurea magistrale
Autore
CASULLI, ANGELO ALBERTO
URN
etd-10032019-113459
Titolo
Fast computation of the roots of polynomials in the Chebyshev basis
Dipartimento
MATEMATICA
Corso di studi
MATEMATICA
Relatori
relatore Prof. Bini, Dario Andrea
relatore Dott. Robol, Leonardo
Parole chiave
  • Chebyshev polynomials
  • Numerical analysis
  • Rootfinding
Data inizio appello
25/10/2019
Consultabilità
Completa
Riassunto
The aim of the thesis is to study methods for computing roots of polynomials and matrix polynomials expressed in the Chebyshev basis, with lower computational cost than the available methods.
Chebyshev polynomials have a fundamental role in approximation theory, in numerical linear algebra and in related applications. A recent application, which is a representative example of their good numerical properties, is the Matlab package ”Chebfun”, which allows to numerically handle smooth functions. The approach used in Chebfun is to interpolate smooth functions at the Chebyshev points and to write the interpolant polynomial in the Chebyshev basis. This technique has good stability properties ad can be done in a fast way by using inverse cosine transforms.
In such a context, finding roots of a polynomial in the Chebyshev basis becomes fundamental.
The main idea used to find the roots of a polynomial is to build a linearization matrix, usually called companion matrix, and find the eigenvalues of that matrix. This is what the Chebfun command roots does for computing the roots of a polynomial expressed in Chebyshev basis. This method computes the roots of a polynomial using O(n^2) memory storage and O(n^3) operations, where n is the polynomial degree.
To reduce this cost, it can be exploited the structure of the companion matrix.
The approach we use in this thesis is to exploit the structure of the companion matrix, for polynomials expressed in the Chebyshev basis, viewed as a symmetric matrix plus a rank-one correction. This fact will allow to design a fast and backward stable rootfinding algorithm based on the QR iteration. In fact, the overall computation cost of this algorithm is O(n^2) arithmetic operations with O(n) memory storage, where n is the degree of the polynomial.
File