바리센트릭 보간

1. 개요

바리센트릭 보간 Barycentric Interpolation
무엇	라그랑주 보간 다항식을 계산하는 공식
준비 비용	가중치 O(n2), 체비쇼프 절점이면 O(n)
평가 비용	점당 O(n)
안정성	제1형 후진 안정, 제2형은 르베그 상수가 작은 절점에서 전진 안정 (하이엄 2004)
확장	베뤼·플로터-호만 유리 보간, AAA

라그랑주 보간은 교과서에선 우아하고 코드에선 느리고 불안정하다는 누명을 썼다. 공식을 한 번 뒤집으면 둘 다 거짓말이 된다.

바리센트릭 보간(barycentric interpolation)은 절점 $x_0, \dots, x_n$ 과 값 $f_j$ 를 지나는 보간 다항식을, 미리 계산한 가중치 $w_j$ 와 $f_j$ 의 가중 평균 꼴로 평가하는 공식이다. 평가가 점당 $O(n)$ 이고, 절점을 하나 추가해도 $O(n)$ 만에 갱신되며, 체비쇼프 절점과 함께 쓰면 $n$ 이 수천이어도 배정밀도 끝까지 안정하다. 「무게중심」이라는 이름은 값 $f_j$ 를 무게 $w_j/(x - x_j)$ 로 평균하는 모양에서 왔다¹.

보간과 근사·룽게 현상 문서의 검산표가 이미 이 공식으로 계산됐다. 이 문서는 그 엔진 자체 — 두 형식, 가중치 닫힌꼴, 안정성, 그리고 다항식을 벗어난 유리 보간 확장 — 를 다룬다.

2. 두 형식

라그랑주 기저 $\ell_j(x) = \prod_{k\ne j} (x - x_k)/(x_j - x_k)$ 를 매번 곱하면 점당 $O(n^2)$ 이다. 노드 다항식 $\ell(x) = \prod_k (x - x_k)$ 와 바리센트릭 가중치

$$w_j = \frac{1}{\prod_{k\ne j}(x_j - x_k)}$$

를 쓰면 $\ell_j(x) = \ell(x)\, w_j / (x - x_j)$ 이므로

$$p(x) = \ell(x) \sum_{j=0}^{n} \frac{w_j}{x - x_j}\, f_j \qquad\text{(제1형, 수정 라그랑주 공식)}.$$

$w_j$ 는 한 번만 $O(n^2)$ 로 구하면 되고, 평가는 $O(n)$ 이다. 여기서 한 번 더 비튼다. 상수함수 1의 보간은 1 자신이므로 $1 = \ell(x) \sum_j w_j/(x - x_j)$ 이고, 위 식을 이걸로 나누면 $\ell(x)$ 가 사라진다.

$$p(x) = \frac{\displaystyle\sum_{j=0}^{n} \frac{w_j}{x - x_j}\, f_j}{\displaystyle\sum_{j=0}^{n} \frac{w_j}{x - x_j}} \qquad\text{(제2형, 진짜 바리센트릭 공식)}.$$

제2형에는 두 가지 선물이 있다. 첫째, 분자·분모에 같은 $w_j$ 가 있으니 가중치에 아무 공통 상수를 곱해도 된다 — 큰 $n$ 에서 $\prod (x_j - x_k)$ 가 넘치거나 꺼지는 문제를 상수로 흡수한다. 둘째, $x$ 가 $x_j$ 와 정확히 같을 때만 0으로 나누므로 그때는 $f_j$ 를 바로 돌려주는 분기 하나면 된다. $x$ 가 $x_j$ 에 아주 가까워 $1/(x - x_j)$ 가 거대해져도 분자·분모가 같이 커져 결과는 멀쩡하다.

3. 가중치 닫힌꼴

절점 분포가 알려져 있으면 $w_j$ 를 $O(n)$, 심지어 공식 한 줄로 쓴다. 공통 상수는 버린 값이다.

절점	$w_j$ (상수배 무시)
등간격	$(-1)^j \binom{n}{j}$
제1종 체비쇼프 $\cos\frac{(2j+1)\pi}{2n+2}$	$(-1)^j \sin\frac{(2j+1)\pi}{2n+2}$
제2종 체비쇼프 $\cos\frac{j\pi}{n}$	$(-1)^j \delta_j$, 양 끝 $\delta = \tfrac12$, 나머지 1

제2종 체비쇼프 가중치(살저 1972)는 그냥 $\pm 1$ 이 번갈아 나오고 끝만 반이다. 반면 등간격은 가중치가 $\binom{n}{n/2}/\binom{n}{0} \approx 2^n/\sqrt{n}$ 배나 차이 난다 — 이 숫자가 곧 룽게 현상과 르베그 상수의 $2^n$ 성장의 그림자다.

4. 검산 — 같은 다항식, 다른 계산법

룽게 함수 $f(x) = 1/(1 + 25x^2)$ 를 $[-1,1]$ 에서 보간하고 20001 점에서 최대 오차를 쟀다(배정밀도).

체비쇼프 절점 + 제2형.

$n$	10	50	100	1000
최대 오차	$1.32\times10^{-1}$	$4.62\times10^{-5}$	$2.26\times10^{-9}$	$1.78\times10^{-15}$

극점 $\pm i/5$ 가 정하는 번스타인 타원 반지름 $\rho = 0.2 + \sqrt{1.04} \approx 1.2198$ 로 예측하면 $\rho^{-100} \approx 2.4\times10^{-9}$ 다. 실측 $2.26\times10^{-9}$ 와 맞는다. $n = 1000$ 에서도 기계 정밀도에 붙어 멈출 뿐 튀지 않는다.

같은 절점, 같은 다항식을 방데르몽드 계수로. 단항식 계수를 solve(V, f) 로 구해 평가하면

$n$	20	50	100
최대 오차	$1.77\times10^{-2}$	$8.35\times10^{-3}$	$5.08\times10^{-3}$
$\kappa(V)$	$1.8\times10^{7}$	$\sim10^{18}$	$\sim10^{19}$

$n = 20$ 까지는 근사 오차가 지배해 둘이 같지만, 그 뒤로 방데르몽드는 $10^{-3}$ 근처에서 멈춘다. 수학적으로 똑같은 다항식인데 기저 선택 하나로 여섯 자릿수가 갈린다. “고차 다항식 보간은 불안정하다”는 통념의 상당 부분은 사실 단항식 기저의 죄다².

등간격 절점(다항식). $n = 40$ 에서 $1.05\times10^{5}$, $n = 80$ 에서 $6.3\times10^{14}$ — 공식이 아니라 절점이 문제인 경우다. 이건 아무 공식으로도 못 고친다.

5. 안정성 — 하이엄 2004

하이엄은 두 형식을 정확히 갈랐다.

• 제1형은 후진 안정이다. 계산값이 「값 $f_j$ 를 조금 흔든 데이터의 정확한 보간」과 같다. 절점이 무엇이든 성립한다.
• 제2형은 후진 안정이 아니지만 전진 안정이다. 단 오차 상계에 르베그 상수 $\Lambda_n$ 이 곱해지므로, 체비쇼프처럼 $\Lambda_n$ 이 $O(\log n)$ 인 절점에서만 실질적으로 안전하다. 등간격에서 제2형을 쓰면 반올림까지 $\Lambda_n$ 배로 불어난다.

실무 결론은 단순하다 — 좋은 절점이면 제2형을 쓰고, 절점을 고를 수 없다면 다항식 보간 자체를 포기하라. 그 「포기」의 가장 좋은 대안이 바로 아래다.

6. 유리 바리센트릭 — 등간격 데이터의 구원

제2형을 다시 보자. 가중치를 $\prod$ 공식이 아닌 아무 값으로 바꿔도, $w_j \ne 0$ 이면 $x \to x_j$ 에서 $j$ 번째 항이 지배하므로 여전히 $p(x_j) = f_j$ 다. 다만 결과는 다항식이 아니라 (차수 $n$ 이하) 유리함수가 된다. 남은 문제는 실축 위에 극점이 안 생기게 가중치를 고르는 것이다.

• 베뤼(1988): $w_j = (-1)^j$. 극점이 없다는 게 증명됐지만 수렴이 $O(h)$ 로 느리다.
• 플로터-호만(2007): 정수 $d$ 를 골라 연속한 $d+1$ 개 절점의 국소 다항식들을 섞는다. 실축에서 극점이 없고 매끄러운 함수면 $O(h^{d+1})$ 로 수렴한다. $d = 0$ 이 베뤼, $d = n$ 이 원래 다항식이다. 등간격이면 가중치가 정수 조합 $(-1)^{k-d}\sum_i \binom{d}{k-i}$ 로 닫힌다.

같은 룽게 함수, 등간격 절점에서:

$n$	다항식	FH $d=0$	FH $d=3$	FH $d=8$
20	$6.0\times10^{1}$	$4.6\times10^{-3}$	$2.8\times10^{-3}$	$7.0\times10^{-2}$
40	$1.1\times10^{5}$	$1.5\times10^{-3}$	$4.3\times10^{-6}$	$1.3\times10^{-4}$
80	$6.3\times10^{14}$	$7.5\times10^{-4}$	$5.1\times10^{-8}$	$4.6\times10^{-10}$
160	—	$3.8\times10^{-4}$	$3.0\times10^{-9}$	$1.1\times10^{-14}$

$d = 0$ 은 $n$ 을 두 배로 할 때마다 오차가 반이 되고($O(h)$), $d = 3$ 은 충분히 큰 $n$ 에서 대략 1/16 씩 준다($O(h^4)$). $d$ 가 크면 점근 속도는 빠르지만 $n$ 이 작을 때는 오히려 나쁘다 — 르베그 상수가 대략 $2^d$ 로 자라기 때문이다. 그래서 등간격 데이터에는 $d = 3$~$8$ 정도가 국룰이다. 같은 등간격 데이터에 3차 스플라인 보간도 $O(h^4)$ 이니 비교 상대가 된다.

7. 쓰이는 곳

• 스펙트럴 방법. 의사스펙트럼법의 체비쇼프 미분행렬은 바리센트릭 가중치로 $D_{ij} = (w_j/w_i)/(x_i - x_j)$, 대각은 “행 합이 0” 조건 $D_{ii} = -\sum_{j\ne i} D_{ij}$ 로 만든다. 대각을 닫힌꼴로 넣는 것보다 반올림에 강하다.
• Chebfun. 함수를 체비쇼프 보간으로 표현하는 MATLAB 도구 상자가 평가를 전부 제2형으로 한다. “다항식 차수 수천”이 일상인 세계다³.
• AAA 알고리즘(2018). 나카쓰카사·세테·트레페텐의 유리 근사 알고리즘은 바리센트릭 유리 형식의 지지점을 탐욕적으로 추가하고 가중치를 최소제곱 SVD 로 정한다. 극점 근처 함수도 몇십 개 지지점으로 잡는다 — 파데 근사의 현대판 경쟁자다.
• 형상함수·유한요소법의 고차 요소. 라그랑주 형상함수를 평가할 때 같은 트릭이 쓰인다.

8. 관련 문서

• 보간과 근사 · 룽게 현상 · 르베그 상수 · 체비쇼프 다항식
• 파데 근사 · AAA 알고리즘 · 의사스펙트럼법 · 스펙트럴 방법
• 후진 오차 해석 · 조건수 · 형상함수

9. Footnotes

1. 제2형을 보면 $p(x)$ 는 점 $f_j$ 들에 무게 $w_j/(x-x_j)$ 를 단 무게중심(barycenter)이다. 무게가 음수일 수도 있다는 점만 빼면 물리 시간에 배운 그 무게중심 맞다. ↩

2. 단항식 $1, x, x^2, \dots$ 는 $[-1,1]$ 위에서 차수가 오를수록 서로 점점 닮아 간다($x^{40}$ 과 $x^{42}$ 를 그래프로 구별해 보라). 닮은 기저로 연립방정식을 풀면 조건수가 터지는 건 당연한 귀결이다. 범인은 다항식이 아니라 기저다. ↩

3. Chebfun 은 함수 하나를 ‘그 함수가 기계 정밀도로 표현될 때까지 체비쇼프 절점 수를 두 배씩 늘리는’ 방식으로 만든다. $|x|$ 같은 꺾인 함수엔 구간을 쪼개서 대응한다. 수치해석 교수님들이 만든 도구라 그런지 ‘일단 돌려’ 정신과 정반대로 ‘일단 증명’이 깔려 있다. ↩