다항함수 보간법

이 글은 12000번째 고지를 달성한 문서입니다. 현재 리브레 위키의 문서수는 59,342개입니다.

다항함수 보간법(Polynomial interpolation)은 주어진 점들을 지나는 다항식을 찾는 보간법이다.

정의

서로 다른 [math]\displaystyle{ x_1,\cdots,x_n }[/math]에 대해 자료 [math]\displaystyle{ (x_1,y_1), \cdots,(x_n,y_n) }[/math]이 주어졌을 때,

[math]\displaystyle{ p(x_i)=y_i,\qquad i\in\{1,\cdots,n\} }[/math]

를 만족하는 다항식 [math]\displaystyle{ p(x) }[/math]를 찾는 방법을 다항함수 보간법(polynomial interpolation)이라 한다. 이때 p의 차수는 n-1을 넘지 않는다.

보간 다항식 구성

(n-1)차 이하의 다항식의 벡터공간 P의 기저 [math]\displaystyle{ \mathcal{B}=\{p_1,p_2,\cdots,p_n\} }[/math]에 대해, 임의의 [math]\displaystyle{ p\in P }[/math]를

[math]\displaystyle{ p(x)=a_1p_1(x)+a_2p_2(x)+\cdots+a_np_n(x) }[/math]

로 나타낼 수 있다. 이때, [math]\displaystyle{ a_1,\cdots,a_n }[/math]은 상수이다. 이때 함수 f와 서로 다른 [math]\displaystyle{ x_1,\cdots, x_n\in \operatorname{dom} f }[/math]에 대해 집합 [math]\displaystyle{ \{(x_1,f(x_1)), \cdots, (x_n,f(x_n))\} }[/math]이 주어지면,

[math]\displaystyle{ \begin{array}{lcl}a_1p_1(x_1)+a_2p_2(x_1)+a_3p_3(x_1)+\cdots+a_np_n(x_1)&=&f(x_1)\\a_1p_1(x_2)+a_2p_2(x_2)+a_3p_3(x_2)+\cdots+a_np_n(x_2)&=&f(x_2)\\a_1p_1(x_3)+a_2p_2(x_3)+a_3p_3(x_3)+\cdots+a_np_n(x_3)&=&f(x_3)\\&\vdots&\\a_1p_1(x_n)+a_2p_2(x_n)+a_3p_3(x_n)+\cdots+a_np_n(x_n)&=&f(x_n)\end{array} }[/math]

을 만족하는 p를 구할 수 있다. 이것을 행렬을 이용해 나타내면

[math]\displaystyle{ \begin{bmatrix}p_1(x_1) & p_2(x_1) & p_3(x_1) & \cdots & p_n(x_1) \\ p_1(x_2) & p_2(x_2) & p_3(x_2) & \cdots & p_n(x_2) \\ p_1(x_3) & p_2(x_3) & p_3(x_3) & \cdots & p_n(x_3) \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ p_1(x_n) & p_2(x_n) & p_3(x_n) & \cdots & p_n(x_n) \end{bmatrix}\begin{bmatrix}a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_n \end{bmatrix}=\begin{bmatrix}f(x_1) \\ f(x_2) \\ f(x_3) \\ \vdots \\ f(x_n) \end{bmatrix} }[/math]

이다.

단항식 기저를 이용한 보간

기저 P의 원소 [math]\displaystyle{ p_i }[/math]를

[math]\displaystyle{ p_i(x)=x^{i-1} }[/math] (단항식 기저)

로 설정하면,

[math]\displaystyle{ \begin{bmatrix}1 & x_1 & x_1^2 & \cdots & x_1^{n-1} \\ 1 & x_2 & x_2^2 & \cdots & x_2^{n-1} \\ 1 & x_3 & x_3^2 & \cdots & x_3^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^{n-1} \end{bmatrix}\begin{bmatrix}a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_n \end{bmatrix}=\begin{bmatrix}f(x_1) \\ f(x_2) \\ f(x_3) \\ \vdots \\ f(x_n) \end{bmatrix} }[/math]

이다. 이때, 왼쪽의 정사각행렬은 방데르몽드 행렬이다.

라그랑주 다항식을 이용한 보간

기저 P의 원소 [math]\displaystyle{ p_i }[/math]를

[math]\displaystyle{ p_i(x)=\prod_{\substack{j=1 \\ j\ne i}}^n \frac{x-x_j}{x_i-x_j} }[/math] (라그랑주 다항식)

로 설정하면,

[math]\displaystyle{ \begin{bmatrix}1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \end{bmatrix}\begin{bmatrix}a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_n \end{bmatrix}=\begin{bmatrix}f(x_1) \\ f(x_2) \\ f(x_3) \\ \vdots \\ f(x_n) \end{bmatrix} }[/math]

이다. 왼쪽의 정사각행렬이 항등행렬이므로, 임의의 [math]\displaystyle{ i\in \{1,\cdots,n\} }[/math]에 대해 [math]\displaystyle{ a_i=f(x_i) }[/math]이다.

뉴턴 다항식을 이용한 보간

기저 P의 원소 [math]\displaystyle{ p_i }[/math]를

[math]\displaystyle{ p_i(x)=\prod_{j=1}^{i-1} (x-x_j) }[/math] (뉴턴 다항식)

로 설정하면,

[math]\displaystyle{ \begin{bmatrix}1 & 0 & 0 & \cdots & 0 \\ 1 & x_2-x_1 & 0 & \cdots & 0 \\ 1 & x_3-x_1 & (x_3-x_1)(x_3-x_2) & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n-x_1 & (x_n-x_1)(x_n-x_2) & \cdots & \prod_{j=1}^{n-1} (x_n-x_j) \end{bmatrix}\begin{bmatrix}a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_n \end{bmatrix}=\begin{bmatrix}f(x_1) \\ f(x_2) \\ f(x_3) \\ \vdots \\ f(x_n) \end{bmatrix} }[/math]

이다. 왼쪽의 정사각행렬이 삼각행렬이므로, 후진대입을 사용할 수 있다.

보간 다항식의 유일성

서로 다른 [math]\displaystyle{ x_1,\cdots,x_n }[/math]와 [math]\displaystyle{ y_1,\cdots,y_n }[/math]에 대해 [math]\displaystyle{ p(x_i)=y_i }[/math]인 (n-1)차 이하의 다항식은 유일하다. 임의의 [math]\displaystyle{ i\in\{1,\cdots,n\} }[/math]에 대해 [math]\displaystyle{ p_1(x_i)=p_2(x_i)=y_i }[/math]인 (n-1)차 이하의 다항식 [math]\displaystyle{ p_1(x),p_2(x) }[/math]가 존재한다고 하자. 그러면 [math]\displaystyle{ q(x)=p_1(x)-p_2(x) }[/math]는 (n-1)차 이하의 다항식이고, [math]\displaystyle{ q(x_i)=0 }[/math]이다. 따라서 방정식 [math]\displaystyle{ q(x)=0 }[/math]은 n개의 해를 가진다. 그런데 대수학의 기본 정리에 의해 상수가 아닌 (n-1)차 이하의 다항식은 n-1개의 근을 가지므로, [math]\displaystyle{ q(x) }[/math]는 상수이다. 따라서 [math]\displaystyle{ q(x)=q(x_i)=0=p_1(x)-p_2(x) }[/math]이므로 원하는 결과를 얻는다.