다항함수 보간법

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

데이터가 주어졌을 때 그 데이터에 맞는 다항함수를 구하려고 한다.

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

정의

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

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

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

예를 들어 자료 [math]\displaystyle{ \left(-1,1\right),\left(0,-2\right),\left(1,2\right) }[/math]가 주어졌을 때 이들을 지나는 이차 이하의 다항함수 [math]\displaystyle{ p\left(x\right)=ax^2+bx+c }[/math]를 찾아보면,

[math]\displaystyle{ a-b+c=1 }[/math]

[math]\displaystyle{ c=-2 }[/math]

[math]\displaystyle{ a+b+c=2 }[/math]

이므로 [math]\displaystyle{ p\left(x\right)=\frac{7}{2}x^2+\frac{1}{2}x-2 }[/math]가 주어진 자료를 보간하는 다항함수임을 알 수 있다.

보간 다항식 구성

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

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

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

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

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

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

이다.

단항식 기저를 이용한 보간

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

[math]\displaystyle{ p_i\left(x\right)=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\left(x_1\right) \\ f\left(x_2\right) \\ f\left(x_3\right) \\ \vdots \\ f\left(x_n\right) \end{bmatrix} }[/math]

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

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

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

[math]\displaystyle{ p_i\left(x\right)=\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\left(x_1\right) \\ f\left(x_2\right) \\ f\left(x_3\right) \\ \vdots \\ f\left(x_n\right) \end{bmatrix} }[/math]

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

뉴턴 다항식을 이용한 보간

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

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

로 설정하면,

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

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

예시

자료가 다음과 같이 주어졌다고 가정하자.

i	1	2	3	4	5
[math]\displaystyle{ x_i }[/math]	0	0.1	0.2	0.3	0.4
[math]\displaystyle{ y_i }[/math]	1	1.1052	1.2214	1.3499	1.4918

이때 라그랑주 다항식을 이용해 보간하면 기저는

[math]\displaystyle{ p_1\left(x\right)=\frac{\left(x-0.1\right)\left(x-0.2\right)\left(x-0.3\right)\left(x-0.4\right)}{\left(0-0.1\right)\left(0-0.2\right)\left(0-0.3\right)\left(0-0.4\right)}=416.667x^4-416.667x^3+145.833x^2-20.8333x+1 }[/math]

[math]\displaystyle{ p_2\left(x\right)=\frac{\left(x-0\right)\left(x-0.2\right)\left(x-0.3\right)\left(x-0.4\right)}{\left(0.1-0\right)\left(0.1-0.2\right)\left(0.1-0.3\right)\left(0.1-0.4\right)}=-1666.67x^4+1500x^3-433.333x^2+40x }[/math]

[math]\displaystyle{ p_3\left(x\right)=\frac{\left(x-0\right)\left(x-0.1\right)\left(x-0.3\right)\left(x-0.4\right)}{\left(0.2-0\right)\left(0.2-0.1\right)\left(0.2-0.3\right)\left(0.2-0.4\right)}=2500x^4-2000x^3+475x^2-30x }[/math]

[math]\displaystyle{ p_4\left(x\right)=\frac{\left(x-0\right)\left(x-0.1\right)\left(x-0.2\right)\left(x-0.4\right)}{\left(0.3-0\right)\left(0.3-0.1\right)\left(0.3-0.2\right)\left(0.3-0.4\right)}=-1666.67x^4+1166.67x^3-233.333x^2+13.3333x }[/math]

[math]\displaystyle{ p_5\left(x\right)=\frac{\left(x-0\right)\left(x-0.1\right)\left(x-0.2\right)\left(x-0.3\right)}{\left(0.4-0\right)\left(0.4-0.1\right)\left(0.4-0.2\right)\left(0.4-0.3\right)}=416.667x^4-250x^3+45.8333x^2-2.5x }[/math]

이고 보간 다항식은

[math]\displaystyle{ \begin{align} p\left(x\right)&=p_1\left(x\right)+1.1052p_2\left(x\right)+1.2214p_3\left(x\right)+1.3499p_4\left(x\right)+1.4918p_5\left(x\right)\\ &\approx -0.8333x^4+0.2667x^3 + 0.4758x^2+1.0018x+1 \end{align} }[/math]

으로 주어진다. 다른 보간 다항식을 쓰더라도 똑같은 보간 다항식을 얻을 수 있다.

보간 다항식의 유일성

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