Spline interpolation

Summary

Spline interpolation passes a spline through given data points, using the data nodes as knots. Unlike polynomial interpolation of high degree, it keeps the degree of each piece low, which avoids Runge's phenomenon and gives small errors for smooth data. The most common choice is the cubic spline, for which two extra conditions at the ends of the interval make the interpolant unique. The coefficients solve a tridiagonal linear system, so the cost grows only linearly with the number of points.