クレンショーアルゴリズム

数値解析において、クレンショウアルゴリズム（クレンショウ和とも呼ばれる）は、チェビシェフ多項式の線形結合を評価する再帰的な手法である。^{[ 1 ] [ 2 ]}この手法は、1955年にチャールズ・ウィリアム・クレンショウ によって発表された。これは、単項式の線形結合を評価するホーナー法の一般化である。

これはチェビシェフ多項式だけでなく、3項再帰関係で定義できるあらゆる関数のクラスに一般化されます。^{[ 3 ]}

クレンショーアルゴリズム

完全に一般化すると、Clenshaw アルゴリズムは、関数の有限級数の加重和を計算します。 ここで、 係数とが事前にわかっている 線形再帰関係を満たす関数のシーケンスです 。${\displaystyle \phi _{k}(x)}$ $${\displaystyle S(x)=\sum _{k=0}^{n}a_{k}\phi _{k}(x)}$$ ${\displaystyle \phi _{k},\;k=0,1,\ldots }$ $${\displaystyle \phi _{k+1}(x)=\alpha _{k}(x)\,\phi _{k}(x)+\beta _{k}(x)\,\phi _{k-1}(x),}$$ ${\displaystyle \alpha _{k}(x)}$ ${\displaystyle \beta _{k}(x)}$

このアルゴリズムは、 が直接計算するのが複雑な関数である一方、と は特に単純な関数である場合に最も有効です。最も一般的な応用では、は に依存せず、は にも にも依存しない定数です。 ${\displaystyle \phi _{k}(x)}$ ${\displaystyle \alpha _{k}(x)}$ ${\displaystyle \beta _{k}(x)}$ ${\displaystyle \alpha (x)}$ ${\displaystyle k}$ ${\displaystyle \beta}$ ${\displaystyle x}$ ${\displaystyle k}$

与えられた係数の系列の合計を実行するには、 「逆」再帰式によって 値を計算します。${\displaystyle a_{0},\ldots ,a_{n}}$ ${\displaystyle b_{k}(x)}$ $${\displaystyle {\begin{aligned}b_{n+1}(x)&=b_{n+2}(x)=0,\\b_{k}(x)&=a_{k}+\alpha _{k}(x)\,b_{k+1}(x)+\beta _{k+1}(x)\,b_{k+2}(x).\end{aligned}}}$$

この計算では関数を直接参照していないことに注意してください。とを計算した後、目的の和はそれらと最も単純な関数およびを用いて表すことができます。 ${\displaystyle \phi _{k}(x)}$ ${\displaystyle b_{2}(x)}$ ${\displaystyle b_{1}(x)}$ ${\displaystyle \phi _{0}(x)}$ ${\displaystyle \phi _{1}(x)}$ $${\displaystyle S(x)=\phi _{0}(x)\,a_{0}+\phi _{1}(x)\,b_{1}(x)+\beta _{1}(x)\,\phi _{0}(x)\,b_{2}(x).}$$

より詳しい情報と安定性の解析についてはFoxとParker ^{[ 4 ]}を参照してください。

例

クレンショーの特別なケースとしてのホーナー

特に単純なケースは、形式の多項式を評価するときに発生します 。 関数は単純に 、再帰係数およびによって生成されます。 $${\displaystyle S(x)=\sum _{k=0}^{n}a_{k}x^{k}.}$$ $${\displaystyle {\begin{aligned}\phi _{0}(x)&=1,\\\phi _{k}(x)&=x^{k}=x\phi _{k-1}(x)\end{aligned}}}$$ ${\displaystyle \alpha (x)=x}$ ${\displaystyle \beta =0}$

この場合、合計を計算するための漸化式は 、そしてこの場合、合計は単に、 通常のホーナー法とまったく同じです。 $${\displaystyle b_{k}(x)=a_{k}+xb_{k+1}(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 \alpha (x)=2x,\quad \beta =-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 b_{0}(x)=a_{0}+2xb_{1}(x)-b_{2}(x),}$$ $${\displaystyle p_{n}(x)={\tfrac {1}{2}}\left[a_{0}+b_{0}(x)-b_{2}(x)\right].}$$

合計の同等の表現は次のようになる。 $${\displaystyle p_{n}(x)=a_{0}+xb_{1}(x)-b_{2}(x).$$

楕円体上の子午線弧の長さ

クレンショウ和は測地学の分野で広く用いられている。^{[ 2 ]} 簡単な応用として、三角級数の和をとって楕円体表面上の 子午線弧距離を計算するものがある。これは以下の式で表される。$${\displaystyle m(\theta )=C_{0}\,\theta +C_{1}\sin \theta +C_{2}\sin 2\theta +\cdots +C_{n}\sin n\theta .}$$

初項を除けば、残りは適切な形式の和である。 であるため、初項は存在しない。 ${\displaystyle C_{0}\,\theta }$ ${\displaystyle \phi _{0}(\theta )=\sin 0\theta =\sin 0=0}$

の漸化式は${\displaystyle \sin k\theta }$ 、漸化式の係数を作成し 、 級数の計算は次のように行われます。 最後のステップは、 であるため特に簡単になり、漸化式の終わりは単に となり、項は別途追加されます。 $${\displaystyle \sin(k+1)\theta =2\cos \theta \sin k\theta -\sin(k-1)\theta ,}$$ $${\displaystyle \alpha_{k}(\theta)=2\cos\theta,\quad\beta_{k}=-1.}$$ $${\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{整列}}}$$ ${\displaystyle \phi _{0}(\theta )=\sin 0=0}$ ${\displaystyle b_{1}(\theta )\sin(\theta )}$ ${\displaystyle C_{0}\,\theta }$ $${\displaystyle m(\theta )=C_{0}\,\theta +b_{1}(\theta )\sin \theta .}$$

このアルゴリズムでは、2 つの三角関数の量との評価のみが必要であることに注意してください。 ${\displaystyle \cos \theta}$ ${\displaystyle \sin \theta}$

子午線弧の長さの差

ときには、2 つの子午線弧の差を、高い相対精度を維持しながら計算することが必要になることがあります。これは、三角恒等式を使用して と書くことで実現できます。 この場合、クレンショウ和を適用できます^{[ 5 ]} ただし、同時に を計算し て行列和を実行する必要があります。 の最初の要素は の平均値で 、 2 番目の要素は平均傾斜です。 は、再帰関係 を満たし 、再帰関係において が に置き換わり、 となります。これで、標準のクレンショウ アルゴリズムを に適用して を得ることができます。 ただし、は 2×2 行列です。最終的に、 が得られます 。この手法は、 の極限でと の導関数を同時に計算するために 使用できます。ただし、とを評価する際にを取る必要があります。 $${\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 )}.}$$ ${\displaystyle m(\theta _{1})+m(\theta _{2})}$ $${\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}}+\sum _{k=1}^{n}C_{k}{\mathsf {F}}_{k}(\theta _{1},\theta _{2}),}$$ $${\displaystyle {\begin{aligned}\delta &={\tfrac {1}{2}}(\theta _{1}-\theta _{2}),\\[1ex]\mu &={\tfrac {1}{2}}(\theta _{1}+\theta _{2}),\\[1ex]{\mathsf {F}}_{k}(\theta _{1},\theta _{2})&={\begin{bmatrix}\cos k\delta \sin k\mu \\{\dfrac {\sin k\delta }{\delta }}\cos k\mu \end{bmatrix}}.\end{aligned}}}$$ ${\displaystyle {\mathsf {M}}(\theta _{1},\theta _{2})}$ ${\displaystyle m}$ ${\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}}}$$ ${\displaystyle \alpha }$ ${\displaystyle \beta =-1}$ $${\displaystyle {\begin{aligned}{\mathsf {B}}_{n+1}&={\mathsf {B}}_{n+2}={\mathsf {0}},\\[1ex]{\mathsf {B}}_{k}&=C_{k}{\mathsf {I}}+{\mathsf {A}}{\mathsf {B}}_{k+1}-{\mathsf {B}}_{k+2},\qquad \mathrm {for\ } n\geq k\geq 1,\\[1ex]{\mathsf {M}}(\theta _{1},\theta _{2})&=C_{0}{\begin{bmatrix}\mu \\1\end{bmatrix}}+{\mathsf {B}}_{1}{\mathsf {F}}_{1}(\theta _{1},\theta _{2}),\end{aligned}}}$$ ${\displaystyle {\mathsf {B}}_{k}}$ $${\displaystyle {\frac {m(\theta _{1})-m(\theta _{2})}{\theta _{1}-\theta _{2}}}={\mathsf {M}}_{2}(\theta _{1},\theta _{2}).}$$ ${\displaystyle \theta _{2}=\theta _{1}=\mu }$ ${\displaystyle \delta =0}$ ${\displaystyle m(\mu )}$ ${\displaystyle dm(\mu )/d\mu }$ ${\displaystyle {\mathsf {F}}_{1}}$ ${\displaystyle {\mathsf {A}}}$ ${\displaystyle \lim _{\delta \to 0}(\sin k\delta )/\delta =k}$

参照

• 単項式形式で多項式を評価するためのホーナースキーム
• ベジェ形式で多項式を評価するDe Casteljau のアルゴリズム

参考文献

1. Clenshaw, CW (1955年7月). 「チェビシェフ級数の和に関する注記」 . 『数学表とその他の計算補助』 . 9 (51): 118. doi : 10.1090/S0025-5718-1955-0071856-0 . ISSN  0025-5718 .この論文は、第 1 種のシフトチェビシェフ多項式 に基づいて書かれていることに注意してください。${\displaystyle T_{n}^{*}(x)=T_{n}(2x-1)}$
2. Tscherning, CC; Poder, K. (1982), "Some Geodetic applications of Clenshaw Summation" (PDF) , Bolletino di Geodesia e Scienze Affini , 41 (4): 349– 375, 2007-06-12にオリジナル(PDF)からアーカイブ, 2012-08-02取得
3. Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)、「Section 5.4.2. Clenshaw's Recurrence Formula」、Numerical Recipes: The Art of Scientific Computing (第3版)、ニューヨーク: Cambridge University Press、ISBN 978-0-521-88068-8
4. Fox, Leslie; Parker, Ian B. (1968), Chebyshev Polynomials in Numerical Analysis , Oxford University Press, ISBN 0-19-859614-6
5. Karney, CFF (2024). 「方位多角形の面積」 . Stud. Geophys. Geod . 68 ( 3–4 ): 99– 120. arXiv : 2303.03219 . doi : 10.1007/s11200-024-0709-z付録B