수치해석(14) Splines and Piecewise Interpolation

 

 

1. Splines

 

주어진 데이터 포인트들을 통해 부드러운 곡선을 생성하는 방법이다. 함수나 곡선의 근사치를 구하거나, 주어진 데이터를 부드럽게 연결하는 데 사용된다. 보통 여러 개의 다항식 조각들로 이루어져 있으며, 각 조각은 인접한 데이터 포인트들을 연결하고 부드럽게 이어져야 한다. 

n개의 점 사이를 interpolation(보간)하기 위해 단일 (n-1)차 다항식을 사용하는 대안적인 접근법은 데이터 포인트의 부분 집합에 부분적인 방식으로 하위 다항식을 적용하는 것이다. 이러한 연결 다항식을 spline functi-on(스플라인 함수)라고 한다. 스플라인은 저차 특성으로 인해 진동을 최소화하고, roundoff error를 줄인다. 

스플라인은 모든 점이 아닌, 간격마다 존재하는 점의 하위 집합을 사용하여 진동을 제거한다. data들 사이 jump가 있을 때 특히 유용하다. 아래 그림에서 (a) 3차 다항식(cubic splines), (b) 5차 다항식, (c) 7차 다항식, (d) Linear spline이다. a, b, c는 f(x)가 1개인 반면 d는 f(x)가 7개다. 이 말은 비선형 함수는 (점 개수 - 1)차 다항식으로 모든 점을 한 번에 나타내는 곡선을 만든다는 의미다. 

 

 

(1) Spline Development

 

 

Spline function si(x)의 계수는 데이터 집합의 각 간격에 의해 계산된다. 각 스플라인 함수에 사용되는 data point fi의 수는 스플라인 함수의 차수에 따라 다르다. 또한 스플라인 함수들이 만나는 지점을 knot라 한다. 

 

 

[1] 1차 스플라인은 각 점 쌍 사이에서 직선 방정식을 찾는다. 포인트의 값만 일치시키면 된다. [2] 2차 스플라인은 각 점 쌍 사이에서 2차 방정식을 찾는다. 포인트의 값, 해당 포인트에서 1차 도함수의 값을 일치시켜야 한다. [3] 3차 스플라인은 각 점 쌍 사이에서 3차 방정식을 찾는다. 포인트의 값, 해당 포인트에서 1차 도함수의 값, 2차 도함수의 값을 일치시켜야 한다. 

참고로 Cubic spline(큐빅 스플라인)의 결과는 Interpolating cubic(큐빅 보간) 결과와 다르다. 

 

(2) Linear Spline

n개의 data point에 대해 (n-1) 개의 구간이 있다. 각 구간 i에는 고유의 스플라인 함수인 si(x)가 있다. 선형 스플라인의 경우, 각 함수는 구간의 각 끝에 있는 두 점을 연결하는 직선에 불과하다. 

 

 

(3) Quadratic Spline

2차 스플라인은 knots(매듭)에서 연속적인 1차 도함수를 갖는다. 각 구간에 대한 다항식은 일반적으로 다음과 같이 나타난다. n개의 data point에 대해 (n-1) 개의 구간이 존재하며, 결과적으로 알 수 없는 상수가 3(n-1)개 나온다. 미지수를 평가하기 위해서는 3(n-1)개의 방정식이 필요하다. 

 

 

[1] continuity condition(연속성 조건)에 의해 함수는 모든 점을 통과해야 한다. (xi, fi)라는 점도 당연히 통과한다. 따라서 ai를 fi로 변경할 수 있으며, 평가할 조건이 2(n-1)개로 감소한다.  

 

 

[2] knot에서 인접한 다항식의 함수 값은 같아야 한다. i번째 구간의 폭을 아래와 같이 정의한 후, 식을 단순화할 수 있다. 이 방식은 knot가 (n-1)개 이므로 총 (n-1)개의 노드에 대해 쓸 수 있다. 따라서 앞으로 평가를 위해선 (n-1)개의 방정식만 남게 된다. 

 

i번째 구간의 폭을 재정의

단순화된 식

 

[3] knot에서 인접한 함수들의 첫번째 도함수 역시 같아야 한다. bi와 bi+1이 사용되므로 i = 1, ..., n-2까지 가능하다. 즉 (n-2)개의 조건을 충족하며, 이제 1개의 조건만 남게 된다. 

 

 

[4] 두 번째 도함수가 첫 번째 점에서 0이라고 가정한다. 이렇게 하면, s1이 1차 함수가 된다. 

 

 

Quadractic Spline의 예제를 알아보자. 18.2를 꼭 풀자. 

 

(4) Cubic Splines

일반적으로, cubic spline을 위한 i번째 spline function은 아래와 같이 쓰인다. n개의 데이터 포인트에 대해 (n-1)개의 구간이 있으므로, 모든 스플라인 함수 계수를 구하기 위해 4(n-1)개의 미지수를 평가해야 한다. 

 

 

연속성 조건이 충족되어야 하며, 1차 도함수와 2차 도함수는 내부 지점에서 연속적이어야 한다. 그래야 매끄러운 결과가 나온다. 

[1] 구간의 첫 번째 지점과 마지막 지점을 거치며 다음과 같은 2(n-1)개의 방정식을 생성한다. 

 

 

[2] knot에서 인접한 함수들의 1차 도함수 값이 같아야 하며, (n-2)개의 방정식을 생성한다. 

 

 

[3] knot에서 인접한 함수들의 2차 도함수 값이 같아야 하며, (n-2)개의 방정식을 생성한다. 

 

 

[4] 이들은 총 (4n-6)개의 방정식을 제공하고, 이 중 (4n-4)개가 필요하다. [3]에서 도출한 식을 [1], [2]에 각각 대입하여 아래와 같은 최종 식을 얻는다. 

 

 

[4]의 공식은 내부 knots, i = 2, 3, ..., n-2에 대해 작성될 수 있다. 이로 인해 (n-1)개의 미지수 c들을 갖는 (n-3)개의 삼각형 방정식이 생성된다. 따라서 추가적으로 2개의 조건이 있으면 c의 문제가 해결된다. natural spline method를 적용하여, 양끝 knot의 2차 도함수가 0이라고 가정하면 해결된다. 

 

 

이를 matrix form으로 나타내면 아래와 같다. 

 

 

(5) Piecewise interpolation in MATLAB

[1] MATLAB에는 piecewise interpolation(조각별 보간)을 구현하기 위한 몇가지 기능이 내장되어 있다. spline 함수는 cubic spline interpolation을 수행한다. 

 

yy = spline(x, y, xx)

#% x : 보간할 값을 포함하는 벡터
#% y : 보간할 값을 포함하는 벡터
#% yy : 벡터 xx의 점에서 평가된 스플라인 보간의 결과를 포함하는 벡터

 

예제를 풀어보자. MATLAB을 사용하여 [-1, 1] 구간에서 아래 함수에 샘플링한 9개의 동일 간격의 데이터 점을 적합시킨다. 

 

 

x = linspace(-1, 1, 9);
y = 1./(1+25*x.^2);
xx = linspace(-1, 1);
yy = spline(x, y, xx);

yr = 1./(1+25*xx.^2);
plot(x, y, 'o', xx, yy, xx, yr, '--')

 

[2] MATLAB의 또다른 함수로는 interp1 함수가 있다. 이는 다양한 유형의 piecewise one-dimensional interpolation을 구현한다. 

 

yi = interp1(x, y, xi, 'method')

#% method : 'nearest', 'linear' (default), 'spline', 'pchip'

 

(6) Multi-dimensional Interpolation

[1] Bilinear interpolation이란 두 변수 z = f(xi, yi)의 함수에 대한 중간 값을 결정한다. 다음 4가지 지점에서 value를 결정한다. 

 

 

매트랩 코드 예제는 아래와 같다. 

 

x = [2 9];
y = [1 6];
z = [60 57.5;55 70];
interp2(x,y,z,5.25,4.8)