Clenshaw–Curtis求積(Clenshaw–Curtis quadrature)とは、$[-1,1]$ の積分を、Chebyshev 多項式 $T_n$ の極値の点 $\cos\frac{j\pi}n$($j=0,\dots,n$)での補間多項式の積分で近似する求積公式のことである。補間多項式の Chebyshev 展開の係数は長さ $2n$ の離散 Fourier 変換で求まるので FFT により $O(n\log n)$ の手間で計算でき、重みは明示式で書けて正である。$n$ が偶数なら次数 $n+1$ の多項式まで正確で、連続関数なら収束し、Bernstein の楕円で正則な関数では誤差が指数的に減る。次数は同じ点数の Gauss の公式の約半分だが、特異点が区間に近い関数では精度があまり変わらないことが多く、$n$ を倍にすると節点が入れ子になって関数の値を使い回せる。
前提知識: Chebyshev多項式, 数値積分, Lagrange補間, 離散Fourier変換
Clenshaw–Curtis求積(Clenshaw–Curtis quadrature)は、区間 $[-1,1]$ の積分 $\int_{-1}^1f(x)\,dx$ を、Chebyshev 点 $x_j=\cos\frac{j\pi}n$($j=0,1,\dots,n$)での $f$ の補間多項式の積分で近似する公式である。$n=2$ では節点が $-1,0,1$ で、数値積分 の Simpson の公式になる。
等間隔の点の補間型の公式(Newton–Cotes 公式)は点を増やすと重みに負のものが現れ、連続関数でも収束しないことがある。Chebyshev 点では重みがすべて正なので、どの連続関数でも収束する(thm-cc-positive、thm-cc-convergence)。補間多項式の Chebyshev 展開の係数は長さ $2n$ の 離散Fourier変換 で求まるので、高速Fourier変換 により $O(n\log n)$ 回の演算で計算できる(prop-cc-fft)。$n+1$ 点の公式の次数は $n$ か $n+1$ で、同じ点数の Gauss求積(次数 $2n+1$)の約半分だが、特異点が区間に近い正則関数の積分では、$n$ が大きすぎなければ Gauss の公式とあまり変わらない速さで収束する(ex-cc-runge)。
この記事では、補間多項式の係数と重みの公式(thm-cc-weights)、重みが正であること(thm-cc-positive)、次数とエイリアシング(thm-cc-degree)、誤差の評価と、正則関数での幾何級数的な収束(thm-cc-convergence、thm-cc-analytic)を証明する。
$n\ge1$ とする。端の項を半分にした和を
$$
\sum_{j=0}^{n}{}''a_j:=\frac12a_0+a_1+\dots+a_{n-1}+\frac12a_n
$$
と書く。$T_k$ は第 1 種の Chebyshev多項式($T_k(\cos\theta)=\cos k\theta$)、$\mathcal P_m$ は次数 $m$ 以下の実係数の多項式全体である。
$x_j:=\cos\frac{j\pi}n$($j=0,\dots,n$)を Chebyshev 点(Chebyshev 多項式 $T_n$ の $[-1,1]$ での極値の点)という。$f\colon[-1,1]\to\mathbb R$ について、$x_0,\dots,x_n$ で $f$ と一致する $\mathcal P_n$ の多項式(Lagrange補間)を $p$ とし、
$$
I_n(f):=\int_{-1}^1p(x)\,dx=\sum_{j=0}^nw_jf(x_j)
$$
を $n$ 次の Clenshaw–Curtis の公式 という。$w_j$ は基本多項式の積分で、$f$ によらない。$I(f):=\int_{-1}^1f(x)\,dx$ とする。
$n$ 次の公式は $n+1$ 点を使う。節点は $x_0=1>x_1>\dots>x_n=-1$ と右から並ぶ。一般の区間 $[c,d]$ では $x=\frac{c+d}2+\frac{d-c}2t$ と置換し、全体に $\frac{d-c}2$ を掛ける。
使える条件は次のとおりである。
| 量 | 式 | 条件 | 根拠 |
|---|---|---|---|
| 補間多項式 | $p=\sum''_{k=0}^na_kT_k$、$a_k=\dfrac2n\sum''_{j=0}^nf(x_j)\cos\dfrac{jk\pi}n$ | $n\ge1$ | thm-cc-weights |
| $T_k$ の積分 | $\displaystyle\int_{-1}^1T_k=\frac2{1-k^2}$($k$ 偶数)、$0$($k$ 奇数) | $k\ge0$ | thm-cc-weights |
| 公式(係数で) | $I_n(f)=\sum''_{k\text{ 偶数},\,0\le k\le n}\dfrac{2a_k}{1-k^2}$ | $\sum''$ は $k=0$ と $k=n$ の項を半分にする | thm-cc-weights |
| 重み | $w_j=\dfrac{c_j}n\Bigl(1-\sum_{k=1}^{\lfloor n/2\rfloor}\dfrac{b_k}{4k^2-1}\cos\dfrac{2kj\pi}n\Bigr)$ | $c_0=c_n=1$、ほかは $c_j=2$;$b_{n/2}=1$、ほかは $b_k=2$ | thm-cc-weights |
| 端の重み | $w_0=w_n=\dfrac1{n^2-1}$($n$ 偶数)、$\dfrac1{n^2}$($n$ 奇数) | $n\ge2$ | thm-cc-positive |
| 重みの符号 | すべて正、和は $2$ | $n\ge1$ | thm-cc-positive |
| 次数 | $n+1$($n$ 偶数)、$n$($n$ 奇数) | $n\ge1$ | thm-cc-degree |
| 計算量 | $O(n\log n)$ | 係数を FFT で | prop-cc-fft |
| 誤差 | $\lvert I(f)-I_n(f)\rvert\le4\inf_{g\in\mathcal P_n}\max\lvert f-g\rvert$ | $f\in C[-1,1]$ | thm-cc-convergence |
| 誤差(正則) | $\lvert I(f)-I_n(f)\rvert\le\dfrac{8M}{(\rho-1)\rho^n}$ | $f$ が楕円 $E_\rho$ の中で正則、$\lvert f\rvert\le M$ | thm-cc-analytic |
小さい $n$ の重みは次のとおりである(節点は右から $x_0=1$ の順)。
| $n$ | 節点 | 重み |
|---|---|---|
| $1$ | $1,-1$ | $1,1$(台形公式) |
| $2$ | $1,0,-1$ | $\frac13,\frac43,\frac13$(Simpson の公式) |
| $3$ | $1,\frac12,-\frac12,-1$ | $\frac19,\frac89,\frac89,\frac19$ |
| $4$ | $1,\frac1{\sqrt2},0,-\frac1{\sqrt2},-1$ | $\frac1{15},\frac8{15},\frac45,\frac8{15},\frac1{15}$ |
整数 $m$ について、$\sum''_{j=0}^n\cos\frac{jm\pi}n$ は $2n\mid m$ のとき $n$、そうでないとき $0$ である。とくに $0\le k,l\le n$ について
$$
\sum_{j=0}^n{}''\cos\frac{jk\pi}n\cos\frac{jl\pi}n=\begin{cases}n&(k=l\in\{0,n\})\\ n/2&(k=l,\ 0< k< n)\\ 0&(k\ne l)\end{cases}
$$
である。
$\cos\frac{(2n-j)m\pi}n=\cos\frac{jm\pi}n$ なので、$j=0,\dots,2n-1$ の和では $j=1,\dots,n-1$ の項が 2 回ずつ、$j=0,n$ の項が 1 回ずつ現れる。よって $\zeta:=e^{im\pi/n}$ として
$$
\sum_{j=0}^n{}''\cos\frac{jm\pi}n=\frac12\sum_{j=0}^{2n-1}\cos\frac{jm\pi}n=\frac12\operatorname{Re}\sum_{j=0}^{2n-1}\zeta^j
$$
である。$2n\mid m$ なら $\zeta=1$ で和は $2n$、そうでなければ $\zeta\ne1$、$\zeta^{2n}=1$ なので和は $(\zeta^{2n}-1)/(\zeta-1)=0$ である。
後半は積和の公式 $\cos A\cos B=\frac12(\cos(A-B)+\cos(A+B))$ で $m=k-l$ と $m=k+l$ の場合に帰着する。$\lvert k-l\rvert< 2n$ なので $2n\mid k-l$ は $k=l$ のときだけで、$0\le k+l\le2n$ なので $2n\mid k+l$ は $k=l=0$ か $k=l=n$ のときだけである。$\square$
$f(x_j)$ の値から
$$
a_k:=\frac2n\sum_{j=0}^n{}''f(x_j)\cos\frac{jk\pi}n\qquad(k=0,\dots,n)
$$
とおく。
この重みの式は DLMF §3.5(iv) の式 (3.5.16)–(3.5.17) と同じである。
$n\ge1$ のすべての $j$ で $w_j>0$ であり、$\sum_jw_j=2$ である。さらに
$$
w_j\ge c_j\,w_0,\qquad w_0=w_n=\begin{cases}\dfrac1{n^2-1}&(n\text{ が偶数})\\[2mm]\dfrac1{n^2}&(n\text{ が奇数})\end{cases}
$$
である($n=1$ では $w_0=w_1=1$)。
$S:=\sum_{k=1}^{\lfloor n/2\rfloor}\frac{b_k}{4k^2-1}$ とおく。thm-cc-weights の 3 の括弧の中は $1-S$ 以上で、$j=0$ と $j=n$ では余弦がすべて $1$ なので $1-S$ に等しい。よって $w_j\ge\frac{c_j}n(1-S)$、$w_0=w_n=\frac{1-S}n$ である。
$\frac2{4k^2-1}=\frac1{2k-1}-\frac1{2k+1}$ から $\sum_{k=1}^m\frac2{4k^2-1}=1-\frac1{2m+1}$ である。$n$ が奇数なら $m=\frac{n-1}2$ として $S=1-\frac1n$、$1-S=\frac1n$ である。$n$ が偶数なら $m=\frac n2$ の項だけ係数が $1$ なので
$$
S=1-\frac1{n-1}+\frac1{n^2-1},\qquad1-S=\frac1{n-1}-\frac1{n^2-1}=\frac n{n^2-1}
$$
である。どちらでも $1-S>0$ なので $w_j>0$ で、$w_0$ は主張の値である。公式は定数で正確なので $\sum_jw_j=\int_{-1}^11\,dx=2$ である。$\square$
$F_j:=f(x_j)$($0\le j\le n$)とし、$F_{2n-j}:=F_j$($1\le j\le n-1$)と長さ $2n$ に延ばす。このとき
$$
a_k=\frac1n\sum_{j=0}^{2n-1}F_j\,e^{-2\pi ijk/(2n)}\qquad(k=0,\dots,n)
$$
である。よって $a_0,\dots,a_n$ は長さ $2n$ の離散 Fourier 変換 1 回で求まり、$I_n(f)$ は $O(n\log n)$ 回の演算で計算できる。
$1\le j\le n-1$ について、$j$ と $2n-j$ の項を組にすると $F_j(e^{-ijk\pi/n}+e^{-i(2n-j)k\pi/n})=2F_j\cos\frac{jk\pi}n$ である。$j=0$ の項は $F_0$、$j=n$ の項は $F_ne^{-ik\pi}=F_n\cos k\pi$ である。よって右辺は $\frac1n\cdot2\sum''_jF_j\cos\frac{jk\pi}n=a_k$ である。長さ $2n$ の離散 Fourier 変換は 高速Fourier変換 で $O(n\log n)$ 回の演算で計算でき、そのあと thm-cc-weights の $I_n(f)=\sum''_{k\text{ 偶数}}\frac{2a_k}{1-k^2}$ は $O(n)$ 回で求まる。$\square$
重み $w_j$ を thm-cc-weights の 3 の式でそのまま計算すると $O(n^2)$ 回かかる。1 つの関数なら係数を経由するほうが速い(多くの関数なら手順 3)。
$f\in C[-1,1]$ について $E_n(f):=\inf_{g\in\mathcal P_n}\max_{[-1,1]}\lvert f-g\rvert$ とおくと
$$
\lvert I(f)-I_n(f)\rvert\le4E_n(f)
$$
である。とくに $n\to\infty$ で $I_n(f)\to I(f)$ である。
$g\in\mathcal P_n$ について $I_n(g)=I(g)$ なので、$I(f)-I_n(f)=I(f-g)-I_n(f-g)$ である。$\delta:=\max\lvert f-g\rvert$ とすると $\lvert I(f-g)\rvert\le2\delta$ で、thm-cc-positive により $\lvert I_n(f-g)\rvert\le\sum_j\lvert w_j\rvert\delta=2\delta$ である。$g$ について下限をとって評価を得る。Weierstrassの近似定理 により $E_n(f)\to0$ である。$\square$
$f$ の Chebyshev 展開の係数が速く減れば $E_n(f)$ も小さい。$\rho>1$ について、焦点が $\pm1$ で長半径と短半径の和が $\rho$ の楕円を $E_\rho$ と書く。$E_\rho$ は円 $\lvert z\rvert=\rho$ の写像 $z\mapsto\frac12(z+z^{-1})$ による像である。
$\rho>1$ とし、$f$ は $E_\rho$ で囲まれた開領域で正則で、そこで $\lvert f\rvert\le M$、$[-1,1]$ の上で実数値とする。このとき $f=\sum'_{k\ge0}\alpha_kT_k$($\sum'$ は $k=0$ の項を半分にする)が $[-1,1]$ の上で一様に成り立ち、$\lvert\alpha_k\rvert\le2M\rho^{-k}$ である。さらに
$$
\lvert I(f)-I_n(f)\rvert\le\frac{8M}{(\rho-1)\rho^n}
$$
である。
$J(z):=\frac12(z+z^{-1})$ とする。$z=se^{i\theta}$($s>0$)なら $J(z)=\frac12(s+s^{-1})\cos\theta+\frac i2(s-s^{-1})\sin\theta$ で、$J(z)$ は楕円 $E_{\max(s,1/s)}$ の上($s=1$ なら $[-1,1]$ の上)にある。$s\ge1$ について $E_s$ の半径 $\frac12(s\pm s^{-1})$ は $s$ について増加するので、円環 $A:=\{\rho^{-1}< \lvert z\rvert< \rho\}$ は $J$ で $E_\rho$ の内部に写る。よって $g:=f\circ J$ は $A$ で正則で $\lvert g\rvert\le M$ である。
$g$ を Laurent展開 $g(z)=\sum_{k\in\mathbb Z}c_kz^k$ と書くと、$1< r< \rho$ について $c_k=\frac1{2\pi i}\oint_{\lvert z\rvert=r}g(z)z^{-k-1}dz$ なので $\lvert c_k\rvert\le Mr^{-k}$($k\ge0$)で、$r\to\rho$ として $\lvert c_k\rvert\le M\rho^{-k}$ である。$J(1/z)=J(z)$ から $g(1/z)=g(z)$ で、Laurent 係数の一意性から $c_{-k}=c_k$ である。また $c_k=\frac1{2\pi}\int_0^{2\pi}f(\cos\theta)e^{-ik\theta}d\theta$ で、$f(\cos\theta)$ は $\theta$ の実数値の偶関数なので $c_k$ は実数である。$\lvert z\rvert=1$ では級数は絶対かつ一様に収束し、$z=e^{i\theta}$ として
$$
f(\cos\theta)=c_0+\sum_{k\ge1}c_k(e^{ik\theta}+e^{-ik\theta})=c_0+\sum_{k\ge1}2c_k\cos k\theta
$$
である。$\alpha_k:=2c_k$ とおけば $f=\sum'_k\alpha_kT_k$ が一様に成り立ち、$\lvert\alpha_k\rvert\le2M\rho^{-k}$ である。
$g_n:=\sum'_{k\le n}\alpha_kT_k\in\mathcal P_n$ とすると、$\lvert T_k\rvert\le1$ から $E_n(f)\le\max\lvert f-g_n\rvert\le\sum_{k>n}\lvert\alpha_k\rvert\le2M\sum_{k>n}\rho^{-k}=\frac{2M}{(\rho-1)\rho^n}$ である。thm-cc-convergence から主張を得る。$\square$
thm-cc-analytic の評価は $\rho^{-n}$ で減る。同じ仮定で $n+1$ 点の Gauss の公式の誤差は $\frac{64M}{15(1-\rho^{-2})\rho^{2n+2}}$ 以下である(Tre08 Theorem 4.5、p. 77)。しかし実際の誤差を比べると、ex-cc-runge のように Clenshaw–Curtis の公式も $\rho^{-2n}$ に近い速さで減ることが多い。ただし $n$ が大きくなると、途中から減る速さが半分に落ちる(Tre08 §6、p. 84)。$f$ が有限回だけ微分できる場合には、次の評価がある。
$k\ge1$ とし、$f,f',\dots,f^{(k-1)}$ が $[-1,1]$ で絶対連続で、$V:=\bigl\|f^{(k)}\bigr\|_T< \infty$ とする。ここで $\|u\|_T:=\int_{-1}^1\frac{\lvert u'(x)\rvert}{\sqrt{1-x^2}}dx$(一般には Stieltjes 積分で定める)である。このとき、$k$ だけで決まる $n_k$ があって、$n>n_k$ なら
$$
\lvert I(f)-I_n(f)\rvert\le\frac{32V}{15\pi k(2n+1-k)^k}
$$
である。
この記事では証明しない。Tre08 Theorem 5.1(p. 78)による。右辺は $n+1$ 点の Gauss の公式についての同じ形の評価(Tre08 Theorem 4.5、式 (4.13)、p. 77)と同じで、次数が約半分であるにもかかわらず、滑らかさが有限の関数では Gauss の公式と同じ冪の速さが保証される。証明の鍵は thm-cc-degree のエイリアシングで、$n+p$ が偶数の $T_{n+p}$ の誤差が $p$ が小さいときに小さいことを使う。
区間 $[c,d]$ の積分を Clenshaw–Curtis の公式で計算する手順は次のとおりである。
thm-cc-weights の 3 で $n=4$、$b_1=2$、$b_2=1$ とする。$w_0=\frac14(1-\frac23-\frac1{15})=\frac1{15}$、$w_1=\frac24(1-\frac23\cos\frac\pi2-\frac1{15}\cos\pi)=\frac8{15}$、$w_2=\frac24(1-\frac23\cos\pi-\frac1{15}\cos2\pi)=\frac45$ で、対称性から $w_3=\frac8{15}$、$w_4=\frac1{15}$ である。
答え:$I_4(e^x)=\frac1{15}(e+e^{-1})+\frac8{15}(e^{1/\sqrt2}+e^{-1/\sqrt2})+\frac45\approx2.3503753769$ で、真の値 $e-e^{-1}\approx2.3504023873$ との差は $2.701\times10^{-5}$ である。公式の次数は $5$ である(thm-cc-degree)。
$\int_{-1}^1e^xdx$ を、$n+1$ 点の Clenshaw–Curtis の公式と $n+1$ 点の Gauss–Legendre の公式で比べる。
答え:
| $n$ | $2$ | $4$ | $8$ | $16$ |
|---|---|---|---|---|
| Clenshaw–Curtis の誤差 | $-1.165\times10^{-2}$ | $2.701\times10^{-5}$ | $2.046\times10^{-11}$ | $4.915\times10^{-24}$ |
| Gauss($n+1$ 点)の誤差 | $6.546\times10^{-5}$ | $8.248\times10^{-10}$ | $1.846\times10^{-21}$ | $6.149\times10^{-49}$ |
$e^x$ はどの $\rho$ の楕円でも正則なので、次数の差がそのまま現れ、Gauss の公式の誤差の桁数は Clenshaw–Curtis の公式の 2 倍近くになる。ただし $n=16$ では誤差はどちらも倍精度の丸めの単位より小さく、差は見えない。
$f(x)=\frac1{1+25x^2}$、$\int_{-1}^1f\,dx=\frac25\arctan5\approx0.5493603068$ とする。$f$ の極 $\pm\frac i5$ を通る楕円は短半径 $\frac15$、長半径 $\frac{\sqrt{26}}5$ なので、$f$ は $\rho< \rho_0:=\frac{1+\sqrt{26}}5\approx1.21980$ の楕円 $E_\rho$ の中で正則である。
答え:
| $n$ | $8$ | $16$ | $32$ | $64$ |
|---|---|---|---|---|
| Clenshaw–Curtis の誤差 | $-5.519\times10^{-2}$ | $-2.196\times10^{-3}$ | $-3.852\times10^{-6}$ | $-2.860\times10^{-11}$ |
| Gauss($n+1$ 点)の誤差 | $-2.934\times10^{-2}$ | $-1.197\times10^{-3}$ | $-2.076\times10^{-6}$ | $-6.236\times10^{-12}$ |
$n\le64$ では、Clenshaw–Curtis の公式の誤差は Gauss の公式の約 $1.8$ 倍から $4.6$ 倍にとどまり、$n=8,16,32$ では $\lvert\text{誤差}\rvert\rho_0^{2n}$ が $1.27$〜$1.33$ とほぼ一定である。
$\rho=1.2$ では楕円の上で $\lvert f\rvert\le6.261$(周の上の最大値。最大値の原理により内部でも同じ上界)なので、thm-cc-analytic の右辺は $n=32$ で $0.733$、$n=64$ で $2.14\times10^{-3}$ である。評価は正しいが、実際の誤差よりはるかに大きい。$\rho^{-n}$ の評価では $\rho^{-2n}$ に近い実際の減り方を説明できない。
$n=128$ では Clenshaw–Curtis の公式の誤差は $-6.483\times10^{-18}$、Gauss の公式の誤差は $-5.623\times10^{-23}$ で、比は約 $1.2\times10^5$ に開く。$n$ が大きくなると Clenshaw–Curtis の公式の減る速さが落ちる現象で、Tre08 §6(p. 84)が $1/(1+16x^2)$ の例で述べている。
$n=4$ の節点 $\cos\frac{j\pi}4$ は $n=8$ の節点 $\cos\frac{2j\pi}8$ の一部である。$I_4(e^x)$ を計算したあと $I_8(e^x)$ を求めるには、$\cos\frac{\pi}8,\cos\frac{3\pi}8,\cos\frac{5\pi}8,\cos\frac{7\pi}8$ の 4 点だけ新しく評価すればよい。
答え:$I_8(e^x)$ の誤差は $2.046\times10^{-11}$ で、$\lvert I_8-I_4\rvert=2.701\times10^{-5}$ は $I_4$ の誤差とほぼ等しい。Gauss の公式では $n=4$ と $n=8$ の節点は中心の $0$ 以外に共有されない。
各行は 1 つの仮定だけを外す。
| 外した仮定 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| $n$ が偶数(thm-cc-degree の 3 の「次数 $n+1$」) | $n=3$、$f=x^4$ | $\mathcal P_{n+1}=\mathcal P_4$ で正確でない:$I_3(x^4)=\frac13$、$I(x^4)=\frac25$ |
| 節点が Chebyshev 点(thm-cc-positive) | 等間隔の 9 点 $-1,-\frac34,\dots,1$ の補間型の公式(閉じた Newton–Cotes 公式) | 重みがすべて正:重みに $-\frac{928}{14175}$ と $-\frac{908}{2835}$ が現れる |
| $f$ が連続(thm-cc-convergence) | $f$=すべての $n$ の Chebyshev 点の集合の指示関数 | $I_n(f)\to I(f)$:すべての $n$ で $I_n(f)=2$ だが Lebesgue 積分は $0$ |
表の 3 行の反例で、それぞれの結論が実際に成り立たないことを確かめる。
1 行目:$n=3$ の節点は $\pm1,\pm\frac12$、重みは $\frac19,\frac89$ である(thm-cc-weights)。$I_3(x^4)=2\cdot\frac19\cdot1+2\cdot\frac89\cdot\frac1{16}=\frac29+\frac19=\frac13$ である。
2 行目:等間隔の 9 点の基本多項式を積分すると、重みは $\frac{989}{14175},\frac{5888}{14175},-\frac{928}{14175},\frac{10496}{14175},-\frac{908}{2835}$(中央)と対称に並ぶ。重みの絶対値の和は $\frac{13714}{4725}\approx2.902>2$ で、thm-cc-convergence の証明の「重みの絶対値の和が $2$」が使えない。等間隔の点の公式が実際に収束しない例は 数値積分 にある。
3 行目:Chebyshev 点の全体 $\{\cos q\pi\mid q\in\mathbb Q\cap[0,1]\}$ は可算なので Lebesgue 測度は $0$ で、$I(f)=0$ である。$I_n(f)$ は $f$ を節点でしか見ないので、$I_n(f)=\sum_jw_j=2$ である。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 節点を $T_{n+1}$ の零点 $\cos\frac{(2j+1)\pi}{2n+2}$ とする | 節点は端点を含む極値の点 $\cos\frac{j\pi}n$。零点を使うのは Fejér の第 1 の公式 | def-cc-rule、rem-cc-fejer |
| 次数が約半分なので、Gauss の公式の半分の桁しか得られない | 特異点が区間に近い正則関数では、$n$ が大きすぎなければ Gauss の公式とあまり変わらないことが多い。差が出るのは整関数や $n$ が大きいときなど | ex-cc-runge、ex-cc-exp |
| $n$ を倍にするたびにすべて評価し直す | 半分の点の値は使い回せる | ex-cc-nested |
| 等間隔の点でも点を増やせば収束する | 重みに負のものが出て、収束しないことがある | 反例の表の 2 行目 |
| 端で無限大になる関数にそのまま使う | 端点の値が要るので使えない | rem-cc-fejer |
公式は Clenshaw と Curtis が 1960 年に発表し、FFT による計算は Gentleman が指摘した。重みが正であることは Imhof が 1963 年に示した(Tre08 pp. 70, 74)。Chebyshev 点の補間そのものの性質は Lebesgue定数 と Runge現象 を参照。
Tre08 §6 は、求積の公式を $\log\frac{z+1}{z-1}$ の有理関数による近似とみなし、Clenshaw–Curtis の公式が無限遠での近似の次数は Gauss の公式の半分なのに、$[-1,1]$ の近くでは同じ程度に正確であることを論じている。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する