잔글 (문자열 찾아 바꾸기 - "{{학술}}" 문자열을 "" 문자열로) |
|||
(사용자 3명의 중간 판 10개는 보이지 않습니다) | |||
1번째 줄: | 1번째 줄: | ||
{{ | {{고지달성|12000}} | ||
[[파일:Interpolation example polynomial.svg|섬네일|데이터가 주어졌을 때 그 데이터에 맞는 다항함수를 구하려고 한다.]] | |||
'''다항함수 보간법'''(Polynomial interpolation)은 주어진 점들을 지나는 다항식을 찾는 [[보간법]]이다. | '''다항함수 보간법'''(Polynomial interpolation)은 주어진 점들을 지나는 다항식을 찾는 [[보간법]]이다. | ||
== 정의 == | == 정의 == | ||
서로 다른 <math>x_1,\cdots,x_n</math>에 대해 자료 <math>(x_1,y_1), \cdots,(x_n,y_n)</math>이 주어졌을 때, | 서로 다른 <math>x_1,\cdots,x_n</math>에 대해 자료 <math>\left(x_1,y_1\right), \cdots,\left(x_n,y_n\right)</math>이 주어졌을 때, | ||
:<math>p(x_i)=y_i,\qquad i\in\{1,\cdots,n\}</math> | :<math>p\left(x_i\right)=y_i,\qquad i\in\left\{1,\cdots,n\right\}</math> | ||
를 만족하는 다항식 <math>p(x)</math>를 찾는 방법을 '''다항함수 보간법(polynomial interpolation)'''이라 한다. 이때 ''p''의 차수는 ''n''-1을 넘지 않는다. | 를 만족하는 다항식 <math>p\left(x\right)</math>를 찾는 방법을 '''다항함수 보간법(polynomial interpolation)'''이라 한다. 이때 ''p''의 차수는 ''n''-1을 넘지 않는다. | ||
예를 들어 자료 <math>\left(-1,1\right),\left(0,-2\right),\left(1,2\right)</math>가 주어졌을 때 이들을 지나는 이차 이하의 다항함수 <math>p\left(x\right)=ax^2+bx+c</math>를 찾아보면, | |||
: <math>a-b+c=1</math> | |||
: <math>c=-2</math> | |||
: <math>a+b+c=2</math> | |||
이므로 <math>p\left(x\right)=\frac{7}{2}x^2+\frac{1}{2}x-2</math>가 주어진 자료를 보간하는 다항함수임을 알 수 있다. | |||
== 보간 다항식 구성 == | == 보간 다항식 구성 == | ||
(''n''-1)차 이하의 다항식의 [[벡터공간]] ''P''의 기저 <math>\mathcal{B}=\{p_1,p_2,\cdots,p_n\}</math>에 대해, 임의의 <math>p\in P</math>를 | (''n''-1)차 이하의 다항식의 [[벡터공간]] ''P''의 기저 <math>\mathcal{B}=\left\{p_1,p_2,\cdots,p_n\right\}</math>에 대해, 임의의 <math>p\in P</math>를 | ||
:<math>p(x)=a_1p_1(x)+a_2p_2(x)+\cdots+a_np_n(x)</math> | :<math>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>a_1,\cdots,a_n</math>은 상수이다. 이때 함수 ''f''와 서로 다른 <math>x_1,\cdots, x_n\in \operatorname{dom} f</math>에 대해 집합 <math>\{(x_1,f(x_1)), \cdots, (x_n,f(x_n))\}</math>이 주어지면, | 로 나타낼 수 있다. 이때, <math>a_1,\cdots,a_n</math>은 상수이다. 이때 함수 ''f''와 서로 다른 <math>x_1,\cdots, x_n\in \operatorname{dom} f</math>에 대해 집합 <math>\left\{\left(x_1,f\left(x_1\right)\right), \cdots, \left(x_n,f\left(x_n\right)\right)\right\}</math>이 주어지면, | ||
:<math>\begin{array}{ | :<math>\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>\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> | :<math>\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>p_i</math>를 | 기저 ''P''의 원소 <math>p_i</math>를 | ||
: <math>p_i(x)=x^{i-1}</math> ([[단항식 기저]]) | : <math>p_i\left(x\right)=x^{i-1}</math> ([[단항식 기저]]) | ||
로 설정하면, | 로 설정하면, | ||
:<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> | :<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\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>p_i</math>를 | ||
: <math>p_i(x)=\prod_{\substack{j=1 \\ j\ne i}}^n \frac{x-x_j}{x_i-x_j}</math> ([[라그랑주 다항식]]) | : <math>p_i\left(x\right)=\prod_{\substack{j=1 \\ j\ne i}}^n \frac{x-x_j}{x_i-x_j}</math> ([[라그랑주 다항식]]) | ||
로 설정하면, | 로 설정하면, | ||
: <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> | : <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\left(x_1\right) \\ f\left(x_2\right) \\ f\left(x_3\right) \\ \vdots \\ f\left(x_n\right) \end{bmatrix}</math> | ||
이다. 왼쪽의 정사각행렬이 항등행렬이므로, 임의의 | 이다. 왼쪽의 정사각행렬이 항등행렬이므로, 임의의 <math>i\in \{1,\cdots,n\}</math>에 대해 <math>a_i=f\left(x_i\right)</math>이다. | ||
=== 뉴턴 다항식을 이용한 보간 === | === 뉴턴 다항식을 이용한 보간 === | ||
기저 | 기저 ''P''의 원소 <math>p_i</math>를 | ||
: <math>p_i(x)=\prod_{j=1}^{i-1} (x-x_j)</math> ([[뉴턴 다항식]]) | : <math>p_i\left(x\right)=\prod_{j=1}^{i-1} \left(x-x_j\right)</math> ([[뉴턴 다항식]]) | ||
로 설정하면, | 로 설정하면, | ||
: <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> | : <math>\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> | ||
이다. 왼쪽의 정사각행렬이 삼각행렬이므로, 후진대입을 사용할 수 있다. | 이다. 왼쪽의 정사각행렬이 삼각행렬이므로, 후진대입을 사용할 수 있다. | ||
== 예시 == | |||
자료가 다음과 같이 주어졌다고 가정하자. | |||
{| class="wikitable" | |||
! ''i'' | |||
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
|- | |||
! <math>x_i</math> | |||
| 0 | |||
| 0.1 | |||
| 0.2 | |||
| 0.3 | |||
| 0.4 | |||
|- | |||
! <math>y_i</math> | |||
| 1 | |||
| 1.1052 | |||
| 1.2214 | |||
| 1.3499 | |||
| 1.4918 | |||
|} | |||
이때 라그랑주 다항식을 이용해 보간하면 기저는 | |||
: <math>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>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>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>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>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>\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>x_1,\cdots,x_n</math>와 <math>y_1,\cdots,y_n</math>에 대해 <math>p\left(x_i\right)=y_i</math>인 (''n''-1)차 이하의 다항식은 유일하다. 임의의 <math>i\in\left\{1,\cdots,n\right\}</math>에 대해 <math>p_1\left(x_i\right)=p_2\left(x_i\right)=y_i</math>인 (''n''-1)차 이하의 다항식 <math>p_1\left(x\right),p_2\left(x\right)</math>가 존재한다고 하자. 그러면 <math>q\left(x\right)=p_1\left(x\right)-p_2\left(x\right)</math>는 (''n''-1)차 이하의 다항식이고, <math>q\left(x_i\right)=0</math>이다. 따라서 방정식 <math>q\left(x\right)=0</math>은 ''n''개의 해를 가진다. 그런데 [[대수학의 기본 정리]]에 의해 상수가 아닌 (''n''-1)차 이하의 다항식은 ''n''-1개의 근을 가지므로, <math>q\left(x\right)</math>는 상수이다. 따라서 <math>q\left(x\right)=q\left(x_i\right)=0=p_1\left(x\right)-p_2\left(x\right)</math>이므로 원하는 결과를 얻는다. | ||
[[분류:보간법]] | [[분류:보간법]] |
2016년 12월 4일 (일) 23:30 기준 최신판
다항함수 보간법(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]이므로 원하는 결과를 얻는다.