폴리노미얼 인터폴레이션
정의 1
서로 다른 $x_{0} , \cdots , x_{n}$ 의 데이터 $(x_{0}, y_{0}) , \cdots , (x_{n} , y_{n})$ 에 대해 $p (x_{i} ) = y_{i}$ 와 $\deg p \le n$ 을 만족하는 인터폴레이션인 다항 함수 $p$ 를 폴리노미얼 인터폴레이션polynomial Interpolation이라 한다.
정리
존재성과 유일성
- [1]: 주어진 데이터에 대해서 $p$ 는 유일하게 존재한다.
라그랑주 공식
- [2]: $$p_{n} (x) = \sum_{i=0}^{n} y_{i} l_{i} (X)$$
뉴턴 계차상 공식
- [3]: $$p_{n} (x) = f(x_{0}) + \sum_{i=1}^{n} f [ x_{0} , \cdots , x_{i} ] \prod_{j=0}^{i-1} (x - x_{j} )$$
오차 분석
- [4]: $(n+1)$번 미분가능한 $f : \mathbb{R} \to \mathbb{R}$ 와 어떤 $\xi \in \mathscr{H} \left\{ x_{0} , \cdots , x_{n} \right\}$ 에 대해 $f$ 의 폴리노미얼 인터폴레이션 $p_{n}$ 은 어떤 $t \in \mathbb{R}$ 에 대해 다음을 만족한다. $$\displaystyle f(t) - p_{n} (t) = {{ (t - x_{0}) \cdots (t - x_{n}) } \over { (n+1)! }} f^{(n+1)} ( \xi )$$
- $\mathscr{H} \left\{ a,b,c, \cdots \right\}$ 는 $a,b,c, \cdots$ 를 포함하는 가장 작은 구간을 나타낸다.
설명
폴리노미얼 인터폴레이션은 한국어로 다항식 보간법이라 순화된다.
조건 $\deg p \le n$
$\deg p \le n$ 라는 조건은 다른 게 아니라 꼭 $\deg p = n$ 을 만족하는 $p$ 가 항상 존재한다는 보장이 없기 때문이다. 간단한 예로써 $n=2$ 일 때 위와 같이 세 점이 일직선 상에 놓여있다면, $(n+1)=3$개의 점을 지나는 $p_{2} (x) = a_{2} x^{2} + a_{1} x + a_{0}$ 는 존재하지 않지만 그보다 차수가 낮은 $p_{1} (x) = a_{1} x + a_{0}$ 는 존재한다. 이것은 사실 $p_{2} (x) = a_{2} x^{2} + a_{1} x + a_{0}$ 을 찾긴 했지만 $a_{2} = 0$ 인 경우를 의미한다.
라그랑주 공식과 뉴턴 계차상 공식은 같다
공식 [2]와 [3]은 생긴 모양은 달라도 사실 [1]에 의해서 서로 같음을 알 수 있다. 본질적으로 두 공식은 정말 말 그대로 $p_{n}$ 을 어떻게 나타내느냐의 차이밖에 없으며, 용도 상 다른 점은 뉴턴 계차상 공식은 새로운 데이터가 추가되었을 때 업데이트가 편하다는 이점이 있다는 정도 뿐이다.
실제 함수와의 오차
정리 [4]는 어떤 함수 $f$ 를 인터폴레이션하는 $p_{n}$ 이 $f$ 와 얼마나 차이가 나느냐를 보여준다. 보통의 경우에 $(n+1)!$ 의 발산 속도는 아주 빠르기 때문에 데이터가 많이 주어질수록 인터폴레이션 $p_{n}$ 의 정확성은 올라간다. 다만 이 공식은 딱히 수렴성을 논하는 것은 아니라는 것에 주의해야한다. 쉬운 예로써 $t$ 가 $\mathscr{H} \left\{ x_{0} , \cdots , x_{n} \right\}$ 에서 정말, 정말 먼 곳에 있는 경우를 생각해볼 수 있다. 또한 $f$ 가 별로 좋지 못해서 미분할때마다 값이 커지고 그것이 심지어 $(n+1)!$ 의 발산속도보다 빠르다면 얼마든지 이상해질 수 있다.
증명
[1]
전략: $(n+1)$개의 연립방정식을 행렬로 나타낸 후 역행렬의 존재성과 유일성을 동시에 가져온다.
모든 $i = 0, \cdots , n$ 에 대해 $y_{i} = p_{n} (x_{i}) = a_{0} + a_{1} x_{i} + \cdots + a_{n} x_{i}^{n}$ 을 만족하는 $p_{n}$ 의 계수 $a_{0} , a_{1} , \cdots , a_{n}$ 가 유일함을 보이면 된다. $$ \mathbf{y} := \begin{bmatrix} y_{0} \\ y_{1} \\ \vdots \\ y_{n} \end{bmatrix}, X := \begin{bmatrix} 1 & x_{0} & \cdots & x_{0}^{n} \\ 1 & x_{1} & \cdots & x_{1}^{n} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_{n} & \cdots & x_{n}^{n} \end{bmatrix} , \mathbf{a} := \begin{bmatrix} a_{0} \\ a_{1} \\ \vdots \\ a_{n} \end{bmatrix} $$ 을 정의하고 연립방정식을 행렬로 나타내면 $$ \begin{bmatrix} y_{0} \\ y_{1} \\ \vdots \\ y_{n} \end{bmatrix} = \begin{bmatrix} 1 & x_{0} & \cdots & x_{0}^{n} \\ 1 & x_{1} & \cdots & x_{1}^{n} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_{n} & \cdots & x_{n}^{n} \end{bmatrix} \begin{bmatrix} a_{0} \\ a_{1} \\ \vdots \\ a_{n} \end{bmatrix} $$ 이제 $\mathbf{y} = X \mathbf{a}$ 를 만족하는 해 $\mathbf{a}$ 를 찾는 문제로 바뀌었다.
방데르몽드 행렬의 행렬식: $X$ 의 행렬식은 $\displaystyle \det X = \prod_{1 \le i < j \le n } (x_{j} - x_{i})$
가정에서 $x_{0} , \cdots , x_{n}$ 는 서로 다르므로 $\det X \ne 0$ 이고, $X^{-1}$ 이 존재한다. 따라서 $\mathbf{a} = X^{-1} \mathbf{y}$ 역시 존재한다. 한편 주어진 행렬에 대한 역행렬은 유일하므로, $\mathbf{a}$ 역시 유일하다.
■
[2]
■
[3]
■
[4]
전략: 더미 함수들을 새로이 정의하고 그들의 미분가능성을 이용해 직접적인 계산을 회피한다. 세팅이 복잡하기 때문에 사실상 뒤에서부터 거꾸로 이해하는 게 편하다.
Claim: $E (x) := f(x) - p_{n} (X)$ 에 대해서 다음이 성립한다. $$ E(t) = {{ (t - x_{0}) \cdots (t - x_{n}) } \over { (n+1)! }} f^{(n+1)} ( \xi ) $$
Part 1.
우선 $t$ 가 노드포인트 $x_{0} , \cdots , x_{n}$ 와 같다면 자명하게 성립하므로 $t$ 는 이들 노드포인트와는 다르다고 가정하자. $$ \begin{align*} \Psi (x) :=& (x - x_{0} ) (x - x_{1}) \cdots (x - x_{n}) \\ G (x) :=& E(x) - {{ \Psi (x) } \over { \Psi (t) }} E(t) \end{align*} $$ 위와 같이 새로운 함수들을 정의하면 $f$, $p_{n}$, $\Psi$ 가 $(n+1)$ 번 미분가능하므로 $G$ 역시 $(n+1)$ 번 미분가능하다.
Part 2.
$G$ 에 $x = x_{i}$ 을 대입하면 $E(x_{i}) = f(x_{i}) - p_{n} (x_{i}) = 0$ 이고 $\Psi (x_{i} ) = 0$ 이므로 $$ G(x_{i}) = E(x_{i} ) - {{ \Psi (x_{i}) } \over { \Psi (t) }} E(t) = 0 $$ $G$ 에 $x = t$ 를 대입하면 $\displaystyle {{ \Psi (t) } \over { \Psi (t) }} = 1$ 이므로 $$ G(t) = E(t) - E(t) =0 $$ 따라서 $G$ 는 $(n+2)$ 개의 서로 다른 영 $x_{0} , \cdots , x_{n} , t$ 을 가진다.
Part 3.
편의상 $x_{n+1} :=t$ 이라 하자.
롤의 정리: 함수 $f(x)$ 가 $[a,b]$ 에서 연속이고 $(a,b)$ 에서 미분가능하며 $f(a)=f(b)$ 면 $f ' (c)=0$ 를 만족하는 $c$ 가 $(a,b)$ 에 적어도 하나 존재한다.
모든 $i=0, \cdots , n$ 에 대해
$$
G(x_{i}) = 0 = G(x_{i+1})
$$
이므로 롤의 정리에 의해 $g ' ( x’_{i}) = 0$ 을 만족하는 $x'_{i} \in \mathscr{H} \left\{ x_{i} , x_{i+1} \right\}$ 가 존재하고, 마찬가지로 모든 $i=0, \cdots , (n-1)$ 에 대해
$$
g ' (x’_{i}) = 0 = g ' (x’_{i+1})
$$
이므로 롤의 정리에 의해 $G''( x’’_{i}) = 0$ 을 만족하는 $x''_{i} \in \mathscr{H} \left\{ x’_{i} , x’_{i+1} \right\}$ 가 존재한다. 이와 같이 귀납적으로 롤의 정리를 $(n+1)$ 번 반복해서 사용하면
$$
G^{(n+1)} ( \xi ) = 0
$$
를 만족하는 $\xi \in \mathscr{H} \left\{ x_{0} , \cdots , x_{n+1} \right\}$ 가 존재함을 보장할 수 있다.
한편 $p_{n}$ 는 $n$차 다항함수이므로 $$ E^{(n+1)} (x) = f^{(n+1)} ( x) $$ $\Psi$ 의 최고차항은 $x^{n+1}$ 이므로 $$ \Psi^{(n+1)} (x) = (n+1)! $$ $\displaystyle G (x) = E(x) - {{ \Psi (x) } \over { \Psi (t) }} E(t)$ 의 양변을 $x$ 에 대해 $(n+1)$번 미분하면 $$ G^{(n+1)} (x) = f^{(n+1)} ( x) - {{ (n+1)! } \over { \Psi (t) }} E(t) $$ $G^{(n+1)}$ 와 $f^{(n+1)}$ 에 $x=\xi$ 을 대입하면 $$ 0 = f^{(n+1)} ( \xi ) - {{ (n+1)! } \over { \Psi (t) }} E(t) $$ $E (t) = f(t) - p_{n} (t)$ 이므로 다음을 얻는다. $$ f(t) - \sum_{j=0}^{n} f( x_{j} ) l_{j} (t) = {{ (t - x_{0}) \cdots (t - x_{n}) } \over { (n+1)! }} f^{(n+1)} ( \xi ) $$
■
Atkinson. (1989). An Introduction to Numerical Analysis(2nd Edition): p131. ↩︎