Subject: Problem with expand in lagrange interpolation
From: Daniel Lakeland
Date: Wed, 13 Jun 2007 12:51:37 -0700
> > By expanding a high degree polynomial we typically create a
> > numerically unstable result, since the first term begins to dominate
> > rapidly, among other things.
> >
> > The newton divided difference formula is designed to avoid that, I
> > think it's the same thing as the horner scheme that we get from
> > "horner" in maxima
> Sorry, no. A divided difference interpolation form is not the same as
> horner's rule.
I wasn't sure about that one because I admit to not fully
understanding the divided difference scheme. The fact that there is
only one interpolation polynomial and many ways to write it makes the
whole thing a bit confusing for the non expert.
> Also the wikipedia entry for Horner is poor. It includes the falsehood...
> "Minimizing the number of multiplications is desirable because they are time
> consuming and numerically unstable compared to addition."
I noticed that one. Pretty aweful, but I wasn't sure how best to
correct it. From a speed perspective horner reduces the number of
operations. From a stability perspective it reduces the possibility of
numerical overflow when calculating things like x^25 or whatever. But
I'm not sure how it affects the possibility of subtractive cancellation.
--
Daniel Lakeland
dlakelan at street-artists.org
http://www.street-artists.org/~dlakelan