Problem with expand in lagrange interpolation

Regarding the numerical properties of horner's rule...
It is usually better than the na?ve way, but there are more accurate ways,
especially if you know that f(x) will be evaluated for x near some
particular point p.   (Try expanding f in a Taylor series around the closest
zero to p).
 
But adding numbers that nearly cancel  e.g. 3.0000  and -3.0001  results in
amplifying any errors. Multiplying numbers does not have this problem.

And for many machines, adding and multiplying might as well be of equal
cost. The real time sink is memory access.

RJF

> -----Original Message-----
> From: maxima-bounces at math.utexas.edu 
> [mailto:maxima-bounces at math.utexas.edu] On Behalf Of Daniel Lakeland
> Sent: Wednesday, June 13, 2007 12:52 PM
> To: maxima at math.utexas.edu
> Subject: Re: [Maxima] Problem with expand in lagrange interpolation
> 
> > > 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
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>