comp 391-079 Numerical Analysis

Different interpolation techniques [top]

Linear regression is used to fit a line to data such as from a science experiment. Line fitting can be applied to nonlinear data sets. In addition, line fitting can be generalized for multiple dimensions; for example, a plane can be fitted to three dimensional data. The concept behind regression fitting is to reduce the deviation from the fit (line, plane, etc) to each of the data samples.

The Fourier transform is a method of construction functions of the superposition of sinusoidal functions with different amplitudes and periods.

Interpolating polynomials [top]

The following methods uses know points to construct a polynomial. The degree of the polynomial is equal to n+1, where n is the number of points used to construct the curve. The points do not need to be equally spaced.

This method is called Newton’s polynomial interpolation. It used the divided difference to estimate the derivate between two points.

The polynomial is defined for points x0…xn. The variable x is the variable parameter of the function.

Error term of interpolation [top]

The error between the real curve and the interpolation is given below. The derivation starts from the Taylor series. Equation 1 below is the accurate error, however, as x is not known, the error is approximated in (2) with another known point.

Programming observations [top]

Adding one more point can derive a higher order polynomial. Only the few terms with the new point would need to be recalculates.

Due to the recursive definition, the divide difference is continually reused and therefore storing the intermediate values and looking them up will speedup the computation.

The error can be calculated with the rest of the approximation, as many of the divided difference terms are similar.

LaGrange [top]

The LaGrange is a reformulation of the Newton polynomial interpolation method. It avoids calculating the divided differences.

Spline Interpolation [top]

Another method to interpolate lines is by interpolating individual sections of the curve, for instance, using a cubic polynomial. The higher the degree of polynomial, the higher the degree of continuity from connected points, to matching first, second, and nth derivative. However, higher degree polynomials have the potential to overshoot the approximated curve. The overshoot also applies to high degree polynomials from the Newton polynomial interpolation. Higher degree polynomials become less stable and can vastly overshoot the estimate the estimated curve.
Constraints needed to solve for splines
Solving the coefficients of splines requires having enough constraints. Given n+1 point and degree d (polynomial with highest power d-1) needs dn constraints as follows (some things quoted directly from the source:

The functions pass through the given points (2n conditions)

The first derivates at the interior knots must be equal (n-1 conditions)

The second derivative at the interior must be equal (n-1 conditions)

The second derivative at the end knots is arbitrarily chosen (2 conditions)

Continue to take the derivative to derive more conditions.

Special case cubic spine
The cubic spline can be derived in a particular point. Although the equation is quite long, it reduces the number of unknowns. The equation, however can be used in the Newton-Cotes integration techniques.