스플라인 보간법

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오.(2021년 7월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

수치해석의 수학적 분야에서 스플라인 보간술은 보간술의 일종으로, 보간술은 스플라인이라 불리는 조각 다항식의 특수한 유형이다.즉, 한 번에 모든 값에 높은 수준의 단일 다항식을 장착하는 대신, 스플라인 보간법은 값의 작은 하위 집합에 낮은 수준의 다항식을 적합시킨다. 예를 들어, 단일 10도 다항식을 모든 값에 장착하는 대신 10점 쌍 사이에 9입방 다항식을 장착하는 것이다.스플라인 보간술은 다항식 보간술보다 선호되는 경우가 많은데, 이는 스플라인에 낮은 도수의 다항식을 사용해도 보간오차를 작게 만들 수 있기 때문이다.^[1]스플라인 보간술도 고도의 다항식을 이용해 보간할 때 점들 사이에 진동이 일어날 수 있는 런지 현상의 문제를 피한다.

소개

원래 스플라인(spline)은 많은 사전 정의된 지점, 즉 매듭을 통과하기 위해 구부러진 탄력 있는 통치자를 일컫는 용어였다.이것들은 그림과 같이 손으로 조선과 건설을 위한 기술도면을 만드는 데 사용되었다.

We wish to model similar kinds of curves using a set of mathematical equations, with one polynomial ${\displaystyle y=q_{i}(x)}$ for each pair of knots ${\displaystyle (x_{i-1},y_{i-1})}$ and ${\displaystyle (x_{i},y_{i})}$, where ${\displ$$aystyle i=1,2,\dots,n$ $따라서{\displaystyle }$ n ${\displaystyle n}$다항식$$ 및 ${\displaystyle \mathrm{n}}$+ 1 ${\displaystyle$ n$+1}$노트가$$ 있을 것이다.첫 번째 다항식은${\displaystyle }$(${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$, ${\displaystyle {y\mathrm{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle (x_{0},y_{0$에서 시작하고 마지막 다항식은${\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$, y ${\displaystyle n_{}}$) ${\displaystyle (x_{n},y_{n}})$에서 끝난다$.$

모든 곡선 $y{\displaystyle }$= f${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle y=f(x)}$의 곡면성은 다음과 같이 정의된다$$.

${\displaystyle \kappa ={\frac {y"}{{{1+y'^{2}^{3/2}}.}$

스플라인에서 휨을 최소화하는 형태를 갖도록(모든 매듭을 통과하는 제약조건 하에서) $′{\$ y$'}$와 $″{\$를 모두 매듭을 포함한 모든 곳에서 연속적으로$$ 정의한다.따라서 각 연속적인 다항식의 첫 번째와 두 번째 파생상품은 매듭에서 동일한 값을 가져야 하는데, 이는 다음과 같다.

${\displaystyle {\displaysty}q'_{i}(x_{i})=q'_{i+1}(x_{i})\\q"_{i}(x_{i}}=q"_{i+1}(x_{i})\end{case}}\case}}\qquad 1\leq i\leq n-1.}$

이것은 3도 이상의 다항식(입방 다항식 이상)을 사용하는 경우에만 달성할 수 있다.고전적 접근법은 정확히 3 —입방 스플라인 다항식을 사용하는 것이다.

보간 큐빅 스플라인 찾기 알고리즘

We wish to find each polynomial ${\displaystyle q_{i}(x)}$ given the points ${\displaystyle (x_{0},y_{0})}$ through ${\displaystyle (x_{n},y_{n})}$. To do this, we will consider just a single piece of the curve, ${\displaystyle q(x)}$, which will interpolate f롬$$${\displaystyle }$( ${\displaystyle {x\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{y\mathrm{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle (x_{1},y_{1}}$ ~ (${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {}_{}}$, ${\displaystyle {}_{}{2\mathrm{}}_{}}$ )$${\$displaystyle (x_{2},y_{2})}$.이 작품은 끝점에 경사$$$$ $k{\displaystyle {}_{}}$ ${\$} 및 ${\displaystyle {k\mathrm{}}_{}}$ $2{\displaystyle {}_{}}$ ${\$}}개가 있다.아니면 더 정확히 말하면

${\displaystyle q(x_{1})=y_{1},}$

${\displaystyle q(x_{2})=y_{2},}$

${\displaystyle q'(x_{1})=k_{1},}$

${\displaystyle q'(x_{2})=k_{2}.}$

전체 방정식 $q{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle q(x)}$은(는) 대칭 형식으로 작성할 수 있다$$.

${\displaystyle q(x)={\big (}1-t(x){\big )}\,y_{1}+t(x)\,y_{2}+t(x){\big (}1-t(x){\big )}{\Big (}{\big (}1-t(x){\big )}\,a+t(x)\,b{\Big )},}$

(1)

어디에

${\displaystyle t(x)={\frac {x-x_{1}:{x_{1}{x_{2}-x_{1}},}$

(2)

${\displaystyle a=k_{1}(x_{2}-x_{1}-(y_{2}-y_{1}),}$

(3)

${\displaystyle b=-k_{2}(x_{2}-x_{1}+(y_{2}-y_{1}).}$

(4)

그러나 $k{\displaystyle {}_{}}$ ${\$및$$ ${\displaystyle {k\mathrm{}}_{}}$ $2{\displaystyle {}_{}}$ ${\$ 이러한 임계값을 도출하기 위해서는 다음 사항을 고려해야 한다.

${\displaystyle q'={\frac {dq}{dx}}={\frac {dt}{dx}}={\frac {1}{dq}{dt}}{\frac {1}{1}{x_-x_{1}}}}.}$

그 뒤를 잇는다.

${\displaystyle q'={\frac {y_{2}-y_{1}{1}{x_{2}-x_{1}+{1-t){\frac {a(1-t)+bt}{x_{1-t}{b-a}{b-a}-x_{1},{1},}}}},{1},},},}$

(5)

${\displaystyle q'=2{\frac {b-2a+(a-b)3t}{{{{(x_{2}-x_}}}^{2}}.}$

(6)

등식 (5)과 (6)에서 t = 0과 t = 1을 각각 설정하며, 실제로 첫 번째 파생상품 q((x₁) = k와₁ q((x₂) = k와₂ 두 번째 파생상품에서도 얻는다.

${\displaystyle q''(x_{1})=2{\frac {b-2a}{{{{(x_{2}-x_}}}^{2}}},}$

(7)

${\displaystyle q''(x_{2})=2{\frac {a-2b}{{{{(x_{2}-x_}}}^{2}}.}$

(8)

만약 지금 (x_i, y_i), i = 0, 1, ..., n은 n + 1점이고,

${\displaystyle q_{i}=(1-t)\,y_{i-1}+t\,y_{i}+t(1-t){\big(1-t){a_{i}+t\,b_{i}{ni}{\big )}},},},}$

(9)

여기서 어디 정도 1,2,...n, t=)−)나는 − 1)나는 −)나는 − 1{\displaystyle t={\tfrac{x-x_{i-1}}{x_{나는}-x_{i-1}}}}은 n3도 다항식 그 사이에 y보간 xi−1≤)≤시에 i=1,...n과 같이 qᆭi+1(크시)에 i=1,...n− 1, n다항식 같이 구별할 수 있는 재미를 정의합니다.t에서 불완전그는₀ interval x x x 그리고_n

${\displaystyle a_{i}=k_{i-1}(x_{i}-x_{i-1}-(y_{i}-y_{i-1}),}$

(10)

${\displaystyle b_{i}=-k_{i}(x_{i}-x_{i-1})+(y_{i}-y_{i-1}}$

(11)

i = 1, ..., n에 대해, 어디에

${\displaystyle k_{0}=q_{1}'(x_{0}),}$

(12)

${\displaystyle k_{i}=q_{i}'(x_{i})=q_{i+1}'(x_{i}),\qquad i=1,\reason,n-1,}$

(13)

${\displaystyle k_{n}=q_{n}'(x_{n}).}$

(14)

또한, sequence₁ k₀, k, ..., k가_n q′(_ix_i) = q′′(_i+1x_i)가 i = 1, ..., n - 1을 유지한다면, 결과 함수는 연속적인 두 번째 파생상품까지 갖게 될 것이다.

(7), (8), (10) 및 (11)부터는 다음과 같이 되어 있다.

${\displaystyle {\frac {k_{i-1}}{x_{i}-x_{i-1}}}+\left({\frac {1}{x_{i}-x_{i-1}}}+{\frac {1}{x_{i+1}-x_{i}}}\right)2k_{i}+{\frac {k_{i+1}}{x_{i+1}-x_{i}}}=3\left({\frac {y_{i}-y_{i-1}}{{(x_{i}-x_{i-1})}^{2}}}+{\frac {y_{i+1}-y_{i}}{{(x_{i+1}-x_{i})}^{2}}:}\오른쪽)}$

(15)

i = 1, ..., n - 1의 경우.관계(15)는 n + 1 값 k₀, k₁, ..., k에_n 대한 n - 1 선형 방정식이다.

신축성 있는 지배자가 스플라인 보간법의 모델인 경우, 가장 왼쪽의 "knot"의 왼쪽과 가장 오른쪽의 "knot"의 오른쪽에는 그 지배자가 자유롭게 움직일 수 있으며 따라서 q′ 0 = 0으로 직선의 형태를 취하게 된다. q′′′은 n - 1 선형 등호 이외에 x "자연 스플라인"의 연속 함수여야 하기 때문이다.Ation (15)은 다음을 가져야 한다.

${\displaystyle q'_{1}(x_{0})=2{\frac {3(y_{1}-y_{0}-(k_{1}+2k_{0})(x_{1}-x_{0})}{{{{{{1}-}}}}}{{2}}=0},}$

${\displaystyle q'_{n}(x_{n})=-2{\frac {3(y_{n}-y_{n-1}-(2k_{n}+k_{n-1})(x_{n-1}-1}){{{n-1}{n-1}{(x_{n}-1})}:{2}^{0,}}$

즉, 저것

${\displaystyle {\frac {2}{x_{1}-x_{0}k_{0}+{\frac {1}{1}-x_{0}}}{1}{1}k_{1}=3}{\frac {y_{1}-y_{0}}}}{{x_{0}}}}}}^{2},}}}}}}$

(16)

${\displaystyle {\frac {1}{x_{n}-x_{n-1}}}k_{n-1}+{\frac {2}{x_{n}-x_{n-1}}}k_{n}=3{\frac {y_{n}-y_{n-1}}{(x_{n}-x_{n-1})^{2}}}.}$

(17)

결국 (15)는 (16) 및 (17)와 함께 n + 1 매개변수 k₀, k, ..., k를_1n 고유하게 정의하는 n + 1 선형 방정식을 구성한다.

다른 엔드 조건인 스플라인 끝의 경사를 지정하는 "클램핑 스플라인"과 세 번째 파생상품도 x와₁ x_n−1 포인트에서 연속해야 하는 인기 있는 "노토 스플라인"이 있다."not-a-knot" 스플라인에 대해 추가 방정식은 다음을 나타낸다.

${\displaystyle q'_{1}(x_{1}=q')_{2}(x_{1})\Rightarrow {\frac {1}{\Delta x_{1}^{2}}}k_{0}+\left({\frac {1}{\Delta x_{1}^{2}}}-{\frac {1}{\Delta x_{2}^{2}}}\right)k_{1}-{\frac {1}{\Delta x_{2}^{2}}}k_{2}=2\left({\frac {\Delta y_{1}}{\Delta x_{1}^{3}}}-{\frac {\Delta y_{2}}{\Delta x_{2}^{3}}}\right),}$

${\displaystyle q'''_{n-1}(x_{n-1})=q'''_{n}(x_{n-1})\Rightarrow {\frac {1}{\Delta x_{n-1}^{2}}}k_{n-2}+\left({\frac {1}{\Delta x_{n-1}^{2}}}-{\frac {1}{\Delta x_{n}^{2}}}\right)k_{n-1}-{\frac {1}{\Delta x_{n}^{2}}}k_{n}=2\left({\frac {\Delta y_{n-1}}{\Delta x_{n-1}^{3}}}-{\frac {\Delta y_{n}}{\Delta x_{n}^{3}}}\right),}$

여기서 $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle x_{}}$ i${\displaystyle {}_{}}$= ${\displaystyle {}_{}}$ i${\displaystyle {}_{}}$- ${\displaystyle {\mathrm{x}}_{}}$ ${\displaystyle {}_{}}$- 1,${\displaystyle {}_{}\text{Δ}\mathrm{}}$ ${\displaystyle y_{}}$ =${\displaystyle {}_{}}$y -${\displaystyle {}_{}}$ ${\displaystyle {\mathrm{i}}_{}}$ -${\displaystyle {}_{}}$1 ${\$

예

3개 지점의 경우 3각 선형방정식을 풀어서 $k{\displaystyle {}_{}}$ 0${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$k ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}개의 값을 구한다$$.

${\displaystyle {\begin{bmatrix}a_{11}&a_{12}&0\\a_{21}&a_{22}&a_{23}\\0&a_{32}&a_{33}\\\end{bmatrix}}{\begin{bmatrix}k_{0}\\k_{1}\\k_{2}\\\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\b_{3}\\\end{bmatrix}}}$

와 함께

${\displaystyle a_{11}={\frac {2}{x_{1}-x_{0}}},}$

${\displaystyle a_{12}={\frac {1}{x_{1}-x_{0}}},}$

${\displaystyle a_{21}={\frac {1}{x_{1}-x_{0}}},}$

${\displaystyle a_{22}=2\leftency\frac {1}{x_{1}-x_{0}}+{\frac {1}{x_{2}-x_{1}}\오른쪽),}$

${\displaystyle a_{23}={\frac {1}{x_{2}-x_{1}},}$

${\displaystyle a_{32}={\frac {1}{x_{2}-x_{1}},}$

${\displaystyle a_{33}={\frac {2}{x_{2}-x_{1}}},}$

${\displaystyle b_{1}=3{\frac {y_{1}-y_{0}}{{0}}}{(x_{1}-x_{0}}):{2}},}$

${\displaystyle b_{2}=3\leftency\frac {y_{1}-y_{0}}{{{{(x_{1}-{0}})}^{2}}+{{\frac {y_{2}-y_{1}{{{(x_{2}-x_{1}}}}}}}}}}}}}}}\}\}\오른쪽)}}),}}}}}}}$

${\displaystyle b_{3}=3{\frac {y_{2}-y_{1}:{1}:{1}{{(x_{2}-x_{1}}^{2}}.}$

세 가지 포인트에 대해

$[\displaystyle(-1,0.5),\(0,0),\(3,3)]$

이해하다

${\displaystyle k_{0}=-0.6875,\ k_{1}=-0.1250,\ k_{2}=1.5625,}$

그리고 (10) 및 (11)로부터

${\displaystyle a_{1}=k_{0}(x_{1}-x_{0})-(y_{1}-y_{0}=-0.1875,}$

${\displaystyle b_{1}=-k_{1}(x_{1}-x_{0})+(y_{1}-y_{0}=-0.3750,}$

${\displaystyle a_{2}=k_{1}(x_{2}-x_{1}-(y_{2}-y_{1})-(y_{1}=-3.3750,}$

${\displaystyle b_{2}=-k_{2}(x_{2}-x_{1}+(y_{2}-y_{1}=-1.6875.}$

그림에는 (9)에서 부여한$$ 2입방 다항식 ${\displaystyle {q\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$( x${\displaystyle }$) ${\displaystyle q_{1}(x)}$ 및$$ ${\displaystyle {q\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$( ${\displaystyle x}$) ${\displaystyle q_{2}(x)}$로 구성된 스플라인 함수가 표시된다.

참고 항목

• 큐빅 헤르미테 스플라인
• 구심 캣멀-롬 스플라인
• 이산 스플라인 보간법
• 모노톤 입방 보간법
• NURBS
• 다변량 보간법
• 다항 보간법
• 스무딩 스플라인
• 스플라인 파장
• 얇은 판 스플라인
• 다화학적 스플라인

컴퓨터 코드

TinySpline:입방 스플라인 보간법을 구현하는 스플라인용 오픈 소스 C-도서관

SciPy 스플라인 보간법: 보간법을 구현하는 Python 패키지

입방 보간:입방 스플라인 보간용 오픈 소스 C# 도서관

참조

• Schoenberg, Isaac J. (1946). "Contributions to the Problem of Approximation of Equidistant Data by Analytic Functions: Part A.—On the Problem of Smoothing or Graduation. A First Class of Analytic Approximation Formulae". Quarterly of Applied Mathematics. 4 (2): 45–99. doi:10.1090/qam/15914.
• Schoenberg, Isaac J. (1946). "Contributions to the Problem of Approximation of Equidistant Data by Analytic Functions: Part B.—On the Problem of Osculatory Interpolation. A Second Class of Analytic Approximation Formulae". Quarterly of Applied Mathematics. 4 (2): 112–141. doi:10.1090/qam/16705.

외부 링크

• 큐빅 스플라인 보간 온라인 계산 및 시각화 도구(JavaScript 소스 코드 포함)
• "Spline interpolation", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• JSXGraph를 사용한 동적 입방 스플라인
• 스플라인 보간 이론과 실천에 관한 강의
• 입방 스플라인 보간법을 단계별로 설명하지만 등거리 매듭에 대해서만 설명되는 용지.
• C의 수치적 조리법, 3장 3-3절 참조
• 입방 스플라인에 대한 노트
• 스플라인 보간(Fortran 77의 코드 포함)에 대한 정보