모노톤 입방 보간법

수치해석 수학적 분야에서 단오톤 입방 보간술은 보간되는 데이터 세트의 단조성을 보존하는 입방 보간술의 변형이다.

단조성은 선형 보간법으로 보존되지만 입방 보간으로는 보장되지 않는다.

모노톤입방 헤르미트 보간법

단일 데이터 세트의 비모노톤 입방 보간(빨간색) 및 모노톤 입방 보간(파란색)을 보여주는 예.

모노톤 보간술은 결과 에르미트 스플라인에 단조성을 보장하기 위해 탄젠트 m ${\$이 수정된 입방체 헤르미트 스플라인을 사용하여 수행할 수 있다.

모노톤 5중주형 헤르미트 보간술에 알고리즘도 사용할 수 있다.

보간선정

각 데이터 점에 대해 보간 접선을 선택하는 방법에는 여러 가지가 있다.이 절에서는 Fritsch-Carlson 방법의 사용에 대해 개략적으로 설명한다.알고리즘의 패스는 하나만 있으면 된다는 점에 유의하십시오.

$데이터{\displaystyle }$${\displaystyle {점}_{}}$을 k = ${\displaystyle 1}$,${\displaystyle }$…${\displaystyle n}$ ${\displaystyle$$(x_{k},$$y_{k$$}})$의 정렬된 순서로 색인화하도록$$ 한다$.$

1. 연속된 점 사이의 등차선 기울기를 계산한다.

   ${\displaystyle \property_{k}={\frac {y_{k+1}-y_{k}{x_{k+1}-x_{k}}}}}}}}}}$

   $k{\displaystyle }$= ${\displaystyle 1}$,${\displaystyle }$…의 경우 -${\displaystyle 1}${\$displaystyle$k=$1,\,\\display \,n-1$
   
   
2. 이러한 임무는 잠정적이며 나머지 단계에서 대체될 수 있다.모든 내부 데이터 포인트의 접선을 세컨트의 평균으로 초기화한다.

   ${\displaystyle m_{k}={\frac {\frac _{k-1}+\properties _{k}{2}}}$

   $k{\displaystyle }$= ${\displaystyle 2}$,${\displaystyle }$…의 경우$,$ ${\displaystyle \mathrm{n}}$- 1 {\$displaystyle$ k=2$,\,\displays \,n-1$
   
   엔드포인트의 경우 단측 차이를 사용하십시오.

   ${\displaystyle m_{}}$ ${\displaystyle {1\mathrm{}}_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle \text{1}}$과 ${\displaystyle m_{}}$ ${\displaystyle n{}_{}}$= ${\displaystyle {}_{}}$ n${\displaystyle {}_{}}$- ${\displaystyle 1_{}}$ $displaystyle m_{1}=\cHB _{$1}=\$cHB _{n}=\cHB _{$n1$}\,}$.

   $\Delta {\displaystyle {}_{}}$ ${\displaystyle {\mathrm{k}}_{}}$- 1 ${\$$}$ 및 ${\displaystyle {\Delta k}_{}}${\$displaystyle \delta _{$k}}이(가) 반대 기호를 갖는$$ 경우 ${\displaystyle \mathrm{m}}$ $k{\displaystyle {}_{}}$= 0${\displaystystyle m_{k$}=0$}$을 설정하십시오$.$
   
   
3. $k{\displaystyle }$= ${\displaystyle 1}$,${\displaystyle }$… n - ${\displaystyle 1}$ ${\displaystyle k=1,\,\dots \,n-1}$의 경우$,$ 여기서 ${\displaystyle {\Delta k}_{}}$= ${\displaystyle 0}$ ${\displaystyle \delta _{k}=0}($여기서 연속적인 두 ${\displaystyle {개}_{}}$의${\displaystyle {}_{}}$y = y ${\displaystyle {\mathrm{k}}_{}}$ +${\displaystyle {}_{}}$1 ${\$+1$}:{k$+1}이 동일$$))
   $set{\displaystyle {}_{}}$ m ${\displaystyle k_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle k_{}}$+ ${\displaystyle 1_{}}$= ${\displaystyle 0,}$ ${\displaystyle m_{k}=m_{k+1}=0,}$을(를) 설정하십시오. 단조성을 보존하려면 이 점들을 연결하는 스플라인들이 평평해야 하기 때문이다$$.
   해당 $k{\displaystyle }$ ${\$에 대해 4단계와 5단계를 무시하십시오$.$
   
   
4. 내버려두다

   ${\displaystyle {\alpha }_{}}$ ${\displaystyle k_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle k_{}}$ /${\displaystyle {}_{}\Delta {}_{}}$ ${\displaystyle k_{}}$ ${\displaystyle \text{및}{}_{}}$ ${\displaystyle {\beta }_{}}$ k${\displaystyle {}_{}}$= ${\displaystyle {\mathrm{m}}_{}}$ ${\displaystyle k_{}}$+ 1 /${\displaystyle {}_{}\Delta {}_{}}$ ${\displaystyle k_{}}$ ${\$}=m_${k+1}/{k$

   $\alpha {\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$ 또는$$ $\beta {\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$ 중 하나가 음수인$$ 경우 입력 데이터 포인트가 엄격히 단조롭지 않고${\displaystyle }$( ${\displaystyle x_{}}$ ${\displaystyle {}_{}}$, ${\displaystyle y{}_{}}$ ${\displaystyle k_{}}$) ${\displaystystyle (x_{k},$y_{$k}}}}}}}}}}}})$은 국부극이다$$.만약β k<>비록 엄격한 monotonicity 전 세계적으로 가능하지 않다 그런 경우에, piecewise 단조로운 곡선 여전히α k<>)0{\displaystyle m_{k}=0\,};0{\displaystyle \alpha_{k}< mk을 선택하여;0}또는 m k+1=0{\displaystyle m_{k+1}=0\,};0{\displaystyle \beta_{k}<. 0}일 경우, 발생할 수 있다..
   
   
5. 오버슈트를 방지하고 단조로움을 보장하려면 다음 세 가지 조건 중 하나 이상을 충족해야 한다.

(a) 함수

${\displaystyle \phi _{k}=\alpha _{k}-{\frac {(2\alpha _{k}+\beta _{k}-3)^{2}}{3(\alpha _{k}+\beta _{k}-2)}}>0\,}$, or

(b) ${\displaystyle {\alpha k}_{}}$+ ${\displaystyle 2}$ ${\displaystyle {}_{}}$ ${\displaystyle k_{}}$- ${\displaystyle 3}$ ${\displaystyle ∆}$ ${\displaystyle 0}$ ${\$}-$3\$leq 0\,}$$또는

(c) $2{\displaystyle \mathrm{}}$ ${\displaystyle {\alpha k}_{}}$+ ${\displaystyle {\beta }_{}}$ k${\displaystyle {}_{}}$- ${\displaystyle 3}$${\displaystyle \le }$ ${\displaystyle 0}$ ${\$

엄격한 단조성을 보장할 수 있는 조건(a)만 ${\displaystyle {충분}_{}}$하다. {$$k {\$displaystyle \pi _{$k}}은(는$$) 양수여야 한다.

이 제약을 충족시키는 한 가지 간단한 방법은 벡터$({\displaystyle {\alpha k}_{}}$ ,${\displaystyle {}_{}\beta {}_{}}$ ${\displaystyle k_{}}$) ${\displaystyle(\alpha _{k}\,\beta _{k}})$을 반경 3의 원으로 제한하는$$ 것이다.즉, + > 9 ${\$ 그리고 나서 설정한다.

${\displaystyle {\tau k}_{}}$= ${\displaystyle 3\frac{\mathrm{}}{}}$ ${\displaystyle \frac{\sqrt{{\alpha k}_{}^{}}}{}}$ ${\displaystyle \frac{\sqrt{{}_{}^{}}}{}}$+ ${\displaystyle \frac{\sqrt{{}_{}^{}}}{}}$ ${\displaystyle \frac{\sqrt{{\mathrm{}}_{}^{}}}{}}$ ${\displaystyle \frac{\sqrt{2_{}^{}}}{}}$ $displaystyle \tau _{k}={$k}={\$frac {3}{\sqrt {\}{k}^{2}+\i1}{k}^{2$

다음을 통해 접선의 크기를 조정하십시오.

${\displaystyle m_{k}=\tau _{k}\,\alpha _{k}\,\delta _{k}\quad {\text{ and }}\quad m_{k+1}=\tau _{k}\,\beta _{k}\,\delta _{k}\,}$.

만약 α k>≤ 3{\displaystyle \alpha_{k}\leq 3}과β k≤ 3{\displaystyle \beta_{k}\leq 3\,}. 이것을 완수하면 또는 그것 α k를 제한하는 3또는β k>3{\displaystyle \alpha_{k}>, 3{\text{또는}}\beta _{k}>, 3\,}, 그때 mk을 세웠다) 충분한 3δ k{\displaystyle m_{k}=3\,\delta$_{k}\,}$.

입방 보간법

위의 사전 처리 후 보간된 스플라인 평가는 데이터 ${\displaystyle x_{}}$ k ${\$ ${\displaystyle y_{}}$ k ${\$$displaystyle$ $y_{k$$$ $displaystyle m_{k}$를 $사용$하여 입방형 헤르미테 스플라인에 해당한다$.$

To evaluate at ${\displaystyle x}$, find the index ${\displaystyle k}$ in the sequence where ${\displaystyle x}$, lies between ${\displaystyle x_{k}}$, and ${\displaystyle x_{k+1}}$, that is: ${\displaystyle x_{k}\leq x\leq x_{k+1}}$. Calculate

${\displaystyle \Delta =x_{k+1}-x_{k}\quad {\text{\}}\quad t={\frac {x-x_{k}}{\Delta }}}}}$

보간된 값은

${\displaystyle f_{\text{interpolated}}(x)=y_{k}\cdot h_{00}(t)+\Delta \cdot m_{k}\cdot h_{10}(t)+y_{k+1}\cdot h_{01}(t)+\Delta \cdot m_{k+1}\cdot h_{11}(t)}$

여기서 $h{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$는 입방체 헤르미테 스플라인에 대한 기본 함수다$$.

구현 예

다음의 자바스크립트 구현은 데이터 세트를 취하고 단조 입방 스플라인 보간 함수를 생성한다.

/* 모노톤 입방 스플라인 보간법 사용 예제: var f = 생성보간체([0, 1, 2, 3, 4], [0, 1, 4, 9, 16]),; var 메시지 = '; (var x = 0; x <= 4; x += 0.5)에 대해 { var x제곱 = f(x); 메시지 += x + '의 제곱은 ' + x제곱 + '\n'에 대한 것이다. } 경보(경보); */ 시합을 하다 인터폴란트를 창조하다 = 기능을 하다(xs, ys) {  시합을 하다 i, 길이 = xs.길이;    // 길이 문제 처리  만일 (길이 != ys.길이) { 던지다 'xs와 ys의 등수가 필요하다.'; }  만일 (길이 === 0) { 돌아오다 기능을 하다(x) { 돌아오다 0; }; }  만일 (길이 === 1) {   // 연루 : 결과를 미리 계산하면 나중에 ys가 변이될 경우 문제가 발생하지 않고 ys의 쓰레기 수거가 허용된다.   // 포함:단항 플러스 값을 숫자로 적절하게 변환   시합을 하다 결과 = +ys[0];   돌아오다 기능을 하다(x) { 돌아오다 결과; };  }    // xs와 ys를 정렬하도록 재정렬  시합을 하다 색인 = [];  을 위해 (i = 0; i < 길이; i++) { 색인.밀다(i); }  색인.분류하다(기능을 하다(a, b) { 돌아오다 xs[a] < xs[b] ? -1 : 1; });  시합을 하다 올드엑스 = xs, 올드시스 = ys;  // 포함: 새 어레이를 생성하면 나중에 입력 어레이가 변질될 경우에도 문제가 발생하지 않음  xs = []; ys = [];  // 포함:단항 플러스 값을 숫자로 적절하게 변환  을 위해 (i = 0; i < 길이; i++) { xs.밀다(+올드엑스[색인[i]]); ys.밀다(+올드시스[색인[i]]); }    // 연속적인 차이 및 경사 확보  시합을 하다 난잡하게 하다 = [], dxs. = [], ms = [];  을 위해 (i = 0; i < 길이 - 1; i++) {   시합을 하다 dx = xs[i + 1] - xs[i], dy = ys[i + 1] - ys[i];   dxs..밀다(dx); 난잡하게 하다.밀다(dy); ms.밀다(dy/dx);  }    // 도-1 계수 가져오기  시합을 하다 c1s = [ms[0]];  을 위해 (i = 0; i < dxs..길이 - 1; i++) {   시합을 하다 m = ms[i], mNext = ms[i + 1];   만일 (m*mNext <= 0) {    c1s.밀다(0);   } 다른 {    시합을 하다 dx_ = dxs.[i], dx다음 = dxs.[i + 1], 통상의 = dx_ + dx다음;    c1s.밀다(3*통상의/((통상의 + dx다음)/m + (통상의 + dx_)/mNext));   }  }  c1s.밀다(ms[ms.길이 - 1]);    // 도-2 및 도-3 계수 가져오기  시합을 하다 c2s = [], c3s = [];  을 위해 (i = 0; i < c1s.길이 - 1; i++) {   시합을 하다 c1 = c1s[i], m_ = ms[i], 인벡스 = 1/dxs.[i], 공통_ = c1 + c1s[i + 1] - m_ - m_;   c2s.밀다((m_ - c1 - 공통_)*인벡스); c3s.밀다(공통_*인벡스*인벡스);  }    // 보간물 기능 반환  돌아오다 기능을 하다(x) {   // 데이터 집합에서 가장 오른쪽 점은 정확한 결과를 제공해야 함   시합을 하다 i = xs.길이 - 1;   만일 (x == xs[i]) { 돌아오다 ys[i]; }      // x가 원래 xs 중 하나일 경우 해당 y를 반환하는 x in 간격 검색   시합을 하다 낮은 = 0, 중앙의, 높은 = c3s.길이 - 1;   하는 동안에 (낮은 <= 높은) {    중앙의 = 수학.마루를 깔다(0.5*(낮은 + 높은));    시합을 하다 xHERE = xs[중앙의];    만일 (xHERE < x) { 낮은 = 중앙의 + 1; }    다른 만일 (xHERE > x) { 높은 = 중앙의 - 1; }    다른 { 돌아오다 ys[중앙의]; }   }   i = 수학.맥스.(0, 높은);      // 보간   시합을 하다 산산이 흩어지다 = x - xs[i], diffSq = 산산이 흩어지다*산산이 흩어지다;   돌아오다 ys[i] + c1s[i]*산산이 흩어지다 + c2s[i]*diffSq + c3s[i]*산산이 흩어지다*diffSq;  }; }; 

참조

• Fritsch, F. N.; Carlson, R. E. (1980). "Monotone Piecewise Cubic Interpolation". SIAM Journal on Numerical Analysis. SIAM. 17 (2): 238–246. doi:10.1137/0717021.
• Dougherty, R.L.; Edelman, A.; Hyman, J.M. (April 1989). "Positivity-, monotonicity-, or convexity-preserving cubic and quintic Hermite interpolation". Mathematics of Computation. 52 (186): 471–494. doi:10.2307/2008477.

외부 링크

• GPLv2 라이센스 C++ 구현:MonotCubicInterpolator.cpp MonotCubicInterpolator.hpp