5 minute read

์ˆ˜ํ•™๊ณผ ๋ณต์ˆ˜์ „๊ณต์„ ์œ„ํ•ด ์กธ์—… ๋งˆ์ง€๋ง‰ ํ•™๊ธฐ์— โ€œ์ˆ˜์น˜ํ•ด์„๊ฐœ๋ก โ€ ์ˆ˜์—…์„ ๋“ฃ๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค. ์ˆ˜ํ•™๊ณผ ์กธ์—…์‹œํ—˜๋„ ๊ฒธ์‚ฌ๊ฒธ์‚ฌ ์ค€๋น„ํ•  ๊ฒธ ํ™”์ดํŒ… ํ•ด๋ด…์‹œ๋‹ค!! ์ „์ฒด ํฌ์ŠคํŠธ๋Š” โ€œ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) ํ•ด๋ฒ„๋ฆฝ๋‹ˆ๋‹ค.