Clenshaw–Curtis求積

同義語:Clenshaw-Curtis求積Clenshaw–Curtisの公式Clenshaw–Curtis quadratureClenshaw-Curtis quadrature

概要

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$ を倍にすると節点が入れ子になって関数の値を使い回せる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 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$ 以下の実係数の多項式全体である。

Clenshaw–Curtis の公式

$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$ を掛ける。
使える条件は次のとおりである。

  1. 端点の値を使う。$f$ が $\pm1$ で定義されている必要がある。端に特異性があるときは、端点を使わない変種(Fejér の公式。rem-cc-fejer)か、特異性を重みに入れた Gauss求積 を使う。
  2. 重みは正(thm-cc-positive)。そのため、$f$ が $[-1,1]$ で連続なら $I_n(f)\to I(f)$ である(thm-cc-convergence)。
  3. 収束の速さは $f$ の滑らかさで決まる。$f$ が $[-1,1]$ を囲む楕円の中で正則なら誤差は $n$ について幾何級数的に減る(thm-cc-analytic)。$f$ が $k$ 回微分できる程度なら、誤差は $n$ の冪で減る(thm-cc-trefethen)。

公式の表

量式条件根拠
補間多項式$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} $$
である。

円周の $2n$ 等分点の和に直す

$\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) $$
とおく。

  1. 補間多項式は $p=\sum''_{k=0}^na_kT_k$ である。
  2. $\int_{-1}^1T_k(x)\,dx$ は $k$ が偶数なら $\frac2{1-k^2}$、奇数なら $0$ である。
  3. $I_n(f)=\sum_jw_jf(x_j)$ の重みは
    $$ w_j=\frac{c_j}n\Bigl(1-\sum_{k=1}^{\lfloor n/2\rfloor}\frac{b_k}{4k^2-1}\cos\frac{2kj\pi}n\Bigr) $$
    である。ここで $c_0=c_n=1$、$0< j< n$ で $c_j=2$、$b_k=2$(ただし $n$ が偶数のとき $b_{n/2}=1$)である。
離散直交性で係数を取り出す
  1. $q:=\sum''_ka_kT_k\in\mathcal P_n$ とおく。$T_k(x_i)=\cos\frac{ik\pi}n$ なので
    $$ q(x_i)=\frac2n\sum_{j=0}^n{}''f(x_j)\sum_{k=0}^n{}''\cos\frac{jk\pi}n\cos\frac{ik\pi}n $$
    である。lem-cc-discrete(添字 $k$ の和として使う)により内側の和は $j\ne i$ で $0$、$j=i\in\{0,n\}$ で $n$、$0< j=i< n$ で $\frac n2$ である。外側の和で $j=0,n$ の項は $\frac12$ 倍されるので、どの $i$ でも $q(x_i)=f(x_i)$ である。$\mathcal P_n$ の多項式は $n+1$ 点の値で決まるので $q=p$ である。
  2. $x=\cos\theta$ と置換すると $\int_{-1}^1T_k\,dx=\int_0^\pi\cos k\theta\sin\theta\,d\theta=\frac12\int_0^\pi(\sin(k+1)\theta-\sin(k-1)\theta)\,d\theta$ である。$\int_0^\pi\sin m\theta\,d\theta$ は $m$ が奇数なら $\frac2m$、偶数なら $0$ である。$k$ が偶数なら $\frac12(\frac2{k+1}-\frac2{k-1})=\frac2{1-k^2}$、奇数なら $0$ である。
    1. と (2) から $I_n(f)=\sum''_k a_k\int T_k$ で、$a_k$ の式を代入して $f(x_j)$ の係数を集めると
      $$ w_j=\frac{c_j}n\sum_{k=0}^n{}''\cos\frac{jk\pi}n\int_{-1}^1T_k\,dx $$
      である($c_j/2$ は外側の $\sum''$ の重み)。$k=0$ の項は $\frac12\cdot2=1$、$k=2m$($1\le m\le\lfloor n/2\rfloor$)の項は $\frac{2}{1-4m^2}\cos\frac{2mj\pi}n$ で、$2m=n$ のときだけ $\frac12$ 倍される。これが主張の式である。$\square$

この重みの式は 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$

高速 Fourier 変換による計算

FFT による計算

$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)。

次数とエイリアシング

エイリアシングと次数
  1. $0\le p\le n$ について、すべての節点で $T_{n+p}(x_j)=T_{n-p}(x_j)$ である。
  2. よって $I_n(T_{n+p})=I(T_{n-p})$ であり、誤差 $I(T_{n+p})-I_n(T_{n+p})$ は、$n+p$ が奇数なら $0$、偶数なら $\frac2{1-(n+p)^2}-\frac2{1-(n-p)^2}$ で、$p\ge1$ ならこれは $0$ でない。
  3. 公式の次数は、$n$ が偶数なら $n+1$、奇数なら $n$ である。
$2n$ 等分点で周波数が重なる
  1. $(n+p)+(n-p)=2n$ なので $\cos\frac{(n+p)j\pi}n=\cos\bigl(2j\pi-\frac{(n-p)j\pi}n\bigr)=\cos\frac{(n-p)j\pi}n$ である。
  2. $I_n$ は節点の値だけで決まり、$\mathcal P_n$ で正確なので $I_n(T_{n+p})=I_n(T_{n-p})=I(T_{n-p})$ である。$n+p$ と $n-p$ の偶奇は同じなので、thm-cc-weights の 2 から誤差の式を得る。$p\ge1$ で $n+p$ が偶数のとき、$k=n\pm p$ はどちらも偶数で $(n+p)^2-(n-p)^2=4np>0$ である。偶数 $k$ について $\frac2{1-k^2}$ は $k=0$ で $2$、$k\ge2$ で負かつ $k$ について増加なので、異なる $k$ では値が異なり、誤差は $0$ でない。
  3. 補間型なので $\mathcal P_n$ で正確である。$n$ が偶数なら、$p=1$ で $n+1$ は奇数なので $T_{n+1}$ でも正確、$p=2$ で $T_{n+2}$ では正確でない。$\mathcal P_{n+2}=\mathcal P_{n+1}\oplus\mathbb RT_{n+2}$ なので次数は $n+1$ である。$n$ が奇数なら $p=1$ で $n+1$ は偶数なので $T_{n+1}$ で正確でなく、次数は $n$ である。$\square$

誤差の評価

最良近似による誤差の評価

$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)$ である。

重みの絶対値の和が $2$ であることを使う

$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} $$
である。

$z\mapsto\frac12(z+z^{-1})$ で円環に持ち上げる

$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 の公式で計算する手順は次のとおりである。

  1. $x=\frac{c+d}2+\frac{d-c}2t$ と置換し、$g(t):=\frac{d-c}2f(x)$ の $[-1,1]$ の積分に直す。
  2. $n$ を決め、$t_j=\cos\frac{j\pi}n$ で $g$ を評価する。
  3. 係数 $a_k$ を prop-cc-fft の離散 Fourier 変換で求め、$I_n=\sum''_{k\text{ 偶数}}\frac{2a_k}{1-k^2}$ を計算する。同じ $n$ で多くの関数を積分するなら、重み $w_j$(thm-cc-weights)を一度計算して使い回す。
  4. $n$ を $2n$ にして $I_{2n}$ を求める。$\cos\frac{j\pi}n=\cos\frac{2j\pi}{2n}$ なので、新しく評価するのは奇数番目の $n$ 個の点だけである。
  5. $\lvert I_{2n}-I_n\rvert$ が許容値を下回れば止める。係数 $\lvert a_k\rvert$ が $k$ の大きいところで丸めの程度まで減っていることも確かめる。減らないときは、$f$ に特異性があるか、区間を分ける必要がある。
    手順 5 の判定は目安で、保証が要るならthm-cc-analytic の $M$ と $\rho$ を見積もるか、thm-cc-convergence の最良近似の誤差を上から抑える。

例題

$n=4$ の重みと $\int_{-1}^1e^xdx$

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)。

整関数 $e^x$ では Gauss の公式がはるかに速い

$\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$ では誤差はどちらも倍精度の丸めの単位より小さく、差は見えない。

Runge の関数では両者がほぼ並ぶ

$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 行の反例で、それぞれの結論が実際に成り立たないことを確かめる。

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

補足

Fejér の公式

同じ考え方で、端点を使わない補間型の公式が 2 つある。$T_n$ の零点 $\cos\frac{(2j-1)\pi}{2n}$($j=1,\dots,n$)を節点とするものを Fejér の第 1 の公式、$T_n$ の内部の極値の点 $\cos\frac{j\pi}n$($j=1,\dots,n-1$)を節点とするものを Fejér の第 2 の公式 という(Tre08 §2、p. 70。DLMF §3.5(iv))。Clenshaw–Curtis の公式は第 2 の公式に端点 $\pm1$ を足したものである。端点を使わないので、端点で $f$ が定義されない積分にも使える。

公式は 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アソシエイト)の紹介料で運営されています。 支援について / 寄付する