삼각 보간법

수학에서 삼각 보간술은 삼각 다항식을 이용한 보간술이다. 보간술은 주어진 데이터 포인트를 통과하는 함수를 찾는 과정이다. 삼각 보간법의 경우 이 함수는 삼각 다항식, 즉 주어진 기간의 사인 및 코사인 합이 되어야 한다. 이 형태는 특히 주기적 기능의 보간술에 적합하다.

중요한 특별한 경우는 주어진 데이터 포인트의 간격이 동일할 때, 이 경우 솔루션은 이산 푸리에 변환에 의해 주어진다.

보간 문제의 공식화

도 K의 삼각 다항식에는 형태가 있다.

${\displaystyle p(x)=a_{0}+\sum _{k=1}a_{k}\cos(kx)+\sum _{k=1}b_{k}\sin(kx)\,}$

(1)

이 식에는 2K + 1 계수 a₀, a₁, … a_K, b₁, … b를_K 포함하며, 함수가 N 포인트를 통과하도록 계수를 계산하고자 한다.

${\displaystyle p(x_{n}=y_{n},\quad n=0,\ldots,N-1.\,}$

삼각 다항식은 주기 2㎛로 주기 때문에 N점들은 한 기간에 분산하여 주문할 수 있다.

${\displaystyle 0\leq x_{0}<x_{1}<x_{2}<\ldots <x_{N-1}<2\pi .\,}$

(일반적으로 이러한 점들이 동일한 간격으로 배치될 것을 요구하지는 않는다는 점에 유의하십시오.) 이제 보간 문제는 삼각 다항식 p가 보간 조건을 만족시키는 계수를 찾는 것이다.

복합 평면에서의 제형

문제는 복잡한 평면에서 공식화하면 더욱 자연스러워진다. 삼각 다항식의${\displaystyle \underset{}{\overset{}{공식}}}$을 $p{\displaystyle }$( ${\displaystyle x}$) = ${\displaystyle \underset{}{\overset{}{}}}$ k${\displaystyle \underset{}{\overset{}{}}}$=${\displaystyle \underset{}{\overset{}{}}}$- ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle c_{}}$ ${\displaystyle {}_{}{}^{}}$ ${\displaystyle e^{}}$ ${\displaystyle k^{}}$ ${\displaystyle x^{}}${\$displaystyle p(x)=\sum _{k=-K}^{K}c_{k}e^{ikx},},$ 여기서$$ 나는 가상의 단위다. z = e를^ix 설정하면

${\displaystyle q(z)=\sum _{k=-K}^{K}c_{k}z^{k}},\,}$

와 함께

${\displaystyle q(e^{ix})\vmxq p(x).\,}$

이것은 단위 원의 다항식 보간으로 삼각 보간 문제를 감소시킨다. 삼각 보간법의 존재와 고유성은 이제 다항 보간법의 해당 결과에서 즉시 나타난다.

복합 평면에서 삼각 보간 다항식의 공식화에 대한 자세한 내용은 푸리에 다항식을 사용한 보간 페이지 156을 참조하십시오.

문제 해결

위의 조건 하에서는 데이터 포인트의 수인 N이 다항식의 계수 수, 즉 N 2 2K+1(특정 데이터 포인트 집합에 따라 N>2K+1일 경우 해결책이 존재할 수도 있고 존재하지 않을 수도 있음)를 초과하지 않는 한 주어진 데이터 포인트 집합 {x_k, y}에_k 대한 해결책이 존재한다. 더욱이 보간 다항식은 조정 가능한 계수의 수가 데이터 포인트의 수와 동일한 경우에만 고유하다. 즉, N = 2K + 1. 이 글의 나머지 부분에서는 이 조건을 참으로 가정한다.

홀수 포인트 수

N점 수가 홀수인 경우, 복합 평면의 다항식 제형에 다항식 보간용 라그랑주 공식을 적용하여 용액이 양식으로 작성될 수 있음을 N=2K+1이라고 한다.

${\displaystyle p(x)=\sum _{k=0}^{2K}y_{k}\,t_{k}(x),}$

(5)

어디에

${\displaystyle t_{k}(x)=e^{-iKx+iKx_{k}\prod _{m=0,m\neq k}^{2K}{\e^{ix}-e^{ix_}}}{e^{e^{ix_{k-e-e^{ix_{m}}}}}}}}}}}}}}}.}$

이 공식의$$ 인자 e${\displaystyle {}^{}}$- i ${\displaystyle K^{}}$ x${\displaystyle {}^{}}$+ i ${\displaystyle K^{}}$ ${\displaystyle {x_{}}^{}}$ $k {\$ e$^{-iKx+iKx_{k}}$는 복합 평면 제형이 e ${\displaystyle i^{}}$ ${\displaystyle x^{}}$ ${\$ e$^{ix}}$의 음력도 포함하므로 $e$ ${\displaystyle x^{}}$ ${\$의 다항식이 아니라는 사실을 보상한다. ${\displaystyle {이}_{}}$ ${\displaystyle {표현식}_{}}$의 정확성은 t${\displaystyle {}_{}}$k( ${\displaystyle \mathrm{x}}$k${\displaystyle {}_{}}$)${\displaystyle }$= 1 {\$displaystyle t_${k}(x_${k})=1}$및 ${\displaystyle t_{}}$( ${\displaystyle x}$) ${\displaystyle t_{k}(x)$가 ${\displaystyle {ei}^{}}$ ${\displaystyle x^{}}$ ${\$ e$^{ix$의 오른쪽 힘을 선형 결합한 것임을$$ 확인하면 쉽게 확인할 수 있다.

${\displaystyle e^{iz_{1}-e^{2}}:=2i\sin \left\frac {z_{1}-z_{2}}:\right)e^{{{{1}{1}{1}:{1}:{1}{1}:{1}{1}:{2}},},},}$

(2)

계수 $t{\displaystyle {}_{}}$ ${\displaystyle k_{}}$( ${\displaystyle x}$) ${\displaystyle t_{k}(x)}$은(는) 형식으로 작성할 수 있다$$.

${\displaystyle t_{k}(x)=\prod _{m=0,m\neq k}^{2K}{\frac {\sin {1}{1}:{2}}(x-x_{m})}}{\sin {\frac {1}{1}:{2}}(x_{k}-x_{m}}}}}).}$

(4)

짝수 포인트 수

N개의 점이 짝수인 경우, 복합 평면의 다항식 제형에 다항식 보간용 라그랑주 공식을 적용하여 N=2K라고 하여 용액을 양식으로 작성할 수 있다.

${\displaystyle p(x)=\sum _{k=0}^{2K-1}y_{k}\,t_{k}(x),}$

(6)

어디에

${\displaystyle t_{k}(x)=e^{-iKx+iKx_{k}}{\frac {e^{ix}-e^{i\alpha _{k}}}{e^{ix_{k}}-e^{i\alpha _{k}}}}\prod _{m=0,m\neq k}^{2K-1}{\frac {e^{ix}-e^{ix_{m}}}{e^{ix_{k}}-e^{ix_{m}}}}.}$

(3)

여기서는 상수 ${\displaystyle {\alpha k}_{}}$ ${\$를 자유롭게 선택할 수 있다$$. 이는 보간함수(1)에 알 수 없는 상수가 홀수 포함되어 있기 때문에 발생한다. A common choice is to require that the highest frequency is of the form a constant times ${\displaystyle \cos(Kx)}$, i.e. the ${\displaystyle \sin(Kx)}$ term vanishes, but in general the phase of the highest frequency can be chosen to be ${\displaystyle \varphi _{K}}$. To get an expression for ${\displaystyle {\alpha }_{}}$ ${\displaystyle k_{}}$ ${\$ (3)을 양식에 쓸 수 있는 것을 (2)를 사용하여 얻는다.

${\displaystyle t_{k}(x)={\frac {\cos \left(Kx-{\frac {1}{2}}\alpha _{k}+{\frac {1}{2}}\sum \limits _{m=0,m\neq k}^{2K-1}x_{m}\right)+\sum \limits _{m=-(K-1)}^{K-1}c_{k}e^{imx}}{2^{N}\sin({\frac {x_{k}-\alpha _{k}}{2}})\prod \limits _{m=0,m\neq k}^{2K-1}\sin({\frac {x_{k}-x_{m}}{2}})}}.}$

이것은 생산된다.

${\displaystyle \alpha _{k}=\sum _{m=0,m\neq k}^{2K-1}x_{m}-2\varphi _{K}}}}$

그리고

${\displaystyle t_{k}(x)={\frac {\sin {\frac {1}{2}}(x-\alpha _{k})}{\sin {\frac {1}{2}}(x_{k}-\alpha _{k})}}\prod _{m=0,m\neq k}^{2K-1}{\frac {\sin {\frac {1}{2}}(x-x_{m})}}{\sin {\frac {1}{1}:{2}}(x_{k}-x_{m}}}}}).}$

분모에서 0으로 인한 불의를 방지하기 위해 주의를 기울여야 한다.

등거리 노드

노드 $x{\displaystyle {}_{}}$ ${\displaystyle m_{}}$ ${\$이(가) 등거리일$$ 경우, 즉, 문제의 추가적인 단순화가 가능하다.

${\displaystyle x_{m}={\frac {2\pi m}{N},}$

자세한 내용은 지그문트를 참조하십시오.

홀수 포인트 수

(4)를 사용함으로써 더 단순화하는 것은 명백한 접근법이 될 수 있지만, 분명히 관련되어 있다. 훨씬 간단한 접근법은 디리클레 커널을 고려하는 것이다.

${\displaystyle D(x,N)={\frac {1}{N}}+{\frac {2}{N}}\sum _{k=1}^{{\frac {1}{2}}(N-1)}\cos(kx)={\frac {\sin {\frac {1}{2}}Nx}{N\sin {\frac {1}{2}}x}},}$

서 N> ${\displaystyle N>0}$은(는) 홀수다. $D{\displaystyle (x}$, ${\displaystyle N}$) ${\displaystyle D(x,N)}$이(가) ${\displaystyle {ei}^{}}$ ${\displaystyle x^{}}$ ${\$ e$^{ix}}$의 오른쪽 힘을 선형적으로 조합하여$$ 충족함을 쉽게 알 수 있다.

${\displaystyle D(x_{m},N)={\begin{case}0{\text{{}{{}m\neq 0\\1\{\text}{{}}{}}}{}m=0\end{case}}}}.}$

이 두 속성은 (5)에서 계수 t $k{\displaystyle {}_{}}$( ${\displaystyle x}$) ${\displaystyle t_{k}(x)}$을(를) 고유하게 정의하기 때문에 다음과 같다.

${\displaystyle{\begin{정렬}())&, =D(x-x_{k},N)={\begin{경우}{\frac{\sin{\frac{1}{2}}N(x-x_{k})}{N\sin{\frac{1}{2}}(x-x_{k})}}{\text{에}}_{x\to 0}{\frac{\sin{\frac{1}{2}}Nx}{N\sin{\frac{1}{2}}x}}=1{\text{에}}x=x_{k}\end{경우}}\\&, ={\frac{\mathrm{sinc}\,{\frac{1}{2}}N(x-x_{k})}{{\mathrm 시 x_{k}\\\lim \limits x\neq.nc}\,{)frac {1}{1}:{2}}(x-x_{k}}).\end{정렬}}}$

여기서 sinc-함수는 어떤 특이점도 방지하고 정의된다.

${\displaystyle \mathrm {sinc} \,x={\frac {\sin x}{x}}.}$

짝수 포인트 수

$N{\displaystyle }$ ${\displaystyle N}$의 경우에도 Dirichlet 커널을 다음과 같이 정의함

${\displaystyle D(x,N)={\frac {1}{N}}+{\frac {1}{N}}\cos {\frac {1}{2}}Nx+{\frac {2}{N}}\sum _{k=1}^{{\frac {1}{2}}N-1}\cos(kx)={\frac {\sin {\frac {1}{2}}Nx}{N\tan {\frac {1}{2}}x}}.}$

다시 말하지만, $D{\displaystyle (x}$,${\displaystyle N}$ ) ${\displaystyle$ D$(x,N)}$은(는) ${\displaystyle {\mathrm{ei}}^{}}$x {\$displaystyle e$^{ix$}}$의 오른쪽 힘을 선형 결합한 것으로$,$ ${\displaystyle \sin }$ 1${\displaystyle \mathrm{2N}}$ x ${\displaystyle \sin{1}{$2}}$Nx}$라는 용어를 포함하지 않고$$ 충족함을 쉽게 알 수 있다.

${\displaystyle D(x_{m},N)={\begin{case}0{\text{{}{{}m\neq 0\\1\{\text}{{}}{}}}{}m=0\end{case}}}}.}$

이러한 속성을 사용하여 (6)의 계수 t $k{\displaystyle {}_{}}$( ${\displaystyle x}$) ${\displaystyle t_{k}(x)}$에 다음이 주어진다.

${\displaystyle {\begin{aligned}t_{k}(x)&=D(x-x_{k},N)={\begin{cases}{\frac {\sin {\frac {1}{2}}N(x-x_{k})}{N\tan {\frac {1}{2}}(x-x_{k})}}{\text{ for }}x\neq x_{k}\\\lim \limits _{x\to 0}{\frac {\sin {\frac {1}{2}}Nx}{N\tan {\frac {1}{2}}x}}=1{\text{ for }}x=x_{k}.\end{case}\\&={\frac {\mathrm {sinc} \,{\frac {1}{1}{1}{1}{2}}: {\frac {1}{1}(x-x_{k}}}}}}}}}}}}{prac {1}:{2}}(x-{k}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

$t{\displaystyle {}_{}}$ ${\displaystyle k_{}}$( ${\displaystyle x}$) ${\displaystyle t_{k}(x)}$에는 ${\displaystyle \sin }$ ${\displaystyle }$ 1 ${\displaystyle \frac{2}{}}$ ${\displaystyle N}$ ${\displaystyle x}$ ${\displaystyle \sin {\frac {1}{2}}Nx}$도 포함되어 있지$$ 않다는 점에 유의하십시오. 마지막으로, ${\displaystyle \mathrm{함수}}$ sin${\displaystyle \frac{2}{}}$ 1 ${\displaystyle 2}$ ${\displaystyle N}$ x$${\$displaystyle$$\sin${\$frac$ {$1$$}{$2$}}$$Nx}$는 모든 $x{\displaystyle {}_{}}$ m $지점$에서 소멸된다는$$ 점에 유의하십시오$.$ 따라서 이 용어의 배수는 항상 추가될 수 있지만 일반적으로 제외된다.

실행

위의 MATLAB 구현은 여기에서 확인할 수 있으며, 다음을 통해 제공된다.

function P = triginterp(xi,x,y) % TRIGINTERP Trigonometric interpolation. % Input: %   xi  evaluation points for the interpolant (vector) %   x   equispaced interpolation nodes (vector, length N) %   y   interpolation values (vector, length N) % Output: %   P   values of the trigonometric interpolant (vector) N = length(x); % Adjust the spacing of 주어진 독립 변수 h = 2/N, 척도 = (x(2)-x(1)) / h, x = x/척도, xi = xi/척도, % 보간물 평가. P = zeros(size(xi)); for k = 1:N  P = P + y(k)*trigcardinal(xi-x(k),N); end function tau = trigcardinal(x,N) ws = warning('off','MATLAB:divideByZero'); % Form is different for even and odd N. if rem(N,2)==1 % odd  tau = sin(N*pi*x/2) ./ (N*sin(pi*x/2)); else % even  tau = sin(N*pi*x/2) ./ (N*tan(pi*x/2)); end warning(ws) tau(x==0) = 1; % fix value x=0으로 

이산 푸리에 변환과의 관계

x점이_n 균등하게 간격을 두는 특별한 경우는 특히 중요하다. 이 경우 우리는 다음과 같은 조치를 취하였다.

${\displaystyle x_{n}=2\pi {\frac {n}{N}},\qquad 0\leqn<N.}$

데이터 포인트 y를_n 계수 a_k, b에_k 매핑하는 변환은 순서 N의 이산 푸리에 변환(DFT)에서 얻는다.

${\displaystyle Y_{k}=\sum _{n=0}^{{N-1}y_{n}\ e^{-i2\pi {\frac {nk}{N}}\,},}$

${\displaystyle y_{n}=p(x_{n})={\frac {1}{1}{{N}\sum _{k=0}^{N-1}Y_{k}\ e^{i2\pi {\frac {nk}}}\,},}$

(위에서 문제가 공식화된 방식 때문에, 우리는 홀수 숫자의 점으로 제한해 왔다. 이것은 꼭 필요한 것은 아니다; 짝수 점수의 경우, 나이키스트 주파수에 해당하는 또 다른 코사인 용어를 포함한다.

균일한 간격의 점들에 대한 코사인 전용 보간법의 경우는, 점들이 일정한 대칭을 가지고 있을 때 삼각 보간법에 해당하며, 1754년에 알렉시스 클레라우에 의해 처리되었다. 이 경우 솔루션은 이산 코사인 변환과 동일하다. 홀수 대칭에 해당하는 균일한 간격의 점들에 대한 사인 전용 확장은 1762년 Joseph Louis Lagrange에 의해 해결되었으며, 그 해법은 이산 사인 변환이다. DFT를 발생시키는 완전한 코사인 및 사인 보간 다항식은 1805년경 미발표 작품에서 칼 프리드리히 가우스에 의해 해결되었고, 그 시점에서 그는 또한 빠른 푸리에 변환 알고리즘을 도출하여 그것을 신속하게 평가하였다. 클레라우트, 라그랑주, 가우스 모두 유한한 관측 지점에서 행성, 소행성 등의 궤도를 유추하는 문제를 연구하는 데 관심을 가졌다. 궤도는 주기적이기 때문에 삼각 보간법은 당연한 선택이었다. 하이데만 외 연구진(1984)도 참조한다.

수치 컴퓨팅에서의 응용 프로그램

기능을 가진 컴퓨팅을 위해 MATLAB에 작성된 완전 통합 소프트웨어 시스템인 Cebfun은 삼각 보간과 주기적인 기능을 가진 컴퓨팅을 위해 푸리에 확장을 사용한다. 삼각 보간과 관련된 많은 알고리즘은 체브펀에서 쉽게 구할 수 있다. 여기에는 몇 가지 예가 있다.

참조

• 켄달 E. 앳킨슨, 수치해석에 대한 소개(2판), 섹션 3.8. 1988년 뉴욕, 존 와일리 & 선즈. ISBN0-471-50023-2.
• M. T. Heideman, D. H. Johnson, C. S. Burrus, "가우스와 빠른 푸리에 변환의 역사," IEEE ASSP 매거진 1 (4), 14–21 (1984).
• G.B. 라이트, M. 자베드, H. 몬타넬리, L.N. Trefethen, "Chebfun을 주기적인 함수로 확장," SIAM. J. Sci. 계산, 37(2015), C554-C573
• A. 지그문트, 삼각계 시리즈, 제2권, X장, 캠브리지 대학 출판부, 1988.

외부 링크

• www.chebfun.org