뉴턴 보간

1. 개요

뉴턴 보간 Newton interpolation
형태	$p(x)=\sum_k f[x_0,\dots,x_k]\prod_{i<k}(x-x_i)$
계수 계산	분할차분표 $O(n^2)$, 평가는 중첩 곱셈 $O(n)$
장점	절점을 추가해도 기존 계수 유지, 중복 절점(에르미트)까지 같은 틀
약점	절점 순서에 따라 안정성이 갈린다 → 레야 순서
쓰임	ENO 재구성, 다단계법 유도, 외삽, 오차식의 이론적 도구

같은 다항식을 쓰는 다른 방식. 그런데 「점 하나 더」가 공짜인 방식이다.

뉴턴 보간(Newton interpolation)은 서로 다른(또는 중복이 허락된) 절점 $x_0, \dots, x_n$ 에서 $f$ 와 일치하는 $n$ 차 이하 다항식을 뉴턴 기저¹ $1,\ (x - x_0),\ (x - x_0)(x - x_1),\ \dots$ 로 쓴 형태

$$p_n(x) = f[x_0] + f[x_0, x_1](x - x_0) + \cdots + f[x_0, \dots, x_n]\prod_{i=0}^{n-1}(x - x_i)$$

다. 계수 $f[x_0, \dots, x_k]$ 는 분할차분(divided difference)이다. 보간과 근사가 라그랑주형과 뉴턴형이 같은 다항식이라는 것, 그리고 반데르몽드 행렬이 단항식 기저의 조건수 문제를 다뤘다. 이 문서는 뉴턴형에만 있는 것 — 분할차분의 성질, 중복 절점(에르미트 보간), 오차식, 그리고 절점 순서가 안정성을 결정한다는 실전 함정 — 을 다룬다.

뉴턴 기저에서 보간 조건을 세우면 계수 행렬이 하삼각이 된다($k$ 번째 기저함수는 $x_0, \dots, x_{k-1}$ 에서 0). 단항식 기저의 꽉 찬 반데르몽드 행렬과 달리 전진대입 한 번으로 풀리고, 그 전진대입을 정리한 것이 분할차분표다.

2. 분할차분

재귀로 정의한다.

$$f[x_i] = f(x_i), \qquad 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}$$

표로 쓰면 첫 열이 함숫값, 다음 열이 이웃 차분을 간격으로 나눈 값이고, 표의 위쪽 대각선이 뉴턴 계수다. 열을 덮어쓰면 메모리 $O(n)$ 으로 계수를 얻는다.

c = f(x)                      # 길이 n+1
for j = 1 … n:
    for i = n … j:  c[i] = (c[i] - c[i-1]) / (x[i] - x[i-j])

평가는 호너 방법과 같은 중첩 곱셈 $p = c_n;\ p = p\,(t - x_k) + c_k$ 다.

알아 둘 성질 다섯 가지.

• 대칭성. $f[x_0, \dots, x_k]$ 는 절점 순서에 무관하다. 같은 다항식의 최고차 계수이기 때문이다(그러나 계산된 값의 반올림 오차는 순서에 따라 다르다 — 아래 절).
• 평균값 정리. $f$ 가 $C^k$ 면 절점들의 최소·최대 사이 어떤 $\xi$ 에 대해 $f[x_0, \dots, x_k] = f^{(k)}(\xi)/k!$. 분할차분은 「간격이 고르지 않은 도함수 근사」다.
• 다항식을 지운다. $k$ 차 다항식의 $k+1$ 개 점 분할차분은 0, $k$ 개 점이면 최고차 계수다.
• 선형 범함수. $f \mapsto f[x_0, \dots, x_k]$ 는 선형이고, 닫힌꼴 $\sum_j f(x_j)/\prod_{i\ne j}(x_j - x_i)$ 를 갖는다. 이 분모가 바리센트릭 보간의 가중치와 같은 물건이다.
• 라이프니츠 규칙. $(fg)[x_0, \dots, x_k] = \sum_r f[x_0, \dots, x_r]\,g[x_r, \dots, x_k]$.

등간격 $h$ 이면 $f[x_0, \dots, x_k] = \Delta^kf_0/(k!\,h^k)$ 로 전방차분과 같아진다. 그래서 뉴턴 전방·후방 차분 공식, 그레고리-뉴턴 공식이 모두 이 틀의 특수형이고, 아담스-배시포스 같은 선형다단계법도 과거 값들의 뉴턴 보간을 적분해 유도한다(강성 방정식 참고).

3. 오차식

$f \in C^{n+1}$ 이면

$$f(x) - p_n(x) = f[x_0, \dots, x_n, x]\prod_{i=0}^{n}(x - x_i) = \frac{f^{(n+1)}(\xi_x)}{(n+1)!}\prod_{i=0}^{n}(x - x_i)$$

다. 첫 등호는 정확한 항등식이다 — $x$ 를 절점으로 하나 더 추가하면 다음 항이 곧 오차라는 뜻이다. 그래서 「다음 항의 크기」를 오차 추정으로 쓰는 실용 규칙이 나온다. 두 번째 등호의 노드 다항식 $\prod(x - x_i)$ 가 등간격에서 끝점 근처 거대해지는 것이 룽게 현상이고, 이를 최소화하는 절점이 체비쇼프 다항식의 영점이다.

4. 중복 절점 — 에르미트 보간

분할차분 정의에서 두 절점을 합치면 극한이 도함수가 된다: $f[x_0, x_0] = f'(x_0)$, 일반적으로 $m+1$ 번 반복된 절점에서 $f[x_0, \dots, x_0] = f^{(m)}(x_0)/m!$. 따라서 표에 같은 절점을 반복해 쓰고, 0/0 이 되는 자리에 도함수값을 넣기만 하면 값과 도함수를 함께 맞추는 에르미트 보간이 같은 코드로 나온다.

예: 두 점 $x_0, x_1$ 에서 값과 기울기를 맞추는 3차 에르미트 보간은 절점열 $(x_0, x_0, x_1, x_1)$ 의 뉴턴 형식이다. 이것이 3차 에르미트 스플라인(유한요소의 오일러-베르누이 보 요소, 컴퓨터 그래픽스의 퍼거슨 곡선)의 조각 하나다. 절점이 전부 한 점에 모이면 뉴턴 형식은 테일러 다항식이 된다 — 뉴턴 보간은 테일러 전개와 라그랑주 보간을 잇는 연속체다.

5. 절점 순서 — 같은 다항식, 다른 반올림

분할차분이 순서에 무관하다는 것은 정확한 산술의 얘기다. 부동소수점에서는 순서가 결정적이다. $f(x) = e^x\sin 3x$ 를 $[-1, 1]$ 의 체비쇼프 1종 영점 $N$ 개에서 보간하고 2001개 점에서 최대 오차를 재 보면:

$N$	증가 순서	레야 순서
20	6.2e-15	2.0e-15
40	8.0e-15	2.7e-15
60	3.9e-5	2.9e-15
80	3.4e+5	5.0e-15

절점은 똑같고 다항식도 수학적으로 똑같다. 그런데 왼쪽에서 오른쪽으로 정렬해 넣으면 $N = 80$ 에서 답이 10의 5승만큼 틀린다. 증가 순서에서는 뉴턴 기저 $\prod_{i<k}(x - x_i)$ 가 구간 한쪽 끝에서 거대하고 다른 쪽 끝에서 미세해져, 계수가 극단적인 크기로 상쇄하며 반올림을 증폭하기 때문이다.

처방은 레야 순서(Leja ordering, 1957)다. 첫 점은 $|x|$ 가 가장 큰 점, 이후로는 이미 고른 점들과의 거리 곱 $\prod_{i<k}|x - x_i|$ 를 최대화하는 점을 탐욕적으로 고른다. 그러면 각 단계의 뉴턴 기저가 구간 전체에 고르게 퍼진다. 라이헬(1990)이 이 순서의 뉴턴 보간이 안정적임을 보였고, 레야 순서여도 $k$ 번째 기저의 크기는 대략 구간 용량(capacity, $[a, b]$ 는 $(b - a)/4$)의 $k$ 제곱으로 자라거나 줄어 큰 $N$ 에서 오버플로·언더플로하므로, 절점을 용량으로 나눠 스케일하라고 권했다.

이 결과가 실무에 주는 말은 이렇다. 고차 보간을 하나 돌릴 거라면 바리센트릭 보간(2종 공식)이 순서 걱정 없이 안정적이라 기본값이다(히검 2004). 뉴턴형을 고르는 이유는 점을 하나씩 추가해야 할 때뿐이고, 그때는 추가 순서 자체를 레야식으로 설계해야 한다.²

6. 어디에 쓰이나

• ENO·WENO 재구성. ENO 도식은 셀 평균의 원시함수에 대한 분할차분표를 한 열씩 키우면서, 매 단계 왼쪽·오른쪽 후보 중 분할차분의 절댓값이 작은 쪽(= 더 매끄러운 쪽)을 고른다. 「점 하나 더」가 공짜인 뉴턴형이 아니면 이 적응 스텐실 선택이 이렇게 싸지 않다.
• 외삽. 리처드슨 외삽법과 롬베르크 적분은 $h \to 0$ 으로의 다항식 외삽이고, 네빌의 표나 분할차분표로 계산한다. 새 $h$ 하나가 들어올 때마다 표에 행 하나만 추가된다.
• 불균일 간격 도함수. 격자 간격이 들쭉날쭉한 유한차분법의 스텐실 계수는 분할차분의 평균값 정리로 바로 나온다(더 일반적으로는 포른버그 알고리즘).
• 이론 도구. 스플라인의 B-기저는 절단 거듭제곱 함수의 분할차분으로 정의되고(커리-쇤버그), 볼록성·단조성 판정도 분할차분의 부호로 한다. 드 보어의 「분할차분」 서베이가 이 쪽을 정리했다.³

7. 관련 문서

• 보간과 근사 · 바리센트릭 보간 · 반데르몽드 행렬 · 룽게 현상 · 르베그 상수
• 호너 방법 · 클렌쇼 점화식 · 체비쇼프 다항식
• 에르미트 보간 · ENO 도식 · 리처드슨 외삽법 · 유한차분법 · 강성 방정식

8. Footnotes

1. 뉴턴은 『프린키피아』 3권 보조정리 5에서 혜성 궤도 관측값을 잇는 데 이 공식을 썼고, 1711년 『차분법』(Methodus differentialis)으로 따로 냈다. 천체 관측 몇 점으로 궤도를 그리던 시절의 실무 도구가 300년 뒤 ENO 스텐실 선택에 쓰이고 있다. ↩

2. 「수학적으로 같다」와 「수치적으로 같다」는 다르다는 교훈의 교과서적 사례. 덧셈의 교환법칙도 부동소수점에선 성립하지 않는데, 80개 점의 순서쯤이야. ↩

3. 드 보어는 스플라인 이론의 대부이고, 그가 「분할차분」 하나만으로 서베이 논문을 썼다는 사실 자체가 이 개념의 깊이를 말해 준다. 학부에서 표 채우기 숙제로 만나고 끝나기엔 아까운 물건이다. ↩