Interpolation

Keywords

interpolation, Newtons polynomials, Lagranges polynomials, linear interpolation, quadratic interpolation

The general formula for an th-order polynomial is

Moreover, for data points, there is only one polynomial of order that passes through all the points—which we can determine using polynomial interpolation. Obtaining that polynomial will allow us to compute for intermediate values between data points.

There are two popular mathematical formats to express this polynomial: the Newton and the Lagrange polynomials.

Newton’s Divided-Difference Interpolating Polynomials

Linear Interpolation

Linear interpolation, the simplest form of interpolation, involves connecting two data points using a straight line.

Characteristics

• First order interpolating polynomial.
• The accuracy of its approximation increases as the interval between the data points decreases.

Formula

The term represents the slope of the line connecting the points and is also the finite-divided-difference approximation of the first derivative.

Quadratic Interpolation

We can obtain a second-order interpolating polynomial (or a quadratic polynomial) when we have three data points given. A convenient for this purpose is

where

The term represents the slope of the line connecting the points and , and, as such, is equivalent to the linear interpolation from to . On the other hand, the introduces the second-order curvature.

General Form

The general form for an th-order polynomial (or Newton’s divided-difference interpolating polynomial) is

For an th-order polynomial, data points are required in order to evaluate the following coefficients:

To find the th finite divided difference

Graphical Depiction of the Nature of Finite Divided Difference

			First	Second	Third

Errors

The th-order interpolating polynomial will have a truncation error expressed as

where is the th finite divided difference. Nevertheless, because it has , it cannot be solved for the error—unless the additional data point is available. If the additional data point is available, we can estimate the error using the following formula:

The issue with higher-order interpolating polynomials, however, is that they are highly sensitive to data errors. When interpolation is applied, they often yield inaccurate predictions. For this reason, they are better suited for exploratory data analysis.

Lagrange Interpolating Polynomials

The Lagrange interpolating polynomial is a reformulation of the Newton’s polynomial that avoids divided differences, thus

where

where refers to the product.

will be at and at any other points; as a result, takes on the value of at .

The error estimate can be computed with

Newton or Lagrange?

For exploratory computations, Newton’s method is preferred because it gives insight to the different-order formulas’ behavior; it is suited for cases where the polynomial’s order is unknown. Furthermore, because Newton’s method employs a finite difference, we can easily integrate the error estimate to it.

Lagrange is preferred over Newton in cases where only one interpolation is to be performed because it is easier to program—it does not depend on divided differences, but the polynomial’s order must be known beforehand.

Sources

1. Numerical Methods for Engineers by Steven Chapra and Raymond Canale (Chapter 18)