잔글편집 요약 없음 |
잔글 (문자열 찾아 바꾸기 - "{{학술}}" 문자열을 "" 문자열로) |
||
(다른 사용자 한 명의 중간 판 하나는 보이지 않습니다) | |||
1번째 줄: | 1번째 줄: | ||
{{고지달성|12000}} | {{고지달성|12000}} | ||
[[파일:Interpolation example polynomial.svg|섬네일|데이터가 주어졌을 때 그 데이터에 맞는 다항함수를 구하려고 한다.]] | [[파일:Interpolation example polynomial.svg|섬네일|데이터가 주어졌을 때 그 데이터에 맞는 다항함수를 구하려고 한다.]] | ||
'''다항함수 보간법'''(Polynomial interpolation)은 주어진 점들을 지나는 다항식을 찾는 [[보간법]]이다. | '''다항함수 보간법'''(Polynomial interpolation)은 주어진 점들을 지나는 다항식을 찾는 [[보간법]]이다. | ||
69번째 줄: | 69번째 줄: | ||
|} | |} | ||
이때 라그랑주 다항식을 이용해 보간하면 기저는 | 이때 라그랑주 다항식을 이용해 보간하면 기저는 | ||
: <math>p_1(x)=\frac{(x-0.1)(x-0.2)(x-0.3)(x-0.4)}{(0-0.1)(0-0.2)(0-0.3)(0-0.4)}=416.667x^4-416.667x^3+145.833x^2-20.8333x+1</math> | : <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(x)=\frac{(x-0)(x-0.2)(x-0.3)(x-0.4)}{(0.1-0)(0.1-0.2)(0.1-0.3)(0.1-0.4)}=-1666.67x^4+1500x^3-433.333x^2+40x</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(x)=\frac{(x-0)(x-0.1)(x-0.3)(x-0.4)}{(0.2-0)(0.2-0.1)(0.2-0.3)(0.2-0.4)}=2500x^4-2000x^3+475x^2-30x</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(x)=\frac{(x-0)(x-0.1)(x-0.2)(x-0.4)}{(0.3-0)(0.3-0.1)(0.3-0.2)(0.3-0.4)}=-1666.67x^4+1166.67x^3-233.333x^2+13.3333x</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(x)=\frac{(x-0)(x-0.1)(x-0.2)(x-0.3)}{(0.4-0)(0.4-0.1)(0.4-0.2)(0.4-0.3)}=416.667x^4-250x^3+45.8333x^2-2.5x</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} | : <math>\begin{align} | ||
p(x)&=p_1(x)+1.1052p_2(x)+1.2214p_3(x)+1.3499p_4(x)+1.4918p_5(x)\\ | 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 | &\approx -0.8333x^4+0.2667x^3 + 0.4758x^2+1.0018x+1 | ||
\end{align}</math> | \end{align}</math> | ||
82번째 줄: | 82번째 줄: | ||
== 보간 다항식의 유일성 == | == 보간 다항식의 유일성 == | ||
서로 다른 <math>x_1,\cdots,x_n</math>와 <math>y_1,\cdots,y_n</math>에 대해 <math>p(x_i)=y_i</math>인 (''n''-1)차 이하의 다항식은 유일하다. 임의의 <math>i\in\{1,\cdots,n\}</math>에 대해 <math>p_1(x_i)=p_2(x_i)=y_i</math>인 (''n''-1)차 이하의 다항식 <math>p_1(x),p_2(x)</math>가 존재한다고 하자. 그러면 <math>q(x)=p_1(x)-p_2(x)</math>는 (''n''-1)차 이하의 다항식이고, <math>q(x_i)=0</math>이다. 따라서 방정식 <math>q(x)=0</math>은 ''n''개의 해를 가진다. 그런데 [[대수학의 기본 정리]]에 의해 상수가 아닌 (''n''-1)차 이하의 다항식은 ''n''-1개의 근을 가지므로, <math>q(x)</math>는 상수이다. 따라서 <math>q(x)=q(x_i)=0=p_1(x)-p_2(x)</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]이므로 원하는 결과를 얻는다.