2 minute read

์ˆ˜ํ•™๊ณผ ๋ณต์ˆ˜์ „๊ณต์„ ์œ„ํ•ด ์กธ์—… ๋งˆ์ง€๋ง‰ ํ•™๊ธฐ์— โ€œ์ˆ˜์น˜ํ•ด์„๊ฐœ๋ก โ€ ์ˆ˜์—…์„ ๋“ฃ๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค. ์ˆ˜ํ•™๊ณผ ์กธ์—…์‹œํ—˜๋„ ๊ฒธ์‚ฌ๊ฒธ์‚ฌ ์ค€๋น„ํ•  ๊ฒธ ํ™”์ดํŒ… ํ•ด๋ด…์‹œ๋‹ค!! ์ „์ฒด ํฌ์ŠคํŠธ๋Š” โ€œNumerical Analysisโ€œ์—์„œ ํ™•์ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋“ค์–ด๊ฐ€๋ฉฐ

โ€œ๋ผ๊ทธ๋ž‘์ง€ ๋ณด๊ฐ„๋ฒ•โ€๊ณผ โ€œ๋ถ„ํ•  ์ฐจ๋ถ„ ๋ณด๊ฐ„๋ฒ•โ€์€ ํ•จ์ˆ˜๋ฅผ ๋ณด๊ฐ„ ๋‹คํ•ญ์‹์œผ๋กœ ๊ทผ์‚ฌํ•œ ๊ฒฐ๊ณผ ์ž…๋‹ˆ๋‹ค. ์ด๊ฒƒ์ด ์‹ค์ œ ํ•จ์ˆ˜์˜ ๊ฐ’๊ณผ ๋ณด๊ฐ„ ๊ฐ’์ด ์–ผ๋งˆ๋‚˜ ์ฐจ์ด๊ฐ€ ๋‚˜๋Š”์ง€๋ฅผ ์ˆ˜ํ•™์ ์œผ๋กœ ์‚ดํŽด๋ณด๋Š” ํŒŒํŠธ ์ž…๋‹ˆ๋‹ค.

Interpolation Error Theorem

Let $x_1, \dots, x_n$ bet $n$ distinct nodes in the interval $[a, b]$. Assume that $f \in C^{n}[a, b]$.

Given that $x \in [a, b]$, there exists a $\xi = \xi(x)$ in $(a, b)$ s.t.

\[f(x) - I_n f(x) = \frac{\omega_n(x)}{n!} f^{(n)} (\xi)\]

where $\omega_n(x)$ is a โ€œnodal polynomialโ€ s.t. $\omega_n(x) = (x-x_1)(x-x_2)\cdots(x-x_n) = \prod (x-x_i)$.

์ด ์ •๋ฆฌ์˜ ์˜๋ฏธ๋Š” ์‹ค์ œ ํ•จ์ˆ˜๊ฐ’๊ณผ ๋ณด๊ฐ„๊ฐ’ ์‚ฌ์ด์˜ ์˜ค์ฐจ๋ฅผ ์ •ํ™•ํžˆ ์œ„์˜ ์ˆ˜์‹์œผ๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ์„ ๋งํ•ฉ๋‹ˆ๋‹ค.

์ด๋•Œ, ์ˆ˜์‹ ์ž์ฒด๋กœ๋„ ๋ช‡๊ฐ€์ง€ ์˜๋ฏธ๊ฐ€ ์œ ๋„ ๋˜๋Š”๋ฐ,

  • ์˜ค์ฐจ๋Š” ๊ณ ์ฐจ ๋„ํ•จ์ˆ˜ $f^{(n)}(\xi)$์— ๋น„๋ก€ํ•œ๋‹ค
    • ํ•จ์ˆ˜๊ฐ€ ๋งŽ์ด ํœ˜์–ด์งˆ์ˆ˜๋ก ์˜ค์ฐจ๊ฐ€ ์ปค์ง‘๋‹ˆ๋‹ค.
  • ์˜ค์ฐจ๋Š” ๋…ธ๋“ค๋“ค๊ณผ์˜ ๊ฑฐ๋ฆฌ ๊ณฑ $\omega_n(x)$์— ๋น„๋ก€ํ•œ๋‹ค
    • $x$๊ฐ€ ๋…ธ๋“œ๋“ค๊ณผ ๋ฉ€๋ฆฌ ๋–จ์–ด์งˆ์ˆ˜๋ก ์˜ค์ฐจ๊ฐ€ ์ปค์ง
  • ์œ„์˜ ์˜ค์ฐจ์‹์€ ๋“ฑํ˜ธ๊ฐ€ ์žˆ๋Š” โ€œ์ •ํ™•ํ•œโ€ ์˜ค์ฐจ ํ‘œํ˜„์‹ ์ž…๋‹ˆ๋‹ค.
    • ๋ญ”ํ•œ๋‹ค๋ฉด, ๋ถ€๋“ฑํ˜ธ๊ฐ€ ์žˆ๋Š” ์˜ค์ฐจ ์ƒํ•œ์„ (error bound)์˜ ํ˜•ํƒœ๋กœ๋„ ์“ธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

ํ•œ๋งˆ๋””๋กœ ์š”์•ฝํ•˜๋ฉด ์•„๋ž˜์™€ ๊ฐ™๊ฒ ๋„ค์š”.

Interpolation error depends on
the nth derivative(=curvature)
and the distance from the interpolation nodes.

Proof

TODO

Properties

Local Bound

โ€œInterpolation Error Theoremโ€์— ์˜ํ•ด ์•„๋ž˜์˜ ๋ถ€๋“ฑ์‹์ด ์„ฑ๋ฆฝ ํ•ฉ๋‹ˆ๋‹ค.

\[\| f(x) - I_n f(x) \| \le \frac{\| \omega_n(x) \|}{n!} M_n\]

where $M_n = \max_{x \in [a, b]} | f^{(n)}(x) |$.

์ด๊ฒƒ์€ $f^{(n)}(\xi)$๊ฐ€ $M_n$์œผ๋กœ ์น˜ํ™˜๋˜๋ฉด์„œ ๋ถ€๋“ฑ์‹์œผ๋กœ ๋ฐ”๋€ ๊ฒƒ ์ž…๋‹ˆ๋‹ค.

Global Bound

โ€œInterpolation Error Theoremโ€์— ์˜ํ•ด ์•„๋ž˜์˜ ๋ถ€๋“ฑ์‹์ด ์„ฑ๋ฆฝ ํ•ฉ๋‹ˆ๋‹ค.

\[\| f(x) - I_n f(x) \| \le \frac{\max_{x\in[a, b]} \| \omega_n(x) \| }{n!} M_n\]

where $M_n = \max_{x \in [a, b]} | f^{(n)}(x) |$.

์ด๊ฒƒ์€ ์ „์—ญ์ ์ธ ์—๋Ÿฌ ์ž…๋‹ˆ๋‹ค. nodal polynomial์ธ $\omega_n(x)$์˜ ์ƒํ•œ์„ ๊ตฌํ•จ์œผ๋กœ์จ, ์ „์—ญ ์—๋Ÿฌ๋ฅผ ์œ ๋„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.