From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: polynomial interpolation
Date: Tue, 7 Apr 2009 07:14:04 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 20
Message-ID: <greufs$pb3$>
References: <grehui$pi$>
Reply-To: <HIDDEN>
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: 1239088444 25955 (7 Apr 2009 07:14:04 GMT)
NNTP-Posting-Date: Tue, 7 Apr 2009 07:14:04 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: comp.soft-sys.matlab:530965

"Pr B" <> wrote in message <grehui$pi$>...
> i'm trying to implement newton interpolation in matlab.  i have already implemented lagrange interpolation.  it seems like the latter is faster in terms of operation counts (O(n)).
> how many operations does newton interpolation require?

  I would say that it is the other way around.  Using Newton's interpolation should involve fewer operations.  For example, suppose for the moment we don't count the operations of computing the divided differences, since that is a fixed calculation and doesn't depend on the number of new points being interpolated between those fixed points.  Furthermore suppose it is cubic interpolation.  Then in Newton's interpolation, each new y for a given x can be expressed in the form

 y = y0 + A*(x-x0) + B*(x-x0)*(x-x1) + C*(x-x0)*(x-x1)*(x-x2)

where A, B, and C are precalculated divided differences.  If this is expressed as:

 y = y0+(x-x0)*(A+(x-x1)*(B+(x-x2)*C))

this is only nine operations: three subtractions, three multiplications, and three additions.  For the corresponding Lagrange interpolation there would be several more, no matter how it is arranged, and that is the price paid for not having precalculated the divided differences.

  If one counts the computation of divided differences, this of course alters the picture somewhat, but that all depends on the number of fixed points versus those to be interpolated within the fixed points.

  I think that was essentially Newton's reason for devising this form of interpolation formula - to minimize the number of arithmetic operations, which was a far more important consideration in the days before computers.  He could devise a table of fixed x and y values along with a set of corresponding divided differences just once.  After that the table could be used any number of times for doing interpolation with a minimum of steps for each new point.

Roger Stafford