Newton’s Divided Difference and Lagrange’s Formulae
Definition
Newton’s Divided Difference and Lagrange’s Interpolation are fundamental numerical methods used to estimate unknown values of a function $f(x)$ when only a set of discrete data points $(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)$ is known. While Lagrange’s formula provides a direct polynomial construction, Newton’s Divided Difference method uses a recursive structure to build the interpolating polynomial step-by-step.
Main Content
1. Lagrange’s Interpolation Formula
- This method is used for both equally and unequally spaced data points.
- It expresses the interpolating polynomial as a linear combination of Lagrange basis polynomials, where the sum of the weights at any point is always 1.
- Formula: $P(x) = \sum_{i=0}^{n} L_i(x)y_i$, where $L_i(x) = \prod_{j=0, j \neq i}^{n} \frac{x - x_j}{x_i - x_j}$.
2. Newton’s Divided Difference Formula
- This method is particularly useful when data points are added to an existing set, as it does not require recalculating the entire polynomial.
- It relies on "divided differences," which measure the rate of change of the function over non-uniform intervals.
- The polynomial takes the form: $P(x) = f[x_0] + (x-x_0)f[x_0, x_1] + (x-x_0)(x-x_1)f[x_0, x_1, x_2] + \dots$
3. Comparison of Approaches
- Lagrange is "monolithic"—if you add a new data point, you must recalculate all basis polynomials from scratch.
- Newton’s method is "incremental"—if a new point $(x_{n+1}, y_{n+1})$ is added, you simply calculate one additional divided difference term and add it to the existing polynomial.
Working / Process
1. Constructing a Divided Difference Table
- List all $x_i$ and $y_i$ values in the first two columns.
- Calculate first-order differences: $f[x_0, x_1] = \frac{f(x_1) - f(x_0)}{x_1 - x_0}$.
- Continue for higher orders: $f[x_0, x_1, x_2] = \frac{f[x_1, x_2] - f[x_0, x_1]}{x_2 - x_0}$.
x | f(x) | 1st DD | 2nd DD
------------------------------------
x0 | y0 | |
| | f[x0,x1] |
x1 | y1 | | f[x0,x1,x2]
| | f[x1,x2] |
x2 | y2 | |
2. Setting up Lagrange Basis Polynomials
- For $n$ points, determine the numerator products by excluding the term $(x - x_i)$ for the current index $i$.
- Determine the denominator constants by plugging $x_i$ into the numerator product.
- Multiply each weight $y_i$ by its respective basis polynomial $L_i(x)$.
3. Final Polynomial Assembly
- For Newton: Sum the product of divided differences and the corresponding $(x-x_i)$ factors.
- For Lagrange: Sum all individual $L_i(x)y_i$ terms to get the final interpolating polynomial.
Advantages / Applications
- Data Approximation: Used in scientific experiments where data is collected at irregular intervals (e.g., weather sensor readings).
- Computer Graphics: Used for curve fitting and smoothing paths in animation and CAD software.
- Efficiency: Newton’s method is superior when the number of data points is expected to increase over time, saving computational power.
Summary
- Newton’s Divided Difference is an incremental interpolation method utilizing recursive differences.
- Lagrange’s formula is a direct algebraic method using basis polynomials to construct a unique interpolating curve.
- Both methods ensure the resulting polynomial passes exactly through all given data points.
- Important terms: Divided difference, Lagrange basis, Interpolation node, Interpolating polynomial, Unequally spaced data.