All previously discussed methods of polynomial interpolation fit
a set of given points
nth degree polynomial, and a higher degree polynomial is needed to
fit a larger set of data points. A major drawback of such methods
is overfitting, as domonstrated by the following example.
Vased on equally spaced points from to
with increment of 1, a function
can be approximated
by any of the interpolation methods discussed above by polynomial
of degree , as shown in the figure below. We note that the
approximation is very poor towards to the two ends where the error
is disappointingly high. This is known as
Runge's phenomenon, indicating the fact that higher degree
polynomial interpolation does not necessarily always produce more
accurate result, as the degree of the interpolating polynomial may
become unnecessarily high and the polynomial may become oscillatory.
This Runge's phenominon is a typical example of overfitting, due to
an excessively complex model with too many parameters relative to the
observed data, here specifically a polynomial of a degree too high
(requiring too many coefficients) to model the given data points.
Now we consider a different method of spline interpolation, which
fits the given points by a piecewise polynomial function ,
known as the spline, a composite function formed by
low-degree polynomials each fitting in the interval
As this method does not use a single polynomial of degree to
fit all points at once, it avoids high degree polynomials
and thereby the potential problem of overfitting.
These low-degree polynomials need to be such that the spline
they form is not only continuous but also smooth.
In the following we consider approximating between any
two consecutive points and by a linear, quadratic,
and cubic polynomial (of first, second, and third degree).
is sampled at the
The interpolation results based on linear, quadratic and cubic
splines are shown in the figure below, together with the original
function , and the interpolating polynomials
, used as the ith segment of
between and .
For the quadratic interpolation, based on
. For the cubic
interpolation, we solve the following equation
The errors of these three methods are
, respectively. Obviously
the higher the degree of the interpolating polynomial, the
higher the accuracy. The error of the cubic spline method is
significantly smaller than
of the polynomial
The Matlab code that implements the cubic spline method is listed below.
function [S C]=Spline3(u,x,y,dya,dyb)
% vectors x and y contain n+1 points and the corresponding function values
% vector u contains all discrete samples of the continuous argument of f(x)
% dya and dyb are the derivatives f'(x_0) and f'(x_n), respectively
n=length(x); % number of interpolating points
k=length(u); % number of discrete sample points
C=zeros(n,k); % the n-1 cubic interpolating polynomials
A=2*eye(n); % coefficient matrix on left-hand side
d=zeros(n,1); % vector on right-hand side
d(1)=((y(2)-y(1))/(x(2)-x(1))-dya)/h0; % first element of d
d(i)=((y(i+1)-y(i))/h1-(y(i)-y(i-1))/h0)/h2; % 2nd divided difference
d(n)=(dyb-(y(n)-y(n-1))/h1)/h1; % last element of d
M=6*inv(A)*d; % solving linear equation system for M's
C(i-1,:)=(x1.^3*M(i-1)+x0.^3*M(i))/6/h... % the ith cubic polynomial
idx=find(u>x(i-1) & u<=x(i)); % indices between x(i-1) and x(i)
S(idx)=C(i-1,idx); % constructing spline by cubic polynomials
used before is now approximated by both
the Newton's method and the cubic spline method, with very different
results as shown below. The Runge's phenomenon suffered by Newton's
method is certainly avoided by the cubic spline method.