Generally, if we have n data points, there is exactly one polynomial of degree at most n −1 going through all the data points. The interpolation error is proportional to the distance between the data points to the power n. Furthermore, the interpolant is a polynomial and thus infinitely differentiable.
Linear interpolation on a data set (red points) consists of pieces of linear interpolants (blue lines). Linear interpolation on a set of data points (x0, y0), (x1, y1), ..., (xn, yn) is defined as the concatenation of linear interpolants between each pair of data points.
Like polynomial interpolation, spline interpolation incurs a smaller error than linear interpolation, while the interpolant is smoother and easier to evaluate than the high-degree polynomials used in polynomial interpolation. However, the global nature of the basis functions leads to ill-conditioning.
The strategy is to de ne an auxiliary function q that has zeros at the n + 1 interpolation points and x, then use the mean value theorem repeatedly to conclude that q(n+1) has one zero - this will be the x. contained in [a; b]: Let pn(x) be the interpolating polynomial.