“Best” approximation function is based on the choice of norm.
Weierstrass approximation theory.
Existence and uniqueness of polynomial interpolation.
Natural basis interpretation: need to solve a linear system (matrix) which maybe ill-conditioned.
Lagrange interpolation: extra efforts to construct Lagrange polynomials but no matrix need to be solved (tradeoff).
Error of polynomial interpolant: = ep_n(f) (1+Lambda_n) (similar to output error in condition numbers, right?), where ep_n(f) is the error measurement of the best polynomial approximation (not necessarily the interpolant for sure!) and Lambda_n is Lebesgue constant (the max norm of Lebesgue function, which is the sum of absolute Lagrange polynomials). Note that Lambda_n is in the order of log(n), while ep_n(f) goes to 0 as n goes to infinity by Weierstrass, but the rate of convergence depends on the smoothness of the function f (more roughly speaking, we need to check the derivatives of f). So we can’t say anything about the convergence rate of polynomial interpolation error in general.
Error rate (error estimate) of polynomial interpolation (smaller than Taylor series approximation in general, since multiple points vs. single point), and we should control the derivatives (smoothness) to get the error bounds.
Convergence of polynomial approximation (w.r.t the degree n) is guaranteed.
The interpolation nodes can be smartly chosen to reduce the approximation error (comes from zeros of Chebyshev polynomials).
Shortcoming: adding a new interpolation point requires all the Lagrange polynomials to be recomputed.
Solution: Newton form using Newton’s divided differences, which are defined recursively, working as the coefficients of the linear combination of the Newton form basis.
Useful tool: divided difference table.
Geometric intuition: the divided differences are like the secant lines which parallel to a tangent line in 1D, and in general they are like the Taylor expansion coefficients but more precise since using multiple points instead of single one.
Question: what if we match not only the function values, but also the derivatives?
Answer: Hermite polynomials.
Overfitting: higher degree polynomials introduce more zeros, which means more oscillations. (“you couldn’t guarantee it wouldn’t look like this, run into this pathology.”)
Solutions: (1) don’t interpolate all the data points, i.e., approximation instead of interpolation, (2) interpolate all data points, but not with a single polynomial, i.e., piecewise interpolation (spline).
1st (linear) and 3rd (cubic) degree polynomials work (spline), 2nd degree (quadratic) the number of unknowns does not match the number of equations, unless we add a boundary one, which is ambiguous since we are usually not sure which side we would like to contain.
Basic rule: number of unknowns/coefficients should match the number of conditions/equations.
Cubic spline: 4n unknowns 4n-2 conditions, so we only need 2 more equations at 2 sides (boundaries).
2 standard conditions: natural conditions (zero 2nd order) or clamped conditions (given 1st order). They are corresponding to natural cubic splines and clamped cubic splines. Of course there are more than these 2.
In the absence of any information about function, we could simply use natural splines.
By carefully handling the coefficients and the consecutive width (knowns), there is a solvable linear system (although annoyingly large) containing (1) function values, (2) 1st order, (3) 2nd order, (4) boundary conditions.
Idea: substitute leading order coefficients d’s (unknown) and linear coefficients b’s (unknown) by quadratic coefficients c’s (unknown) and constant coefficients a’s (known, since they are exactly just function values at nodes). I.e., represent everything unknowns by c’s.
Method: make the linear coefficients left. Ax = b. A contains node width h’s, x contains quadratic coefficients c’s, b contains leading width h’s and leading order coefficients a’s. A is a diagonally dominant matrix, which indicates a unique solution since A is invertible.
The existence and uniqueness of the solution are guaranteed in both natural cubic spline and clamped cubic spline cases.
Natural cubic spline is the “smoothest” interpolation method.