\part{Interpolation and Approximation theory}
\chapter{Interpolation}

Often one has a function of discrete 'data points' to evaluate a function from, however if one seeks to evaluate a function at a point between the given data points one resorts to \emph{interpolation}; extending a function of discrete data points to a continuous domain to evaluate points within the range of the data points.

If one wishes to evaluate points above the largest data point or below the smallest data point, this becomes a problem of \emph{extrapolation}.

\section{Lagrange polynomial interpolation}

Consider a vector $\mathbf{x}$ of domain elements with each entry mapped to the image element in $\mathbf{y}$. Note the following.
\[\mathbf{y}_i = f(\mathbf{x}_i)\]

\[U = \{ (x_1,y_1), \hdots , (x_{n},y_{n}) \} \]
\[\ell_n (x) = \frac{\prod_{i \neq n}(x-x_i)}{\prod_{i \neq n}(x_n-x_i)}\]
\[f(x) = \sum_{k=1}^{n} y_k \ell_k (x)\]


\section{Vandermonde polynomial interpolation}

Consider a vector $\mathbf{x}$ of domain elements with each entry mapped to the image element in $\mathbf{y}$. Note the following.
\[\mathbf{y}_i = f(\mathbf{x}_i)\]

Like Lagrange interpolation, we will attempt to use the theory of polynomails to interpolate $f$.

\begin{proposition}
For a set of $n$ mappings of distinct domain elements , there is a unique polynomial of order $n-1$ that interpolates these mappings.
\end{proposition}

This gives rise to a strong idea; assume an $n-1$ degree polynomial and solve for its coefficients. This can indeed be reduced to system of linear equations and hence a simple matrix equation. We can express this problem by means of the \emph{Vandermonde matrix}.


\begin{definition}
A \emph{Vandermonde matrix} $\mathbf{V}$ is a matrix of the first $n$ powers of a set of real numbers.
\[ \mathbf{V}(\mathbf{x}) = \begin{bmatrix} 1 & \mathbf{x}_1 & \mathbf{x}_{1}^2 & \hdots & \mathbf{x}_{1}^n \\ 1 & \mathbf{x}_2 & \mathbf{x}_{2}^2 & \hdots & \mathbf{x}_{2}^n \\ \vdots & \ddots & \vdots & \vdots \\ 1 & \mathbf{x}_n & \mathbf{x}_{n}^2 & \hdots & \mathbf{x}_{n}^n\end{bmatrix} \]

\[ \mathbf{V}(\mathbf{x})_{ij} = \mathbf{x}^{j}_{i} \]
\end{definition}

We can now start to see that the vector of coefficients $\mathbf{c}$ is subject to $\mathbf{V}(\mathbf{x})\mathbf{c}=\mathbf{y}$. i have foreshadowed that there must exist a $n-1$ degree polynomial, so it must be that $\mathbf{V}(\mathbf{x})$ is invertible. Indeed, this checks out by the following proposition.

\begin{proposition}
\[ \det [ \mathbf{V}(\mathbf{x}) ] = \prod_{0 \leq i < j < n} ( \mathbf{x}_j - \mathbf{x}_i ) \]
\end{proposition}

Since we're dealing with distinct domain elements, the determinant is nonzero and hence invertible. We're then left with the following interpolation formula.

\[f(x) = \sum^{n}_{k=1} ( \mathbf{V}^{-1}(\mathbf{x})\mathbf{y} )_{k} x^k\]


\section{Spline interpolation}


\subsection{Bézier curves}

It finds many applications in graphical design; from animation, computer graphics, digital typography, and designing automobile bodies!


			<p>Vector-valued function \(\vec{B} : t \in [0,1]  \to \mathbb{R}^2\) that uses <b>control points</b> \( \{\vec{P}_0 , \vec{P}_1 , \vec{P}_2 , ..., \vec{P}_k \} \subset \mathbb{R}^2 \) to model a curve</p>
			<h4>Definition</h4>
			<p>\( \deg (\vec{B}_{\vec{P}_0 \to \vec{P}_1}) = 1 \implies \vec{B}_{\vec{P}_0 \to \vec{P}_1}(t) = (1-t)\vec{P}_0 + t\vec{P}_1\)</p>
			<p>\( \deg (\vec{B}_{\vec{P}_0 \to \vec{P}_1}) = k \implies \vec{B}_{\vec{P}_0 \to \vec{P}_k}(t) = (1-t)\vec{B}_{\vec{P}_0 \to \vec{P}_{k-1}}(t) + t\vec{B}_{\vec{P}_1 \to \vec{P}_k}(t)\)</p>




\chapter{Approximation theory}
\section{Taylor series approximation}
- Taylor series approximation
\[f(x) = \sum^{n}_{k=0} \frac{f^{(k)}(0)}{k!}x^k\]
\section{Padé approximant}


\subsection{Bhaskara approximation}

I 
\[\sin (\theta) \approx \frac{16 \theta(\pi - \theta}{5\pi^2 - 4\theta (\pi - \theta)} \]

It seems that Bhaskara used this Padé approximant, applied the symmetry $\sin(\theta)=\sin (\pi- \theta)$, and applied the following interpolations.
\[ \sin(0)=0\]
\[ \sin(\frac{pi}{2})=1\]
\[ \sin(\frac{pi}{6})=\frac{1}{2}\]


While in an Airbnb at San Ġiljan, I dropped this last interpolation and used the fact that $\lim_{\theta \to 0} \frac{\sin(\theta)}{\theta}=1$  to derive the following.

\[\sin (\theta) \approx \frac{ ( \frac{-\pi}{4-\pi} ) \theta(\pi - \theta}{( \frac{-\pi^2}{4-\pi} ) + \theta (\pi - \theta)} \]

It's slightly less accuracte than the Bhaskara approximation (interpolation is quite powerful), but it is an interesting example of how Padé approximants can be used in conjunction with certain differential contraints. 





\section{Stirling's formula}


\[n! \sim \sqrt{2\pi n}(\frac{n}{e})^n\]