0. Interpolation

Interpolation(보간법)은 주어진 함숫값 $(x_i, y_i)$을 지나는 함수를 구하는 과정을 의미한다. 일부 수치해석 책에서는 다항식만을 의미하기도 하지만 fast fourier transformation을 tridiagonometric interpolation이라고도 하기 때문에 굳이 다항식으로 한정하지 않겠다.

통계를 전공한 사람은 regression과 interpolation을 헷갈려 할 수 있지만 수학에서는 regression을 approximation theory라는 분야로 따로 다룬다. 가장 결정적인 차이는 regression은 주어진 함수값의 수와 polynomial의 차수가 관계가 없이 사용자가 각각 선택할 수 있지만 interpolation은 정확히 1만큼의 차이가 난다. 즉, 함수값이 정해지면 polynomial이 구성된다.

1. Conventional Interpolation

우선 $(x_i, y_i),i=0,1,2$를 지나는 $p_2(x)$를 생각해보자. $p_2(x)=ax^2+bx+c$라고 둔다면 고등학교때의 지식을 단순히 이용하면 다음과 같이 구할 수 있다.

(1.1)식을 행렬식으로 바꿔주면 다음과 같다.

(1.2)식을 풀어 $a,b,c$를 각각 계산하면 $p_2(x)$를 구성할 수 있다. 하지만 $n$차 interpolation을 구성하는데 $(n+1)\times (n+1)$ 행렬 식을 계산해야 하는 것은 computational cost 측면에서 매우 부담스럽다.

2. Lagrange Interpolation

$n$차 Lagrange interpolation은 (1.2)와 같은 행렬식을 계산하는 과정을 생략한채 다음과 같이 구성된다.

$p_n(x) = \sum_{i=0}^n l_i(x) y_i\cdots(2.1)$

여기서 $l\_i(x)$는 다음과 같다.

$l_i(x) = \pi_{0\leq j \leq n, j\neq i} \frac{(x_j-x)}{x_j-x_i}(2.2)\cdots(2.2)$

(2.2)식을 자세히 보자. $x=x_i$일때는 분모는 분자와 같게되어 $l_i(x_i)=1$이 된다. $x\neq x_i$인 경우에는 분자가 0이 되며 $l_i(x)=0$이 된다. 매우 smart한 방법이지 않나? 그렇다 Lagrange 선생님은 매우 똑똑하신 분이다.

Note 1. $l_i(x)$는 $n$차 polynomial이다.

Note 1은 당연한 이야기 같지만 꽤나 심오한 수학적 이론을 바탕으로 한다.  $l_i(x)$가 $n$차 polynomial이기 때문에 $p_n$도 $n$차 polynomial이 된다. 다시 말해서 $n+1$개의 함수값에 대해 $n$차의 polynomial이 나온다는 이야기가 된다.

Note 2. $p_n(x)$는 미분 가능하다.

당연히 polynomial이니깐 미분이 무한번 가능한 것은 쉽게 이해할 수 있을 것이다. Note 2는 수치 해석에서 매우 강력한 특징인데 Lagrange Interpolation을 이용하면 FDM에서 편미분을 근사하는 finite difference를 설명할 수 있다.

Note 3. Lagrange interpolation을 이용하면 (1.2)식에서처럼 계수를 메모리상에 저장할 필요가 없다.

이것은 실제 수치 simulation 코드를 작성하다보면 생각보다 강력한 역할을 한다. Note 3을 이해하고 싶다면 (1.2)식과 (2.1)식에 대한 코드를 각각 작성해보면 된다. 단순히 메모리를 아끼는 것은 ~메모리가 X값인 현재에는~ 생각보다 의미가 없다. (1.2)은 한 번 계수들을 다 구해놓으면 다음 번에는 간단히 대입만 하면 되기 때문에 특정한 case에 대해 computational cost를 절약할 수 있다. Note 3은 수치 해석 전공자가 아니면 이해할 필요가 없기 때문에 굳이 이해하지 않아도 된다.

Note 4. $n$차 Lagrange interpolation은 truncation error로 $\mathcal{O}(\Delta x^{n+1})$을 갖는다.

이것도 수치 해석 전공자가 아니면 넘어가자. 이것을 증명하려면 Newton divided difference를 알아야하고 mean value theorem이 필요하다. 그리고 결정적으로 증명이 매우 쉬우면서 길다.

3. Runge Phenomenon

Runge는 공학 계열을 공부해본 사람이라면 Runge-Kutta method란 상미분 방정식에 대한 numerical approximation으로 한 번쯤은 들어봤을 것이다. Runge 선생님도 매우 훌륭한 분이다. 여튼 우선 그림을 보고가자.

그림1. Runge Phenomenon

그림 1은 Runge phenomenon(혹은 oscillation)을 나타내는 그림이다. 통계학에서 overfiting과 비슷하게 무조건 함수값을 많이 넣어서 고차의 polynomial interpolation을 구성하는 것은 매우 큰 문제를 야기한다. 위의 그림은 $f(x) = \frac{1}{1+25x^2}$에 대해 $N+1$차의 polynomial을 구성한 그림이다. $N$이 10만 되어도 -1과 1에서 큰 오차를 보이며 $N$이 커질수록 가장자리에서 매우 큰 오차를 만들어낸다. 따라서 interpolation을 구성할 때에는 너무 높은 차수는 큰 문제점을 가지며 내 경험에는 4차 이상인 경우에는 많이 위험하다. 

사실 책에는 Runge phenomenon이라는 용어를 사용하지만 연구실에서는 oscillation이라는 용어를 주로 사용했다. 여튼 Runge phenomenon을 해결하는 대표적인 방법은 다음과 같다.

• WENO(Weight Especially Non-oscillation)을 사용한다.
• 저차의 local interpolation을 여러 개 사용한다.
• filter를 사용한다.
• CGL(Chebyshev-Gauss-Lobatto) point를 사용한다.

WENO는 nonlinear weight인 smoothness indicator를 주어서 oscillation을 줄인 interpolation 방식으로 Shu 선생님이 개발하셨고 덕분에 석사 학위 졸업도 했다. local interpolation을 사용하는게 현업에서 자주 사용되는 방법이다. filter는 자연과학이나 컴퓨터 계열에서 수치 simulation 관련 논문에서 많이 사용되는데 사실 수치 해석 전공자는 그렇게 선호하는 방법은 아니다. 마지막으로 CGL point를 사용하는 것은 Runge phenomenon를 조금 줄여줄 뿐이다. CGL point는 가장자리의 point를 많이 사용하고 중심부의 point를 적게 사용하는데 수치 simulation보다는 approximation theory에서 많이 사용하는 방식이다.

4. Other topics about Interpolation

사실 Lagrange interpolation이 매우 smart해보이지만 conventional interpolation이나 newton divided difference를 활용한 interpolation도 많이 사용된다. 그렇기 때문에 무조건 이것을 쓰라고 하는 것은 매우 위험하며 정확이 어떻게 사용되는지에 대해서 interpolation technique를 선택해야한다.

Interpolation과 approximation theory는 정말 한끗차이기 때문에 하나를 명확히 이해하고 싶다면 두 분야 모두 공부하는 것도 좋은 선택이다.

5. Reference

[1] https://math.boisestate.edu/~calhoun/teaching/matlab-tutorials/lab_11/html/lab_11.html