반데르몽드 행렬

1. 개요

반데르몽드 행렬 Vandermonde Matrix
정의	$V_{ij} = x_i^{\,j}$ — 행마다 한 절점의 거듭제곱
행렬식	$\prod_{i<j}(x_j - x_i)$ — 절점이 서로 다르면 가역
정체	단항식 기저로 쓴 다항식 보간·맞춤의 계수 행렬
빠른 풀이	비요르크-페레이라, $O(n^2)$ 연산·$O(n)$ 저장
악명	실수 절점이면 어떻게 골라도 조건수가 지수적으로 커진다
예외	단위원 위 등간격 절점 → DFT 행렬, $\kappa_2 = 1$

다항식 보간을 「연립방정식 하나 풀면 끝」으로 만들어 주는 행렬. 그리고 그 연립방정식을 풀지 말아야 하는 이유를 가장 잘 보여 주는 행렬.

반데르몽드 행렬(Vandermonde matrix)은 서로 다른 절점 $x_0, \dots, x_{n-1}$ 에 대해 $(i, j)$ 성분이 $x_i^{\,j}$ 인 $n \times n$ 행렬이다.

$$V = \begin{pmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^{n-1}\\ 1 & x_1 & x_1^2 & \cdots & x_1^{n-1}\\ \vdots & & & & \vdots\\ 1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^{n-1} \end{pmatrix}$$

다항식 $p(x) = a_0 + a_1 x + \cdots + a_{n-1}x^{n-1}$ 의 계수 벡터 $\mathbf a$ 에 $V$ 를 곱하면 절점에서의 값 $(p(x_0), \dots, p(x_{n-1}))$ 이 나온다. 그러니 $V\mathbf a = \mathbf f$ 를 푸는 것이 곧 「$n$ 개 점을 지나는 $n-1$ 차 다항식 찾기」, 즉 보간과 근사의 가장 원시적인 형태다. 행보다 열이 적은 직사각 $V$ 로 $\lVert V\mathbf a - \mathbf f\rVert_2$ 를 최소화하면 다항식 최소자승법 맞춤이 된다. 18세기 프랑스 수학자 알렉상드르테오필 반데르몽드(1735–1796)의 이름이 붙어 있다¹.

수학적으로는 깔끔하기 그지없다. 행렬식에 닫힌꼴이 있고, 역행렬도 라그랑주 기저 다항식의 계수로 정확히 쓸 수 있고, $O(n^2)$ 에 푸는 전용 알고리즘도 있다. 그런데 수치적으로는 거의 언제나 악조건이다. 이 두 얼굴을 동시에 아는 것이 이 행렬 문서의 요점이다.

2. 행렬식과 가역성

반데르몽드 행렬식은

$$\det V = \prod_{0 \le i < j \le n-1} (x_j - x_i)$$

이다. 증명은 짧다. $\det V$ 를 $x_{n-1}$ 의 다항식으로 보면 차수가 $n-1$ 이고, $x_{n-1} = x_i$ ($i < n-1$) 를 넣으면 두 행이 같아져 0 이 되므로 $\prod_{i<n-1}(x_{n-1} - x_i)$ 로 나누어떨어진다. 남는 계수는 한 차원 작은 반데르몽드 행렬식이니 귀납법으로 끝난다. 검산: $x = (1, 2, 4, 7)$ 이면 곱은 $1\cdot3\cdot6\cdot2\cdot5\cdot3 = 540$ 이고 부동소수점 det 도 $540.0000000000002$ 를 낸다.

이 식에서 두 가지가 바로 나온다.

• 절점이 서로 다르면 가역이다. 그러니 서로 다른 $n$ 개 점을 지나는 $n-1$ 차 다항식은 존재하고 유일하다. 보간 문제의 존재·유일성 정리가 이 한 줄이다.
• 절점이 가까우면 행렬식이 0 에 붙는다. 차이의 곱이 $n(n-1)/2$ 개라, $[0,1]$ 에 등간격 $n$ 개를 넣으면 행렬식이 $n = 20$ 에서 이미 $10^{-105}$ 이고, 큰 $n$ 에서는 대략 $e^{-3n^2/4}$ 꼴로 사라진다. 행렬식 크기가 조건수를 말해 주지는 않지만, 이 경우엔 뒤에 볼 조건수 폭발과 같은 방향을 가리킨다.

같은 성질이 유한체에서도 그대로 성립한다. 유한체 위에서 서로 다른 원소로 만든 반데르몽드 행렬은 어떤 정사각 부분행렬도 가역이라(부분행렬 역시 반데르몽드이므로), 메시지 $k$ 개를 $n$ 개 값으로 부풀린 뒤 아무 $k$ 개만 받아도 복원할 수 있다. 이것이 리드-솔로몬 부호의 뼈대다. 여기선 정확한 산술이니 조건수 걱정이 없다.

3. 조건수 — 실수 절점의 저주

실수 절점에서 단항식 기저를 쓰면 조건수는 차수에 대해 지수적으로 자란다. 절점 배치를 바꿔 보며 2-노름 조건수 $\kappa_2(V)$ 를 재면:

$n$	등간격 $[0,1]$	등간격 $[-1,1]$	체비쇼프 점 $[-1,1]$	단위원 등간격
5	$6.9\times10^{2}$	$23$	$20$	$1$
10	$1.5\times10^{7}$	$4.6\times10^{3}$	$1.5\times10^{3}$	$1$
15	$4.0\times10^{11}$	$1.1\times10^{6}$	$1.2\times10^{5}$	$1$
20	$1.2\times10^{16}$	$2.7\times10^{8}$	$9.5\times10^{6}$	$1$

읽을 것이 셋이다.

1. 구간을 원점 대칭으로 옮기는 것만으로 수만 배가 좋아진다. $[0,1]$ 에서는 $1, x, x^2, \dots$ 가 모두 양수이고 $x \to 1$ 근처에서 서로 거의 평행해, 열벡터들이 한 방향으로 몰린다. $[-1,1]$ 에서는 짝·홀 거듭제곱이 서로 직교에 가까워 조금 낫다. 실무 국룰인 「입력을 $[-1,1]$ 로 스케일하라」가 여기서 나온다.
2. 좋은 절점도 단항식 기저를 구하지 못한다. 체비쇼프 다항식의 영점을 써도 $n = 20$ 에서 $10^7$ 이다. 가우치(1962)의 역행렬 노름 공식과 베커만(2000)의 하한이 말하는 바가 이것이다 — 실수 절점이면 어떻게 배치해도 조건수가 지수적으로 커진다. 문제는 절점이 아니라 기저다.
3. 단위원 위 등간격 절점은 완벽하다. $x_k = e^{2\pi i k/n}$ 이면 $V$ 는 이산 푸리에 변환 행렬이고 $V^{*}V = nI$ 라 $\kappa_2 = 1$ 이다. 고속 푸리에 변환은 「특수한 반데르몽드 행렬을 $O(n\log n)$ 에 곱하는 법」이라고 읽을 수도 있다.

다항식 최소자승에서는 사정이 더 나쁘다. 정규방정식 $V^{\top}V\mathbf a = V^{\top}\mathbf f$ 의 계수 행렬은 모멘트 행렬, 곧 행켈 행렬이고(절점이 $[0,1]$ 에 고르게 퍼지면 힐베르트 행렬에 가까워진다) 조건수가 $\kappa(V)^2$ 다. 촐레스키 분해 문서의 반데르몽드 실험이 이 제곱이 실제로 몇 자리를 잡아먹는지 보여 준다.

4. 비요르크-페레이라 알고리즘 — 조건수를 이기는 순서

반데르몽드 계를 가우스 소거법으로 풀면 $O(n^3)$ 이다. 비요르크와 페레이라(1970)는 보간 문제의 구조를 그대로 따라가 $O(n^2)$ 에 푸는 알고리즘을 냈다. 두 단계다.

1. 뉴턴 분할차분. $\mathbf f$ 를 제자리에서 분할차분표로 바꾼다. $k = 0, \dots, n-2$ 에 대해 $i = n-1$ 부터 $k+1$ 까지 $f_i \leftarrow (f_i - f_{i-1})/(x_i - x_{i-k-1})$. 결과는 뉴턴 형태 $p(x) = c_0 + c_1(x - x_0) + c_2(x-x_0)(x-x_1) + \cdots$ 의 계수다.
2. 단항식으로 펼치기. 호너 법을 거꾸로 돌리듯 $k = n-2$ 부터 0 까지 $i = k, \dots, n-2$ 에 대해 $c_i \leftarrow c_i - x_k c_{i+1}$.

연산 $\tfrac{5}{2}n^2$ 남짓, 저장은 입력 벡터 하나. 여기까지는 「빠르다」는 이야기다. 놀라운 쪽은 정확도다. 하이엄(1987)은 절점이 $0 < x_0 < x_1 < \cdots$ 로 양수이고 오름차순이며 우변 부호가 번갈아 나오면(해 $\mathbf a$ 의 부호도 번갈아 나온다), 비요르크-페레이라가 성분별 상대오차를 기계 정밀도 수준으로 낸다는 것을 보였다. 조건수와 무관하게.

직접 재 보면 이렇다. 절점 $x_i = (i+1)/n$, 우변 $f_i = (-1)^i$, 80자리 정밀도로 구한 참해와 비교한 성분별 최대 상대오차:

$n$	$\kappa_2(V)$	부분 피벗 가우스 소거	비요르크-페레이라
10	$5.6\times10^{7}$	$2.3\times10^{-11}$	$2.1\times10^{-16}$
15	$1.5\times10^{12}$	$7.4\times10^{-6}$	$3.3\times10^{-16}$
20	$4.6\times10^{16}$	$7.7\times10^{-2}$	$5.0\times10^{-16}$

$n = 20$ 에서 가우스 소거는 해의 첫 자리부터 틀리는데 비요르크-페레이라는 16자리를 전부 맞힌다. 조건수 $4.6\times10^{16}$ 은 「$\mathbf f$ 에 임의 방향 섭동을 줬을 때 최악의 증폭」이고, 반올림 오차가 구조를 존중하는 방향으로만 들어가면 그 최악이 실현되지 않는다는 것이다². 다만 조건이 깨지면(절점 부호가 섞이거나 우변 부호 패턴이 다르면) 이 마법은 보장되지 않는다. 일반 우변에서는 「빠르고, 가우스 소거보다 대체로 나쁘지 않다」 정도로 기대하는 게 맞다.

5. 실무에서의 결론

• 보간값만 필요하면 계수를 구하지 마라. 바리센트릭 보간은 반데르몽드 계를 전혀 풀지 않고 절점 값에서 바로 $p(x)$ 를 평가하며, 체비쇼프 점과 짝지으면 수천 차수에서도 안정하다. 반데르몽드의 조건수는 「단항식 계수」라는 표현의 조건수이지 보간 문제 자체의 조건수가 아니다 — 보간 문제 자체의 민감도는 르베그 상수가 잰다.
• 맞춤은 직교 기저로. 다항식 최소자승은 단항식 대신 직교다항식(르장드르·체비쇼프)으로 열을 만들거나, 반데르몽드를 QR 분해로 푼다(정규방정식 금지). numpy.polyfit 도 내부적으로 열 스케일링 + 최소자승 SVD 를 쓰고, 문서에서 고차 맞춤 시 Polynomial.fit(정의역을 $[-1,1]$ 로 사상) 쪽을 권한다.
• 단항식 계수가 꼭 필요하면 절점을 대칭 구간으로 옮기고, 비요르크-페레이라를 쓰고, 결과 계수의 유효숫자를 믿지 마라. 차수 15 를 넘는 단항식 계수는 대개 소수 둘째 자리부터 의미가 없다.
• 같은 구조가 다른 이름으로 숨어 있다. 프로니 방법의 진폭 단계는 복소 절점 $z_i$ 의 반데르몽드 최소자승이고, 지수 성분 극이 서로 가까우면 여기서 조건수가 터진다. 미분값까지 맞추는 에르미트 보간은 같은 절점이 반복되는 합류 반데르몽드(confluent Vandermonde) 행렬을 낳는데, 가우치(1962)가 그 역행렬 노름도 함께 다뤘다. 크리로프 부분공간법의 거듭제곱 기저 $[\mathbf b, A\mathbf b, A^2\mathbf b, \dots]$ 도 $A$ 의 고유기저로 보면 고유값을 절점으로 하는 반데르몽드라, 이 기저를 그대로 쓰면 안 되고 직교화(아놀디·란초스)해야 하는 이유가 같다³.

6. 관련 문서

• 보간과 근사 · 바리센트릭 보간 · 체비쇼프 다항식 · 직교다항식 · 르베그 상수
• 조건수 · 행켈 행렬 · 힐베르트 행렬 · 촐레스키 분해 · QR 분해
• 가우스 소거법 · 최소자승법 · 고속 푸리에 변환 · 크리로프 부분공간법
• 프로니 방법 · 유한체 · 리드-솔로몬 부호 · 코시 행렬

7. Footnotes

1. 이름과 달리 반데르몽드 본인의 논문에는 이 행렬식이 그대로 나오지 않는다는 지적이 오래전부터 있다. 그가 남긴 건 대칭함수·행렬식 일반론이고, 이름은 후대가 붙였다는 쪽이 정설에 가깝다. 수학판 「원작에 없는 명대사」. ↩

2. 조건수는 문제의 성질이고 알고리즘의 성질이 아니다 — 이 문장은 맞다. 그런데 「어떤 섭동에 대한」 조건수인지까지 따지면, 구조를 지키는 섭동만 받는 문제의 조건수는 일반 조건수보다 훨씬 작을 수 있다. 같은 행렬, 다른 조건수. 격자가 아니라 구조가 다 했다. ↩

3. 크릴로프 기저를 거듭제곱 그대로 쓰는 「s-스텝」 방법이 통신 회피 알고리즘 연구에서 다시 유행했는데, 실제 구현은 단항식 대신 뉴턴·체비쇼프 기저로 바꿔 쓴다. 반데르몽드의 저주를 피하는 법은 40년째 같다 — 기저를 바꿔라. ↩