Polynomial Interpolation

Polynomial interpolation is a fundamental numerical method for constructing a single polynomial that passes exactly through a set of distinct data points.

Given $ N $ points with coordinates $ (x_i, y_i) $, the goal is to find a polynomial $ P(x) $ of degree at most $ N-1 $ such that $ P(x_i) = y_i $ for all points.

This polynomial can then be used to estimate values outside the data set (extrapolation).

Several algebraic methods lead to the same unique polynomial, but differ in their formulation and computational efficiency.

— Lagrange: Constructs the polynomial directly as a linear combination of Lagrange basis polynomials. Each basis polynomial is equal to 1 at a point xᵢ and 0 at all others. The method is conceptually simple and straightforward.

— Newton (divided differences): Constructs the polynomial iteratively using a divided difference table. This method is more numerically efficient, especially for adding new data points, because it does not require recalculating the entire polynomial.

— Neville: Evaluates the interpolating polynomial at a specific point without explicitly calculating its coefficients. It is a recursive algorithm that cleverly combines lower-degree interpolations. It is particularly useful when only the interpolated values, and not the complete equation, are needed.

The Runge phenomenon is a counterintuitive phenomenon where increasing the number of points (and therefore the degree of the polynomial) in an interpolation with equidistant points can lead to unwanted oscillations.

The accuracy of the interpolation then degrades significantly. To mitigate this effect, use non-equidistant points, which minimize the oscillation of the error polynomial.

Interpolation: Estimates a value within the data's range (between the minimum and maximum $ x_i $). Confidence in the result is generally high.

Extrapolation: Estimates a value outside the data's range. This is a risky operation because the polynomial's behavior outside the known range is unpredictable and often erroneous, especially with high-degree polynomials.

If two or more points have the same x-coordinate but different y-coordinates, it is impossible to find a function (and therefore a polynomial) that passes through all these points simultaneously. Check the data to remove duplicate x-coordinates.

A polynomial of degree $ N-1 $ has exactly $ N $ free coefficients.

Each condition $ P(x_i) = y_i $ yields a linear equation. With $ N $ points, it is possible to obtain a system of $ N $ equations with $ N $ unknowns (the coefficients), which has a unique solution.

A lower degree would be underconstrained, and a higher degree would be overconstrained.