Doctor of Philosophy
Corless, Robert M.
This thesis investigates eigenvalue techniques for the location of roots of polynomials expressed in the Lagrange basis. Polynomial approximations to functions arise in almost all areas of computational mathematics, since polynomial expressions can be manipulated in ways that the original function cannot. Polynomials are most often expressed in the monomial basis; however, in many applications polynomials are constructed by interpolating data at a series of
points. The roots of such polynomial interpolants can be found by computing the eigenvalues of a generalized companion matrix pair constructed directly from the values of the interpolant. This affords the opportunity to work with polynomials expressed directly in the interpolation basis in which they were posed, avoiding the often ill-conditioned transformation between bases.
Working within this framework, this thesis demonstrates that computing the roots of polynomials via these companion matrices is numerically stable, and the matrices involved can be reduced in such a way as to significantly lower the number of operations required to obtain the roots.
Through examination of these various techniques, this thesis offers insight into the speed, stability, and accuracy of rootfinding algorithms for polynomials expressed in alternative bases.
Lawrence, Piers W., "Eigenvalue Methods for Interpolation Bases" (2013). Electronic Thesis and Dissertation Repository. 1359.