방데르몽드 행렬(Vandermonde Matrix)

[경고] 아래 글을 읽지 않고 "방데르몽드 행렬"을 보면 바보로 느껴질 수 있습니다.

1. 행렬

2. 행렬식

방데르몽드 행렬(Vandermonde matrix)은 각 행 벡터(row vector)를 구성하는 원소 간의 비율이 일정해서 공비(共比, common ratio)가 행 개수만큼 있다. 다시 말해 각 행의 원소는 등비 수열(geometric series)의 항으로 간주할 수 있다.

                  (1)

여기서 $r_i$는 $i$번째 행 벡터에 대한 공비이다. 전체 행렬의 원소를 관찰해도 식 (1)에 있는 $i$번 행의 원소 배치는 $1, r_i, r_i^2, \cdots, r_i^{n-1}$과 같은 등비 수열[$a_j$ = $r_i^{j-1}$]이 분명하다. 행끼리는 서로 공비만큼만 다르기 때문에, $n \times n$ 차원(dimension)을 가진 방데르몽드 행렬의 행렬식(determinant)은 다음과 같은 인수를 가지고 있다.

                  (2)

식 (2)를 더 발전시켜서 공비 차이의 곱으로 방데르몽드 행렬식(Vandermonde determinant)을 다음처럼 정확히 표현할 수 있다.

[방데르몽드 행렬식]

정방 행렬인 방데르몽드 행렬식은 모든 공비 차이의 서로 다른 곱이다.

                  (3)

여기서 $\bf V$의 차원은 $n \times n$이다.

[증명]

임의의 정방 행렬(square matrix)의 행렬식은 라이프니츠 공식(Leibniz formula)으로 구할 수 있다.

                          (4)

식 (1)에 있는 행렬의 대각선 원소만 고려해도 행렬식을 구성하는 $r_i$에 대한 다항식의 차수[= $0 + 1 + \cdots + n-1$]는 $n(n-1)/2$이다. 또한 선택 가능한 서로 다른 공비 차이[= $r_j - r_i$]를 조합(combination)으로 구하면, 경우의 수는 $_nC_2$ = $n(n-1)/2$이다. 따라서 $r_i$에 대한 다항식의 차수와 선택 가능한 경우의 수가 같아서 방데르몽드 행렬식을 다음처럼 공식화할 수 있다.

                  (5)

여기서 $C$는 결정해야 하는 상수이다. 상수 $C$를 결정하기 위해 식 (4)와 (5)의 항을 비교하자. 식 (4)에서 $\bf V$의 대각선 원소만 선택해 곱하면, 그 결과는 $+r_2 r_3^2 \cdots r_n^{n-1}$이다. 비슷하게 식 (5)에서 부호가 (+)인 처음 $r_j$의 곱만 계산해서 $C r_2 r_3^2 \cdots r_n^{n-1}$를 얻는다. 따라서 $C$ = $1$이다.

______________________________

방데르몽드 행렬식은 공비에 대한 다항식이라서 방데르몽드 다항식(Vandermonde polynomial)이라 부르기도 한다. 방데르몽드 행렬에서 공비 $r_i$가 서로 다르면, 행렬식이 절대 $0$이 될 수 없어서 항상 역행렬(inverse matrix)이 존재한다. 즉 서로 다른 공비를 가진 방데르몽드 행렬로 구성한 연립 방정식은 해가 항상 유일하다.

[다음 읽을거리]

1. 다항 함수 보간

삼각 함수 보간(Trigonometric Interpolation)

[경고] 아래 글을 읽지 않고 "삼각 함수 보간"을 보면 바보로 느껴질 수 있습니다.

1. 다항 함수 보간

2. 푸리에 급수의 시작

3. 이산 푸리에 변환

[그림 1] 복소 평면에서 보간의 예(출처: wikipedia.org)

다항 함수 보간(polynomial interpolation)은 고차 다항식의 계수를 바꾸어서 함수값을 정확히 아는 점 혹은 표본점(sampling point) $(x_0, y_0)$, $(x_1, y_1)$, $\cdots$, $(x_n, y_n)$ 사이의 중간값을 채운다. 다항 함수 보간을 사용하는 대표적인 예는 라그랑주 보간(Lagrange interpolation)이다.

                 (1)

식 (1)이 좋은 보간법이기는 하지만, $x$가 커지면 $L_n (x)$의 함수값이 급격히 커질 수 있다. 그래서 큰 $x$에 대해서도 보간한 함수값이 커지지 않는 새로운 보간법이 필요하다. 보간에 사용하는 기저 함수(basis function)를 1차 함수 대신 삼각 함수(trigonometric function)를 쓰면, 보간 영역의 바깥[외삽(extrapolation)]에서 보간한 함수값이 매우 커지는 현상을 완화시킬 수 있다. 이와 같이 삼각 함수를 이용해서 함수를 보간하는 방법은 삼각 함수 보간(trigonometric interpolation)이라 한다[1]. 삼각 함수 보간에는 오일러의 공식(Euler's formula)을 적극적으로 사용한다.

                 (2)

오일러 공식을 이용해 $z$ = $e^{ix}$라 두면, 1차 함수 관계를 삼각 함수 관계로 손쉽게 바꿀 수 있다. 또한 우리가 고려하는 정의역은 실수에서 [그림 1]과 같은 복소 평면(complex plane)으로 확대된다. 더 구체적으로 알아보기 위해 먼저 실수 영역에서 삼각 함수 보간을 표현한다[1].

                 (3)

여기서 $0 \le x < 2 \pi$, $a_k, b_k$는 알고 있는 함수값으로 결정하는 계수이다. 식 (2)를 이용해 식 (3)의 삼각 함수를 복소 지수 함수(complex exponential function)로 바꾸어본다.

                 (4)

여기서 $a_0$ = $c_0$, $a_k$ = $c_k + c_{-k}$, $b_k = i (c_k - c_{-k})$이다. 복소수 $z$ = $e^{ix}$로 정하면, 식 (4)는 복소 평면에서 정의되는 다항식이 될 수 있다.

                 (5)

정의역이 복소수로 확대되기는 했지만, 식 (5)의 우변은 분명 다항식이다. 만약 식 (1)에 제시한 라그랑주 보간을 사용하면, 삼각 함수 보간에 대한 공식을 쉽게 유도할 수 있다. 알고 있는 함수값의 개수[= $2n+1$]가 홀수인 경우는 다음과 같은 삼각 함수 보간으로 표현된다.

                 (6)

여기서 $0 \le x < 2 \pi$이다. 라그랑주 보간의 기저 함수를 참고해서, 식 (6)의 삼각 함수 보간을 이루는 기저 함수 $t_k(x)$를 다음처럼 얻는다.

                 (7)

여기서 유한번 곱한 $e^{ix}$의 최대 차수가 $n$이 되도록 $e^{in(x_k - x)}$를 맨앞에 곱한다. 식 (7)의 우변에 의해 $t_k(x_m)$ = $\delta_{km}$이 성립한다. 여기서 $\delta_{km}$은 크로네커 델타(Kronecker delta)이다. 식 (7)에 복소 지수 함수의 항등식을 적용한다.

                 (8)

그러면 식 (7)은 매우 간단한 삼각 함수 관계식으로 바뀐다[1].

                 (9)

여기서 $t_k(x+2\pi)$ = $t_k(x)$이므로 $t_k(x)$는 주기가 $2 \pi$인 주기 함수(periodic function)이다. 아는 함수값의 개수[= $2n$]가 짝수인 경우도 홀수와 비슷하게 $F_n(x)$와 $t_k(x)$를 정의한다.

                 (10)

                 (11)

여기서 $t_k(x_m)$ = $\delta_{km}$이다. 다만 식 (11)에서 $t_k (x)$를 구성하는 $e^{ix}$의 최대 차수는 $n - 0.5$가 되어서 정수가 아니다. 추가적으로 식 (11)은 식 (9)처럼 사인 함수만으로 표현될 수 있다.

                 (12)

여기서 $t_k(x+2\pi)$ = -$t_k(x)$이다. 기저 함수 $t_k(x)$는 주기가 $4 \pi$이지만, $x$가 $2 \pi$만 바뀌어도 원래 함수값과 부호만 다를 뿐 종속성이 나타난다. 그래서 식 (12)의 $x$도 $0 \le x < 2 \pi$로 제한되어야 한다.

이상을 종합해서 식 (6)과 (10)의 결과에서 $2n \to N$ 및 $2n-1 \to N$으로 각각 바꾸면, 아는 함수값의 개수가 홀수든 짝수든 같은 공식으로 삼각 함수 보간을 할 수 있다. 하지만 짝수인 경우는 아쉽게도 $t_k (x)$에 나오는 $e^{ix}$의 최대 차수는 분수가 된다.

식 (4)는 푸리에 급수와 비슷한 유한 급수이므로, $c_k$를 다음처럼 구할 수 있다. 

                 (13)

만약 $x_m$이 균등하게 분포되면, $x_m$ = $2 \pi m / (2n+1)$[$m$ = $0, 1, \cdots, 2n$]이라 정할 수 있다. 그러면 이산 푸리에 변환(discrete Fourier transform, DFT) 개념을 도입해서 편하게 $c_k$를 구한다.

                 (14)

여기서 $l$ = $-n, -n+1, \cdots, n-1, n$이다. DFT의 푸리에 계수는 $(2n+1)c_k$이므로, DFT로 계산해 $c_k$를 정할 수도 있다.

두 표본점 $x_0, x_1$이 매우 가까운 경우도 삼각 함수 보간이 가능할까? 두 표본점의 차이 $x_1 - x_0$이 분모에 있기 때문에 기저 함수 $t_k(x)$의 크기가 매우 커질 수도 있다. 두 표본점이 매우 근접한 경우의 보간 특성을 파악하기 위해 식 (9) 혹은 (12)를 다음처럼 변형한다.

                 (15)

                 (16)

                 (17)

식 (16)에 정의한 두 함수값의 차이 평균 $y_d$는 다음처럼 함수의 미분 $y'$와 연결된다.

                 (18)

평균값의 정리(mean value theorem)에 의해, 구간 $[x_0, x_1]$ 사이에 있는 적당한 $x_d$에 대해 $y'$ = $y'(x_d)$ = $\Delta y / \Delta x$가 성립하는 미분이 존재한다. 식 (18)을 식 (17)에 대입해서 깔끔하게 정리한다.

                 (19)

여기서 $\operatorname{Sa}(x)$ = $\sin x / x$이다. 따라서 $x_0, x_1$이 아무리 근접하더라도 함수의 미분이 존재하면, 삼각 함수 보간은 절대 발산하지 않는다. 

[참고문헌]

[1] G. E. O. Giacaglia, "Trigonometric interpolation," Celestial Mechanics, vol. 1, pp. 360–367, Sep. 1970.

행렬 미적분학(Matrix Calculus)

[경고] 아래 글을 읽지 않고 "행렬 미적분학"를 보면 바보로 느껴질 수 있습니다.

1. 벡터 미적분학

2. 행렬

3. 행렬식

숫자가 아닌 행렬(matrix)은 어떻게 미분(differentiation)할까? 행렬은 숫자가 2차원으로 엮여서 미분이 매우 어렵다고 오판할지 모르지만, 행렬의 미분을 위한 방법론은 이미 익혔다. 벡터를 어떻게 미분했는지 생각해보자. [그림 1]처럼 매개변수 $t$를 정의한 후, 벡터를 $t$에 대해 미분하면 손쉽게 벡터의 미분을 정의할 수 있다. 

[그림 1] 매개변수 $t$를 이용한 벡터 $\bar r(t)$의 미분(출처: wikipedia.org)

벡터의 차원에 관계없이 임의의 벡터 $\bar r(t)$를 다음과 같이 미분할 수 있다.

                   (1)

여기서 $\bar r(t)$는 $t$에 따라 변한다. 그러면 식 (1)처럼 매개변수 $t$를 이용해서 임의 행렬 ${\bf A}(t)$의 미분을 다음처럼 정의한다.

                  (2)

여기서 ${\bf A}(t)$의 원소는 $t$에 따라 변할 수 있다.

행렬식 $|{\bf A}|$를 행렬 원소 $a_{ij}$로 미분해보자. 행렬식의 라플라스 전개(Laplace expansion)에 편미분을 적용한다.

                  (3)

여기서 ${\bf A}$의 차원은 $n \times n$, $\operatorname{cof}(a_{ij})$는 $a_{ij}$의 여인자(cofactor), $\delta_{kj}$는 크로네커 델타(Kronecker delta)이다. 우리 예상과는 많이 다르게 행렬식의 미분은 매우 간단한 결과인 여인자가 된다. 왜냐하면 여인자의 정의에 의해 $\operatorname{cof}(a_{ij})$는 $a_{ij}$를 포함하지 않아서 여인자의 편미분은 항상 $0$이 되기 때문이다. 식 (3)에서 얻은 행렬식의 미분은 야코비 공식(Jacobi's formula)으로 알려져 있다. 야코비 공식은 딸림 행렬(adjugate or adjoint matrix) $\operatorname{adj}({\bf A})$을 이용한 행렬의 곱으로 표현할 수도 있다. 매개변수 $t$에 대한 미분을 완전 미분(exact differential)으로 바꾸어 증명한다.

                  (4)

행렬 원소의 곱을 포함하고 있는 식 (4)를 행렬의 곱으로 바꾸기 위해 다음 항등식을 사용한다.

                  (5)

                  (6)

여기서 $\operatorname{tr}(\cdot)$은 행렬의 대각합(trace), $\bf C$는 여인자 $\operatorname{cof}(a_{ij})$를 원소로 하는 행렬, $\operatorname{adj}({\bf A})$ = ${\bf C}^T$이다.