다항식 보간

점을 지나는 다항식: 존재와 유일성

서로 다른 노드(node) $x_0, x_1, \dots, x_n$과 값 $y_0, \dots, y_n$이 주어졌을 때 $p(x_i) = y_i$를 만족하는 다항식 $p$를 찾는 문제를 다항식 보간(polynomial interpolation)이라 합니다. 값이 어떤 함수 $f$에서 왔다면($y_i = f(x_i)$) $p$를 $f$의 보간 다항식이라 부릅니다.

가장 직접적인 계산법은 $p(x) = a_0 + a_1x + \dots + a_nx^n$로 두고 조건 $n+1$개를 연립방정식으로 쓰는 것입니다.

이론으로는 이것으로 끝입니다. 문제는 계산입니다. $x^5$와 $x^6$은 $[0, 1]$에서 그래프가 거의 겹칩니다. 기저 함수들이 서로 비슷하면 $V$의 열들이 거의 평행해지고, 2장에서 본 조건수가 폭발합니다. 아래 표는 실제로 계산한 2-노름 조건수 $\kappa_2(V)$입니다(노드 $n$개).

$[0, 1]$의 등간격 노드 20개에서 $\kappa_2 \approx 10^{16}$, 곧 배정밀도의 $1/\varepsilon$에 닿았습니다. 계수 $a_k$는 소수 첫 자리도 믿을 수 없습니다. 체비쇼프 노드(6절)를 써도 조건수는 지수적으로 자랍니다. 반데르몽드의 병은 노드가 아니라 단항식 기저에 있습니다. 그래서 이 장의 나머지는 같은 다항식을 다른 기저로 쓰는 이야기입니다. 다행히 조건수가 크다고 해서 $p(x)$의 값이 언제나 틀리는 것은 아닙니다(7절에서 그 미묘한 차이를 실험합니다).

라그랑주 형식: 노드마다 하나씩의 기저

상수 함수 1도 보간 다항식이므로(모든 $y_k = 1$) 언제나 $\sum_k \ell_k(x) = 1$입니다. 곧 $p(x)$는 데이터의 가중 평균인데, 가중치 $\ell_k(x)$가 음수일 수도 있고 1보다 클 수도 있습니다. 노드 밖으로 나가면(외삽) 가중치의 크기가 급격히 커지고, 데이터의 작은 오차가 크게 증폭됩니다.

라그랑주 형식은 이론에 편리하지만 그대로 계산하면 한 점 $x$에서 $p(x)$를 얻는 데 $O(n^2)$번의 곱셈이 들고, 점을 하나 추가하면 모든 $\ell_k$를 새로 만들어야 합니다. 이 두 약점을 뉴턴 형식(3절)과 무게중심 공식(7절)이 고칩니다.

뉴턴 형식과 분할 차분표

$p_n$을 처음 $n+1$개 점의 보간 다항식이라 하면 $p_{n+1} - p_n$은 $x_0, \dots, x_n$에서 0이 되는 $n+1$차 이하 다항식이므로 $c\,(x - x_0)\cdots(x - x_n)$ 꼴입니다. 그래서 보간 다항식을 점을 하나씩 더하는 꼴로 쓸 수 있습니다.

(다)는 분할 차분이 "이산적인 도함수"라는 뜻입니다. 1차 분할 차분은 할선의 기울기이고(CalculusBook: 도함수), 노드가 모이면 도함수가 됩니다. 이 사실이 8절의 에르미트 보간과 9장 수치 미분의 출발점입니다.

// 분할 차분 계수 c[0..n] (제자리 계산, O(n²))
c ← y
for k = 1 to n
  for i = n downto k
    c[i] ← (c[i] − c[i−1]) / (x[i] − x[i−k])
// 뉴턴 형식의 계산 (호너와 같은 중첩, O(n))
function evaluate(t)
  p ← c[n]
  for i = n−1 downto 0
    p ← p · (t − x[i]) + c[i]
  return p

계수 계산은 한 번 $O(n^2)$, 그 뒤 점마다 $O(n)$. 점을 하나 더하면 표의 새 행 하나, $O(n)$만 추가로 계산한다.

보간 오차 공식

이 식은 테일러 정리의 나머지 $f^{(n+1)}(\xi)(x - a)^{n+1}/(n+1)!$과 꼴이 같습니다. 테일러 다항식은 한 점에 $n+1$개의 조건을 몰아넣은 보간이고, 그때 $\omega = (x - a)^{n+1}$입니다. 오차는 세 요소의 곱입니다. 함수의 매끄러움 $f^{(n+1)}$, 차수 $(n+1)!$, 그리고 우리가 고를 수 있는 유일한 요소인 노드 배치 $\omega(x)$.

룽게 현상: 점을 늘렸는데 더 틀린다

1901년 룽게(Carl Runge)가 이 예를 연구했습니다. 등간격 노드 $n+1$개로 보간한 최대 오차를 계산하면 다음과 같습니다.

등간격에서는 오차가 줄기는커녕 지수적으로 커지고, 그 오차는 모두 구간의 양 끝 근처에서 생깁니다. 이것이 룽게 현상(Runge phenomenon)입니다. 같은 함수를 체비쇼프 노드(6절)로 보간하면 꾸준히 줄어듭니다.

왜일까요? 오차 공식의 두 요소가 서로 싸웁니다. $1/(1 + 25x^2)$의 도함수는 $x = \pm i/5$의 복소 특이점 때문에 $f^{(n+1)}$이 대략 $(n+1)!\,5^{n+1}$만큼 자랍니다. $(n+1)!$은 지워지고 $5^{n+1}\max|\omega|$이 남는데, 등간격 노드의 $\max|\omega|$는 대략 $(2/e)^{n}$ 정도로만 줄어 $5\cdot 2/e \gt 1$이 이깁니다. 더 정확한 이론(복소 평면의 퍼텐셜 이론)은 등간격 보간이 수렴하는 영역이 실수축 위의 대략 $|x| \lt 0.726$뿐임을 보여 줍니다. 시뮬레이터에서 가운데는 맞아 들어가고 양 끝만 터지는 것이 그 결과입니다.

체비쇼프 노드와 최적성

답은 체비쇼프 다항식(Chebyshev polynomial) $T_m(\cos\theta) = \cos m\theta$에서 나옵니다. $T_0 = 1$, $T_1 = x$, $T_{m+1} = 2xT_m - T_{m-1}$이므로 $T_m$은 최고차 계수가 $2^{m-1}$인 $m$차 다항식이고, $[-1, 1]$에서 $|T_m| \le 1$이며 $m+1$개의 점 $\cos(k\pi/m)$에서 $\pm1$을 번갈아 찍습니다.

등간격과 비교하면 차이가 분명합니다. 노드 3개에서 등간격 $\{-1, 0, 1\}$의 $\omega = x^3 - x$는 최대 $2/(3\sqrt3) = 0.385$, 체비쇼프 $\{\pm\sqrt3/2, 0\}$의 $\omega = x^3 - \tfrac34 x$는 최대 $0.25$입니다. 노드 21개에서는 $2.34\times10^{-4}$ 대 $9.54\times10^{-7}$, 245배 차이입니다. 예제 5.3의 사인 보간을 체비쇼프 노드 $\{0.1052, 0.7854, 1.4656\}$으로 바꾸면 오차 한계는 $0.0311$에서 $0.0202$로, 실제 최대 오차는 $0.0235$에서 $0.0162$로 줄어듭니다.

노드 배치의 품질을 재는 더 완전한 척도는 르베그 상수(Lebesgue constant) $\Lambda_n = \max_x\sum_k|\ell_k(x)|$입니다. 최선의 $n$차 근사 $p^*$에 대해 $\|f - p_n\|_\infty \le (1 + \Lambda_n)\|f - p^*\|_\infty$이고, 데이터의 오차도 최대 $\Lambda_n$배로 증폭됩니다. 계산해 보면 등간격은 $n = 10$에서 $29.9$, $n = 20$에서 $10987$로 지수적으로 커지고, 체비쇼프는 $2.49$, $2.90$으로 $\frac{2}{\pi}\ln n$ 정도로만 자랍니다.

무게중심 공식: 빠르고 안정적인 계산

라그랑주 기저의 공통 인수를 묶어 냅니다. $\omega(x) = \prod_j(x - x_j)$와 무게중심 가중치(barycentric weight) $w_k = 1/\prod_{j \ne k}(x_k - x_j)$를 쓰면 $\ell_k(x) = \omega(x)\,w_k/(x - x_k)$입니다. 여기에 $\sum_k\ell_k = 1$로 나누면 $\omega(x)$가 지워집니다.

// 무게중심 가중치 (한 번, O(n²))
for k = 0 to n
  w[k] ← 1
  for j = 0 to n, j ≠ k
    w[k] ← w[k] / (x[k] − x[j])
// 한 점 t에서의 값 (O(n))
function bary(t)
  num ← 0;  den ← 0
  for k = 0 to n
    d ← t − x[k]
    if d = 0 then return y[k]      // 노드 위에서는 데이터 그대로
    q ← w[k] / d
    num ← num + q · y[k];  den ← den + q
  return num / den

안정성은 놀랍습니다. $t$가 노드 $x_k$에 아주 가까우면 $1/(t - x_k)$가 거대해지지만, 분자와 분모에 같은 비율로 나타나 서로 지워집니다. 하이엄(Nicholas Higham)은 2004년에 이 공식이 르베그 상수가 작은 노드(체비쇼프 등)에서 전방 안정임을 증명했습니다. 반면 같은 다항식을 반데르몽드로 구한 단항식 계수로 계산하면, 계수 자체가 조건수만큼 틀려서 정확도에 바닥이 생깁니다. 아래 시뮬레이터의 세 번째 곡선이 그 바닥입니다.

에르미트 보간: 기울기까지 맞추기

계산은 분할 차분표에 각 노드를 두 번 적으면 됩니다. 정리 5.5(다)에 의해 같은 노드의 1차 분할 차분은 $f[x_i, x_i] = \lim_{h\to0}\frac{f(x_i + h) - f(x_i)}{h} = f'(x_i)$로 정의하는 것이 자연스럽습니다. 나머지 칸은 보통 점화식 그대로입니다.

구간 하나에서의 3차 에르미트 보간은 6장의 조각별 3차 에르미트(PCHIP)와 3차 스플라인의 부품이 됩니다. 노드마다 기울기를 어떻게 정하느냐가 두 방법의 차이입니다.

이 도구가 쓰이는 곳

보간 다항식은 그 자체로 쓰이기보다 다른 알고리즘의 부품으로 더 자주 쓰입니다. "모르는 함수를 다항식으로 바꾸고, 다항식에 대해서는 정확히 계산한다"가 수치해석의 기본 동작입니다.