Hermite Interpolation
์ํ๊ณผ ๋ณต์์ ๊ณต์ ์ํด ์กธ์ ๋ง์ง๋ง ํ๊ธฐ์ โ์์นํด์๊ฐ๋ก โ ์์ ์ ๋ฃ๊ฒ ๋์์ต๋๋ค. ์ํ๊ณผ ์กธ์ ์ํ๋ ๊ฒธ์ฌ๊ฒธ์ฌ ์ค๋นํ ๊ฒธ ํ์ดํ ํด๋ด ์๋ค!! ์ ์ฒด ํฌ์คํธ๋ โNumerical Analysisโ์์ ํ์ธํ ์ ์์ต๋๋ค.
๋ค์ด๊ฐ๋ฉฐ
์๋ฅด๋ฏธํธ ๋ณด๊ฐ๋ฒ์ ๋ผ๊ทธ๋์ฃผ ๋ณด๊ฐ๋ฒ์ ํ์ฅ๋ ๋ฐฉ์ ์ ๋๋ค. ๋ผ๊ทธ๋์ฃผ ๋ณด๊ฐ๋ฒ์ด ๊ฐ ์ $x_i$์์ ํจ์๊ฐ $f(x_i)$๋ง์ ๋ง์ถฐ์ฃผ์๋ค๋ฉด, ์๋ฅด๋ฏธํธ ๋ณด๊ฐ๋ฒ์ ํจ์๊ฐ๊ณผ ํจ๊ป ๋ํจ์์ ๊ฐ $fโ(x_i)$๋ ๋ชจ๋ ๋ง์ถ์ด ์ค๋๋ค.
๋ง์ฝ ํจ์์ ๋ฏธ๋ถ๊ฐ๋ ์๊ณ ์๋ ์ํฉ์ด๋ผ๋ฉด, ์๋ฅด๋ฏธํธ ๋ณด๊ฐ๋ฒ์ ํตํด ํจ์ฌ ๋ ์ ํํ ๋ณด๊ฐ์ด ๊ฐ๋ฅํฉ๋๋ค. ์ด๋ ๋ฌผ๋ฆฌ ์๋ฎฌ๋ ์ด์ ๊ณผ ์ปดํจํฐ ๊ทธ๋ํฝ ๋ถ์ผ์์ ํจ์ฌ ๋ถ๋๋ฌ์ด ๊ณก์ ์ ๊ทธ๋ฆฌ๊ธฐ ์ํด ์ฌ์ฉํ๋ ์ ๊ทผ ์ ๋๋ค.
Given the distinct interpolation nodes $x_i$, $i=1,\dots,n$
and two sets of real numbers $y_i$ and $dy_i$ with $n\ge 0$.
we need to find a polynomial $P \in \mathbb{P}_{2n-1}$ s.t.
\[P(x_i) = y_i \quad P'(x_i) = dy_i\]Hermite Interpolation
์๋ฅด๋ฏธํธ ๋ณด๊ฐ๋ฒ์์๋ ํจ์ซ๊ฐ์ ๋ง์ถฐ์ฃผ๋ ๋คํญ์ $H_i(x)$์ ๋ฏธ๋ถ๊ฐ์ ๋ง์ถฐ์ฃผ๋ ๋คํญ์ $K_i(x)$๋ก ๊ตฌ์ฑ ๋ฉ๋๋ค.
- $H_i(x)$
- $P(x_i) = y_i$๊ฐ ๋๋๋ก ํฉ๋๋ค.
- $H_i(x_j) = \delta_{ij}$๊ฐ ๋๋๋ก ๊ตฌ์ฑํ๊ณ ,
- $H_iโ(x_j) = 0$์ด ๋๋๋ก ํฉ๋๋ค.
- $K_i(x)$
- $Pโ(x_i) = dy_i$๊ฐ ๋๋๋ก ํฉ๋๋ค.
- $K_i(x_j) = 0$์ด ๋ฉ๋๋ค.
- ๋ฐ๋ฉด์, $K_iโ(x_j) = \delta_{ij}$๊ฐ ๋ฉ๋๋ค.
์ด๋ฐ $H_i(x)$์ $K_i(x)$๋ฅผ ์ฐพ์ ์ ์๋ค๋ฉด, ์ฐ๋ฆฌ๋ ์๋์ ๊ฐ์ด ์๋ฅด๋ฏธํธ ๋ณด๊ฐ๋ฒ์ ๊ตฌ์ฑํ ์ ์์ต๋๋ค.
\[P(x) = \sum_{i=1}^n \left[ y_i H_i(x) + dy_i K_i(x) \right]\]๊ทธ๋ฆฌ๊ณ ์๋ฅด๋ฏธํธ๋ ์ด ๋คํญ์ $H_i(x)$์ $K_i(x)$๋ฅผ ํน๋ณํ ๋ฐฉ์์ผ๋ก ์ ์ํ๋๋ฐ, ์ด๋ ์๋์ โ์กด์ฌ์ฑ ์ ๋ฆฌโ์์ ํํ๋ฅผ ์ดํด๋ณด๊ฒ ์ต๋๋ค.
Existence & Uniqueness
Supp. that $x_i$ are distinct real numbers.
Then, given two sets of real numbers $y_i$ and $dy_i$, there is a โuniqueโ polynomial $P \in \mathbb{P}_{2n-1}$ s.t.
\[P(x_i) = y_i \quad P'(x_i) = dy_i\]๋ผ๊ทธ๋์ฃผ ๋ณด๊ฐ๋ฒ์์๋ $n$๊ฐ ๋ฐ์ดํฐ ๋ ธ๋๋ฅผ ์ง๋๋ ๋ณด๊ฐ ๋คํญ์์ด ์ ์ผํ๊ฒ ์กด์ฌํ๋ค๋ ๊ฒ์ ์ดํด๋ณด์์ต๋๋ค. ์๋ฅด๋ฏธํธ ๋ณด๊ฐ๋ฒ์์๋ ํจ์๊ฐ๊ณผ ๋ฏธ๋ถ๊ฐ์ ๋ชจ๋ ๋ง์กฑํ๋ ๋ณด๊ฐ ๋คํญ์์ด ์ ์ผํ๊ฒ ์กด์ฌํ๋ค๋ ๊ฒ์ ์๊ธฐํ๋ ์ ๋ฆฌ๊ฐ ์ด๊ฒ ์ ๋๋ค.
Existence
์๋ฅด๋ฏธํธ๋ $H_i(x)$์ $K_i(x)$๋ฅผ ์๋์ ๊ฐ์ด ์ธ ์ ์๋ค๊ณ ์ ์ ํฉ๋๋ค. ์ด๋, $L_i(x)$๋ ๋ผ๊ทธ๋์ฃผ ๋ณด๊ฐ๋ฒ์ ๊ธฐ์ ๋คํญ์ ์ ๋๋ค.
\[\begin{aligned} L_i(x) &= \prod_{j=1, j \ne i} \frac{x-x_j}{x_i - x_j} \\ H_i(x) &= \left[ 1 - 2 L_i'(x_i) (x - x_i) \right] \left[L_i(x)\right]^2 \\ K_i(x) &= (x-x_i)\left[L_i(x)\right]^2\\ \end{aligned}\]๋จผ์ , ๋ ๋คํญ์์ด $H_i(x_j) = \delta_{ij}$์ $K_i(x_j) = 0$์ ๋ง์กฑํ๋์ง ์ดํด๋ด ์๋ค.
[$i=j$]
\[H_i(x_i) = \left[ 1 - 2 L_i'(x_i) \cancel{(x_i - x_i)} \right] \left[L_i(x_i)\right]^2 = 1 \cdot \left[L_i(x_i)\right]^2 = 1 \cdot 1^2 = 1\][$i\ne j$]
\[H_i(x_j) = \left[ 1 - 2 L_i'(x_i) (x_j - x_i) \right] \left[\cancel{L_i(x_j)}\right]^2 = \left[ \cdots \right] \cdot 0^2 = 0\][$i=j$]
\[K_i(x_i) = \cancel{(x_i-x_i)}\left[L_i(x_i)\right]^2 = 0 \cdot 1^2 = 1\][$i\ne j$]
\[K_i(x) = (x_j-x_i)\left[\cancel{L_i(x_j)}\right]^2 = (x_j-x_i) \cdot 0^2 = 0\]๊ทธ๋ฆฌ๊ณ ๋ ๋คํญ์์ด $H_iโ(x_j) = 0$์ $K_iโ(x_j) = \delta_{ij}$์ ๋ง์กฑํ๋์ง ์ดํด๋ด ์๋ค. ๋จผ์ ๋ ๋คํญ์์ ๋ฏธ๋ถํ ๊ฐ์ ์๋์ ๊ฐ์ต๋๋ค.
\[\begin{aligned} H_i'(x) &= -2 L_i'(x_i) [L_i(x)]^2 + \left( 1 - 2 L_i'(x_i) (x-x_i) \right) \cdot 2 L_i(x) L_i'(x) K_i'(x) &= [L_i(x)]^2 + (x-x_i)\cdot 2 L_i(x) L_i'(x) \end{aligned}\][$i=j$]
\[\begin{aligned} H_i'(x) &= -2 L_i'(x_i) \cancelto{1}{[L_i(x_i)]^2} + \left( 1 - 2 L_i'(x_i) \cancel{(x_i-x_i)} \right) \cdot 2 \cancelto{1}{L_i(x_i)} L_i'(x_i) \\ &= -2 L_i'(x_i) + 2 L_i'(x_i) = 0 \end{aligned}\][$i\ne j$]
\[\begin{aligned} H_i'(x) &= -2 L_i'(x_i) [\cancel{L_i(x_j)}]^2 + \left( 1 - 2 L_i'(x_i) (x_j-x_i) \right) \cdot 2 \cancel{L_i(x_j)} L_i'(x_j) \\ &= 0 + 0 = 0 \end{aligned}\][$i=j$]
\[K_i'(x_i) = \cancelto{1}{[L_i(x_i)]^2} + \cancel{(x_i-x_i)} \cdot 2 L_i(x_i) L_i'(x_i) = 1 + 0 = 1\][$i\ne j$]
\[K_i'(x_j) = \cancel{[L_i(x_j)]^2} + (x_j-x_i)\cdot 2 \cancel{L_i(x_j)} L_i'(x_j) = 0 + 0 = 0\]Uniqueness
์ด ๋ถ๋ถ์ ์ฆ๋ช ๋ ๋ผ๊ทธ๋์ฃผ ๋ณด๊ฐ๋ฒ์ ์ ์ผ์ฑ์ ์ฆ๋ช ํ ๋์ ๋์ผํ๊ฒ โ๊ท๋ฅ๋ฒโ์ผ๋ก ์ฆ๋ช ํฉ๋๋ค.
Supp that there exists a polynomial $Q \in \mathbb{P}_{2n-1}$ with $Q \ne P$ s.t.
\[Q(x_i) = y_i \quad Q'(x_i) = dy_i\]Let $R(x) = P(x) - Q(x)$. Then $R \in \mathbb{P}{2n-1}$ and thus $Rโ \in \mathbb{P}{2n-2}$.
Since $R(x_i) = 0$, then $R$ has $n$ distinct zeros.
โRolleโs Theoremโ implies that $Rโ$ has at least $n-1$ zeros which interlace the $x_i$.
[Rolleโs Theorem]
ํจ์ $f(x)$๊ฐ ๋ซํ ๊ตฌ๊ฐ $[a, b]$์์ ๋ค์ ์กฐ๊ฑด์ ๋ง์กฑํ๋ค๋ฉด,
- $f$๋ ์ฐ์ ํจ์์ด๋ค.
- $f$๋ ๋ฏธ๋ถ ๊ฐ๋ฅํ๋ค.
- $f(a) = f(b)$์ด๋ค.
๊ทธ๋ฌ๋ฉด, ์ด๋ฆฐ ๊ตฌ๊ฐ $(a, b)$ ์์ ์ด๋ค ์ $c$๊ฐ ์ ์ด๋ ํ๋ ์กด์ฌํด์ $fโ(c) = 0$์ ๋ง์กฑํ๋ค.
โฆ. TODO!
๋งบ์๋ง
Hermite Polynomial์ ์ฒ์ ์ ํ๋ค๋ฉด, ๋ฐ๋์ ์ฐ์ต ๋ฌธ์ ๋ฅผ ํ๋๋ ํ์ด๋ณด๊ธธ ๋ฐ๋๋คโฆ ใ ใ
๋ง์ฝ, ์ง์ ์์ผ๋ก ํด๋ณด๋ฉด ์ ๋ง ๊ท์ฐฎ๋คโฆ!! ๊ทธ๋์ ๋ค์ ๋ด์ฉ์ด ๋์จ ๊ฒ์ธ๋ฐ, Hermite Polynomial์ approximation์ ๋์ ๊ตฌํ๋ค.
๋ฐฉ๋ฒ์ Newtonโs Divided Difference ๊ณต์์ผ๋ก ๊ตฌํ๋ ๊ฒ์ด๋ค.
์์ธํ ๋ด์ฉ์ ๋ค์ ํฌ์คํธ์์ ใ ใ