Interpolation using dynamic programming

Question

I'm having trouble on doing a homework exercise.

I need to describe an efficient algorithm which solves the polynomial interpolation problem:

1. Let P[i,j] be the polynomial interpolation of the points (xi, yi),...,(xj,yj). Find 3 simple polynomials q(x), r(x), s(x) of degree 0 or 1 such that:

   P[i,j+1]={q(x)P[i,j](x)-r(x)P[i+1,j+1](x)}/s(x)

2. Given the points (x1,y1),....(xn,yn), describe an efficient dynamic programming algorithm based on the recurrence relation which you found in section 1 for computing the coefficients a0,...an-1 of the polynomial interpolation.

Well, I know how to solve the polynomial interpolation problem using Newton polynomial which looks quite similar to the above recurrence relation but I don't see how it helps me to find q(x), r(x), s(x) of degree 0 or 1, and assuming I have the correct q(x), r(x), s(x)- how do I solve this problem using dynamic programming?

Any help will be much appreciated.

Answer 1

q(x) = (x at {j+1}) - x
r(x) = (x at i) - x
s(x) = (x at {j+1}) - (x at i)

x at i or x at j mean their place in the ordered list of input points.

Some explanations:

First we need to understand what P[i,j](x) means.

Put all your initial (x,y) pairs in the main diagonal of an n x n matrix. Now you can extract P[0,0](x) to be the y value of the point in your matrix at (0,0). P[0,1] is the linear interpolation of the points in your matrix at (0,0) and (1,1). This will be a straight line function.

((x at 0 - x)(y at 1) - (x at 1 - x)(y at 0)) 
---------------------------------------------
              (x at 1 - x at 0)

P[0,2] is the linear interpolation of two previous linear interpolations, which means that your ys now will be the linear functions which you calculated at the previous step. This is also the dynamic algorithm which builds the full polynom.

I highly recommend you have a look at this very good lecture, and the full lecture notes.