Seminar Details
2013-10-08 (14.00) : Barycentric Lagrange Interpolation and Rootfinding
At Euler building
Organized by Mathematical Engineering
Speaker :
Piers Lawrence (UCLouvain/KULeuven)
Abstract :
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.
In many numerical analysis textbooks the Lagrange basis is quickly disposed of in favour of the Newton basis, due to the larger amount of work required for evaluation and questionable numerical stability of the Lagrange interpolation formula. However, a simple rearrangement yields the so called barycentric interpolation formula which can be shown to be numerically stable, and can be evaluated using the same number of operations as for the Newton basis.
To compute the roots of a polynomial expressed in barycentric form, we may linearize the polynomial, which is to say we convert the rootfinding problem into a generalized eigenvalue problem. This particular linearization is constructed directly from the coefficients in the Lagrange basis (that is, directly from function values). In this talk we show how the linearization can be reduced Hessenberg form in only O(n^2) operations by taking advantage of the structure of the matrices. Thus, we may compute all of the roots of a degree n polynomial in O(n^2) time and O(n) storage. We further show that computing the roots of polynomials via this linearization is backward stable, and give easily computable (and intelligible) bounds for the backward error.