Newton's Divided Difference Interpolation

Definitions

Interpolation

Interpolation is the process of estimating the value of a function at a point that lies within the range of the given data points. That is, if we have data points $x_0, x_1, \ldots, x_n$, interpolation finds $f(x)$ for some $x$ such that $x_0 \leq x \leq x_n$.

Example: Given velocity at $t = 10, 15, 20, 25, 30$ seconds, finding velocity at $t = 16$ seconds is interpolation.

Extrapolation

Extrapolation is the process of estimating the value of a function at a point that lies outside the range of the given data points. That is, finding $f(x)$ for $x < x_0$ or $x > x_n$.

Example: Using the same velocity table, finding velocity at $t = 35$ seconds is extrapolation. Extrapolation is generally less reliable than interpolation.

Newton's Divided Difference Interpolation

Formula

The Newton's divided difference interpolating polynomial of degree $n$ is:

$$P_n(x) = a_0 + a_1(x - x_0) + a_2(x - x_0)(x - x_1) + \cdots + a_n(x - x_0)(x - x_1)\cdots(x - x_{n-1})$$

where the coefficients are:

$$a_0 = f[x_0], \quad a_1 = f[x_0, x_1], \quad a_2 = f[x_0, x_1, x_2], \ldots$$

The divided differences are defined as:

$$f[x_i] = f(x_i)$$

$$f[x_i, x_{i+1}] = \frac{f[x_{i+1}] - f[x_i]}{x_{i+1} - x_i}$$

$$f[x_i, x_{i+1}, x_{i+2}] = \frac{f[x_{i+1}, x_{i+2}] - f[x_i, x_{i+1}]}{x_{i+2} - x_i}$$

In general:

$$f[x_i, x_{i+1}, \ldots, x_{i+k}] = \frac{f[x_{i+1}, \ldots, x_{i+k}] - f[x_i, \ldots, x_{i+k-1}]}{x_{i+k} - x_i}$$

Algorithm for Newton's Divided Difference Interpolation

1. START

2. Read the number of data points n.

3. Read the data points x[0], x[1], ..., x[n-1]
   and corresponding function values f[0], f[1], ..., f[n-1].
   Store f[] in a divided difference table dd[].
   (i.e., dd[i] = f[i] for i = 0 to n-1)

4. Read the interpolating point xp (the value of x at which
   f(x) is to be estimated).

5. Build the divided difference table:
   For i = 1 to n-1:
       For j = n-1 downto i:
           dd[j] = (dd[j] - dd[j-1]) / (x[j] - x[j-i])
       End For
   End For
   (Now dd[0], dd[1], ..., dd[n-1] hold the leading
    divided differences a0, a1, ..., a(n-1))

6. Calculate the interpolated value:
   Set result = dd[n-1]
   For i = n-2 downto 0:
       result = result * (xp - x[i]) + dd[i]
   End For
   (This uses Horner's nested multiplication form)

7. Print result as the interpolated value at xp.

8. STOP

C Program for Newton's Divided Difference Interpolation

#include <stdio.h>

#define MAX 20

int main()
{
    int n, i, j;
    float x[MAX], dd[MAX], xp, result, product;

    /* Step 1: Read number of data points */
    printf("Enter the number of data points: ");
    scanf("%d", &n);

    /* Step 2: Read data points and function values */
    printf("Enter x[i] and f(x[i]) values:\n");
    for(i = 0; i < n; i++)
    {
        printf("x[%d] = ", i);
        scanf("%f", &x[i]);
        printf("f(x[%d]) = ", i);
        scanf("%f", &dd[i]);
    }

    /* Step 3: Read the interpolating point */
    printf("Enter the value of x to interpolate: ");
    scanf("%f", &xp);

    /* Step 4: Build the divided difference table */
    for(i = 1; i < n; i++)
    {
        for(j = n-1; j >= i; j--)
        {
            dd[j] = (dd[j] - dd[j-1]) / (x[j] - x[j-i]);
        }
    }

    /*
     * Now dd[0] = f[x0]         (0th divided difference)
     *     dd[1] = f[x0,x1]      (1st divided difference)
     *     dd[2] = f[x0,x1,x2]   (2nd divided difference)
     *     ...and so on
     */

    /* Step 5: Calculate interpolated value using
               Newton's divided difference formula */
    result = dd[0];
    product = 1.0;

    for(i = 1; i < n; i++)
    {
        product = product * (xp - x[i-1]);
        result  = result + dd[i] * product;
    }

    /* Step 6: Display the result */
    printf("\nInterpolated value at x = %.4f is f(x) = %.4f\n", xp, result);

    return 0;
}

Summary

Newton's divided difference method builds a triangular table of successive divided differences from the raw function values, then evaluates the interpolating polynomial at the required point using nested (Horner-style) multiplication, which keeps the computation efficient and numerically stable. Unlike the direct Lagrange form, a new data point can be added by simply extending the divided-difference table, without recomputing the whole polynomial from scratch.

Poisson's Equation: ∇²f = xy with f = 2 on Boundary

STEP 1 - Given Data

• PDE: $\nabla^2 f = xy$
• Boundary condition: $f = 2$ on all boundaries
• Domain: $0 \le x \le 3$, $0 \le y \le 3$
• Step size: $h = 1$

Grid points at $x = 0,1,2,3$ and $y = 0,1,2,3$. Interior nodes at $(1,1),(2,1),(1,2),(2,2)$.

STEP 2 - Solution

Finite difference form

$$f_{i-1,j} + f_{i+1,j} + f_{i,j-1} + f_{i,j+1} - 4f_{i,j} = h^2 (xy)$$

With $h = 1$, RHS $= xy$ at each node.

Grid layout

y=3:  2    2    2    2
y=2:  2   f3   f4   2
y=1:  2   f1   f2   2
y=0:  2    2    2    2
     x=0  x=1  x=2  x=3

• $f_1 = (1,1)$, $f_2 = (2,1)$, $f_3 = (1,2)$, $f_4 = (2,2)$

Equations

f1 at (1,1), xy = 1: $$2 + f_2 + 2 + f_3 - 4f_1 = 1 \Rightarrow -4f_1 + f_2 + f_3 = -3 \quad (1)$$

f2 at (2,1), xy = 2: $$f_1 + 2 + 2 + f_4 - 4f_2 = 2 \Rightarrow f_1 - 4f_2 + f_4 = -2 \quad (2)$$

f3 at (1,2), xy = 2: $$2 + f_4 + f_1 + 2 - 4f_3 = 2 \Rightarrow f_1 - 4f_3 + f_4 = -2 \quad (3)$$

f4 at (2,2), xy = 4: $$f_3 + 2 + f_2 + 2 - 4f_4 = 4 \Rightarrow f_2 + f_3 - 4f_4 = 0 \quad (4)$$

Solving

Equations (2) and (3) are identical, so $f_2 = f_3 = p$.

From (1): $-4f_1 + 2p = -3 \Rightarrow f_1 = \dfrac{2p+3}{4}$

From (4): $2p - 4f_4 = 0 \Rightarrow f_4 = \dfrac{p}{2}$

Substitute into (2): $f_1 - 4p + f_4 = -2$

$$\frac{2p+3}{4} - 4p + \frac{p}{2} = -2$$

Multiply by 4:

$$(2p+3) - 16p + 2p = -8$$ $$-12p + 3 = -8$$ $$-12p = -11 \Rightarrow p = \frac{11}{12} \approx 0.9167$$

Back-substitution

$$f_2 = f_3 = \frac{11}{12} \approx 0.9167$$

$$f_1 = \frac{2(11/12) + 3}{4} = \frac{11/6 + 18/6}{4} = \frac{29/6}{4} = \frac{29}{24} \approx 1.2083$$

$$f_4 = \frac{p}{2} = \frac{11}{24} \approx 0.4583$$

Verification (Eq. 4)

$$f_2 + f_3 - 4f_4 = \frac{11}{12} + \frac{11}{12} - 4\cdot\frac{11}{24} = \frac{22}{12} - \frac{44}{24} = \frac{11}{6} - \frac{11}{6} = 0 \checkmark$$

Final Answers

$$\boxed{f_1 = \frac{29}{24} \approx 1.2083,\quad f_2 = f_3 = \frac{11}{12} \approx 0.9167,\quad f_4 = \frac{11}{24} \approx 0.4583}$$

The complete value is $f_4 = 11/24 \approx 0.4583$.