I am learning interpolation via Newton's polynomial. Generally, I understand the incremental method described here (page 12) in detail. However, from what I see, it is not fully 'incremental' since I still need to loop thru all x-coordinates of points I am trying to interpolate.
To me, it appears that 'incremental' method would mean that given a polynomial P that interpolates points (x1,y1)…(xn,yn) and a set of new points (xx1,yy1)…(xxn,yyn), I should be able to construct new polynomial PP that interpolates all of the points above without the need to go thru the points already interpolated by P.
The method described in the link accomplishes everything except that I need to go thru x1…xn as well as xx1…xxn. So, can anybody confirm that there is no better way than this?
Best Answer
Consider this case. You originally have 5 points and you used Newton's divided difference to obtain the polynomial coefficients, essentially $f[x_0, x_j]\text{ , for j=}0\ldots 4 $, and your current polynomial construction is $f(x) = \sum_{j=0}^4 f[x_0,x_j]\phi_j(x) = \sum_{j=0}^4 f[x_0,x_j]\Pi_{i=0}^{j-1}(x-x_i)$.
Now, if you have one more point, the only thing you need to do is to calculate $f[x_0, x_5]$ such that you can get your new polynomial, $f(x) = \sum_{j=0}^5 f[x_0,x_j]\phi_j(x)$. And this is the reason why Newton's Polynomial is called incremental. You have to recalculate the polynomial coefficients for the other methods, e.g. monomial or Lagrange interpolation.
But you are right, you do need to go over all the data points when you are evaluating Newton's polynomial, but it is still pretty cheap computationally. It is the construction process that is "incremental".
Hope this helps. Cheers!