6 minute read

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

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

์—๋ฅด๋ฏธํŠธ ๋ณด๊ฐ„๋ฒ•์€ ๋ผ๊ทธ๋ž‘์ฃผ ๋ณด๊ฐ„๋ฒ•์˜ ํ™•์žฅ๋œ ๋ฐฉ์‹ ์ž…๋‹ˆ๋‹ค. ๋ผ๊ทธ๋ž‘์ฃผ ๋ณด๊ฐ„๋ฒ•์ด ๊ฐ ์  $x_i$์—์„œ ํ•จ์ˆ˜๊ฐ’ $f(x_i)$๋งŒ์„ ๋งž์ถฐ์ฃผ์—ˆ๋‹ค๋ฉด, ์—๋ฅด๋ฏธํŠธ ๋ณด๊ฐ„๋ฒ•์€ ํ•จ์ˆ˜๊ฐ’๊ณผ ํ•จ๊ป˜ ๋„ํ•จ์ˆ˜์˜ ๊ฐ’ $fโ€™(x_i)$๋„ ๋ชจ๋‘ ๋งž์ถ”์–ด ์ค๋‹ˆ๋‹ค.

๋งŒ์•ฝ ํ•จ์ˆ˜์˜ ๋ฏธ๋ถ„๊ฐ’๋„ ์•Œ๊ณ  ์žˆ๋Š” ์ƒํ™ฉ์ด๋ผ๋ฉด, ์—๋ฅด๋ฏธํŠธ ๋ณด๊ฐ„๋ฒ•์„ ํ†ตํ•ด ํ›จ์”ฌ ๋” ์ •ํ™•ํ•œ ๋ณด๊ฐ„์ด ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. ์ด๋Š” ๋ฌผ๋ฆฌ ์‹œ๋ฎฌ๋ ˆ์ด์…˜๊ณผ ์ปดํ“จํ„ฐ ๊ทธ๋ž˜ํ”ฝ ๋ถ„์•ผ์—์„œ ํ›จ์”ฌ ๋ถ€๋“œ๋Ÿฌ์šด ๊ณก์„ ์„ ๊ทธ๋ฆฌ๊ธฐ ์œ„ํ•ด ์‚ฌ์šฉํ•˜๋Š” ์ ‘๊ทผ ์ž…๋‹ˆ๋‹ค.

Given the distinct interpolation nodes $x_i$, $i=1,\dots,n$
and two sets of real numbers $y_i$ and $dy_i$ with $n\ge 0$.

we need to find a polynomial $P \in \mathbb{P}_{2n-1}$ s.t.

\[P(x_i) = y_i \quad P'(x_i) = dy_i\]

Hermite Interpolation

์—๋ฅด๋ฏธํŠธ ๋ณด๊ฐ„๋ฒ•์—์„œ๋Š” ํ•จ์ˆซ๊ฐ’์„ ๋งž์ถฐ์ฃผ๋Š” ๋‹คํ•ญ์‹ $H_i(x)$์™€ ๋ฏธ๋ถ„๊ฐ’์„ ๋งž์ถฐ์ฃผ๋Š” ๋‹คํ•ญ์‹ $K_i(x)$๋กœ ๊ตฌ์„ฑ ๋ฉ๋‹ˆ๋‹ค.

  • $H_i(x)$
    • $P(x_i) = y_i$๊ฐ€ ๋˜๋„๋ก ํ•ฉ๋‹ˆ๋‹ค.
    • $H_i(x_j) = \delta_{ij}$๊ฐ€ ๋˜๋„๋ก ๊ตฌ์„ฑํ•˜๊ณ ,
    • $H_iโ€™(x_j) = 0$์ด ๋˜๋„๋ก ํ•ฉ๋‹ˆ๋‹ค.
  • $K_i(x)$
    • $Pโ€™(x_i) = dy_i$๊ฐ€ ๋˜๋„๋ก ํ•ฉ๋‹ˆ๋‹ค.
    • $K_i(x_j) = 0$์ด ๋ฉ๋‹ˆ๋‹ค.
    • ๋ฐ˜๋ฉด์—, $K_iโ€™(x_j) = \delta_{ij}$๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.

์ด๋Ÿฐ $H_i(x)$์™€ $K_i(x)$๋ฅผ ์ฐพ์„ ์ˆ˜ ์žˆ๋‹ค๋ฉด, ์šฐ๋ฆฌ๋Š” ์•„๋ž˜์™€ ๊ฐ™์ด ์—๋ฅด๋ฏธํŠธ ๋ณด๊ฐ„๋ฒ•์„ ๊ตฌ์„ฑํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

\[P(x) = \sum_{i=1}^n \left[ y_i H_i(x) + dy_i K_i(x) \right]\]

๊ทธ๋ฆฌ๊ณ  ์—๋ฅด๋ฏธํŠธ๋Š” ์ด ๋‹คํ•ญ์‹ $H_i(x)$์™€ $K_i(x)$๋ฅผ ํŠน๋ณ„ํ•œ ๋ฐฉ์‹์œผ๋กœ ์ œ์‹œํ•˜๋Š”๋ฐ, ์ด๋Š” ์•„๋ž˜์˜ โ€œ์กด์žฌ์„ฑ ์ •๋ฆฌโ€์—์„œ ํ˜•ํƒœ๋ฅผ ์‚ดํŽด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

Existence & Uniqueness

Supp. that $x_i$ are distinct real numbers.

Then, given two sets of real numbers $y_i$ and $dy_i$, there is a โ€œuniqueโ€ polynomial $P \in \mathbb{P}_{2n-1}$ s.t.

\[P(x_i) = y_i \quad P'(x_i) = dy_i\]

๋ผ๊ทธ๋ž‘์ฃผ ๋ณด๊ฐ„๋ฒ•์—์„œ๋„ $n$๊ฐœ ๋ฐ์ดํ„ฐ ๋…ธ๋“œ๋ฅผ ์ง€๋‚˜๋Š” ๋ณด๊ฐ„ ๋‹คํ•ญ์‹์ด ์œ ์ผํ•˜๊ฒŒ ์กด์žฌํ•œ๋‹ค๋Š” ๊ฒƒ์„ ์‚ดํŽด๋ณด์•˜์Šต๋‹ˆ๋‹ค. ์—๋ฅด๋ฏธํŠธ ๋ณด๊ฐ„๋ฒ•์—์„œ๋„ ํ•จ์ˆ˜๊ฐ’๊ณผ ๋ฏธ๋ถ„๊ฐ’์„ ๋ชจ๋‘ ๋งŒ์กฑํ•˜๋Š” ๋ณด๊ฐ„ ๋‹คํ•ญ์‹์ด ์œ ์ผํ•˜๊ฒŒ ์กด์žฌํ•œ๋‹ค๋Š” ๊ฒƒ์„ ์–˜๊ธฐํ•˜๋Š” ์ •๋ฆฌ๊ฐ€ ์ด๊ฒƒ ์ž…๋‹ˆ๋‹ค.

Existence

์—๋ฅด๋ฏธํŠธ๋Š” $H_i(x)$์™€ $K_i(x)$๋ฅผ ์•„๋ž˜์™€ ๊ฐ™์ด ์“ธ ์ˆ˜ ์žˆ๋‹ค๊ณ  ์ œ์‹œ ํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ, $L_i(x)$๋Š” ๋ผ๊ทธ๋ž‘์ฃผ ๋ณด๊ฐ„๋ฒ•์˜ ๊ธฐ์ € ๋‹คํ•ญ์‹ ์ž…๋‹ˆ๋‹ค.

\[\begin{aligned} L_i(x) &= \prod_{j=1, j \ne i} \frac{x-x_j}{x_i - x_j} \\ H_i(x) &= \left[ 1 - 2 L_i'(x_i) (x - x_i) \right] \left[L_i(x)\right]^2 \\ K_i(x) &= (x-x_i)\left[L_i(x)\right]^2\\ \end{aligned}\]

๋จผ์ €, ๋‘ ๋‹คํ•ญ์‹์ด $H_i(x_j) = \delta_{ij}$์™€ $K_i(x_j) = 0$์„ ๋งŒ์กฑํ•˜๋Š”์ง€ ์‚ดํŽด๋ด…์‹œ๋‹ค.

\[H_i(x_j) = \delta_{ij}\]

[$i=j$]

\[H_i(x_i) = \left[ 1 - 2 L_i'(x_i) \cancel{(x_i - x_i)} \right] \left[L_i(x_i)\right]^2 = 1 \cdot \left[L_i(x_i)\right]^2 = 1 \cdot 1^2 = 1\]

[$i\ne j$]

\[H_i(x_j) = \left[ 1 - 2 L_i'(x_i) (x_j - x_i) \right] \left[\cancel{L_i(x_j)}\right]^2 = \left[ \cdots \right] \cdot 0^2 = 0\]
\[K_i(x_j) = 0\]

[$i=j$]

\[K_i(x_i) = \cancel{(x_i-x_i)}\left[L_i(x_i)\right]^2 = 0 \cdot 1^2 = 1\]

[$i\ne j$]

\[K_i(x) = (x_j-x_i)\left[\cancel{L_i(x_j)}\right]^2 = (x_j-x_i) \cdot 0^2 = 0\]


๊ทธ๋ฆฌ๊ณ  ๋‘ ๋‹คํ•ญ์‹์ด $H_iโ€™(x_j) = 0$์™€ $K_iโ€™(x_j) = \delta_{ij}$์„ ๋งŒ์กฑํ•˜๋Š”์ง€ ์‚ดํŽด๋ด…์‹œ๋‹ค. ๋จผ์ € ๋‘ ๋‹คํ•ญ์‹์„ ๋ฏธ๋ถ„ํ•œ ๊ฐ’์€ ์•„๋ž˜์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

\[\begin{aligned} H_i'(x) &= -2 L_i'(x_i) [L_i(x)]^2 + \left( 1 - 2 L_i'(x_i) (x-x_i) \right) \cdot 2 L_i(x) L_i'(x) K_i'(x) &= [L_i(x)]^2 + (x-x_i)\cdot 2 L_i(x) L_i'(x) \end{aligned}\]
\[H_i'(x_j) = 0\]

[$i=j$]

\[\begin{aligned} H_i'(x) &= -2 L_i'(x_i) \cancelto{1}{[L_i(x_i)]^2} + \left( 1 - 2 L_i'(x_i) \cancel{(x_i-x_i)} \right) \cdot 2 \cancelto{1}{L_i(x_i)} L_i'(x_i) \\ &= -2 L_i'(x_i) + 2 L_i'(x_i) = 0 \end{aligned}\]

[$i\ne j$]

\[\begin{aligned} H_i'(x) &= -2 L_i'(x_i) [\cancel{L_i(x_j)}]^2 + \left( 1 - 2 L_i'(x_i) (x_j-x_i) \right) \cdot 2 \cancel{L_i(x_j)} L_i'(x_j) \\ &= 0 + 0 = 0 \end{aligned}\]
\[K_i'(x_j) = \delta_{ij}\]

[$i=j$]

\[K_i'(x_i) = \cancelto{1}{[L_i(x_i)]^2} + \cancel{(x_i-x_i)} \cdot 2 L_i(x_i) L_i'(x_i) = 1 + 0 = 1\]

[$i\ne j$]

\[K_i'(x_j) = \cancel{[L_i(x_j)]^2} + (x_j-x_i)\cdot 2 \cancel{L_i(x_j)} L_i'(x_j) = 0 + 0 = 0\]

Uniqueness

์ด ๋ถ€๋ถ„์˜ ์ฆ๋ช…๋„ ๋ผ๊ทธ๋ž‘์ฃผ ๋ณด๊ฐ„๋ฒ•์˜ ์œ ์ผ์„ฑ์„ ์ฆ๋ช…ํ•  ๋•Œ์™€ ๋™์ผํ•˜๊ฒŒ โ€œ๊ท€๋ฅ˜๋ฒ•โ€์œผ๋กœ ์ฆ๋ช… ํ•ฉ๋‹ˆ๋‹ค.

Supp that there exists a polynomial $Q \in \mathbb{P}_{2n-1}$ with $Q \ne P$ s.t.

\[Q(x_i) = y_i \quad Q'(x_i) = dy_i\]

Let $R(x) = P(x) - Q(x)$. Then $R \in \mathbb{P}{2n-1}$ and thus $Rโ€™ \in \mathbb{P}{2n-2}$.

Since $R(x_i) = 0$, then $R$ has $n$ distinct zeros.

โ€œRolleโ€™s Theoremโ€ implies that $Rโ€™$ has at least $n-1$ zeros which interlace the $x_i$.

[Rolleโ€™s Theorem]

ํ•จ์ˆ˜ $f(x)$๊ฐ€ ๋‹ซํžŒ ๊ตฌ๊ฐ„ $[a, b]$์—์„œ ๋‹ค์Œ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•œ๋‹ค๋ฉด,

  • $f$๋Š” ์—ฐ์† ํ•จ์ˆ˜์ด๋‹ค.
  • $f$๋Š” ๋ฏธ๋ถ„ ๊ฐ€๋Šฅํ•˜๋‹ค.
  • $f(a) = f(b)$์ด๋‹ค.

๊ทธ๋Ÿฌ๋ฉด, ์—ด๋ฆฐ ๊ตฌ๊ฐ„ $(a, b)$ ์•ˆ์— ์–ด๋–ค ์  $c$๊ฐ€ ์ ์–ด๋„ ํ•˜๋‚˜ ์กด์žฌํ•ด์„œ $fโ€™(c) = 0$์„ ๋งŒ์กฑํ•œ๋‹ค.

โ€ฆ. TODO!

๋งบ์Œ๋ง

Hermite Polynomial์„ ์ฒ˜์Œ ์ ‘ํ•œ๋‹ค๋ฉด, ๋ฐ˜๋“œ์‹œ ์—ฐ์Šต ๋ฌธ์ œ๋ฅผ ํ•˜๋‚˜๋Š” ํ’€์–ด๋ณด๊ธธ ๋ฐ”๋ž€๋‹คโ€ฆ ใ…‹ใ…‹

๋งŒ์•ฝ, ์ง์ ‘ ์†์œผ๋กœ ํ•ด๋ณด๋ฉด ์ •๋ง ๊ท€์ฐฎ๋‹คโ€ฆ!! ๊ทธ๋ž˜์„œ ๋‹ค์Œ ๋‚ด์šฉ์ด ๋‚˜์˜จ ๊ฒƒ์ธ๋ฐ, Hermite Polynomial์„ approximation์„ ๋Œ€์‹  ๊ตฌํ•œ๋‹ค.

๋ฐฉ๋ฒ•์€ Newtonโ€™s Divided Difference ๊ณต์‹์œผ๋กœ ๊ตฌํ•˜๋Š” ๊ฒƒ์ด๋‹ค.

์ž์„ธํ•œ ๋‚ด์šฉ์€ ๋‹ค์Œ ํฌ์ŠคํŠธ์—์„œ ใ…Žใ…Ž