클렌쇼 알고리즘

수치해석에서는 클렌쇼합계라고도 하는 클렌쇼 알고리즘은 체비셰프 다항식의 선형 결합을 평가하는 재귀적 방법이다.^[1][2]이 방법은 1955년 찰스 윌리엄 클린쇼에 의해 출판되었다.호너의 단수형 선형 결합 평가법을 일반화한 것이다.

그것은 체비셰프 다항식에만 적용되는 것이 아니라, 3개월의 재발 관계에 의해 정의될 수 있는 어떤 종류의 기능에도 적용된다.^[3]

클렌쇼 알고리즘

완전한 일반성에서, Clenshaw 알고리즘은 유한 계열 함수 $functionsk{\displaystyle {}_{}}$ (${\displaystyle {}_{}x}$) ${\displaystyle \pi _{k}(x)}$의 가중 합계를 계산한다$.$

${\displaystyle S(x)=\sum _{k=0}^{n}a_{k}\phi _{k}(x)}$

여기서 ${\displaystyle {\varphi k}_{}}$, ${\displaystyle k}$= ${\displaystyle 0}$, ${\displaystyle 1}$,${\displaystyle }$… ${\displaystyle \phi _{k}\;k=0,1,\ldots$}은$($는) 선형 반복 관계를 만족하는 함수의 순서다.

${\displaystyle \phi \phi_{k+1}(x)=\phi_{k}(x)\,\phi_{k-1}(x),}$

여기서$$ 계수 ${\displaystyle {\alpha k}_{}x}$) ${\displaystyle \alpha$ \alpha $_{k}(x)}$ 및 $\beta {\displaystyle {}_{}}$ ${\displaystyle k_{}x}$) ${\displaystyle \beta _{k}(x)}$을(를) 미리 알 수 있다$$.

알고리즘은 ${\displaystyle {\varphi k}_{}x}$) ${\displaystyle \phi _{k$$}(x$$)}$이(가) 직접 계산하기 복잡한 함수일$$ 때 가장 유용하지만 ${\displaystyle {\alpha k}_{}x)}$ ${\displaystyle$ $\$$alpha$ $_{$$k}(x)$와 $)$가$$특히 $단순$하다.가장 일반적인 애플리케이션에서 $\alpha {\displaystyle (}$ ${\displaystyle x}$) ${\displaystyle \alpha(x)}$은(는) $k{\displaystyle }$ ${\displaystyle k}$에 종속되지 않으며$$$,$ $\beta {\displaystyle }$ ${\displaystyle \beta }$은(는) $x{\displaystyle }$ ${\$$displaystystyle x$$}$도 k$}$에도 종속되지 않는 상수입니다$.$

${\displaystyle {지정}_{}}$된 일련의 계수를 $0{\displaystyle {}_{}}$ ,${\displaystyle }$… ,${\displaystyle {}_{}{n\mathrm{}}_{}}$ ${\$ldots ,$a_{n}}}$에 ${\displaystyle {}_{}}$ 합계를 수행하려면 "역방향" 반복 공식으로$$ $값{\displaystyle {}_{}}$ ${\displaystyle b_{}}$ k${\displaystyle {}_{}}$(${\displaystyle x}$ $){\displaystyle b_{k}(x)$를 계산하십시오$.$

${\displaystyle {\regated}b_{n+1}b_{n+1}(x)&=b_{n+2}(x)=0,\\b_{k}(x)&=a_{k}+}\,b_{k+1}(x)+\,b_{k+1}(x)_{k+2(x).\end{정렬}}}$

$이{\displaystyle {}_{}}$ 계산은 함수 ${\displaystyle \mathrm{\varphi k}{}_{}}$(${\displaystyle }$x )$${\$displaystyle \phi$ _${k$${\displaystyle {}_{}}$$x)}$을(를) 직접 참조하지 않는다는${\displaystyle 점}$에 유의하십시오$.$ b 2 ( x ) {\displaystyle $b_{2}($${\displaystyle x}$$)}$와 $b{\displaystyle {}_{}{1\mathrm{}}_{}}$ ($$x${\displaystyle )}$ {\$displaystyle b_{1}(x$을 계산한 후 원하는 합을 $\varphi {\displaystyle {}_{}}$ 0${\displaystyle {}_{}}$($x$$)$과 가장 단순한 함수로서 표현할 수 있다.$\phi _{0}(x)}$ 및$$ $and{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}x}$) ${\displaystyle \phi _{1}(x)}$:

${\displaystyle S(x)=\phi _{0}(x)\,a_{0}+\phi _{1}(x)\,b_{1}(x)+\{1}(x)\,\phi _{0}(x)\,b_{2}(x).}$

자세한 정보 및 안정성 분석은 Fox와 Parker를^[4] 참조하십시오.

예

클렌쇼의 특별한 경우로서 호너

특히 간단한 경우는 양식의 다항식을 평가할 때 발생한다.

${\displaystyle \underset{}{\overset{}{S}}}$( ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle \underset{}{\overset{}{}}}$ k${\displaystyle \underset{}{\overset{}{}}}$= ${\displaystyle \underset{}{\overset{}{0}}}$ ${\displaystyle \underset{}{\overset{}{}}}$ a ${\displaystyle \underset{}{\overset{}{}}{}_{}}$ ${\displaystyle x_{}}$ ${\displaystyle k^{}}$ ${\$

기능은 간단하다.

${\displaystyle {\regated}\phi _{0}(x)&=1,\\\phi _{k}=x^{k}=x\pi _{k-1}(x)\ended}}}}}}}}$

${\displaystyle \mathrm{그리고}}$ 재발 계수 $\alpha {\displaystyle (x}$ ${\displaystyle )}$= x ${\displaystyle \chd(x)=x}$ 및$$ $\beta {\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle \chd =0}$에 의해 생성된다$.$

이 경우, 합계를 계산하기 위한 반복 공식은 다음과 같다.

${\displaystyle b_{k}(x)=a_{k}+xb_{k+1}(x)}$

그리고, 이 경우, 합계는 간단하다.

${\displaystyle {S\mathrm{}}_{}}$( ${\displaystyle x}$)${\displaystyle }$= 0${\displaystyle {}_{}}$+ x ${\displaystyle {b\mathrm{}}_{}}$ ${\displaystyle {}_{}}$( ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle {b\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ (${\displaystyle {}_{}x}$) ${\displaystyle S(x)=a_{0}+xb_{1}(x)=b_{0}(x$

그게 바로 일반적인 호너의 방법이야

체비셰프 시리즈 특별 케이스

잘린 체비셰프 시리즈 고려

${\displaystyle p_{n}(x)=a_{0}+a_{1{}T_{1}(x)+a_{2}T_{2}(x)+\cdots +a_{n}T_{n}(x).}$

체비셰프 다항식의 재귀 관계에 있는 계수는 다음과 같다.

${\displaystyle \cHB(x)=2x,\cHB \cHB =-1,}$

초기의 조건으로

${\displaystyle T_{0}(x)=1,\quad T_{1}(x)=x.}$

따라서, 재발은 다음과 같다.

${\displaystyle b_{k}(x)=a_{k}+2xb_{k+1}(x)-b_{k+2}(x)}$

그리고 최종 합계는

${\displaystyle p_{n}(x)=a_{0}+xb_{1}(x)-b_{2}(x).}$

이를 평가하는 한 가지 방법은 한 단계 더 반복하여 계산하는 것이다.

${\displaystyle b_{0}=2a_{0}+2xb_{1}(x)-b_{2}(x),}$

(계수가₀ 두 배로 증가했다는 점에 유의) 그 다음

${\displaystyle p_{n}(x)={\frac {1}{1}{2}}\왼쪽[b_{0}(x)-b_{2}(x)\오른쪽]}$

타원형의 자오선 호 길이

클렌쇼 합계는 측지학적 용도에 광범위하게 사용된다.^[2]간단한 응용은 타원체 표면의 자오선 호 거리를 계산하기 위해 삼각계 시리즈를 합친 것이다.이것들이 그 형태를 띠고 있다.

${\displaystyle m(\theta )=C_{0}\theta +C_{1}\sin \theta +C_{2}\sin 2\theta +\cdots +C_{n}\sina .}$

초기 $C{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle \theta {}_{}}$ ${\displaystyle C_{0}\,\theta }$의 용어를 제외하고 나머지는 적절한 형식의 합이다.$\varphi {\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ (${\displaystyle \theta }$ )${\displaystyle }$= ${\displaystyle 죄}$ ${\displaystyle 0}$ ${\displaystyle }$= ${\displaystyle 죄}$ 0 = 죄 ${\displaystyle 0}$= ${\displaystyle 0}$ ${\displaystyle \pi _{0}(\theta )=\sin 0\theta =\sin$ 0$=0}$이기 때문에 선도적인 용어는 없다$.$

${\displaystyle \sin }$ ${\displaystyle }$ ${\displaystyle k}$ ${\displaystyle \theta }$ ${\displaystyle \sin k\theta}$에 대한 반복 관계는 다음과$$ 같다.

${\displaystyle \sin }$ ${\displaystyle }$ ${\displaystyle (k}$+ ${\displaystyle 1}$) ${\displaystyle \theta }$= 2 ${\displaystyle \cos \sin }$ ${\displaystyle \sin k}$- ${\displaystyle \sin }$ ${\displaystyle }$ ${\displaystyle (k}$- ${\displaystyle 1}$) ${\displaystyle \theta }$ ${\displaystyle \sin(k+1)\theta \sina$ -$\sin(k-1)\ta \cos$\sina $\},$ ,

재귀 관계에 계수 만들기

${\displaystyle \cHB(\theta )=2\cos \theta,\cos \theta,\cos \cos \cos \cos \cos \theet \$

그리고 이 시리즈의 평가는 다음과 같다.

${\displaystyle {\begin{aligned}b_{n+1}(\theta )&=b_{n+2}(\theta )=0,\\b_{k}(\theta )&=C_{k}+2\cos \theta \,b_{k+1}(\theta )-b_{k+2}(\theta ),\quad \mathrm {for\ } n\geq k\geq 1.\end{aligned}}}$

The final step is made particularly simple because ${\displaystyle \phi _{0}(\theta )=\sin 0=0}$, so the end of the recurrence is simply ${\displaystyle b_{1}(\theta )\sin(\theta )}$; the ${\displaystyle C_{0}\,\theta }$ term is added separately:

${\displaystyle m(\theta )=C_{0}\,\theta +b_{1}(\theta )\sin \theta .}$

알고리즘에는${\displaystyle \mathrm{trig}}$ ${\displaystyle \cos \cos \$${\displaystyle \mathrm{theta<img\; alt="\backslash cos\; \backslash theta"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/611e5c70de1d1cf4ebc3b70d2b5467f45d17a483"\; style="vertical-align:\; -0.338ex;\; width:4.589ex;\; height:2.176ex;"\; papago-attr-id="109">}\}}$ 및$$ $display$ {\$displaystyle$\sin \$theta}$의 두 삼각측량만 평가하면 된다는 점에 유의하십시오$.$

자오선 호 길이의 차이

때로는 높은 상대적 정확도를 유지하는 방식으로 두 자오선 호의 차이를 계산할 필요가 있다.이것은 삼각측량적 정체성을 사용하여 작성한다.

${\displaystyle m(\theta _{1}-m(\theta _{2})=C_{0}(\theta _{1}-\theta _{2})+\sum _{k=1}^{n}2C_{k}\sin {\bigl (}{\textstyle {\frac {1}{2}}}k(\theta _{1}-\theta _{2}){\bigr )}\cos {\bigl (}{\textstyle {\frac {1}{2}}}k(\theta _{1}+\theta _{2}){\bigr )}.}$

우리가 $동시$에 m ($θ$ ${\displaystyle {1\mathrm{}}_{}}$)${\displaystyle }$+ ${\displaystyle m}$ ($$ ${\displaystyle {2\mathrm{}}_{}}$)을 계산하고$$ 매트릭스 $합계$를 수행한다면, 이 경우에^[5] $클렌쇼$ 합계가 $적용$될 수 있다$.$

${\displaystyle {\mathsf {M}}(\theta _{1},\theta _{2})={\begin{bmatrix}(m(\theta _{1})+m(\theta _{2}))/2\\(m(\theta _{1})-m(\theta _{2}))/(\theta _{1}-\theta _{2})\end{bmatrix}}=C_{0}{\begin{bmatrix}\mu \\\1\end{bmatrix}+++_{k=1}^{n_{k}{\mathsf{F}{F}}(\teta _{1},\teta _{2}),}}$

어디에

${\displaystyle {\begin{aligned}\delta &={\textstyle {\frac {1}{2}}}(\theta _{1}-\theta _{2}),\\\mu &={\textstyle {\frac {1}{2}}}(\theta _{1}+\theta _{2}),\\{\mathsf {F}}_{k}(\theta _{1},\theta _{2})&={\begin{bmatrix}\cos k\delta \sin k\mu \\\displaystyle {\frac {\sin k\delta }{\delta }}\cos k\mu \end{bmatrix}}.\end{정렬}}}$

${\displaystyle {M\mathrm{}}_{}(}$ element 1, ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$)$${\$displaystyle {\mathsf{M}(\theta _{1},\theta _{2})$의 첫 번째 요소는 $m{\displaystyle }$ ${\displaystyle m}$의 평균 값이고$$$$ 두 번째 요소는 평균 기울기입니다.${\displaystyle {\mathsf{F}}_{}}$ ${\displaystyle k_{}}$ (${\displaystyle {}_{}{}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{\theta \mathrm{}}_{}}$ 2${\displaystyle {}_{}}$) ${\displaystyle {\mathsf {F}_{k}(\theta _{1},\theta _{2})$는 재발 관계를 만족한다$$.

${\displaystyle {\mathsf {F}}_{k+1}(\theta _{1},\theta _{2})={\mathsf {A}}(\theta _{1},\theta _{2}){\mathsf {F}}_{k}(\theta _{1},\theta _{2})-{\mathsf {F}}_{k-1}(\theta _{1},\theta _{2}),}$

어디에

${\displaystyle {\mathsf {A}}(\theta _{1},\theta _{2})=2{\begin{bmatrix}\cos \delta \cos \mu &-\delta \sin \delta \sin \mu \\-\displaystyle {\frac {\sin \delta }{\delta }}\sin \mu &\cos \delta \cos \mu \end{bmatrix}}}$

재발 관계에서$$ $\alpha {\displaystyle }$ ${\displaystyle \alpha }$을(를) 대신하고, $\beta {\displaystyle }$=${\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle \beta =-1}$을(를) 대신한다$.$표준 Clenshaw 알고리즘은 이제 수율에 적용될 수 있다.

${\displaystyle{\begin{정렬}{\mathsf{B}}_{n+1}&, ={\mathsf{B}}_{n+2}={\mathsf{0}},\\{\mathsf{B}}_{k}&amp을 말한다.=C_{k}{\mathsf{나는}}+{\mathsf{A}}{\mathsf{B}}_{k+1}-{\mathsf{B}}_{k+2},\qquad\mathrm{for\}n\geq k\geq 1,\\{\mathsf{M}}(\theta_{1},\theta_{2})&, =.C_{0}{\begin{bmatrix}\mu \\1\end{bmatrix}}+{\mathsf{B}}_{1}{\mathsf{F}}_{1}(\theta _{1},\t.헤타 _{2}),\end{aigned}}}$

여기서 $B{\displaystyle {\mathsf{}}_{}}$ ${\displaystyle k_{}}$ ${\$은(는) 2×2 행렬이다$$.드디어 우리가 가지게 되었다.

${\displaystyle {\frac(\theta _{1}-m)(\theta _{2}){\theta_{1}-\theta_{2}}={\mathsf{M}}{2}(\teta _{1},\ta _{2}).}$

This technique can be used in the limit ${\displaystyle \theta _{2}=\theta _{1}=\mu }$ and ${\displaystyle \delta =0\,}$ to simultaneously compute ${\displaystyle m(\mu )}$ and the derivative ${\displaystyle dm(\mu )/d\mu }$, provided that, in evaluating ${\displaystyle {\mathsf{F}}_1}$${\displaystyle {\mathsf{F}_{$$1$}$$및$$ $A{\displaystyle \mathsf{}}$ ${\$${\displaystyle \mathrm{mathsf}}${\mathsf{$A$$}},$${\displaystyle }$Δ = ${\displaystyle 1}$ ${\delta${\$delta \rightarrow$ 0$}(\sin \delta )/\delta$ =$1$

참고 항목

• 다항식을 단항식으로 평가하기 위한 호너 계획
• 다항식을 베지어 형태로 평가하는 데 카스텔자의 알고리즘

참조