보간(Interpolation)이란 데이터가 충분하지 못하고 이산적으로 띄엄띄엄 주어져 있을 때
주어진 데이터들을 적절한 곡선으로 이어서 주어지지 않은 데이터 값을 가상으로 만들어 내주는 작업을 말한다.
이론적이 아닌 현실의 상황에서는 데이터를 정확하게 표현하는 함수를 알기 힘들고
측정을 통해 데이터를 띄엄띄엄 얻어낼 수 밖에 없는 상황이 많다.
하지만 측정되지 않은 구간에서의 데이터가 필요할 때가 많고,
이를 위해서 띄엄띄엄 얻은 데이터 사이를 적절히 연결해주어 예측하는 것이 적절할 것이다.
두 점 $(1, 2)$, $(5, 4)$ 가 주어졌다고 해보자.
$x = 1$, $x = 5$ 사이에서는 $y$ 값들이 어떻게 분포할까?
가장 쉽게는 두 점 사이가 직선으로 이어져 있다고 예측할 수 있다.
물론 두 점 사이를 이차곡선이나 삼차곡선 혹은 그 이상의 다항식으로 연결할 수도 있고
다항식이 아닌 삼각함수, 지수함수, 심지어 이름도 모를 이상한 곡선으로 연결할 수도 있다.
실제로 다항식이 아닌 다른 함수로 보간하는 방법도 존재하지만,
이번 글에서는 다항식 보간법에 대해 다루기 때문에 다항식에 대해서만 따질 것이다.
만약 이 두 점 사이를 이차곡선이나 삼차곡선으로 연결하면 어떻게 될까?
조금만 머릿속으로 시뮬레이션 돌려 보아도 무수히 많은 방법으로 연결할 수 있다는 것이 예상된다.
대수적으로도 증명할 수 있다.
이차함수를 예로 들자. 다음의 이차함수
$$y = ax^2 + bx + c$$
는 두 점
$$ (1, 3), \; (5, 4) $$
를 지나므로 각각 대입해보면 다음과 같다.
$$ \begin{align} 3 &= a + b + c \\ 4 &= 25a + 5b + c \end{align} $$
미지수는 $a, \; b, \; c$ 로 3개인데 주어진 식은 2개이므로 $a, b, c$ 값을 유일하게 결정할 수 없다.
따라서 두 점을 지나는 이차함수를 무한히 많이 만들어낼 수 있게 된다.
삼차 이상의 함수도 같은 방법으로 유일하게 결정할 수 없다는 것이 증명된다.
이는 선형대수에서 다루는 내용인데, 선형대수를 잘 모르는 사람을 위해 길게 풀어쓰자면 이렇다.
위 연립방정식을 행렬로 표현하면 다음과 같다.
$$ \begin{bmatrix} 1 & 1 & 1 \\ 25 & 5 & 1 \end{bmatrix} \begin{bmatrix} a \\ b \\ c \end{bmatrix} = \begin{bmatrix} 3 \\ 4 \end{bmatrix} $$
이 것을 다르게 표현하면 다음과 같다.
$$ \textcolor{orange}{\begin{bmatrix} 1 \\ 25 \end{bmatrix}}a + \textcolor{orange}{\begin{bmatrix} 1 \\ 5 \end{bmatrix}}b + \textcolor{orange}{\begin{bmatrix} 1 \\ 1 \end{bmatrix}}c = \textcolor{skyblue}{\begin{bmatrix} 3 \\ 4 \end{bmatrix}} $$
즉, 벡터 $\textcolor{orange}{\begin{bmatrix} 1 \\ 25 \end{bmatrix}}$ 의 $a$ 배, 벡터 $\textcolor{orange}{\begin{bmatrix} 1 \\ 5 \end{bmatrix}}$ 의 $b$ 배, $\textcolor{orange}{\begin{bmatrix} 1 \\ 1 \end{bmatrix}}$ 의 $c$ 배한 것을 조합하여 $\textcolor{skyblue}{\begin{bmatrix} 3 \\ 4 \end{bmatrix}}$ 를 만드는 것과 같은데,
이 3개의 벡터는 서로 독립이므로 2개만 있어도 $\begin{bmatrix} 3 \\ 4 \end{bmatrix}$ 를 만드는 것이 충분하다.
따라서 하나의 벡터가 불필요하게 추가된 꼴이며 가능한 $a, \; b, \; c$ 의 조합을 무한개로 만든다.
잘 이해가 안된다면 2차원 벡터말고 1차원 벡터, 즉 상수로 차원을 낮춰보자.
$\textcolor{skyblue}{[7]}$ 이라는 1차원 벡터를 만들려고 하면 1차원 벡터 하나로 충분하다.
예를들어 $\textcolor{orange}{[1]}$ 이라는 벡터로는 $7$ 을 곱해주면 $\textcolor{skyblue}{[7]}$ 을 얻을 수 있고
$\textcolor{orange}{[2]}$ 로는 $3.5$ 를 곱해서 $\textcolor{skyblue}{[7]}$ 을 얻을 수 있으며 $\textcolor{orange}{[-5]}$ 로는 $-\dfrac{7}{5}$ 을 곱해서 만들 수 있다.
각각의 1차원 벡터에 대해 곱해야 하는 값은 유일하다.
그런데 $\textcolor{orange}{[1]}$ 과 $\textcolor{orange}{[-5]}$ 라는 두 개의 재료가 주어지게 되면
$\textcolor{orange}{[1]} \times 12 + \textcolor{orange}{[-5]} \times 1 = \textcolor{skyblue}{[7]}$ 도 가능하고
$\textcolor{orange}{[1]} \times 3 + \textcolor{orange}{[-5]} \times (-\dfrac{4}{5}) = \textcolor{skyblue}{[7]}$ 도 역시 가능하다. 이외에도 무수히 많이 있다.
반면 0개의 1차원 벡터 재료로는 1차원 벡터를 만들 수 없다.
(만들고자 하는 1차원 벡터가 [0] 이라면 가능하지만 일반적으로는 만들 수 없다.)
마찬가로 2차원 벡터도 2개의 독립인 벡터의 조합으로는 유일하게 만들 수 있지만,
3개 이상의 재료가 주어진다면 가능한 조합은 무한히 많아진다.
역시 두 벡터가 같지 않은 이상 일반적으로 1개 이하의 2차원 벡터로는 2차원 벡터를 만들 수 없다.
선형(linear) 연립방정식에서 $n$ 개의 미지수를 반드시 결정하기 위해서는
최소 $n$ 개의 방정식이 필요하다는 말이 여기서 유래한다.
만약 연립방정식이 선형이 아니라면 일반적으로는 이 명제가 참이 아니다.
반면에, 1차함수일 때는 2개의 점만으로도 유일하게 이을 수 있다는 것을 직관적으로 알 수 있다.
그리고 0차함수, 즉 상수함수로는 일반적으로 두 개의 점을 동시에 지나게 할 수 없다.
(두 점이 평행하게 놓이는 경우가 유일한 예외이다.)
이를 일반화해보면,
$n$개의 점을 다항식 보간(Polynominal interpolation)할 때는
$(n-1)$ 차 다항함수를 택해야 유일하게 만들 수 있다는 것을 알 수 있다.
일반화 하기에 앞서 점의 갯수를 조금만 늘려서 Polynominal interpolation이 어떻게 결정되는지 살펴보자.
다음과 같이 4개의 점(데이터)이 주어져 있다고 하자.
$$ \begin{align} &(-2, &4) \\ &(0, &-2) \\ &(1, &1) \\ &(3, &0) \end{align} $$
4개의 점이 존재하므로 이 점들을 지나며 유일하게 결정할 수 있는 다항식은 3차 다항식이다.
따라서 미지의 값 $a, \; b, \; c, \; d$ 에 대해 3차 다항식을 다음과 같이 세울 수 있다.
$$ f(x) = ax^3 + bx^2 + cx + d $$
이 함수가 네 점을 지나므로 각각 대입하면
$$ \begin{align} 4 &= (-2)^3 a + (-2)^2 b + (-2) c + d \\ -2 &= (0)^3a + (0)^2b + (0)c + d \\ 1 &= (1)^3a + (1)^2b + (1)c + d \\ 0 &= (3)^3a + (3)^2b + (3)c + d \end{align} $$
이를 행렬로 표현하면 다음과 같다. 여기서 계수 행렬(맨 앞의 행렬)을 Vandermonde matrix 라고 부른다.
$$ \begin{bmatrix} (-2)^3 & (-2)^2 & (-2)^1 & 1 \\ (0)^3 & (0)^2 & (0)^1 & 1 \\ (1)^3 & (1)^2 & (1)^1 & 1 \\ (3)^3 & (3)^2 & (3)^1 & 1 \end{bmatrix} \begin{bmatrix} a \\ b \\ c \\ d \end{bmatrix} = \begin{bmatrix} 4 \\ -2 \\ 1 \\ 0 \end{bmatrix} $$
Gaussian elimination을 쓰든 Inverse matrix를 양변에 곱해 해를 구하든 어떤 방법으로든 해를 구하면 다음과 같이 나온다.
$$ \begin{bmatrix} a \\ b \\ c \\ d \end{bmatrix} = \begin{bmatrix} -\frac{19}{30} \\ \frac{41}{30} \\ \frac{34}{15} \\ -2 \end{bmatrix} $$
행렬이 뭔지 모르겠으면 위의 연립방정식을 그냥 노가다를 통해 풀어도 똑같은 답을 얻는다.
(사실 손으로 풀면 행렬을 이용한 풀이도 노가다이긴 마찬가지이다.
다만 보기에 깔끔하고 수치해석 과목인 만큼 컴퓨터가 다루기 편한 꼴인 행렬로 쓰는 것이다.)
따라서 네 점을 지나는 보간 다항 함수는 다음과 같다.
$$ y = -\dfrac{19}{30}x^3 + \dfrac{41}{30}x^2 + \dfrac{34}{15}x - 2 $$
이제 점의 갯수가 $n$ 개인 일반적인 상황을 살펴보자.
다음과 같이 $n$ 개의 점이 주어져 있으면
$$(x_1, y_1), \; (x_2, y_2), \; (x_3, y_3), \; \cdots \; (x_n, y_n)$$
다음과 같은 $(n-1)$ 차 다항식이 필요하다.
$$ y = a_{n-1}x^{(n-1)} + a_{n-2}x^{(n-2)} + \cdots + a_1x + a_0 $$
이 다항식에서 우리는 $a_0, \; a_1, \; a_2, \; \cdots , a_{n-1}$ 값을 결정해야 한다.
$n$ 개의 점들을 각각 대입하여 얻는 연립방정식을 행렬로 표현하면 다음과 같다.
$$ \begin{bmatrix} x_1^{(n-1)} & x_1^{(n-2)} & \cdots & x_1 & 1 \\ x_2^{(n-1)} & x_2^{(n-2)} & \cdots & x_2 & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ x_{n-1}^{(n-1)} & x_{n-1}^{(n-2)} & \cdots & x_{n-1} & 1 \\ x_n^{(n-1)} & x_n^{(n-2)} & \cdots & x_n & 1 \end{bmatrix} \begin{bmatrix} a_{n-1} \\ a_{n-2} \\ \vdots \\ a_1 \\ a_0 \end{bmatrix} = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_{n-1} \\ y_n \end{bmatrix} $$
이 때 Vandermonde matrix 가 Nonsingular 이면 $a_0, a_1, a_2, \cdots , a_{n-1}$ 값이 유일하게 결정된다.
그런데 Vandermonde matrix 는 항상 Nonsingular 이다.
왜냐하면 각각의 행은 $\begin{bmatrix} x^{(n-1)} & x^{(n-2)} & \cdots & x & 1 \end{bmatrix}$ 꼴인데,
이 때의 $x$ 에 대입되는 값들은 주어진 점들의 $x$ 값들이고
애초에 서로 다른 $x$ 값들에 대해서 데이터가 주어지기 때문에
행들은 서로 같을 수도 없으며 선형적으로 종속일 수도 없다.
모든 행들이 독립이므로 Vandermonde matrix는 항상 Nonsingular 이다.
Vandermonde matrix 가 Nonsingular 임을 알았으므로 해를 구할 수 있고
이렇게 결정한 $a_{n-1}, \; a_{n-2}, \; \cdots \; , a_0$ 을 다항식
$$ y = a_{n-1}x^{(n-1)} + a_{n-2}x^{(n-2)} + \cdots + a_1x + a_0 $$
에 대입하면 보간 다항식이 완성된다.
정말 쉽게 이번 글을 요약하자면,
1. $n$ 개의 점이 주어졌을 때 이를 모두 지나는 $(n-1)$ 차 다항식으로 interpolation 할 것이다.
2. 모든 점들을 대입하여 다항식의 계수를 결정해주면 끝
다항식으로 보간하는 방법은 이 방법 외에도 여러가지가 있고 모두 같은 결과를 도출한다.
이외의 방법은 시간이 날 때 천천히 올려볼 것이다
'수학 > 수치해석' 카테고리의 다른 글
| 수치적으로 해를 찾는 알고리즘 1 - Bisection Method (0) | 2022.10.27 |
|---|