라그랑주 보간법은 수치 해석학에서 주어진 데이터 점들의 집합을 지나는 가장 낮은 차수의 다항식을 찾는 방법이다. 1795년 조제프루이 라그랑주(Joseph-Louis Lagrange)가 발표하여 그의 이름이 붙었으나, 실제로는 1779년 에드워드 웨어링(Edward Waring)이 먼저 발견했다.
이 방법은 뉴턴-코츠 적분 공식, 셰미르의 비밀 분산, 리드-솔로몬 오류 정정 코드 등 다양한 분야의 기초가 된다.
서로 다른 $k+1$개의 데이터 점 $(x_0, y_0), (x_1, y_1), \dots, (x_k, y_k)$가 주어졌을 때, 이 점들을 모두 지나는 $k$차 이하의 유일한 다항식 $L(x)$는 다음과 같이 정의된다.
$$ L(x) = \sum_{j=0}^{k} y_j \ell_j(x) $$
여기서 $\ell_j(x)$는 라그랑주 기저 다항식으로 다음과 같이 정의된다.
$$ \ell_j(x) = \prod_{\substack{0 \le m \le k \\ m \neq j}} \frac{x - x_m}{x_j - x_m} $$
라그랑주 기저 다항식은 크로네커 델타($\delta_{jm}$) 성질을 가진다.
즉, $L(x)$에 $x_j$를 대입하면 $y_j$항을 제외한 나머지 모든 항이 0이 되어 $L(x_j) = y_j$가 성립함이 보장된다.
<aside> 💡
정리:
서로 다른 $x$ 좌표를 가진 $k$개의 점에 대해, 이를 지나는 $k-1$차 다항식은 유일하게 결정된다.
</aside>
1. 문제 설정
$$ f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_{k-1} x^{k-1} $$
$$ f(x_i) = y_i \quad \text{for } i = 1, 2, \ldots, k $$
2. 선형 연립방정식 구성
$$ a_0 + a_1 x_1 + a_2 x_1^2 + \cdots + a_{k-1} x_1^{k-1} = y_1 $$
$$ a_0 + a_1 x_2 + a_2 x_2^2 + \cdots + a_{k-1} x_2^{k-1} = y_2 $$
$$ \vdots $$
$$ a_0 + a_1 x_k + a_2 x_k^2 + \cdots + a_{k-1} x_k^{k-1} = y_k $$
\begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_k \end{bmatrix} $$
3. 반데르몬드 행렬의 정의
$$ V = \begin{bmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^{k-1} \\ 1 & x_2 & x_2^2 & \cdots & x_2^{k-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_k & x_k^2 & \cdots & x_k^{k-1} \end{bmatrix} $$
4. 반데르몬드 행렬의 행렬식
$$ \det(V) = \prod_{1 \leq i < j \leq k} (x_j - x_i) $$
5. 행렬식이 0이 아님을 보이기
$$ \det(V) = \prod_{1 \leq i < j \leq k} (x_j - x_i) \neq 0 $$
6. 역행렬의 존재성
7. 유일한 해의 존재
$$ \mathbf{a} = V^{-1} \mathbf{y} $$