The Interpolation Song

(to the tune of "Long Long Ago")

Given some points to interpolate,
We have three ways to interpolate.
Monomial, Lagrange, or the way of Newton,
equivalent ways it's done.
Monomial seems the most straightforward.
But when you get to know, it's really absurd.
But no matter how interpolation is done,
the error term is the same one. [*]

Monomial is a curious one,
Just form the matrix of Vandermonde.
The matrix is dense and its problems abound
when high degrees are found.
O of n cubed, coefficients to find
Plus the conditioning's not very kind:
Growing exponentially with n
Don't try to use this again!

Lagrange basis makes it easy to get
coefficients from a diagonal matrix.
But to evaluate is a much harder trick,
for the inverse is so thick!
Lagrange is the sum of y_i times l_j;
l_j's the product of t minus t_k
over the product of t_j minus t_k.
This is the Lagrange way.

Newton interpolation does not make me stir
its basis matrix is triangular.
The coefficients of it can be found
by divided dif'rences all around.
f of t_1 through t_k is the diff
of f[t_2,t_k] and f[t_1,t_k-1]
divide all that by t_k minus t_1,
and with Newton, you have won.

"The Interpolation Song" Copyright (c) 2000-2007 Rebecca Hartman-Baker.

Last updated January 22, 2007

hartmanbakrj@ornl.gov