New fast algorithms for polynomial interpolation and evaluation on the chebyshev node set

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Fen Bilimleri Enstitüsü, Fen Bilimleri Enstitüsü, Türkiye

Tezin Onay Tarihi: 2000

Tezin Dili: İngilizce

Öğrenci: ALİ DELİCEOĞLU

Danışman: MÜNEVVER TEZER

Özet:

ABSTRACT NEW FAST ALGORITHMS FOR POLYNOMIAL INTERPOLATION AND EVALUATION ON THE CHEBYSHEV NODE SET Deliceoğlu, Ali M.Sc, Department of Mathematics Supervisor: Prof. Dr. Münevver Tezer June 2000, 126 pages In this thesis, new fast algorithms for polynomial interpolation and evalua tion on the Chebyshev node set are introduced and the computational complexity of these methods are discussed. We consider polynomial evaluation and interpo lation on a set of points, with particular attention to the case of Fourier points (roots of unity). This case brings us to the Discrete Fourier Transform and to the Fast Fourier Transform algorithms. Then the evaluation-interpolation technique is introduced and is also applied to the computation of a polynomial product and the evaluation of a polynomial at a shifted variable. In order to make com parisons of these new algorithms with the standard algorithms (Horner's method and standard polynomial product), Fortran program codes are written for each technique and the results are discussed at several points. All these work showed that the cost of the new fast algorithms are of 0(nlogn) arithmetic operations. Keywords: Chebyshev nodes, Polynomial interpolation, Polynomial evaluation, Algorithms, Computational complexity, Fast Fourier transform. Ill