[수치해석] Polynomial interpolation

보간(interpolation)을 할 때 누구나 생각할 수 있는 방법이 다항식을 이용한 방법입니다. 

점으로 데이터를 가져올 것이라서 그걸 잇는 방법으로 직선이나 곡선으로 이을것인데 다항식은 직선이나 곡선을 만드는 식이니깐 심플하게 시도해 볼 수 있습니다.

수학적으로 어느정도까지 만들어낼 수 있는지 살펴보겠습니다.

 

Linear interpolation

먼저 두점부터 생각해봅시다. 두 점을 잇는 건 다항식으로는 직선으로만 할 수 있습니다.

어떤 선(y=ax+b)이 두 점 $ (x_{0},f_{0}), (x_{1},f_{1}) $을 지난다고 하면 다음과 같이 쓸 수 있습니다.

$$ f_{0} = a+bx_{0} $$

$$ f_{1} = a+bx_{1} $$

 

목적은 직선을 생성하는것이니 적절한 a와 b를 만들어야 합니다. 

중고등학교 때 배운 거라서 쉽게 풀 수 있을겁니다.

'두점이 지날 때 직선의 방정식을 구하시오' 라는 일차함수 문제와 동일합니다. 

기울기를 구하고 점 하나 대입하면 됩니다. 

 

$$ P_{1}(x) = a+bx = \frac{f_{1}-f_{0}}{x_{1}-x_{0}}(x-x_{0})+f_{0} \tag{1}$$

중,고등학교 때 배운 직선의 방정식입니다

 

Error

Error를 살펴보기 전에 우리가 원하는 이상적인 f(x)가 있다고 여기고 Error 함수를 $ e_{1}(x) $ 이라 하겠습니다.

그러면 $ e_{1}(x) = f(x) - P_{1}(x) $ 가 됩니다.

$ x= x_{0}, x_{1} $인 곳에서는 당연히 $e_{1}(x)= 0 이므로 그 점을 제외한 x 에 대하여, (1)식을 활용하면 다음과 같이 됩니다.

 

$$ e_{1}(x) = f(x)-P_{1}(x) = f(x) - f(x_{0}) - \frac{x-x_{0}}{x_{1}-x_{0}}(f(x_{1})-f(x_{0})) $$

 

이제 Error의 범위를 찾아내야 어느정도 정확하게 움직이는지 알 수가 있습니다.

관건은 $ f(x_{1}), f(x_{0}) $ 이 얼마나 움직일 것인가 입니다. 그런데 f(x)는 우리가 알지 못하는 함수이므로 

일반적인 형태로 풀어나가야 할 것같습니다. 

일단 f(x)도 다항식으로써 이상적인 함수이니 미분가능하다는 전제입니다. 

그래서 Taylor polynomial로 표현이 가능하고 표현된 식 $ f_{0},f_{1} $ 가 비슷하게 생길것이라 제거되는 부분을 살펴볼 수 있습니다.

결과적으로 얘기하면 다음과 같습니다.

$ f(x_{0}) = f(x) + (x_{0}-x)f'(x) + \frac{(x_{0}-x)^2}{2}f''(x) +... , \\ f(x_{1}) = f(x) +(x_{1}-x)f'(x)+\frac{(x_{1}-x)^2/2}f''(x)+... $ 일때, 

$$ e_{1}(x) = \frac{x-x_{0}}{2}(x-x_{1})f''(\alpha), \ x_{0}<\alpha<x_{1} \tag{2}$$

 

즉, $ f''(\alpha) $ 이 오차를 형성하는 중심값이 됩니다. 최악의 시나리오로 움직여 오차가 가장 많다면 , $ M = max|f''(x)|, \ x_{0}<x<x_{1} $ 이라 정의하겠습니다.

그러면 다음과 같이 오차범위를 알 수 있습니다.

$$ |e_{1}(x)| ≤ \frac{1}{2} |(x-x_{0})(x-x_{1})|M $$

 

Quadratic interpolation

이제 세점을 지난다고 한다면 위에서 보인 일차함수로는 식이 2개가 되어서 범위함수로 나눠줘야 합니다.

그림도 직선으로만 이루어져 뭔가 작업을 할 때 두가지 경우로 나눠서 해야합니다.

그래서 곡선으로 표현하면서 식을 하나로 나타낸다면 간단해지므로 이차함수로 표현해보는 시도입니다. 

세 점 $ (x_{0},f_{0}), (x_{1},f_{1}) , (x_{2},f_{2}) $ 을 잇는 하나의 함수를 만들어봅시다. 

그러면 이차함수 $ y = a+bx+cx^2 $ 이 적합합니다.

점이 세개니깐 3개의 식으로 이루어진 연립방정식이 생깁니다.

여기서 a,b,c를 구해야하는 상황입니다. 

이럴 땐 행렬로 해서 풀어나가면 되겠죠. 행렬로 표현하면 다음과 같이 나옵니다.

 

$$ \begin{pmatrix} 1 & x_0 & x_0^2 \\ 1 & x_1 & x_1^2 \\ 1 & x_2 & x_2^2 \end{pmatrix} \begin{pmatrix} a \\ b \\ c\end{pmatrix} = \begin{pmatrix} f_0 \\ f_1 \\ f_2 \end{pmatrix} $$

 

이 행렬이 유일한 해를 갖는지 확인하기 위해 행렬식이 0 이 아님을 확인합니다. 

Vandermonde 행렬이므로 행렬식은 다음과 같이 나옵니다. 

 

$$ \begin{vmatrix} 1 & x_0 & x_0^2 \\ 1 & x_1 & x_1^2  \\ 1 & x_2 & x_2^2 \end{vmatrix} = (x_2-x_1)(x_2-x_0)(x_1-x_0) \ne 0 $$

 

행렬식이 0이 아니면 역행렬을 가질 수 있기 때문에 유일한 해를 가지게 됩니다. a,b,c 를 결정하는데 큰 어려움이 없고 풀기만 하면 됩니다.

행렬을 일일히 다 풀면 너무 복잡하니 c는 cramer's rule 으로 풀고

b는 c의 관계식, a는 b,c의 관계식으로 나타내겠습니다.

그러면 다음과 같이 a,b,c 를 구하게 됩니다.

$$ c = \frac{1}{x_2-x_1} \left[ \frac{f_2-f_0}{x_2-x_0} - \frac{f_1-f_0}{x_1-x_0} \right], $$

$$b = \frac{f_1-f_0}{x_1-x_0} - c(x_1+x_0) , \\ a = f_0-b x_0-c x_0^2 $$

 

구한 a,b,c를 넣어서 $ P_2(x) = a+bx+cx^2 $ 에 다항식을 완성하게 됩니다.

오차범위는 Lagrange interpolation에서 다시 설명을 하도록 하겠습니다. 

 

c 계산과정입니다. 요약해서 적어놓았습니다.

$ X = \begin{pmatrix} 1 & x_0 & x_0^2 \\ 1 & x_1 & x_1^2 \\ 1 & x_2 & x_2^2 \end{pmatrix}, \ X_3 = \begin{vmatrix} 1 & x_0 & f_0^2 \\ 1 & x_1 & f_1^2 \\ 1 & x_2 & f_2^2 \end{vmatrix} $

 

$ \begin{align} c  & = \frac{det X_3}{detX} = \dfrac{ \begin{vmatrix} 1 & x_0 & f_0^2 \\ 1 & x_1 & f_1^2 \\ 1 & x_2 & f_2^2 \end{vmatrix} }{ (x_2-x_1)(x_2-x_0)(x_1-x_0) } \\ & = \frac{ (x_1-x_0)f_2-(x_2-x_0)f_1+(x_2-x_1)f_0 }{ (x_2-x_1)(x_2-x_1)(x_1-x_0)} \left( add \  x_0f_0-x_0f_0 \ on \ numerator  \right) \\ & = \frac{1}{x_2-x_1} \left(\frac{f_2-f_0}{x_2-x_0}-\frac{f_1-f_0}{x_1-x_0} \right) \\ \end{align} $

 

관련 포스팅

[수치해석] Polynomial form