Newtonโs Divided Differences
์ํ๊ณผ ๋ณต์์ ๊ณต์ ์ํด ์กธ์ ๋ง์ง๋ง ํ๊ธฐ์ โ์์นํด์๊ฐ๋ก โ ์์ ์ ๋ฃ๊ฒ ๋์์ต๋๋ค. ์ํ๊ณผ ์กธ์ ์ํ๋ ๊ฒธ์ฌ๊ฒธ์ฌ ์ค๋นํ ๊ฒธ ํ์ดํ ํด๋ด ์๋ค!! ์ ์ฒด ํฌ์คํธ๋ โNumerical Analysisโ์์ ํ์ธํ ์ ์์ต๋๋ค.
Divided Differences
๋ดํด์ ๋ฐฉ๋ฒ์ ์๊ธฐ ์ ์ ๊ธฐ๋ณธ ์ฌ๋ฃ๊ฐ ๋๋ โ๋๋์ ์ฐจ๋ถ(Divided Difference)โ์ ๋จผ์ ์์์ผ ํฉ๋๋ค. ์ฃผ์ด์ง ์ฌ๋ฌ ์ ๋ค์ ์ด์ฉํด์ ํจ์์ ๋ณํ ์์์ ๊ณ์ฐํ๋ ๋ฐฉ๋ฒ ์ ๋๋ค.
\[c_0 = f[x_0] = f(x_0)\]- 0์ฐจ ๋๋์
์ฐจ๋ถ
- ๋ง ๊ทธ๋๋ก ํจ์์ ๊ฐ ์ ๋๋ค.
- ๊ณ์ $c_0$์ ํด๋น
- 1์ฐจ ๋๋์
์ฐจ๋ถ
- ๋ ์ ์ฌ์ด์ ๊ธฐ์ธ๊ธฐ(ํ๊ท ๋ณํ์จ) ์ ๋๋ค.
- 2์ฐจ ๋๋์
์ฐจ๋ถ
- ๊ธฐ์ธ๊ธฐ์ ๋ณํ์จ ์ ๋๋ค.
- ๋ 1์ฐจ ๋๋์ ์ฐจ๋ถ์ ๊ฐ์ผ๋ก ๋๋์ ์ฐจ๋ถ์ ๊ณ์ฐํ ๊ฒ์ ๋๋ค.
- $i$์ฐจ ๋๋์
์ฐจ๋ถ
- ๋ $i-1$์ฐจ ๋๋์ ์ฐจ๋ถ์ ๊ฐ์ผ๋ก ๋๋์ ์ฐจ๋ถ์ ๊ณ์ฐํ ๊ฒ์ ๋๋ค.
0๋ถํฐ $i$์ฐจ ๋๋์ ์ฐจ๋ถ์ ์ดํด๋ณด๋ฉด, ๊ทธ ์ ์์ ๋ชจ๋ ํ์ ์ฐจ๋ถ์ ๊ฐ์ ํ์๋ก ํฉ๋๋ค. ์ฆ, ์ฌ๊ท์ (Recursive)์ผ๋ก ๋๋์ ์ฐจ๋ถ์ ๊ฐ์ ๊ณ์ฐํ๊ฒ ๋ฉ๋๋ค.
Newtonโs Divided Difference
๋ดํด์ ์์์ ์ ์ํ ๋๋์ ์ฐจ๋ถ์ผ๋ก $n$๊ฐ ์ ์ ๋ณด๊ฐํ๋ ๋ฐฉ๋ฒ์ ๊ณ ์ํฉ๋๋ค. ๋ฐฉ๋ฒ์ ์๋์ ๊ฐ์ต๋๋ค.
\[\begin{aligned} I_n f(x) = f[x_1] &+ f[x_1, x_2](x-x_1) \\ &+ f[x_1, x_2, x_3](x-x_1)(x-x_2) \\ &+ \cdots \\ &+ f[x_1, \dots, x_n] \prod_{i=1}^{n} (x - x_i) \end{aligned}\]๋๋์ ์ฐจ๋ถ ๋ถ๋ถ๋ง ๊ณ์ $c_k$๋ก ํํํ๋ฉด ์๋์ ๊ฐ์ต๋๋ค.
\[\begin{aligned} I_n f(x) &= c_0 + c_1(x-x_1) + c_2(x-x_1)(x-x_2) + \cdots + c_{n-1} \prod_{i=0}^{n-1} (x - x_i) \\ \text{where} \quad c_k &= f[x_1, \dots, x_k] \end{aligned}\]The divided difference table
โDr. Will Woodโ์ ์์์์๋ ๋๋์ ์ฐจ๋ถ์ ์ฝ๊ฒ ๊ณ์ฐํ๊ธฐ ์ํ ํ ์ด๋ธ์ ์ ์ ํฉ๋๋ค.
์์ผ๋ก ๋๋์ ์ฐจ๋ถ์ ๊ตฌํด์ผ ํ๋ค๋ฉด, ์ด๋ ๊ฒ ํ ์ด๋ธ์ ๋ง๋ค์ด์ ๊ณ์ฐํ๋๊ฒ ์ค์ํ์ง ์๋ ๋ฐฉ๋ฒ์ผ ๊ฒ ๊ฐ์ต๋๋ค. ๊ทธ๋ฆฌ๊ณ ๋๋์ ์ฐจ๋ถ์ด ์ฌ๊ท์ ์ํด ์ ๋๋๋ค๋ ๊ฒ๋ ์๊ฐ์ ์ผ๋ก ํ์ธํ ์ ์์ต๋๋ค.
๊ฐ ๋จ๊ณ์ ๋๋์ ์ฐจ๋ถ์ ๋ชจ๋ ๊ณ์ฐํ๋ค๋ฉด, ๋๋์ ์ฐจ๋ถ์ ๋งจ ์ ๋ถ๋ถ๋ค๋ง ๋ชจ์์ ์ต์ข ํํ๋ฅผ ์ ๋ํ ์ ์์ต๋๋ค.
How interpolation works
$p_n(x)$๋ฅผ $0$๋ถํฐ $n$๊น์ง์ ์ ๋ค์ ์ฌ์ฉํด ๋ณด๊ฐํ ํจ์๋ผ๊ณ ํ๊ณ ,
$q_n(x)$๋ฅผ $1$๋ถํฐ $n+1$๊น์ง์ ์ ๋ค์ ์ฌ์ฉํด ๋ณด๊ฐํ ํจ์๋ผ๊ณ ํฉ๋๋ค.
๋ ํจ์๋ฅผ ์๊ฐ์ ์ผ๋ก ํํํ๋ฉด ์๋์ ๊ฐ์ต๋๋ค.
์ด์ ๋ ํจ์๋ฅผ ์กฐํฉํ์ฌ ํ์ฅํ ํจ์ $p_{n+1}(x)$๋ฅผ ์ ์ ํฉ๋๋ค.
์ด ํจ์๋ $0$๋ถํฐ $n+1$๊น์ง ๋ชจ๋ ์ ์ ์ง๋๊ฐ๋๋ค. ๊ทธ๋ฌ๋ ์ด๊ฒ์ด ์ ๋ง ์ฌ์ค์ธ์ง ์๋ฐํ๊ฒ ์ดํด๋ด์ผ ํฉ๋๋ค.
์ ๋์ $x_0$๊ณผ $x_{n+1}$์์ ํจ์๋ ๊ฐ๊ฐ $p_n(x)$์ $q_n(x)$์ฒ๋ผ ํ๋ ํฉ๋๋ค. ๋ฐ๋ผ์, $p_{n+1}(x)$ ํจ์๋ $x_0$๊ณผ $x_{n+1}$๋ฅผ ์ง๋๊ฐ๋๋ค.
์ ๋์ ์ ์ฌ์ด์ ์๋ $x_k$์ ๋ํด์๋ ํ์ธํด๋ณด์์ผ ํฉ๋๋ค. ์์ ์ ์ ๋ฆฌํ๋ฉด, $x_k$์์ ํ์ฅ ํจ์๊ฐ $p_n(x_k)$์ ๊ฐ์ ๊ฐ์ง์ ๋ณด์ผ ์ ์์ต๋๋ค.
Proof of Theorem
TODO
vs. Langrage Interpolation
์๋ก์ด ๋ฐ์ดํฐ ๋ ธ๋๊ฐ ์ถ๊ฐ๋ ๋, ๋ ๋ฐฉ๋ฒ์ ๋์ ๋ฐฉ์์ด ๋ค๋ฆ ๋๋ค.
- ๋ผ๊ทธ๋์ฃผ ๋ณด๊ฐ๋ฒ
- ๊ฐ ์ ๋ง๋ค ์๋ก์ด ๋คํญ์ ํญ์ด ์๊น๋๋ค.
- ๊ทธ๋์ ์๋ก์ด ๋ฐ์ดํฐ ๋ ธ๋๊ฐ ์ถ๊ฐ๋๋ฉด, ๋ณด๊ฐ์์ ์ฒ์๋ถํฐ ๋ค์ ๊ณ์ฐํด์ผ ํฉ๋๋ค.
- ๋ฐ๋ผ์, ์ ์ด ์ถ๊ฐ๋๋ ์ํฉ์์๋ ์์ฃผ ๋นํจ์จ์ ์ ๋๋ค.
- ๋ถํ ์ฐจ๋ถ ๋ณด๊ฐ๋ฒ
- ์ด์ ์ ๊ณ์ฐ๋ ๊ฐ๋ค์ ๊ทธ๋๋ก ํ์ฉํ ์ ์์ต๋๋ค.
- ์๋ก์ด ๋ฐ์ดํฐ ๋ ธ๋๊ฐ ๋ค์ด์ค๋ฉด, ์๋ก์ด ํญ ํ๋๋ง ๊ณ์ฐํ๋ฉด ๋ฉ๋๋ค.
- ๊ทธ๋์ ๋ณด๊ฐ ํจ์์ โ์ค์๊ฐ ์ ๋ฐ์ดํธโ๊ฐ ๊ฐ๋ฅ ํฉ๋๋ค.
Property
No matter the data points orders
For any permutation $\sigma$ on $\left\{ 1, \dots, n \right\}$,
\[f[x_1, \dots, x_n] = f[x_{\sigma(1)}, \dots, x_{\sigma(n)}]\]์ฆ, ๋ถํ ์ฐจ๋ถ ๋ฐฉ๋ฒ์ ์ ๋ ฅ๋ $x$๋ค์ ์์์ ์ ํ ์ํฅ์ ๋ฐ์ง ์๋๋ค๋ ์ฑ์ง ์ ๋๋ค. ๊ทธ๋์ ๋ถํ ์ฐจ๋ถ์ ๊ณ์ฐํ๊ฑฐ๋ ํํํ ๋, ๋ฐ์ดํฐ์ ์์์์ ์์ ๋กญ์ต๋๋ค.
Connection between Divided Difference and Functionโs Differential
Given divided difference $f[x_1, \dots, x_n]$, it can be derived from the $n-1$-th derivatives like
\[[x_1, \dots, x_n] = \frac{f^{(n-1)}(\xi)}{(n-1)!}\]where $\xi \in \left(\min(\left\{ x_i \right\}), \max(\left\{ x_i \right\})\right)$
์ด๊ฒ์ ์ง๊ด์ ์ธ ์์ ๋ 1์ฐจ ๋ถํ ์ฐจ๋ถ $f[x_1, x_2]$ ์ ๋๋ค. ์ด๊ฒ์
\[f[x_1, x_2] = \frac{f(x_2) - f(x_1)}{x_2 - x_1}\]๋ฅผ ๋ง์กฑํ๋๋ฐ, ์ด๋, โํ๊ท ๊ฐ ์ ๋ฆฌโ์ ์ํด
\[f[x_1, x_2] = \frac{f(x_2) - f(x_1)}{x_2 - x_1} = f'(\xi)\]๋ฅผ ๋ง์กฑํ๋ $\xi$๊ฐ $\xi \in (x_1, x_2)$ ๋ฒ์ ๋ด์ ์กด์ฌํ๊ฒ ๋ฉ๋๋ค. ๊ทธ๋์ ์ด ์ฑ์ง์ โ๊ณ ์ฐจ ํ๊ท ๊ฐ ์ ๋ฆฌ(Generalized Mean Value Theorem)โ์ด๋ผ๊ณ ๋ ํฉ๋๋ค.
Proof: TODO