12
$\begingroup$

I was taught that the forward formula should be used when calculating the value of a point near $x_0$ and the backward one when calculating near $x_n$. However, the interpolation polynomial is unique, so the value should be the same. So is there any difference between the two, or my lecturer is wrong?

Here are the formulas:

  1. Gregory-Newton or Newton Forward Difference Interpolation $$P(x_{0}+hs)=f_{0}+s\Delta f_{0}+\frac{s(s-1)}{2!}\Delta^{2}f_{0}+\cdots+\frac{s(s-1)(s-2)...(s-n+1)}{n!}\Delta^{n}f_{0}$$ where $$s=\frac{(x-x_{0})}{h}; \qquad f_0=f(x_0); \qquad \Delta^k f_i=\sum_{j=0}^k{(-1)^j \frac{k!}{j!(k-j)!}f_{i+k-j}}$$
  2. Gregory-Newton or Newton Backward Difference Interpolation $$P(x_{n}+hs)=f_{n}+s\nabla f_{n}+\frac{s(s+1)}{2!}\nabla^{2}f_{n}+\cdots+\frac{s(s+1)(s+2)...(s+n-1)}{n!}\nabla^{n}f_{n}$$ where $$s=\frac{(x-x_{n})}{h}; \qquad f_n=f(x_n); \qquad \nabla^k f_i=\sum_{j=0}^k{(-1)^j \frac{k!}{j!(k-j)!}f_{i-j}}$$

Example: For interpolating at the points $x_0=-3,-2.9,-2.8,...,2.9,3=x_n$ with $f(x)=e^x$ using MATLAB we have

>> x = -3:0.1:3; y = exp(x);
>> frwrdiffdata = frwrdiff(x, y, 0.1, -3:0.5:3);
>> bckwrdiffdata = bkwrdiff(x, y, 0.1, -3:0.5:3);
>> mostAccurateData = exp(-3:0.5:3)';
>> [abs(frwrdiffdata-mostAccurateData)./mostAccurateData ... 
abs(bckwrdiffdata-mostAccurateData)./mostAccurateData]

ans =

   1.0e-03 *

                   0   0.672871398134864
   0.000000000000169   0.001123487151044
   0.000000000000205   0.000000247108705
                   0   0.000000006452206
   0.000000000000302   0.000000000010412
   0.000000000000366   0.000000000005491
   0.000000000000222   0.000000000001776
   0.000000000000135                   0
   0.000000000000327   0.000000000000327
   0.000000000093342                   0
   0.000000006938894                   0
   0.000003364235903                   0
   0.000053772150047                   0

where the first column is the relative error of Newton Forward Difference and the second column is the relative error of Newton Backward Difference for sample points $x=-3,-2.5,-2,...,2.5,3$. As you see in the table above and in the following figure the relative error in the first column increases as $x\to x_n$ and the relative error of the second column decreases as $x\to x_n$.

newton forward and backward difference comparison

The MATLAB functions frwrdiff and bkwrdiffused above are

function polyvals = frwrdiff(x, y, h, p) % Newton Forward Difference function
n = length(x);
ps = length(p);
polyvals = zeros(ps, 1);
dd = zeros(n,n);
dd(:, 1) = y(:);
for i = 2: n % divided diference table
    for j = 2: i
        dd(i,j) = (dd(i, j-1) - dd(i-1, j-1));
    end
end
a = diag(dd); %y_0, delta_0, ..., delta_n
for k = 1: ps
    s = (p(k) - x(1))/h; %(x - x_0) / h
    t = s;
    polyvals(k) = a(1) + s*a(2); %y_0 + s * delta_0
    for i = 1: n-2
       t = t * (s - i);
       polyvals(k) = polyvals(k) + t*a(i+2)/factorial(i+1);
    end
end

and

function polyvals = bkwrdiff(x, y, h, p) % Newton Backward Difference function
n = length(x);
ps = length(p);
polyvals = zeros(ps, 1);
dd = zeros(n,n);
dd(:, 1) = y(:);
for i = 2: n % divided diference table
    for j = 2: i
        dd(i,j) = (dd(i, j-1) - dd(i-1, j-1));
    end
end
a = dd(n,:); %y_n, nabla_0, ..., nabla_n
for k = 1: ps
    s = (p(k) - x(n))/h; %(x - x_n) / h
    t = s;
    polyvals(k) = a(1) + s*a(2); %y_0 + s * nabla_0
    for i = 1: n-2
       t = t * (s + i);
       polyvals(k) = polyvals(k) + t*a(i+2)/factorial(i+1);
    end
end

Note: The results seem different when at first we obtain the polynomials and then substitute the points $x=-3,-2.5,-2,...,2.5,3$ to the polynomials:

ans =

   1.0e+02 *

   0.000000132146955   1.528566476043447
   0.000000000047960   0.000683674054800
   0.000000000000000   0.000000095605754
   0.000000000000000   0.000000000002139
   0.000000000000000   0.000000000000000
   0.000000000000000   0.000000000000000
   0.000000000000000                   0
   0.000000000000000                   0
   0.000000000000000   0.000000000000000
   0.000000000000331   0.000000000000000
   0.000000004277456   0.000000000000000
   0.000006632407337   0.000000000000896
   0.001154767626752   0.000000000785245

The above results obtained by modifying the two matlab functions already mentioned in this question.

$\endgroup$
  • $\begingroup$ it must be because of the finite arithmetic involved in the calculation of the polynomial and value of it in a specific point ! $\endgroup$ – kiyarash Mar 30 '15 at 18:20
3
$\begingroup$

theoretically assuming that the calculations are done in a infinite arithmetic then the polynomials are the same so they give the same answer .

But since the computer and applied arithmetic are finite then when calculating the polynomials they do no turn out to be equal (at least not in all the cases). and note that the more arithmetic operations you do the more you loose accuracy!

so if the input x is closer to $ x_i $ (one of the data we already have); then choosing $x_i$ as $x_0$ gives a better accuracy if we are using the forward differences formula in our finite arithmetic system .(or in the case of back ward differences choosing $x_i$ as $x_n$) (or even in the case of Centered Differences choosing $x_i$ as the middle data)

since

e.g. in the case of $x_i$ as $x_0$ using the forward differences formula ; the $f(x_0)$ is a single term (with no additional arithmetic to loose accuracy like other terms) and since we are assuming that if x is close to $x_i$ then $f(x)$ is also close to $f(x_i)$. so we get the least possible error in calculating $f(x)$.(which is also the case for Centered Differences and back ward differences).

Additional notes:

if we use the newton's divided differences formula then indexing the data really does not matter . so to raise the accuracy we simply re-index the data the way its more accurate and find the polynomial.

BUT if we are using the assumption that $x_{i+1} - x_{i} = h$(where h is the step size).

then we cannot re-index the data as we wish an the data should be either increasing or decreasing .so to get more accuracy and to be able to choose the single term ($f(x_{0})$ or $f(x_{n})$ or ...) to be the closest data; we need to change the polynomial formula to meet our needs.

$\endgroup$
-2
$\begingroup$

Interpolation polynomial for a set of values $\{x_k, f(x_k)\}_{k = 1}^n$ is unique. You may get the proof in any standard text using Vandermond determinant.

When we want to find out the value of the function $f(x)$ at some given point $x$ by interpolation, an error term used to come. $f(x) = L_n(x) + R_n(x)$, where $L_n(x)$ is the value of the interpolation polynomial at $x$ and $R_n(x)$ is the value of the error term at $x$. Our fundamental goal is to decrease the error as much as possible.

So we use forward and backward interpolation in different places as required.

$\endgroup$
  • $\begingroup$ Can you elaborate? How is the error decreased if we use the "correct" formula? $\endgroup$ – Rei Jan 2 '14 at 14:32
  • $\begingroup$ You can do it yourself. Take a problem for forward interpolation from your text book and solve it by backward interpolation. Take another problem for backward interpolation and solve it by forward interpolation. Try to correct your calculation for 10 to 12 significant digits as you used to do for your practical work of numerical analysis. You shall see it at once. I can not post very big numerical calculations. $\endgroup$ – Dutta Jan 2 '14 at 14:54
  • $\begingroup$ Still, I don't understand why it is the case. Beside, it seems that both formulas have the same formula of error. $\endgroup$ – Rei Jan 2 '14 at 15:06
  • $\begingroup$ Where is your problem ? $\endgroup$ – Dutta Jan 2 '14 at 15:08
  • 2
    $\begingroup$ The problem is I can't find a general proof for this. If we don't know the exact value of f(x), then we can only evaluate the maximal error. And it is the same regardless the formula used. $\endgroup$ – Rei Jan 2 '14 at 15:35
-3
$\begingroup$

Suppose $x_0,x_1,x_2,\dots,x_n$ are the given nodal points. Then Newton forward difference method is better for points which are closer to $x_0$, while Newton backward difference method is better for points which are closer to $x_n$.

But both of these methods are used to find the value of a function at a given point.

$\endgroup$
  • 2
    $\begingroup$ Why "Newton forward difference method is better for points which are closer to $x_0$, while Newton backward difference method is better for points which are closer to $x_n$"? $\endgroup$ – Dante Mar 18 '14 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.