Numerical Analysis HT24, Hermite interpolation
Flashcards
Suppose:
- Have $x _ 0 < x _ 1 < \cdots < x _ n$ and $f _ i$, $g _ i$ for each $0 \le i \le n$
- Want to find some degree $2n+1$ polynomial $p$ such that $p(x _ i) = f _ i$ and $p’(x _ i) = g _ i$
Describe the construction used to do this and briefly justify why it works.
This is Hermite interpolation. Let
\[\begin{aligned} &L _ {n,k}(x) := \prod^n _ {i = 0, i \ne k} \frac{(x -x _ i)}{(x _ k - x _ i)} \\\\ &F _ {n,k}(x) := (L _ {n, k}(x))^2 (1 - 2(x - x _ k)L' _ {n, k}(x _ k)) \\\\ &G _ {n,k}(x) := (L _ {n, k}(x))^2 (x - x _ k) \end{aligned}\]then
\[p _ {2n+1}(x) := \sum^n _ {k = 0} \left( f _ k F _ {n, k}(x) + g _ k G _ {n, k}(x) \right)\]is a unique degree $2n+1$ polynomial that satisfies the required properties.
Quick justification:
- $F _ {n, k}(x _ i) = \delta _ {ik}$ and $F’ _ {n,k}(x _ i) = 0$
- $G _ {n,k}(x _ i) = 0$ and $G’ _ {n, k}(x _ i) = \delta _ {ik}$
Suppose:
- Have $x _ 0 < x _ 1 < \cdots < x _ n$ and $f _ i$, $g _ i$ for each $0 \le i \le n$
- Want to find some degree $2n+1$ polynomial $p$ such that $p(x _ i) = f _ i$ and $p’(x _ i) = g _ i$
To do this, let
\[\begin{aligned}
&L _
{n,k}(x) := \prod^n _
{i = 0, i \ne k} \frac{(x -x _
i)}{(x _
k - x _
i)} \\\\
&F _
{n,k}(x) := (L _
{n, k}(x))^2 (1 - 2(x - x _
k)L' _
{n, k}(x _
k)) \\\\
&G _
{n,k}(x) := (L _
{n, k}(x))^2 (x - x _
k)
\end{aligned}\]
and then the Hermite interpolating polynomial is defined by
\[p _ {2n+1}(x) := \sum^n _ {k = 0} \left( f _ k F _ {n, k}(x) + g _ k G _ {n, k}(x) \right)\]
Can you state a theorem which gives you a bound on the error, assuming $f$ has at least $2n+2$ smooth derivatives?
For every $x \in [x _ 0, x _ n]$, there exists $\xi _ x \in (x _ 0, x _ n)$ such that
\[e(x) = \frac{f^{(2n+2)}(\xi _ x)}{(2n+2)!}\left(\prod^n _ {k = 0}(x-x _ k)\right)^2\]where $e(x) = f(x) - p _ {2n+1}(x)$. This is almost the same as the Lagrange interpolating case, but now the “product term” has been squared, and we are taking the $2n+2$th derivative instead of the $n+1$st derivative.