[[분류:가져온 문서/오메가]]
Polynomial interpolation
주어진 점들을 지나는 [[다항식]]을 찾는 보간법이다.
== 정의 ==
서로 다른 [math(x_1,\cdots,x_n)]에 대해 자료 [math((x_1,y_1), \cdots,(x_n,y_n))]이 주어졌을 때,
[math(p(x_i)=y_i,\quad i=1,\dots,n)]
를 만족하는 다항식 [math(p(x))]를 찾는 방법을 다항함수 보간법이라 한다. 이때 [math(p)]의 차수는 [math(n-1)]을 넘지 않는다.
== 보간 다항식 구성 ==
[math((n-1))]차 이하의 다항식의 벡터공간 [math(P)]의 기저 [math(\mathcal{B}=\{p_1,p_2,\cdots,p_n\})]에 대해, 임의의 [math(p\in P)]를
[math(p(x)=a_1p_1(x)+a_2p_2(x)+\cdots+a_np_n(x))]
로 나타낼 수 있다. 이때, [math(a_1,\cdots,a_n)]은 상수이다. 이때 함수 [math(f)]와 서로 다른 [math(x_1,\cdots, x_n\in \operatorname{dom} f)]에 대해 집합 [math(\{(x_1,f(x_1)), \cdots, (x_n,f(x_n))\})]이 주어지면,
[math(\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(\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(p_i)]를
[math(p_i(x)=x^{i-1})] (단항식 기저)
로 설정하면,
[math(\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(p_i)]를
[math(p_i(x)=\prod_{\substack{j=1 \\ j\ne i}}^n \frac{x-x_j}{x_i-x_j})] (라그랑주 다항식)
로 설정하면,
[math(\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(i\in \{1,\cdots,n\})]에 대해 [math(a_i=f(x_i))]이다.
=== 뉴턴 다항식을 이용한 보간 ===
기저 [math(P)]의 원소 [math(p_i)]를
[math(p_i(x)=\prod_{j=1}^{i-1} (x-x_j))] (뉴턴 다항식)
로 설정하면,
[math(\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(x_1,\cdots,x_n)]와 [math(y_1,\cdots,y_n)]에 대해 [math(p(x_i)=y_i)]인 [math((n-1))]차 이하의 다항식은 유일하다. 임의의 [math(i\in\{1,\cdots,n\})]에 대해 [math(p_1(x_i)=p_2(x_i)=y_i)]인 [math((n-1))]차 이하의 다항식 [math(p_1(x),p_2(x))]가 존재한다고 하자.
그러면 [math(q(x)=p_1(x)-p_2(x))]는 [math((n-1))]차 이하의 다항식이고, [math(q(x_i)=0)]이다. 따라서 방정식 [math(q(x)=0)]은 [math(n)]개의 해를 가진다.
그런데 대수학의 기본 정리에 의해 상수가 아닌 [math((n-1))]차 이하의 다항식은 [math(n-1)]개의 근을 가지므로, [math(q(x))]는 상수이다. 따라서 [math(q(x)=q(x_i)=0=p_1(x)-p_2(x))]이므로 원하는 결과를 얻는다.
== 영상 ==
[youtube(h6KGbSJF2oU)]
[Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]
