Notes - Numerical Analysis HT24, Lagrange interpolation
Flashcards
Give a formula for a polynomial $p _ n \in \Pi _ n$ such that
\[p_n(x_i) = f_i\]
for $n+1$ points $(x _ i, f _ i)$.
where
\[L_{n,k}(x) = \prod^n_{i = 0, i \ne k} \frac{(x -x_i)}{(x_k - x_i)}\]Quickly prove that the Lagrange interpolating polynomial for $n+1$ distinct points is unique.
Suppose $p _ n, q _ n$ are Lagrange polynomials of degree $n$. $p _ n - q _ n$ has $n + 1$ distinct roots, so since these polynomials are only of degree $n$, they must be identically $0$.
State the theorem that gives you a bound on the error for a Lagrange interpolating polynomial $p _ n$ approximating a function $f$ on the interval $[x _ 0, x _ n]$.
For every $x \in [x _ 0, x _ n]$, there exists $\xi _ x \in (x _ 0, x _ n)$ such that
\[e(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod^n_{k = 0} (x-x_k)\]where $e(x) = f(x) - p _ {2n+1}(x)$.
Quickly prove that if:
- $p _ n$ is the lagrange interpolating polynomial for points $x _ 0, \cdots, x _ n$
- $f$ is the actual function
- $e(x) = f(x) - p _ n(x)$
Then:
- For every $x \in [x _ 0, x _ n]$, there exists $\xi _ x \in (x _ 0, x _ n)$ such that
\[e(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod^n_{k = 0} (x-x_k)\]
If $x = x _ k$ for any $k$, both sides are $0$ and so the equality follows immediately. So suppose $x \ne x _ k$. Define
\[\phi(t) := e(t) - \frac{e(x)}{\pi(x)} \pi(t)\]where
\[\pi(t) := \prod_{k=0}^n (x -x_k)\]Then note that $\phi(t)$ vanishes at $n + 2$ points: $t = x _ k$ for each $k$, and $t = x$. Then by repeated applications of Rolle’s theorem, $\phi^{(k)}(t)$ vanishes at $n + 2 - k$ points in $(x _ 0, x _ n)$ so $\phi^{(n+1)}(t)$ vanishes at an unknown point $\xi \in (x _ 0, x _ n)$.
Then
\[\begin{aligned} \phi^{(n+1)}(\xi) &= e^{(n+1)}(\xi) - \frac{e(x)}{\pi(x)} \pi^{(n+1)}(\xi) \\\\ &= f^{(n+1)} (\xi) - \frac{e(x)}{\pi(x)} (n+1)! \end{aligned}\]So
\[e(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \pi(x)\]as required.
Quickly prove that if
- $\hat f$ is the $n$-th degree Taylor approximation at $x _ 0$
- $f$ is the actual function
- $e(x) = f(x) - \hat f(x)$ is the error
Then for all $x$, there exists $\xi \in (x _ 0, x)$ such that
\[e(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} (x - x_0)^{n+1}\]
Define the function
\[\phi(t) := e(t) - \frac{e(x)}{\pi(x)}\pi(t)\]where
\[\pi(t) = (t - x_0)^{n+1}\]Since $\phi(x) = 0$ and for each $k$ we have $\phi^{(k)}(x _ 0) = 0$, we can repeatedly apply Rolle’s theorem to determine that $\exists \xi \in (x _ 0, x)$ such that
\[\phi^{(n+1)}(\xi) = 0\]Then
\[e^{(n+1)}(\xi) - \frac{e(x)}{\pi(x)} \pi^{(n+1)}(\xi) = 0\]which implies, after rearranging
\[e(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \pi(x)\]