Week 2 - Interpolation#

Interpolation#

Construct a continuous function $f(x)$ through discrete data points $(x_j,y_j)$ .

$f(x_j)=y_j$

Interpolation	Curve fitting
Passes exactly through every point	Approximates the overall trend
$f(x_j)=y_j$	May not pass through the points

Interpolation vs Extrapolation#

Interpolation	Extrapolation
Evaluate inside the data range	Evaluate outside the data range
Usually safer	Requires knowledge of the underlying system

Types of interpolation#

Continuous	Piecewise
One function for the whole dataset	Different functions for parts of the domain

Linear Interpolation#

Fit a straight line between two points:

$y=mx+c$

$m=\frac{y_1-y_0}{x_1-x_0}$

Equivalent two-point form:

$P_1(x) = y_0+ \frac{y_1-y_0}{x_1-x_0}(x-x_0)$

Specific heat of air

Given:

$T\ (^\circ\mathrm C)$	$C_p\ (\mathrm{J/(kg\cdot K)})$
$0$	$1003$
$50$	$1006$

$m=\frac{1006-1003}{50-0}=0.06$

$C_p(T)=0.06T+1003$

At $T=25^\circ\mathrm C$ :

$C_p(25)=1004.5\ \mathrm{J/(kg\cdot K)}$

Piecewise Linear Interpolation#

Apply linear interpolation between each adjacent pair of points.

from scipy.interpolate import interp1d

Problems:

Poor approximation of smoothly varying functions
Derivatives are discontinuous at each data point

Higher-order Polynomial Interpolation#

For $n$ data points, use a polynomial of degree $n-1$ :

$P_{n-1}(x) = c_0+c_1x+c_2x^2+\cdots+c_{n-1}x^{n-1}$

$P_{n-1}(x) = \sum_{i=0}^{n-1}c_ix^i$

Each point produces one equation:

$P_{n-1}(x_j)=y_j$

Matrix form#

$\begin{bmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^{n-1}\\ 1 & x_1 & x_1^2 & \cdots & x_1^{n-1}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^{n-1} \end{bmatrix} \begin{bmatrix} c_0\\ c_1\\ \vdots\\ c_{n-1} \end{bmatrix} = \begin{bmatrix} y_0\\ y_1\\ \vdots\\ y_{n-1} \end{bmatrix}$

Solve for the coefficients $c_i$ .

Quadratic interpolation

Given:

$T\ (^\circ\mathrm C)$	$C_p\ (\mathrm{J/(kg\cdot K)})$
$0$	$1003$
$50$	$1006$
$100$	$1010$

Assume:

$C_p(T)=aT^2+bT+c$

Solving gives:

$a=0.0002,\qquad b=0.05,\qquad c=1003$

Therefore:

$C_p(T)=0.0002T^2+0.05T+1003$

Applications#

Tabulated experimental data
CAD and computer graphics
Numerical differentiation
Numerical integration
Signal processing and filtering

Basis Functions#

A function may be represented as a sum of basis functions:

$y(x)=\sum_{i=0}^{n-1}c_if_i(x)$

Lagrange polynomials are one family of basis functions.

Lagrange Basis Functions#

The $j$ th Lagrange basis function satisfies:

$\ell_j(x_i) = \begin{cases} 1, & i=j\\ 0, & i\neq j \end{cases}$

It has roots at every $x_i$ except $x_j$ .

$\ell_j(x) = \prod_{\substack{i=0\\i\neq j}}^{n-1} \frac{x-x_i}{x_j-x_i}$

The interpolating polynomial is:

$P_{n-1}(x) = \sum_{j=0}^{n-1}y_j\ell_j(x)$

Avoids directly solving for polynomial coefficients
Produces the same polynomial as the matrix approach

Interpolate

$C_p$ at

$75^\circ\mathrm C$

Given:

$T\ (^\circ\mathrm C)$	$C_p\ (\mathrm{J/(kg\cdot K)})$
$0$	$1003$
$50$	$1006$
$100$	$1010$
$150$	$1016$

At $T=75^\circ\mathrm C$ :

$\ell_0=-\frac{1}{16}, \qquad \ell_1=\frac{9}{16}, \qquad \ell_2=\frac{9}{16}, \qquad \ell_3=-\frac{1}{16}$

$C_p(75) = \sum_{j=0}^{3}C_{p,j}\ell_j(75)$

$C_p(75)=1007.8125\ \mathrm{J/(kg\cdot K)}$

High-order Polynomial Problems#

Using many points in one polynomial can cause:

Problem	Effect
Overfitting	Follows noise in the data
Round-off error	Small coefficient errors become large
Ill-conditioned matrix	Coefficients become difficult to solve accurately

Possible solutions:

Use better basis functions
Choose better interpolation points
Interpolate subsets of the data, such as with splines

Choice of Points#

The number and spacing of interpolation points affect accuracy.

For numerical or analytical functions, the point locations can be selected.

Runge Function#

$f(x)=\frac{1}{1+x^2}, \qquad -5\le x\le5$

Runge's Phenomenon#

Oscillation near the ends of a polynomial interpolant.

It becomes worse with:

Higher-degree polynomials
Equally spaced points

Chebyshev Nodes#

Chebyshev nodes are:

Roots of first-kind Chebyshev polynomials
Projections of equally spaced points on a circle
Chosen to reduce interpolation error

For $n$ nodes between $x_{\min}$ and $x_{\max}$ :

$x_j = \frac{x_{\min}+x_{\max}}{2} + \frac{x_{\min}-x_{\max}}{2} \cos\left( \frac{(2j+1)\pi}{2n} \right)$

$j=0,1,\ldots,n-1$

Four Chebyshev nodes on

$[-5,5]$

Given:

$n=4,\qquad x_{\min}=-5,\qquad x_{\max}=5$

The nodes are approximately:

$x_0=-4.6194$

$x_1=-1.9134$

$x_2=1.9134$

$x_3=4.6194$

Good Programming Practice

Three main principles:

Write readable code
Modularise using functions and modules
Start small and test as you go

Readable code#

Use descriptive names
Keep each line to one understandable operation
Avoid overly complicated nested expressions
Use comments to explain difficult reasoning

def lagrange_basis_function(x, index, points):
    ...

Modularise#

Put repeated code into functions
Put related functions into separate files
Import reusable functions where needed

from polyfit import fit_norder_polynomial

Key ideas#

Interpolation passes exactly through the data points
Linear interpolation is simple but has discontinuous derivatives
$n$ points determine a polynomial of degree at most $n-1$
Lagrange functions provide a direct interpolation formula
High-degree interpolation can suffer from Runge's phenomenon
Chebyshev nodes reduce endpoint oscillation and interpolation error

Contributors: Keys

Comments

Powered by GitHub issues