Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
polynomial interpolation

Subject: polynomial interpolation

From: Pr B

Date: 7 Apr, 2009 03:40:02

Message: 1 of 2

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?

Subject: polynomial interpolation

From: Roger Stafford

Date: 7 Apr, 2009 07:14:04

Message: 2 of 2

"Pr B" <pb2297@columbia.edu> wrote in message <grehui$pi$1@fred.mathworks.com>...
> 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

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us