Interpolation for Uniformly Spaced Nodes, Runge Phenomenon
์ํ๊ณผ ๋ณต์์ ๊ณต์ ์ํด ์กธ์ ๋ง์ง๋ง ํ๊ธฐ์ โ์์นํด์๊ฐ๋ก โ ์์ ์ ๋ฃ๊ฒ ๋์์ต๋๋ค. ์ํ๊ณผ ์กธ์ ์ํ๋ ๊ฒธ์ฌ๊ฒธ์ฌ ์ค๋นํ ๊ฒธ ํ์ดํ ํด๋ด ์๋ค!! ์ ์ฒด ํฌ์คํธ๋ โNumerical Analysisโ์์ ํ์ธํ ์ ์์ต๋๋ค.
๋ค์ด๊ฐ๋ฉฐ
Uniformly Spaced Nodes Interpolation
์ด๋ฒ์๋ ๋ฐ์ดํฐ ๋ ธ๋๊ฐ ํน์ํ๊ฒ ๋ฐฐ์น๋ ๊ฒฝ์ฐ๋ฅผ ์ดํด๋ด ์๋ค.
๋ชจ๋ ๋ฐ์ดํฐ ๋ ธ๋๊ฐ $[a, b]$ ๊ณต๊ฐ ์์ ๋์ผํ ๊ฑฐ๋ฆฌ๋งํผ ๋ถ์ฐ ๋์ด ์๋ค๊ณ ํฉ์๋ค. ๊ฐ ์ ์ด ๋ถ์ฐ๋ ๊ฑฐ๋ฆฌ๋ฅผ $h$๋ผ๊ณ ํ๋ค๋ฉด, ๊ฐ ์ ์ ์๋์ ๊ฐ์ด ๋ฐฐ์น๋ ๊ฒ ์ ๋๋ค.
\[x_i = a + i h \quad \text{where} \quad h = \frac{b-a}{n}\]๊ทธ๋ฆฌ๊ณ ๋ณด๊ฐ ์ค์ฐจ๋ ์๋์ ๊ฐ์ด ์ฃผ์ด์ง๋๋ค.
\[\| f(x) - I_n f(x) \| \le \frac{\max_{x\in[a, b]} \| \omega_n(x) \| }{n!} M_n\]Estimate for nodal polynomial error bound
๋ฐ์ดํฐ ๋ ธ๋๊ฐ ๊ท ๋ฑํ๊ฒ ๋ถ๋ ๋์ด ์๋ค๋ฉด, nodal polynomial $\omega_n(x)$์ ์ํ์ ์ ํํ๊ฒ ์ ๋ํ ์ ์์ต๋๋ค.
์ฝ๊ฒ ์งํํ๊ธฐ ์ํด ํ์ $x$๋ฅผ $x = a + hs$๋ก ๋ณ์ ์นํ์ ํฉ๋๋ค. $x$๋ ๋ฐ์ดํฐ ๋ ธ๋ $x_i$๊ฐ ์๋๋ผ ์์์ ํ์ ์ธ ๊ฒ์ ์ ์ํฉ๋๋ค. ๊ทธ๋ฌ๋ฉด $\omega_n(x)$๋ ์๋์ ๊ฐ์ด ๋ค์ ์์ฑ ๋ฉ๋๋ค.
\[\begin{aligned} \omega_n(x) &= \prod_{j=1}^n (x-x_j) \\ &= \prod_{j=1}^n \left((a + hs)-(a + hj)\right) \\ &= \prod_{j=1}^n h(s - j) \\ &= h^n \prod_{j=1}^n (s - j) \end{aligned}\]์ค์ฐจ ์ํ $W$๋ฅผ ์ ์ ํฉ๋๋ค.
\[\begin{aligned} W &= \max_{x\in[a, b]} \| \omega_n (x) \| \\ &= \max_{s \in (0, n)} \left\{h^n \prod_{j=1}^n \| s - j \|\right\} \\ &= h^n \cdot \max_{s \in (0, n)} \left\{\prod_{j=1}^n \| s - j \|\right\} \end{aligned}\]์ฆ, ์๋์ ๊ณฑ์ ์ต๋๊ฐ์ ๊ตฌํ๋ ๊ฒ์ด ๋ชฉํ ์ ๋๋ค.
\[\prod_{j=1}^n \| s - j \|\]์ด๊ฒ์ ๊ตฌํ๊ธฐ ์ํด ์ฝ๊ฐ์ ํธ๋ฆญ์ ์จ์ผ ํฉ๋๋ค. $s \in (0, n)$๋ ๊ตฌ๊ฐ ๋ด์ ์๋ ์ด๋ค ์ค์ ์ ๋๋ค. ๊ทธ๋์ ์ด๋ค ์ ์ $i \in [0, n]$์ ๋ํด $i < s < i+1$๋ฅผ ๋ง์กฑ ํฉ๋๋ค. ์ด ์ ์ $i$๋ฅผ ๊ธฐ์ค์ผ๋ก ๊ณฑ์ ๋๋ ์ค๋๋ค.
\[\begin{aligned} \prod_{j=1}^n \| s - j \| = \left(\prod_{j=1}^{i-1} \| s - j \|\right) \cdot \left( s - i \right) \cdot \left( s - (i+1) \right) \cdot \left( \prod_{j=i+2}^{n} \| s - j \| \right) \end{aligned}\]์ ๋๊ฐ์ด ์๋ ๋ถ๋ถ๋ง ์ค์ฐจ ํ๊ณ๋ฅผ ๊ณ์ฐํด๋ณด๋ฉด ์๋์ ๊ฐ์ต๋๋ค.
\[\|(s-j)(s-(i+1))\| \le \frac{1}{4}\]๊ทธ๋ฆฌ๊ณ ๊ณฑ์ ์ ๋ถ๋ถ์ ์ดํด๋ณด๋ฉด, $s \le i+1$๋ผ๋ ์ฑ์ง์ ํ์ฉํด ์๋์ ๊ฐ์ ๋ถ๋ฑ์์ด ์ ๋ ๋ฉ๋๋ค.
\[\prod_{j=1}^{i-1} \| s - j \| = \prod_{j=1}^{i-1} ( s - j ) \le \prod_{j=1}^{i-1} ( i + 1 - j ) = (i+1)!\]๊ทธ๋ฆฌ๊ณ ๊ณฑ์ ๋ท ๋ถ๋ถ์ ์ดํด๋ณด๋ฉด, $s > i$์ด๊ธฐ ๋๋ฌธ์,
\[\prod_{j=i+2}^{n} \| s - j \| = \prod_{j=i+2}^{n} (j - s) \le \prod_{j=i+2}^{n} (j - i) = (2)(3)\cdots(n-i) \le (i+2)(i+3)\cdots n\]๋ฐ๋ผ์, ๊ณฑ์ ์ค์ฐจ ํ๊ณ๋ ์๋์ ๊ฐ์ด ์ ๋ฆฌ ๋ฉ๋๋ค.
\[\begin{aligned} \prod_{j=1}^n \| s - j \| &= \left(\prod_{j=1}^{i-1} \| s - j \|\right) \cdot \left( s - i \right) \cdot \left( s - (i+1) \right) \cdot \left( \prod_{j=i+2}^{n} \| s - j \| \right) \\ &\le (i+1)! \cdot \frac{1}{4} \cdot \left\{(i+2)(i+3)\cdots n\right\} \\ &= \frac{1}{4} n! \end{aligned}\]๋ฐ๋ผ์, ์๋์ ์์ด ์ฑ๋ฆฝํฉ๋๋ค.
\[\max \omega_n(x) = W \le h^n \frac{1}{4} n!\]์ ๋ฆฌํ๋ฉด,
\[\|f(x) - I_n f(x) \| \le \frac{h^{n}}{4 n!} \max_{x \in [a, b]} \| f^{(n+1)} (x) \|\]Runge Phenomenon
์ํ์ โRungeโ๊ฐ ์ ์ํ ํจ์๋ก, ๋ณด๊ฐ๋ฒ์์ ๋ฐ์ํ๋ ์์ฃผ ์ ๋ช ํ ๋ฌธ์ ์ฌ๋ก ์ ๋๋ค.
Runge๋ ์๋์ ๊ฐ์ ๊ฐ๋จ ํจ์๋ฅผ ์ ์ ํฉ๋๋ค.
\[f(x) = \frac{1}{1+12 x^2}\]์ด ํจ์๋ฅผ ๋งค๋๋ฝ๊ณ , ์ ์ฒด์ ์ผ๋ก ์ ์๊ธด ์ข ๋ชจ์ ํจ์ ์ ๋๋ค. ๊ทธ๋ฐ๋ฐ, ์ด๊ฑธ ๊ท ๋ฑํ๊ฒ ๋๋ ๋ ธ๋(equally spaced nodes)๋ฅผ ์ฌ์ฉํด ๋คํญ์์ผ๋ก ๋ณด๊ฐํ๋ฉด ์ฌ๊ฐํ ๋ฌธ์ ๊ฐ ๋ฐ์ ํฉ๋๋ค!
์ด ๋ฌธ์ ๋ ๋คํญ ๋ณด๊ฐ์์, ๋ ธ๋๊ฐ ๊ท ๋ฑํ๊ฒ ๋ฐฐ์น๋์ด ์๊ณ ๋ณด๊ฐ ํจ์์ ์ฐจ์๊ฐ ๋์์ง์๋ก, ํจ์ ์ ๋๋จ์์ ๋ณด๊ฐ ๋คํญ์์ด ์ฌํ๊ฒ ์ง๋ํ๋ ํ์ ์ ๋๋ค.
์ฆ, ์ค์ฌ ์ชฝ์ ๋ณด๊ฐ์ด ์ ๋ง๋๋ฐ ๋นํด, ์ ๋ ๊ตฌ๊ฐ์์๋ ํฌ๊ฒ ์ง๋(wiggle) ํด๋ฒ๋ฆฝ๋๋ค.