[Numerical Analysis] 10. Interpolation
Interpolation
Interpolation
- A process of finding a function that passes through a given set of points $(x_i, y_i)$ (data fitting or curve fitting)
- it can be used to estimate variable $y$ corresponding to unknown $x \in [a,b]-{x_i}$
Extrapolation
- Estimate variable $y$ corresponding to $x < x_0$ or $x>x_n$
Interpolation EX
$x_0 = 0, x_1 = \frac{\pi }{4}, x_2 = \frac{\pi }{2}$
$y_i = \cos x_i$ , $i=0,1,2$
-> 3points
-Find quadratic funcion : $p(x) = a_0 + a_1 x + a_2 x^2$, $p(x_i) = y_i$
- estimate $a_0, a_1, a_2$ in range $x \in [0, \frac{\pi }{2}]$
- outside of range : extrapolation -> low accuracy
Purpose of interpolation
1. Replace a set of data points with a function given analytically.
2. Approximate functions with simpler ones, usually polynomials or 'piecewise polynomial'.
Linear Interpolation
Interpolation with straight line
- Let two data points be given. There is a unique straight line passing through these points. We can write the formula for a straight line as $P_1(x) = a_0 + a_1 x$
Quadratic Interpolation
Lagrange interpolation - $P_2(x) = y_0 L_0(x) + y_1 L_1(x) + y_2 L_2(x)$ -> weighted sum (coefficient -> $L$)
- $L_0(x) = \frac{(x-x_1)(x -x_2) }{(x_0-x_1)(x_0-x_2)}$
- $L_1(x) = \frac{(x - x_0)(x-x_2)}{(x_1 - x_0)(x_1-x_2)}$
- $L_2(x) = \frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}$
- Lagrange basis functions
- $L_i(x_j) = \begin{cases} 1 & \text{ if } i=j \\ 0 & \text{ if } i\neq j \end{cases}$ -> all have degree 2
Uniquness
- can there be another polynomial, call it $Q(x)$, for which $deg(Q) \leq 2$, $Q(x_i) = y_i $
- Let $R(x) = P_2(x) - Q(x)$ : from the properties of $P_2$ and $Q$, we have $deg(R) \leq 2$
- $R(x_i) = P_2(x_i) - Q(x_i) = y_i- y_i = 0$
- Three zeros for quadratic function => $R(x) = 0$ for all $x$,$Q(x) = P_2(x)$ for all $x$
Higher Degree Interpolation
Polynomial function of degree $n$
- $deg(P_n) \leq n$ -> $P_n(x_i) = y_i$, $i = 0,1,\cdots n$
Lagrange interpolation
- $P_n(x) = y_0 L_0(x) + y_1 L_1(x) + \cdots + y_n L_n(x)$
Lagrange Basis function
- $L_k(x) = \frac{ (x-x_0)\cdots (x-x_{k-1})(x-x_{k+1})\cdots (x- x_n) }{ (x_k - x_0)\cdots (x_k - x_{k-1})(x_k - x_{k+1}) \cdots (x_k - x_n) }$
Newton Polynomials
It is cometimes useful to fine $P_1(x), P_2(x), \cdots, P_N (x)$
Lagrange polynomial : No constructive relationship between $P_{N-1}(x)$ and $P_N(x)$
Newton polynomials
- Reursive patterns
- $P_N(x) = P_{N-1}(x) + g_N(x)$
$P_N(x)= P_{N-1}(x) + g_N(x)$, for $ x \in [x_0,x_{N_1}]$
$P_N(x) = a_0 + a_1 (x-x_0) + a_2(x - x_0)(x-x_1) + \cdots + a_N (x- x_0) \cdots (x- x_{N-1}$
$P_N(x) = P_{N-1}(x) + a_N(x-x_0) \cdots (x-x_{N-1})$
$g_N(x) = a_N(x-x_0) \cdots (x - x_{N-1})$
- To find $a_k$ for all polynomials $P_1(x), P_2(x), \cdots, P_N(x)$ that approximate a given function $f(x)$.
- $P_k(x)$ is based on the centers $x_0, x_1, \cdots, x_k$
- For $P_1(x)$ : $P_1(x) = f(x_0) = y_0$ and $P_1(x_1) = f(x_1) = y_1$ ( given )
$f(x_0) = P_1(x_0) = a_0 + a_1(x_0 - x_0) = a_0$ Hence $a_0 = f(x_0) = y_0$
$f(x_1) = P_1(x_1) = a_0 + a_1 (x_1 - x_0) = f(x_0) + a_1(x_1 - x_0) = y_1$.
$a_1 = \frac{f(x_1) - f(x_0)}{x_1 - x_0}$
- $a_1$: slope of the line between $(x_0, f(x_0))$ and $(x_1, f(x_1))$ => First-Order divided differences)
- For $P_2(x)$ : $a_0$ and $a_1$ are the same for both $P_1(x)$ and $P_2(x)$
$f(x_2) = P_2(x_2) = a_0 + a_1 (x_2 - x_0) + a_2(x_2 - x_0)(x_2 - x_1)$.
$a_2 = \frac{ \frac{f(x_2) - f(x_1)}{x_2 - x_1} - \frac{f(x_1) - f(x_0)}{x_1 - x_0} }{x_2 - x_0}$
- Difference between the First-Order divided differences ( Second-Order divided differences )
- The divided Differences
$a_0 = f[x_k] = f(x_k)$
$a_1 = f[x_{k-1}, x_k] = \frac{f[x_k] - f[x_{k-1}]}{x_k - x_{k-1}}$
$a_2 = f[ x_{k-2}, x_{k-1}, x_k ] = \frac{ f[x_{k-1}, x_k] - f[x_{k-2}, x_{k-1}] }{x_k - x_{k-2}}$
...
- Higher-order Divided differences
$a_j = f[ x_{k-j}, x_{k-j+1}, \cdots, x_k ] = \frac{ f[x_{k-j+1}, \cdots , x_k] - f[x_{k-j}, \cdots , x_{k-1} ] }{x_k - x_{k-j}}$
First Order Divided Difference
- First order divided difference of $f(x)$ : $f[x_0, x_1] = \frac{ f(x_1) - f(x_0) }{ x_1 - x_0}$
- By mean-value theorem : $f[x_0, x_1] = f'(c)$ for some $c$ between $x_0$ and $x_1$
- $f[x_0, x_1]$ is approximation of derivative : $f'(\frac{x_1 + x_0}{2}) \approx f[x_0, x_1]$
Second Order Divided Difference
- Second order Divided Difference : Given Three distanct points $x_0, x_1, x_2$
- $f[x_0, x_1,x_2] = \frac{ f[x_1, x_2] - f[x_0, x_1] }{x_2 - x_0}$
- $f[x_0, x_1, x_2] = \frac{1}{2} f''(c)$, for some $c$ intermediate to $x_0, x_1, x_2$
- $f''(x_1) \approx 2f[x_0, x_1, x_2]$, in the case the nodes are evenly spaced, $x_1 - x_0 = x_2 - x_1$
General Divided Difference
- Given $n+1$ distinct points $x_0, \cdots, x_n$ with $n \geq 2$
- define : $f[x_0, \cdots , x_n] = \frac{ f[x_1, \cdots, x_n] - f[x_0, \cdots x_{n-1}] }{x_n - x_0}$
- $f[x_0, \cdots, x_n] = \frac{1}{n!} f^n(c)$, for some $c$ intermediate to the points $x_0, \cdots, x_n$
Linear Interpolation -> Lerp
$P_1(x) = (1-t) \vec{x_0} + t \vec{x_1}$
$P_1(x) = \frac{x-x_1}{x_0 - x_1} y_0 + \frac{x - x_0}{x_1 - x_0} y_1 = y_0 + \frac{y_1 - y_0}{x_1 - x_0} (x-x_0)$
-Arc between two unit vectors $q_1, q_2$ ( ex - quaternions, animation pose )
$q(t) = (1-t)q_1 + t q_2 \to q(t) = \frac{(1-t)q_1 + t q_2 }{|| (1-t)q_1 + t q_2 || } $
-> angle is different ( velocity of angle : begining slow, become fast, end slow )
Spherical Linear Interpolation -> Slerp
$q(t) = a(t) q_1 + b(t)q_2 $
$a(t) = \frac{\sin \theta (1-t)}{\sin \theta}, b(t) = \frac{\sin \theta t}{\sin \theta}$
$q(t) = \frac{\sin \theta (1-t)}{\sin \theta} q_1 + \frac{\sin \theta t}{\sin \theta} q_2$
$\theta = \cos^{-1}(q_1 \cdot q_2)$
Bilinear Interpolation
Interpolation 2D ( map interpolation)
- 4 Data point $Q_{11}, Q_{12}, Q_{21}, Q_{22}$
-$f(R_1)$ : interpolation of $Q_{11}, Q_{21}$, $f(R_2)$ : interpolation of $Q_{12}, Q_{22}$
- $f(P)$ : Bilinear Interpolation
$f(R_1) \approx \frac{x_2 - x}{x_2 - x_1} f(Q_{11}) + \frac{x - x_1}{x_2 - x_1} f(Q_{21})$
$f(R_2) \approx \frac{x_2 - x}{x_2 - x_1} f(Q_{12}) + \frac{x - x_1}{x_2 - x_1} f(Q_{22})$
$f(P) \approx \frac{y_2 - y}{y_2 - y_1} f(R_1) + \frac{y - y_1}{y_2 - y_1}f(R_2) = (1-\alpha ) f(R_1) + \alpha f(R_2)$
Trilinear Interpolation
Interpolation 3D ( 2D + height )
- 8 Data point : $C_{000}, \cdots, C_{111}$
same with 2D interpolation -> interpolate 2D two times and interpolation 1D one times