Relating the Arnoldi approximation to the best Chebyshev approximation of the characteristic polynomial - A study using a complex valued variant of the Remez algorithm
(2022) In Bachelor's Theses in Mathematical Sciences NUMK11 20212Mathematics (Faculty of Sciences)
Centre for Mathematical Sciences
- Abstract
- The Remez algorithm is a beautiful algorithm that finds the best approximation to a function by finding points satisfying the alternation condition. In 1987 Ping Tang published his doctoral thesis detailing a version of the Remez algorithm modified for functions of complex values with complex coefficients. He later followed the thesis with an article presenting an algorithm for finding the coefficients of a complex valued function. The Arnoldi approximation is a well-known iterative method for approximating the m eigenvalues of a matrix by a smaller set of n eigenvalues. The accuracy of the Arnoldi approximation is however dependent on an initial choice of a vector. The best choice of this initial vector leads to the so called ideal... (More)
- The Remez algorithm is a beautiful algorithm that finds the best approximation to a function by finding points satisfying the alternation condition. In 1987 Ping Tang published his doctoral thesis detailing a version of the Remez algorithm modified for functions of complex values with complex coefficients. He later followed the thesis with an article presenting an algorithm for finding the coefficients of a complex valued function. The Arnoldi approximation is a well-known iterative method for approximating the m eigenvalues of a matrix by a smaller set of n eigenvalues. The accuracy of the Arnoldi approximation is however dependent on an initial choice of a vector. The best choice of this initial vector leads to the so called ideal Arnoldi approximation. In 1994 Anne Greenbum and Lloyd Trefethen published an article discussing the possibility of finding the ideal Arnoldi approximation using Chebyshev approximation. The purpose of this thesis is to experiment with Ping Tangs algorithm to approximate the characteristic equation of a matrix on a circle set and compare the results to that of the ideal Arnoldi approximation to see if the ideal Arnoldi is a best approximation in a Chebyshev sense. (Less)
- Popular Abstract (Swedish)
- Beräkningar med stora matriser är svåra och långsamma att utföra, även för datorer. Med hjälp av en matrisens egenvärden kan man istället arbeta med dess karaktäristiska polynom, där egenvärdena är nollställen. För mycket stora matriser får detta polynom en hög grad och vi skulle vilja approximera det med ett av lägre grad för att förenkla beräkningarna ytterligare. En populär metod för att göra detta är den så kallade Arnoldimetoden som ger oss ett set av färre egenvärden som approximerar de ursprungliga. Den metoden kan dock ge olika resultat beroende på dess startparametrar. I detta arbete kommer vi jämföra det bästa möjliga resultatet ifrån Arnoldimetoden, med optimala startparametrar, med en annan metod presenterad av Ping Tang som... (More)
- Beräkningar med stora matriser är svåra och långsamma att utföra, även för datorer. Med hjälp av en matrisens egenvärden kan man istället arbeta med dess karaktäristiska polynom, där egenvärdena är nollställen. För mycket stora matriser får detta polynom en hög grad och vi skulle vilja approximera det med ett av lägre grad för att förenkla beräkningarna ytterligare. En populär metod för att göra detta är den så kallade Arnoldimetoden som ger oss ett set av färre egenvärden som approximerar de ursprungliga. Den metoden kan dock ge olika resultat beroende på dess startparametrar. I detta arbete kommer vi jämföra det bästa möjliga resultatet ifrån Arnoldimetoden, med optimala startparametrar, med en annan metod presenterad av Ping Tang som approximerar komplexvärda funktioner med polynom. Vi kommer att applicera Tangs metod på den ursprungliga matrisens karaktäristiska polynom och se hur de olika metodernas resultat skiljer sig åt. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/9098223
- author
- Renström, Thomas LU
- supervisor
-
- Claus Führer LU
- organization
- alternative title
- Om Arnoldiapproximationens relation till det karakteristiska polynomets bästa Chebyshevapproximation - en experimentell studie med en komplexvärd variant av Remez algoritm
- course
- NUMK11 20212
- year
- 2022
- type
- M2 - Bachelor Degree
- subject
- keywords
- Chebyshev, Arnoldi, Remez, Tang, approximation, matrix, complex, characteristic polynomial
- publication/series
- Bachelor's Theses in Mathematical Sciences
- report number
- LUNFNA-4042-2022
- ISSN
- 1654-6229
- other publication id
- 2022:K16
- language
- English
- id
- 9098223
- date added to LUP
- 2022-09-19 15:32:16
- date last changed
- 2022-09-19 15:32:16
@misc{9098223,
abstract = {{The Remez algorithm is a beautiful algorithm that finds the best approximation to a function by finding points satisfying the alternation condition. In 1987 Ping Tang published his doctoral thesis detailing a version of the Remez algorithm modified for functions of complex values with complex coefficients. He later followed the thesis with an article presenting an algorithm for finding the coefficients of a complex valued function. The Arnoldi approximation is a well-known iterative method for approximating the m eigenvalues of a matrix by a smaller set of n eigenvalues. The accuracy of the Arnoldi approximation is however dependent on an initial choice of a vector. The best choice of this initial vector leads to the so called ideal Arnoldi approximation. In 1994 Anne Greenbum and Lloyd Trefethen published an article discussing the possibility of finding the ideal Arnoldi approximation using Chebyshev approximation. The purpose of this thesis is to experiment with Ping Tangs algorithm to approximate the characteristic equation of a matrix on a circle set and compare the results to that of the ideal Arnoldi approximation to see if the ideal Arnoldi is a best approximation in a Chebyshev sense.}},
author = {{Renström, Thomas}},
issn = {{1654-6229}},
language = {{eng}},
note = {{Student Paper}},
series = {{Bachelor's Theses in Mathematical Sciences}},
title = {{Relating the Arnoldi approximation to the best Chebyshev approximation of the characteristic polynomial - A study using a complex valued variant of the Remez algorithm}},
year = {{2022}},
}