(+)분류 : 가져온 문서/오메가
Polynomial interpolation
주어진 점들을 지나는 다항식을 찾는 보간법이다.
1. 정의 ✎ ⊖
서로 다른 x_1,\\cdots,x_n에 대해 자료 (x_1,y_1), \\cdots,(x_n,y_n)이 주어졌을 때,
p(x_i)=y_i,\\quad i=1,\\dots,n
를 만족하는 다항식 p(x)를 찾는 방법을 다항함수 보간법이라 한다. 이때 p의 차수는 n-1을 넘지 않는다.
p(x_i)=y_i,\\quad i=1,\\dots,n
를 만족하는 다항식 p(x)를 찾는 방법을 다항함수 보간법이라 한다. 이때 p의 차수는 n-1을 넘지 않는다.
2. 보간 다항식 구성 ✎ ⊖
(n-1)차 이하의 다항식의 벡터공간 P의 기저 \\mathcal{B}=\\{p_1,p_2,\\cdots,p_n\\}에 대해, 임의의 p\\in P를
p(x)=a_1p_1(x)+a_2p_2(x)+\\cdots+a_np_n(x)
로 나타낼 수 있다. 이때, a_1,\\cdots,a_n은 상수이다. 이때 함수 f와 서로 다른 x_1,\\cdots, x_n\\in \\operatorname{dom} f에 대해 집합 \\{(x_1,f(x_1)), \\cdots, (x_n,f(x_n))\\}이 주어지면,
\\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}
을 만족하는 p를 구할 수 있다. 이것을 행렬을 이용해 나타내면
\\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}
이다.
p(x)=a_1p_1(x)+a_2p_2(x)+\\cdots+a_np_n(x)
로 나타낼 수 있다. 이때, a_1,\\cdots,a_n은 상수이다. 이때 함수 f와 서로 다른 x_1,\\cdots, x_n\\in \\operatorname{dom} f에 대해 집합 \\{(x_1,f(x_1)), \\cdots, (x_n,f(x_n))\\}이 주어지면,
\\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}
을 만족하는 p를 구할 수 있다. 이것을 행렬을 이용해 나타내면
\\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}
이다.
2.1. 단항식 기저를 이용한 보간 ✎ ⊖
기저 P의 원소 p_i를
p_i(x)=x^{i-1} (단항식 기저)
로 설정하면,
\\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}
이다. 이때, 왼쪽의 정사각행렬은 방데르몽드 행렬이다.
p_i(x)=x^{i-1} (단항식 기저)
로 설정하면,
\\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}
이다. 이때, 왼쪽의 정사각행렬은 방데르몽드 행렬이다.
2.2. 라그랑주 다항식을 이용한 보간 ✎ ⊖
기저 P의 원소 p_i를
p_i(x)=\\prod_{\\substack{j=1 \\\\ j\\ne i}}^n \\frac{x-x_j}{x_i-x_j} (라그랑주 다항식)
로 설정하면,
\\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}
이다. 왼쪽의 정사각행렬이 항등행렬이므로, 임의의 i\\in \\{1,\\cdots,n\\}에 대해 a_i=f(x_i)이다.
p_i(x)=\\prod_{\\substack{j=1 \\\\ j\\ne i}}^n \\frac{x-x_j}{x_i-x_j} (라그랑주 다항식)
로 설정하면,
\\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}
이다. 왼쪽의 정사각행렬이 항등행렬이므로, 임의의 i\\in \\{1,\\cdots,n\\}에 대해 a_i=f(x_i)이다.
2.3. 뉴턴 다항식을 이용한 보간 ✎ ⊖
기저 P의 원소 p_i를
p_i(x)=\\prod_{j=1}^{i-1} (x-x_j) (뉴턴 다항식)
로 설정하면,
\\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}
이다. 왼쪽의 정사각행렬이 삼각행렬이므로, 후진대입을 사용할 수 있다.
p_i(x)=\\prod_{j=1}^{i-1} (x-x_j) (뉴턴 다항식)
로 설정하면,
\\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}
이다. 왼쪽의 정사각행렬이 삼각행렬이므로, 후진대입을 사용할 수 있다.
3. 보간 다항식의 유일성 ✎ ⊖
서로 다른 x_1,\\cdots,x_n와 y_1,\\cdots,y_n에 대해 p(x_i)=y_i인 (n-1)차 이하의 다항식은 유일하다. 임의의 i\\in\\{1,\\cdots,n\\}에 대해 p_1(x_i)=p_2(x_i)=y_i인 (n-1)차 이하의 다항식 p_1(x),p_2(x)가 존재한다고 하자.
그러면 q(x)=p_1(x)-p_2(x)는 (n-1)차 이하의 다항식이고, q(x_i)=0이다. 따라서 방정식 q(x)=0은 n개의 해를 가진다.
그런데 대수학의 기본 정리에 의해 상수가 아닌 (n-1)차 이하의 다항식은 n-1개의 근을 가지므로, q(x)는 상수이다. 따라서 q(x)=q(x_i)=0=p_1(x)-p_2(x)이므로 원하는 결과를 얻는다.
그러면 q(x)=p_1(x)-p_2(x)는 (n-1)차 이하의 다항식이고, q(x_i)=0이다. 따라서 방정식 q(x)=0은 n개의 해를 가진다.
그런데 대수학의 기본 정리에 의해 상수가 아닌 (n-1)차 이하의 다항식은 n-1개의 근을 가지므로, q(x)는 상수이다. 따라서 q(x)=q(x_i)=0=p_1(x)-p_2(x)이므로 원하는 결과를 얻는다.
