18
$\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$
1
  • $\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$
    – KFkf
    Commented Mar 30, 2015 at 18:20

3 Answers 3

6
$\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$
1
  • $\begingroup$ please suggest me some online resources to study forward and backward interpolation, and if possible then resources for numerical analysis, it would help me a lot. $\endgroup$
    – mnulb
    Commented Sep 24, 2019 at 15:52
-3
$\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$
6
  • $\begingroup$ Can you elaborate? How is the error decreased if we use the "correct" formula? $\endgroup$
    – Rei
    Commented Jan 2, 2014 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$
    – Supriyo
    Commented Jan 2, 2014 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
    Commented Jan 2, 2014 at 15:06
  • $\begingroup$ Where is your problem ? $\endgroup$
    – Supriyo
    Commented Jan 2, 2014 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
    Commented Jan 2, 2014 at 15:35
-4
$\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$
1
  • 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
    Commented Mar 18, 2014 at 10:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .