다항식 보간

다음 정리를 이용하여 $n + 1$개의 점을 지나는 다항식을 찾는 것을 다항식 보간 (Polynomial interpolation) 이라고 합니다.

$n + 1$개의 점 $\left( x_0, y_0 \right)$, $\left( x_1, y_1 \right)$, $\left( x_2, y_2 \right)$, $\cdots$, $\left( x_n, y_n \right)$ 을 지나는 $n$차 (이하의) 다항식 $$ p(x) = \sum_{i = 0}^{n} a_{i} x^{i} = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n $$ 는 유일하게 존재한다.
존재성 증명

$i \not= j$이면 $x_{i} \not= x_{j}$라 하자. $a_{0}$, $a_{1}$, ... $a_{n}$의 값을 찾기 위해 $y_0 = a_0 + a_1 x_0 + a_2 {x_{0}}^2 + \cdots + a_n {x_{0}}^n$, $y_1 = a_0 + a_1 x_1 + a_2 {x_{1}}^2 + \cdots + a_n {x_{1}}^n$, $\cdots$ 으로 $n + 1$개의 연립 방정식을 세우고 이를 행렬곱 꼴로
$$ \begin{bmatrix} 1 & {x_0}^{1} & {x_0}^{2} & \ldots & {x_0}^{n} \\ 1 & {x_1}^{1} & {x_1}^{2} & \ldots & {x_1}^{n} \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & {x_n}^{1} & {x_n}^{2} & \ldots & {x_n}^{n} \\ \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_n \end{bmatrix} = \begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_n \end{bmatrix} $$ 와 같이 나타낼 수 있다.
좌변의 큰 행렬은 방데르몽드 행렬이고 $i \not= j$이면 $x_{i} \not= x_{j}$이므로 역행렬이 존재한다.
따라서 $n + 1$개의 점 $\left( x_0, y_0 \right)$, $\left( x_1, y_1 \right)$, $\left( x_2, y_2 \right)$, $\cdots$, $\left( x_n, y_n \right)$ 을 지나는 $n$차 (이하의) 다항식 $$ p(x) = \sum_{i = 0}^{n} a_{i} x^{i} = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n $$ 이 존재한다.

유일성 증명

두 함수 $p(x)$, $g(x)$가 모두 $n + 1$개의 점 $\left( x_0, y_0 \right)$, $\left( x_1, y_1 \right)$, $\left( x_2, y_2 \right)$, $\cdots$, $\left( x_n, y_n \right)$을 지나는 $n$차 (이하의) 다항식이라고 하자.
$0 \leq k \leq n$인 정수 $k$에 대해 $p(x_{k}) = q(x_{k})$에서 다항식 $p(x) - q(x)$는 $n + 1$개의 근 $x_{0}$, $x_{1}$, $\cdots$, $x_{n}$을 갖는다.
이때, 두 $n$차 다항식의 차는 최대 $n$차임을 알 수 있는데, $n$차 다항식 $(n \geq 1)$ 은 최대 $n$개의 근을 갖는다는 사실이 인수정리를 통해서 (혹은 대수학의 기본정리를 통해서) 알려져있다.
그런데 $p(x) - q(x)$는 $n$차 (이하의) 다항식인데 근이 $n + 1$개 있으므로, 상수함수임을 알 수 있고, $p(x) - q(x) = 0$의 근이 존재하므로 $p(x) - q(x)$는 $0$인 상수함수이다.
$p(x) - q(x) = 0$에서 $p(x) = q(x)$이다.

$n + 1$개의 계수로 이루어진 표기법인 "coefficient representation"과 $n + 1$개의 점으로 이루어진 표기법인 "point-value representation"은 서로 동치이며 유일하다는 것을 보여줍니다.
고속 푸리에 변환 을 정당화 하는데에도 쓰입니다.