6 minute read

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

Divided Differences

๋‰ดํ„ด์˜ ๋ฐฉ๋ฒ•์„ ์•Œ๊ธฐ ์ „์— ๊ธฐ๋ณธ ์žฌ๋ฃŒ๊ฐ€ ๋˜๋Š” โ€œ๋‚˜๋ˆ—์…ˆ ์ฐจ๋ถ„(Divided Difference)โ€์„ ๋จผ์ € ์•Œ์•„์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ฃผ์–ด์ง„ ์—ฌ๋Ÿฌ ์ ๋“ค์„ ์ด์šฉํ•ด์„œ ํ•จ์ˆ˜์˜ ๋ณ€ํ™” ์–‘์ƒ์„ ๊ณ„์‚ฐํ•˜๋Š” ๋ฐฉ๋ฒ• ์ž…๋‹ˆ๋‹ค.

\[c_0 = f[x_0] = f(x_0)\]
  • 0์ฐจ ๋‚˜๋ˆ—์…ˆ ์ฐจ๋ถ„
    • ๋ง ๊ทธ๋Œ€๋กœ ํ•จ์ˆ˜์˜ ๊ฐ’ ์ž…๋‹ˆ๋‹ค.
    • ๊ณ„์ˆ˜ $c_0$์— ํ•ด๋‹น


\[c_1 = f[x_0, x_1] = \frac{f(x_1) - f(x_0)}{x_1 - x_0}\]
  • 1์ฐจ ๋‚˜๋ˆ—์…ˆ ์ฐจ๋ถ„
    • ๋‘ ์  ์‚ฌ์ด์˜ ๊ธฐ์šธ๊ธฐ(ํ‰๊ท  ๋ณ€ํ™”์œจ) ์ž…๋‹ˆ๋‹ค.


\[c_2 = f[x_0, x_1, x_2] = \frac{f[x_1, x_2] - f[x_0, x_1]}{x_2 - x_0}\]
  • 2์ฐจ ๋‚˜๋ˆ—์…ˆ ์ฐจ๋ถ„
    • ๊ธฐ์šธ๊ธฐ์˜ ๋ณ€ํ™”์œจ ์ž…๋‹ˆ๋‹ค.
    • ๋‘ 1์ฐจ ๋‚˜๋ˆ—์…ˆ ์ฐจ๋ถ„์˜ ๊ฐ’์œผ๋กœ ๋‚˜๋ˆ—์…ˆ ์ฐจ๋ถ„์„ ๊ณ„์‚ฐํ•œ ๊ฒƒ์ž…๋‹ˆ๋‹ค.


\[c_i= f[x_0, \cdots, x_i] = \frac{f[x_1, \cdots, x_i] - f[x_0, \cdots, x_{i-1}]}{x_i - x_0}\]
  • $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โ€™์˜ ์˜์ƒ์—์„œ๋Š” ๋‚˜๋ˆ—์…ˆ ์ฐจ๋ถ„์„ ์‰ฝ๊ฒŒ ๊ณ„์‚ฐํ•˜๊ธฐ ์œ„ํ•œ ํ…Œ์ด๋ธ”์„ ์ œ์‹œ ํ•ฉ๋‹ˆ๋‹ค.

Dr. Will Wood

์†์œผ๋กœ ๋‚˜๋ˆ—์…ˆ ์ฐจ๋ถ„์„ ๊ตฌํ•ด์•ผ ํ•œ๋‹ค๋ฉด, ์ด๋ ‡๊ฒŒ ํ…Œ์ด๋ธ”์„ ๋งŒ๋“ค์–ด์„œ ๊ณ„์‚ฐํ•˜๋Š”๊ฒŒ ์‹ค์ˆ˜ํ•˜์ง€ ์•Š๋Š” ๋ฐฉ๋ฒ•์ผ ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋‚˜๋ˆ—์…ˆ ์ฐจ๋ถ„์ด ์žฌ๊ท€์— ์˜ํ•ด ์œ ๋„๋œ๋‹ค๋Š” ๊ฒƒ๋„ ์‹œ๊ฐ์ ์œผ๋กœ ํ™•์ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Dr. Will Wood

๊ฐ ๋‹จ๊ณ„์˜ ๋‚˜๋ˆ—์…ˆ ์ฐจ๋ถ„์„ ๋ชจ๋‘ ๊ณ„์‚ฐํ–ˆ๋‹ค๋ฉด, ๋‚˜๋ˆ—์…ˆ ์ฐจ๋ถ„์˜ ๋งจ ์œ— ๋ถ€๋ถ„๋“ค๋งŒ ๋ชจ์•„์„œ ์ตœ์ข… ํ˜•ํƒœ๋ฅผ ์œ ๋„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

How interpolation works

$p_n(x)$๋ฅผ $0$๋ถ€ํ„ฐ $n$๊นŒ์ง€์˜ ์ ๋“ค์„ ์‚ฌ์šฉํ•ด ๋ณด๊ฐ„ํ•œ ํ•จ์ˆ˜๋ผ๊ณ  ํ•˜๊ณ ,
$q_n(x)$๋ฅผ $1$๋ถ€ํ„ฐ $n+1$๊นŒ์ง€์˜ ์ ๋“ค์„ ์‚ฌ์šฉํ•ด ๋ณด๊ฐ„ํ•œ ํ•จ์ˆ˜๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

๋‘ ํ•จ์ˆ˜๋ฅผ ์‹œ๊ฐ์ ์œผ๋กœ ํ‘œํ˜„ํ•˜๋ฉด ์•„๋ž˜์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

Dr. Will Wood

์ด์ œ ๋‘ ํ•จ์ˆ˜๋ฅผ ์กฐํ•ฉํ•˜์—ฌ ํ™•์žฅํ•œ ํ•จ์ˆ˜ $p_{n+1}(x)$๋ฅผ ์ •์˜ ํ•ฉ๋‹ˆ๋‹ค.

Dr. Will Wood

์ด ํ•จ์ˆ˜๋Š” $0$๋ถ€ํ„ฐ $n+1$๊นŒ์ง€ ๋ชจ๋“  ์ ์„ ์ง€๋‚˜๊ฐ‘๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ์ด๊ฒƒ์ด ์ •๋ง ์‚ฌ์‹ค์ธ์ง€ ์—„๋ฐ€ํ•˜๊ฒŒ ์‚ดํŽด๋ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

์–‘ ๋์  $x_0$๊ณผ $x_{n+1}$์—์„œ ํ•จ์ˆ˜๋Š” ๊ฐ๊ฐ $p_n(x)$์™€ $q_n(x)$์ฒ˜๋Ÿผ ํ–‰๋™ ํ•ฉ๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ, $p_{n+1}(x)$ ํ•จ์ˆ˜๋Š” $x_0$๊ณผ $x_{n+1}$๋ฅผ ์ง€๋‚˜๊ฐ‘๋‹ˆ๋‹ค.

Dr. Will Wood

์–‘ ๋์ ์˜ ์‚ฌ์ด์— ์žˆ๋Š” $x_k$์— ๋Œ€ํ•ด์„œ๋„ ํ™•์ธํ•ด๋ณด์•„์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์‹์„ ์ž˜ ์ •๋ฆฌํ•˜๋ฉด, $x_k$์—์„œ ํ™•์žฅ ํ•จ์ˆ˜๊ฐ€ $p_n(x_k)$์˜ ๊ฐ’์„ ๊ฐ€์ง์„ ๋ณด์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Dr. Will Wood

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

์ฐธ๊ณ ์ž๋ฃŒ