Interpolation: Lagrange, Newton
실제 자료는 연속적인 현상을 대상으로 하더라도 모든 지점에서 관측되는 것은 아니다. 대개는 서로 떨어진 몇 개의 지점에서만 값이 주어지며, 그 사이의 값은 직접 알 수 없다.
수치해석에서는 이처럼 주어진 자료점을 모두 지나도록 적절한 함수를 구성하고, 이를 이용하여 자료 사이의 값을 추정하는 방법을 보간법(interpolation)이라고 한다. 보간법은 특히 관측값의 수는 많지 않지만 각 자료를 비교적 정확한 값으로 간주할 수 있는 경우에 유용하다.
서로 다른 $n+1$개의 자료점
\[(x_i,y_i), \qquad i=0,1,\dots,n\]이 주어졌다고 하자. 이때
\[p(x_i)=y_i, \qquad i=0,1,\dots,n\]을 만족하도록 함수 $p(x)$를 구성하는 방법이 보간법이다.
$p(x)$가 다항식이면 이를 보간다항식(interpolation polynomial)이라고 하며,
\[x_0,x_1,\dots,x_n\]을 마디점(node)이라고 한다.
보간법은 크게 다음 두 종류로 구분할 수 있다.
| 구분 | 기본 아이디어 |
|---|---|
| 전역 다항 보간 | 전체 자료점을 하나의 다항식으로 연결 |
| 스플라인 보간 | 각 구간마다 낮은 차수의 다항식을 연결 |
이 글에서는 먼저 전역 다항 보간의 대표적인 표현인 Lagrange 형태와 Newton 형태를 살펴보고, 이후 보간오차와 고차 다항 보간에서 나타나는 Runge 현상, 그리고 이를 완화하기 위한 Chebyshev 마디점을 다룬다.
1. 다항식과 함수의 근사
보간에서 다항식이 널리 사용되는 이유는 구조가 비교적 단순하기 때문이다. 다항식은 함수의 근사뿐 아니라 방정식의 해, 수치미분, 수치적분, 미분방정식 등 다양한 수치계산에서 이용된다.
그렇다면 연속함수를 다항식으로 충분히 잘 근사할 수 있을까?
이에 대한 이론적 근거를 제공하는 것이 Weierstrass 근사정리이다.
정리 1.1 Weierstrass 근사정리
함수
\[f:[a,b]\to\mathbb{R}\]가 연속이라고 하자. 그러면 임의의 $\varepsilon\gt 0$에 대하여 적당한 다항식 $p_n(x)$가 존재하여
\[\max_{x\in[a,b]} |f(x)-p_n(x)| \lt \varepsilon\]을 만족한다.
즉, 닫힌 구간에서 정의된 연속함수는 원하는 만큼 작은 오차를 갖도록 다항식으로 근사할 수 있다.
다만 Weierstrass 근사정리는 그러한 다항식이 존재한다는 사실만을 보장할 뿐, 실제로 어떤 다항식을 사용해야 하는지는 알려 주지 않는다.
연속함수를 실제 다항식으로 구성하는 대표적인 방법 가운데 하나가 Bernstein 다항식이다.
정의 1.1 Bernstein 다항식
연속함수
\[f:[0,1]\to\mathbb{R}\]에 대하여
\[B_n(f)(x) = \sum_{k=0}^{n} \binom{n}{k} f(\frac{k}{n}) x^k(1-x)^{n-k}\]를 함수 $f$의 $n$차 Bernstein 다항식이라고 한다.
Bernstein 다항식은 $n$이 증가함에 따라 연속함수 $f$에 균등수렴한다. 따라서 Weierstrass 근사정리가 보장하는 다항식의 존재를 구체적으로 보여 주는 하나의 예가 된다.
그러나 Bernstein 다항식을 구성하려면 함수 $f$의 값을 이미 알고 있어야 한다. 보간법에서 다루고자 하는 문제는 이와 조금 다르다.
보간에서는 함수 전체가 주어진 것이 아니라 유한한 개수의 자료점만 알고 있다고 가정한다. 따라서 우리가 해결해야 할 문제는 다음과 같다.
주어진 자료점을 정확하게 통과하는 다항식을 어떻게 구성할 수 있는가?
2. 보간다항식의 존재성과 유일성
서로 다른 $n+1$개의 마디점
\[x_0\lt x_1\lt \cdots\lt x_n\]에서 함수값
\[f(x_0),f(x_1),\dots,f(x_n)\]을 알고 있다고 하자.
찾고자 하는 것은
\[p_n(x_i)=f(x_i), \qquad i=0,1,\dots,n\]을 만족하는 $n$차 이하의 다항식이다.
먼저 이러한 다항식이 존재하는지, 그리고 존재한다면 유일한지를 확인한다.
정리 1.2 보간다항식의 존재성과 유일성
서로 다른 $n+1$개의 실수
\[x_0,x_1,\dots,x_n\]이 주어졌다고 하자.
그러면
\[p_n(x_i)=f(x_i), \qquad i=0,1,\dots,n\]을 만족하는 차수가 $n$ 이하인 다항식 $p_n(x)$는 유일하게 존재한다.
Proof
보간다항식을
\[p_n(x) = a_0+a_1x+a_2x^2+\cdots+a_nx^n\]이라 하자.
보간조건
\[p_n(x_i)=f(x_i), \qquad i=0,1,\dots,n\]을 적용하면
\[A\mathbf{a}=\mathbf{f}, \qquad A=(x_i^j)_{0\le i,j\le n}, \qquad \mathbf{a}=(a_0,a_1,\dots,a_n)^T, \qquad \mathbf{f}=(f(x_0),f(x_1),\dots,f(x_n))^T\]을 얻는다.
계수행렬 $A$는 Vandermonde 행렬이며 그 행렬식은
\[\det A=\prod_{0\le i\lt j\le n}(x_j-x_i)\]이다.
모든 마디점이 서로 다르므로
\[x_i\ne x_j \qquad (i\ne j)\]이고 따라서
\[\det A\ne0\]이다.
그러므로 $A$는 가역행렬이며 연립방정식의 해
\[a_0,a_1,\dots,a_n\]은 유일하게 결정된다.
따라서 주어진 $n+1$개의 자료점을 지나는 $n$차 이하의 보간다항식 $p_n(x)$는 유일하게 존재한다.
여기서 중요한 점은 보간다항식의 차수가 반드시 정확히 $n$일 필요는 없다는 것이다. 자료의 형태에 따라 최고차항의 계수가 $0$이 될 수 있으므로 정확하게는 $n$차 이하의 다항식이 유일하게 존재한다고 표현한다.
3. Lagrange 형태의 보간다항식
앞의 정리는 보간다항식의 존재성과 유일성을 보여 준다.
하지만 실제 계산을 위해 Vandermonde 행렬을 직접 풀어 다항식의 계수를 구하는 방법은 효율적이지 않을 수 있다. 이를 피할 수 있는 대표적인 방법이 Lagrange 형태이다.
정의 1.2 Lagrange 기저다항식
서로 다른 마디점
\[x_0,x_1,\dots,x_n\]에 대하여
\[L_k(x) = \prod_{\substack{j=0\\j\ne k}}^n \frac{x-x_j}{x_k-x_j}, \qquad k=0,1,\dots,n\]을 Lagrange 기저다항식이라고 한다.
Lagrange 기저다항식은
\[L_k(x_i)=1 \text{ if } i=k, \qquad L_k(x_i)=0 \text{ if } i\ne k\]를 만족한다.
즉, $L_k(x)$는 $x_k$에서는 $1$이 되고 나머지 모든 마디점에서는 $0$이 된다.
따라서 임의의 마디점 $x_i$에서
\[p_n(x_i) = \sum_{k=0}^{n} f(x_k)L_k(x_i) = f(x_i)\]가 된다.
그러므로 보간다항식은
\[\boxed{ p_n(x) = \sum_{k=0}^{n} f(x_k)L_k(x) }\]로 나타낼 수 있다.
Lagrange 형태의 장점은 다항식의 일반적인 계수
\[a_0,a_1,\dots,a_n\]을 구하기 위해 연립방정식을 직접 풀 필요가 없다는 데 있다.
다항식 공간
\[\mathcal{P}_n=\{a_0+a_1x+\cdots+a_nx^n \mid a_i\in\mathbb{R}\}\]에서는 일반적으로
\[1,x,x^2,\dots,x^n\]을 기저로 사용한다.
그러나 보간 문제에서는
\[L_0(x),L_1(x),\dots,L_n(x)\]을 기저로 사용하면 각 마디점의 함수값을 보간다항식에 직접 반영할 수 있다.
4. Newton 형태와 분할차분
Lagrange 형태는 보간다항식을 직접 구성할 수 있다는 장점이 있다.
그러나 새로운 자료점이 하나 추가되면 기존의 Lagrange 기저다항식도 함께 변경되어야 한다.
동일한 $n+1$개의 자료점을 보간하는 $n$차 이하의 다항식은 유일하게 존재하므로 Lagrange 형태와 Newton 형태는 동일한 보간다항식을 서로 다른 방식으로 표현한 것이다.
Lagrange 형태는 각 자료점의 기여를 직접 확인하기 쉽고, Newton 형태는 분할차분(divided difference)을 이용하여 계수를 순차적으로 계산할 수 있다는 장점이 있다.
Newton 형태는
\[p_n(x) = a_0 +a_1(x-x_0) +a_2(x-x_0)(x-x_1) +\cdots +a_n \prod_{j=0}^{n-1}(x-x_j)\]와 같이 나타낼 수 있다.
이를 한 단계 전의 다항식과 비교하면
\[p_n(x) = p_{n-1}(x) + a_n \prod_{j=0}^{n-1}(x-x_j)\]이다.
따라서 새로운 마디점이 추가되면 기존 다항식에 새로운 항 하나를 추가하는 방식으로 확장할 수 있다.
Newton 형태의 핵심은 계수
\[a_0,a_1,\dots,a_n\]을 계산하는 데 있으며, 이를 위해 분할차분을 사용한다.
정의 1.3 분할차분
함수 $f$와 서로 다른 마디점들이 주어졌다고 하자.
0차 분할차분은
\[f[x_i] = f(x_i)\]로 정의한다.
그보다 높은 차수의 분할차분은 재귀적으로
\[f[x_i,\dots,x_{i+k}] = \frac{ f[x_{i+1},\dots,x_{i+k}] - f[x_i,\dots,x_{i+k-1}] }{ x_{i+k}-x_i }\]로 정의한다.
특히 1차 분할차분은
\[f[x_i,x_{i+1}] = \frac{f(x_{i+1})-f(x_i)} {x_{i+1}-x_i}\]이므로 두 자료점 사이의 평균변화율에 해당한다.
고차 분할차분은 이전 단계에서 얻은 변화율의 차이를 다시 계산하는 방식으로 정의된다.
정리 1.3 Newton 보간다항식
서로 다른 마디점
\[x_0,x_1,\dots,x_n\]에 대한 보간다항식은
$p_n(x)=a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+\cdots+a_n(x-x_0)(x-x_1)\cdots(x-x_{n-1})$ 로 나타낼 수 있다.
즉 Newton 형태의 계수는
\[\boxed{ a_k = f[x_0,x_1,\dots,x_k] }\]이다.
Proof
Newton 형태를
\[p_n(x) = a_0+a_1(x-x_0)+\cdots +a_n\prod_{j=0}^{n-1}(x-x_j)\]이라 하자.
먼저 $x=x_0$을 대입하면
\[p_n(x_0)=a_0=f(x_0)\]이므로
\[a_0=f[x_0]\]이다.
다음으로 $x=x_1$을 대입하면
\[f(x_1) = a_0+a_1(x_1-x_0)\]이므로
\[a_1 = \frac{f(x_1)-f(x_0)} {x_1-x_0} = f[x_0,x_1]\]이다.
같은 과정을 $x_2,x_3,\dots$에 순차적으로 적용하면 각 단계에서 새롭게 결정되는 계수는 해당 마디점들에 대한 분할차분과 일치한다.
따라서
\[a_k = f[x_0,x_1,\dots,x_k]\]가 성립한다.
5. 분할차분과 도함수
분할차분은 Newton 보간다항식의 계수를 계산하는 데 사용되며 함수의 도함수와도 직접 연결된다.
이 관계는 이후 보간오차를 구하는 데 중요한 역할을 한다.
정리 1.4 분할차분과 도함수
함수
\[f\in C^n[a,b]\]이고
\[x_0\lt x_1\lt \cdots\lt x_n\]이 $[a,b]$ 안의 서로 다른 점이라고 하자.
그러면 어떤
\[\xi\in(x_0,x_n)\]가 존재하여
\[\boxed{ f[x_0,x_1,\dots,x_n] = \frac{f^{(n)}(\xi)}{n!} }\]가 성립한다.
Proof
$x_0,x_1,\dots,x_n$에서 함수 $f$를 보간하는 다항식을 $p_n(x)$라 하고
\[e_n(x) = f(x)-p_n(x)\]라 하자.
보간조건에 의해
\[e_n(x_i)=0, \qquad i=0,1,\dots,n\]이므로 $e_n(x)$는 서로 다른 $n+1$개의 영점을 갖는다.
Rolle의 정리를 반복하여 적용하면
\[e_n(x)=0 \quad\text{은 }n+1\text{개의 영점},\] \[e_n'(x)=0 \quad\text{은 적어도 }n\text{개의 영점},\] \[\vdots\] \[e_n^{(n-1)}(x)=0 \quad\text{은 적어도 }2\text{개의 영점},\] \[e_n^{(n)}(x)=0 \quad\text{은 적어도 }1\text{개의 영점}\]을 갖는다.
따라서 어떤
\[\xi\in(x_0,x_n)\]가 존재하여
\[e_n^{(n)}(\xi)=0\]이고,
\[f^{(n)}(\xi) = p_n^{(n)}(\xi)\]가 된다.
한편 Newton 형태에서 $p_n(x)$의 최고차항은
\[f[x_0,x_1,\dots,x_n]x^n\]과 같은 최고차계수를 갖는다.
$n$차 다항식의 최고차항 $ax^n$을 $n$번 미분하면
\[\frac{d^n}{dx^n}(ax^n) = n!a\]이므로
\[p_n^{(n)}(x) = n!f[x_0,x_1,\dots,x_n]\]이다.
따라서
\[f^{(n)}(\xi) = n!f[x_0,x_1,\dots,x_n]\]이고,
\[f[x_0,x_1,\dots,x_n] = \frac{f^{(n)}(\xi)}{n!}\]를 얻는다.
6. 보간다항식의 오차
Lagrange 형태와 Newton 형태는 동일한 보간다항식의 서로 다른 표현이다.
따라서 보간오차 역시 두 표현에서 동일하다.
보간오차를
\[e_n(x) = f(x)-p_n(x)\]라고 정의하자.
기존 마디점
\[x_0,x_1,\dots,x_n\]에 새로운 점 $x$를 하나 추가한다고 생각한다.
$n+2$개의 점을 보간하는 Newton 다항식은
\[p_{n+1}(t) = p_n(t) + f[x_0,\dots,x_n,x] \prod_{i=0}^{n} (t-x_i)\]로 나타낼 수 있다.
여기에 $t=x$를 대입하면
\[p_{n+1}(x)=f(x)\]이므로
\[f(x)-p_n(x) = f[x_0,\dots,x_n,x] \prod_{i=0}^{n}(x-x_i)\]를 얻는다.
분할차분과 도함수의 관계를 적용하면 다음의 보간오차 공식을 얻을 수 있다.
정리 1.5 보간다항식의 오차
함수
\[f\in C^{n+1}[a,b]\]이고 $p_n(x)$가 서로 다른 마디점
\[x_0,x_1,\dots,x_n\]에서 함수 $f$를 보간하는 $n$차 이하의 다항식이라고 하자.
그러면 임의의
\[x\in[a,b]\]에 대하여 어떤
\[\xi\in(a,b)\]가 존재하여
\[\boxed{ f(x)-p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^{n}(x-x_i) }\]가 성립한다.
Proof
앞에서
\[f(x)-p_n(x) = f[x_0,\dots,x_n,x] \prod_{i=0}^{n}(x-x_i)\]를 얻었다.
분할차분과 도함수의 관계에 의해 어떤 $\xi$가 존재하여
\[f[x_0,\dots,x_n,x] = \frac{f^{(n+1)}(\xi)}{(n+1)!}\]가 성립하므로
\[f(x)-p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^{n}(x-x_i)\]를 얻는다.
이 식에서 보간오차는 크게 두 요소의 영향을 받는다.
첫째는 함수 자체의 특성을 나타내는
\[f^{(n+1)}(\xi)\]이고, 둘째는 마디점의 배치에 의해 결정되는
\[\omega_{n+1}(x) = \prod_{i=0}^{n}(x-x_i)\]이다.
즉,
\[\boxed{ \text{보간오차} = \text{함수의 고차 도함수} \times \text{마디점 배치의 영향} }\]으로 볼 수 있다.
따라서 단순히 다항식의 차수를 높인다고 해서 보간오차가 반드시 작아지는 것은 아니다.
6.1 1차 보간다항식의 오차
두 마디점 $x_0,x_1$을 이용한 1차 보간의 오차는
\[e_1(x) = \frac{f''(\xi)}{2!} (x-x_0)(x-x_1)\]이다.
만약 구간에서
\[|f''(x)|\le M\]이라면
\[|e_1(x)| \le \frac{M}{2} |(x-x_0)(x-x_1)|\]이다.
$x\in[x_0,x_1]$에서
\[|(x-x_0)(x-x_1)|\]은
\[x=\frac{x_0+x_1}{2}\]에서 최대가 되며,
\[\max_{x\in[x_0,x_1]} |(x-x_0)(x-x_1)| = \frac{(x_1-x_0)^2}{4}\]이다.
따라서
\[\boxed{ \|e_1\|_\infty \le \frac{M}{8} (x_1-x_0)^2 }\]를 얻는다.
6.2 균등격자에서의 보간오차
마디점이
\[x_i=x_0+ih\]와 같이 균등하게 배치되었다고 하자.
이때
\[\omega_{n+1}(x) = \prod_{i=0}^{n}(x-x_i)\]에 대하여
\[\|\omega_{n+1}\|_\infty \le \frac{n!}{4}h^{n+1}\]의 상계를 얻을 수 있다.
따라서 보간오차 정리에 의해
\[\boxed{ \|f-p_n\|_\infty \le \frac{1}{4(n+1)} \|f^{(n+1)}\|_\infty h^{n+1} }\]이다.
이 식만 보면 $h$가 작아질수록 오차가 빠르게 감소할 것처럼 보인다.
그러나 $n$이 증가하면 동시에
\[\|f^{(n+1)}\|_\infty\]도 달라진다는 점에 주의해야 한다.
따라서
\[\text{높은 차수} \quad\Longrightarrow\quad \text{더 작은 보간오차}\]가 일반적으로 성립하는 것은 아니다.
7. 고차 다항 보간과 Runge–Méray 현상
앞의 오차공식만 보면 더 많은 마디점을 사용하여 높은 차수의 보간다항식을 만들수록 원래 함수에 더욱 가까워질 것이라고 예상하기 쉽다.
즉,
\[\|f-p_n\|_\infty \to0 \qquad (n\to\infty)\]을 기대할 수 있다.
그러나 균등하게 배치된 마디점을 이용하여 하나의 고차 보간다항식을 구성하면 구간의 양 끝부분에서 다항식이 크게 진동하고 보간오차가 오히려 증가하는 경우가 있다.
이러한 현상을 Runge 현상(Runge phenomenon) 또는 Runge–Méray 현상이라고 한다.
Runge 현상은 보간오차식
\[f(x)-p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^{n}(x-x_i)\]을 통해 이해할 수 있다.
오차는 크게
\[\frac{f^{(n+1)}(\xi)}{(n+1)!}\] \[\prod_{i=0}^{n}(x-x_i)\]의 영향을 받는다.
먼저 차수 $n$이 증가하면 더 높은 차수의 도함수
\[f^{(n+1)}\]가 등장한다.
함수에 따라 고차 도함수의 크기는 빠르게 증가할 수 있으므로 분모에 $(n+1)!$이 존재한다는 사실만으로 이 항이 반드시 작아진다고 할 수 없다.
또한 마디점의 배치도 중요하다.
균등한 마디점을 이용하여 하나의 고차 다항식을 구성하면 구간의 끝부분에서 Lagrange 기저다항식의 크기가 크게 증가할 수 있다. 따라서 각 자료점에서 발생한 작은 변화가 끝점 부근에서는 크게 증폭될 수 있다.
결국 Runge 현상은 다음 두 요인이 함께 작용하여 나타나는 현상으로 볼 수 있다.
- 고차 도함수의 영향
- 균등 마디점에서의 불리한 다항식 거동
즉, 보간의 정확도를 높이기 위해서는 자료점의 수뿐 아니라 마디점의 배치 역시 고려해야 한다.
8. Chebyshev 다항식과 Chebyshev 마디점
Runge 현상을 완화하는 대표적인 방법은 마디점을 균등하게 배치하지 않는 것이다.
특히 구간의 끝부분에 더 많은 마디점을 배치하면 고차 다항식이 끝점 부근에서 크게 진동하는 현상을 줄일 수 있다.
이러한 목적에 적합한 대표적인 선택이 Chebyshev 다항식의 근이다.
정의 1.4 Chebyshev 다항식
구간 $[-1,1]$에서
\[\boxed{ T_n(x) = \cos(n\arccos x) }\]로 정의되는 다항식을 $n$차 Chebyshev 다항식이라고 한다.
$x=\cos\theta$라고 두면
\[T_n(\cos\theta) = \cos(n\theta)\]가 된다.
또한 Chebyshev 다항식은 다음 점화식을 만족한다.
\[\boxed{ T_{n+1}(x) = 2xT_n(x)-T_{n-1}(x) }\]보간에서 $n+1$개의 마디점을 사용할 경우에는 $T_{n+1}(x)$의 근을 이용할 수 있다.
정의 1.5 Chebyshev 마디점
구간 $[-1,1]$에서
\[\boxed{ x_j = \cos( \frac{(2j+1)\pi}{2(n+1)} ), \qquad j=0,1,\dots,n }\]을 Chebyshev 마디점이라고 한다.
Chebyshev 마디점은 균등하게 배치되지 않는다.
구간의 중앙에서는 상대적으로 간격이 넓고,
\[-1,\qquad1\]에 가까워질수록 마디점이 조밀하게 배치된다.
일반적인 구간 $[a,b]$에서는 $[-1,1]$의 Chebyshev 마디점을 선형변환하여
\[\boxed{ x_j = \frac{a+b}{2} + \frac{b-a}{2} \cos( \frac{(2j+1)\pi}{2(n+1)} ) }\]와 같이 사용할 수 있다.
Chebyshev 마디점을 사용하는 중요한 이유는 보간오차에서 마디점의 배치에 의해 결정되는
\[\omega_{n+1}(x) = \prod_{i=0}^{n}(x-x_i)\]의 최대 크기를 줄일 수 있기 때문이다.
균등 마디점과 Chebyshev 마디점의 차이는 다음과 같이 정리할 수 있다.
| 구분 | 균등 마디점 | Chebyshev 마디점 |
|---|---|---|
| 배치 | 일정한 간격 | 끝점 부근에 조밀 |
| 고차 보간 | 끝점 진동이 커질 수 있음 | 끝점 진동을 상당 부분 완화 |
| Runge 현상 | 발생하기 쉬움 | 완화 가능 |
| 핵심 | 계산과 배치가 단순 | $|\omega_{n+1}|_\infty$를 줄이는 데 유리 |
Chebyshev 마디점을 이용하면 고차 다항 보간에서 발생하는 Runge 현상을 상당 부분 완화할 수 있다.
그러나 자료점의 수가 많아질수록 하나의 전역 다항식의 차수 역시 증가한다. 또한 특정 구간에서의 변화가 전체 다항식에 영향을 줄 수 있다는 전역 다항 보간의 특성도 그대로 남는다.
따라서 많은 자료점을 안정적으로 보간해야 하는 경우에는 하나의 고차 다항식을 사용하는 대신, 각 구간마다 낮은 차수의 다항식을 연결하는 스플라인 보간(spline interpolation)을 고려할 수 있다.
가 매우 중요하다.