[수치해석] Spline interpolation(스플라인 보간법)

컴퓨터로 보간법을 사용한다고 할 때 코딩짜기 편한게 스플라인 보간법이 아닌가 싶습니다.

스플라인도 마찬가지로 주어진 데이터에 대한 다항식을 찾아내는 작업인데 

piecewise 방법으로 접근한다는 게 다릅니다. 

즉, 두점 사이의 다항식을 만들고 구한 각각을 함수가 연속되게 이어주는 작업을 하는 방법입니다.

다항식을 구하면서 동시에 다항식간 연속이 가능하도록 해야하기 때문에 수학적 지식이 조금 요구되지만 

원리를 알기만 하면 됩니다.

실제로 구하는것은 컴퓨터고 워낙 유명해서 스플라인보간법에 대한 라이브러리가 이미 잘 갖추어져 있기 때문에 

표준 라이브러리를 쓰면 됩니다. 

물론 라이브러리가 맘에 들지 않아 커스텀하게 바꿀려고 한다면 당연히 원리를 알고 그에 맞게 코딩을 다시 짜야 할겁니다.

 

가장 쉬운 접근법

가장 쉬운 접근법으로는 두 점 사이에서 직선의 방정식을 도출해 만들어진 각각의 다항식을 연속하게끔 연결하는 것입니다.

수학적으로 설명하면 다음과 같습니다.

주어진 데이터 (x_0,f_0),...,(x_n,f_n) 에 대해서,

데이터 $ (x_{i-1},f_{i-1}) $, (x_{i},f_i) $ 를 보간한다면 다음과 같은 직선을 구할 수 있습니다.

$$ p_{1,i}(x) = f_{i-1} + \left( \frac{f_i-f_{i-1}}{x_i-x_{i-1}} \right) (x-x_{i-1}) , \ \ i = 1,...n $$

 

이렇게 직선을 만들면 다항식끼리 연속하게 만들어야 합니다. 

만약 $ x= x_i $ 에서 $p_{1,i} $ , $p_{1,i+1} $ 을 연속하게 만든다면 $ p_{1,i}(x_i) = p_{1,i+1}(x_i) $ 가 되어야 합니다.

이런식으로 반복해서 만들어 linear spline $ S_1 $ 을 만들게 됩니다. ($ S_1 $ 은 제가 붙인 이름입니다.) 

 

하지만 이렇게 직선으로 만들게 된다면 각 데이터의 점에 도달할 때마다 꺽기는 모양이 나와서 비현실적이게 됩니다. 

이를 보완하기 위해 'smoothness' 를 부여해주어야 합니다.

 

Cubic spline

위의 문제를 해결하기 위한 방법 중 하나는 다항식의 차수를 높이는 시도입니다. 2차함수를 생각하더라도 직선의 꺽기를 보완하고 각 점에서 부드러운 함수를 만들 수 있습니다. 

그러면 차수를 어떻게 정해야할지 고민이 될 수 있습니다. 

먼저 가장 보편적인 방법을 쓰는게 무난합니다. 보통 3차 다항식을 만드는것을 주로 쓰기 때문에 이를 소개할까 합니다. 

스플라인을 하면 주로 쓰여서 Cubic spline이라고 따로 명명을 하고 있습니다.

정의는 다음과 같습니다.

 

정의

데이터 $ {\{(x_i,f_i)\}}_{i=0}^{n} $ 에 대하여, 다음을 만족하면 $ S_3 $ 은 $ [x_0,x_n] $ 에서 cubic spline 이다.

1.  $ S_3 $ 이 각 [x_{i-1},x_i] 에서 최대 3차방정식이다.
2. $ S_3 \in C^2[x_0,x_n] $이다.

여기서 $ C^2 $ 는 2번미분한 함수까지 연속인 함수들의 모임을 뜻합니다. 

$C^2 $ 가 와닿지 않으면 $ S_3 $ 이 2번까지 미분해도 연속이 유지되는 함수라고 받아들여도 무방합니다.

 

이 정의를 보면 다항식을 n 개 만들면 n개가 하나의 유기적인 연결을 해야하고 첫번째, 두번째 미분한 함수도 연속이어야 합니다.

즉, 수학적으로 본다면, 임의의 i에 대해, 다항식 $ s_{3,i}$ , $ s_{3,i+1} $ 은 세가지를 만족해야합니다.

1. $ s_{3,i}(x_i) = s_{3,i+1}(x_i) = f_i $
2. $ s'_{3,i}(x_i) = s'_{3,i+1}(x_i) $
3. $ s''_{3,i}(x_i) = s''_{3,i+1}(x_i) $

 

 

정의대로 한번 구해보도록 하겠습니다.

 

$ [x_{i-1}, x_i], \ \ i=1,...n $ 에서, cubic spline을 만족했으면 하는 다항식을 $ s_{3,i} $ 이라 하면,

$ s_{3,i}(x_{i_1}) = f_{i-1} $ 이어야 하고 최대 3차방정식이어야 하므로 다음과 같이 쓸 수 있습니다.

$$ s_{3,i}(x) = f_{i-1} + a_i(x-x_{i-1}) + b_i(x-x_{i-1})^2 + c_i(x-x_{i-1})^3 $$

 

이 식을 잘 보면 전체 데이터에 대해서 각각 다항식을 결정하는 계수를 구해야하는데 그 갯수가 3n개가 됩니다.

즉, $ a_1, b_1, c_1, ..., a_n, b_n, c_n $ 입니다. 

한 방정식으로 구하기에는 너무 많은 계수들이고 미분했을때에도 다항식마다 값이 맞아야 하니 행렬로 유도해 값을 구해야 할 것 같습니다.

 

일단 $s_{3,i}(x_{i}) = f_i $ 도 되도록 해야합니다. $ x_i $ 를 실제로 넣는다면 다음과 같이 되어야 합니다.

$ h_i = x_i - x_{i-1} $ 로 했을 때, 

$$ f_{i-1}  + a_ih_i + b_ih_i^2 + c_ih_i^3 = f_i, \ \ i = 1,...,n \tag{1} $$

위 식이 만족한다면, $ s_{3,i}(x_i) = s_{3,i+1}(x_i) = f_i $ 을 만족하게 됩니다. 

그러니 (1) 식은 어떤한 경우가 있더라도 만족해야 다음을 전개할 수 있습니다.

 

첫번째 미분함수도 연속해야하니, $ s'_{3,i}(x_i) = s'_{3,i+1}(x_i) $ 를 만족해야합니다.

미분함수를 쓰면 각각 아래와 같이 나옵니다.

$$ \begin{align} s'_{3,i}(x) & = a_i + 2b_i(x-x_{i-1}) + 3c_i(x-x_{i-1})^2, \\ s'_{3,i+1}(x) & = a_{i+1} +2b_{i+1}(x-x_i) + 3c_{i+1}(x-x_i)^2 \end{align} $$

주어진 조건을 만족한다면,

$ x = x_i $ 에서,

$$ a_i +2b_ih_i + 3c_ih_i^2 = a_{i+1}, \ \ i = 1,..., n-1 $$

이 됩니다.

 

두번째 미분함수도 연속이어야 합니다. 

먼저 두번 미분한 방정식을 써보면 다음과 같습니다.

$$ \begin{align} s''_{3,i}(x) & = 2b_i + 6c_i(x-x_{i-1}) \\ s''_{3,i+1}(x) & = 2b_{i+1} +6c_{i+1}(x-x_i) \end{align} $$

 

마찬가지로 $ x=x_i $ 에서, 

$$ b_i + 3c_ih_i = b_{i+1} , \ \ i= 1,...,n-1 \tag{2} $$

이 됩니다.

 

풀어낸 모든 식을 다 만족하는 계수들을 구해야하는데 현재 상태로 한다면 값이 구해지지 않습니다. 

식이 부족하기 때문이죠. 총 3n 의 미지수를 구하려면 3n의 식이 있어야하는데 첫번째 미분함수와 두번째 미분함수에서 n-1개씩 식을 나옵니다. 따라서, 2개의 식이 부족한 상황입니다.

 

그래서 초기값을 설정해 2개의 식을 만들어서 전개를 합니다.

다양한 방법이 있는 줄 알지만 가장 쉬운 접근인 natural cubic spline 을 적용하겠습니다. 즉, $ s''_{3,1}(x_0) = s''_{3,n}(x_n) = 0 $ 으로 설정을 하고 하겠습니다. 

설정된 것을 적용하면 다음을 알 수 있습니다.

$$ b_1 = 0, b_n +3c_nh_n = 0 \tag{3} $$

2개의 식을 더 만들어 총 3n 의 식이 되었으니 이제 3n 개의 갯수를 구할 수 있을 것 같습니다.

먼저 , 식 (1)을 $ a_i $ 에 대해, 식 (2)를 $ c_i $ 에 대해 , 식 (3)을 $ c_n $ 에 대해 정리하면 다음과 같습니다.

$$ \begin{align} a_1 & = \frac{f_i-f_{i-1}}{h_i} - b_ih_i - c_ih_i^2 , \ \ i = 1,...,n, \\ c_i & = \frac{b_{i+1}-b_i}{3h_i}, \ \ i = 1,...,n-1, \\ c_n & = - \frac{b_n}{3h_n} \end{align} $$

 

즉, 구한 식은 모두 $ b_i $ 에 대한 식으로 된 것을 알 수 있습니다.

그래서 $ b_i $ 로 재정리를 한다면 행렬로써 풀어낼 수 있게 됩니다. 중간과정은 생략하고 결과를 쓴다면 다음과 같습니다.

$$ H = \begin{bmatrix} 1 & & & &  \\  & 2(h_1+h_2) & h_2 & & & \\ & h_2 & 2(h_2+h_3) & h_3 & & \\ & & \ddots & & & \\ & & h_{n-2} & 2(h_{n-2}+h_{n-1}) & h_{n-1} \\ & & & h_{n-1} & 2(h_{n-1}+h_n) \end{bmatrix} $$

$$ g_1 = 0, g_i = 3( \nabla f_i/h_i - \nabla f_{i-1}/h_{i-1} ) , \ \ i= 2,...,n $$

$$ \mathbf{b} = [b_1,...,b_n]^{T} $$

인 Hb = g 을 얻습니다. 이 행렬을 푼다면 다항식 $ S_3 $ 을 구하게 됩니다.

 

다 쓰고 보니 긴 글이 되었네요. 

정리하면 cubic spline은 초기값을 설정했지만 정의해서 출발해 도출되었다는 것을 알 수 있습니다.

아무튼 스플라인 보간법을 구하기 위한 수학적 과정이었습니다.

 

관련 포스팅

[데이터 사이언스/머신러닝 딮러닝] - [기초] 보간법(Interpolation)

[수학] - [수치해석] Polynomial interpolation

[수학] - [수치해석] Divided difference interpolation

[수학] - [수치해석] Equispaced interpolation(등간격 보간)

 

참고문헌

Introduction to numberical analysis / alastair wood