スペクトル法

同義語:spectral method

概要

スペクトル法(spectral method)とは、微分方程式の解を、周期的な問題では三角関数、区間の問題では Chebyshev 多項式のような領域全体で滑らかな関数の有限和で近似する数値解法である。Fourier 係数の絶対値の和が有限な連続な周期関数では、等間隔の格子点での三角補間の誤差は、捨てた高い波数の Fourier 係数の絶対値の和の 2 倍以下で、係数は関数が滑らかなほど速く減る。関数が実軸を含む帯で有界な正則関数に延びるなら誤差は指数関数的に減り、区間では $x=\cos\theta$ の置き換えで同じ結論が Chebyshev 展開に移る。周期的な流体や波動、区間の境界値問題の高精度の計算に使う。

$$\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}} $$

前提知識: Fourier級数, 離散Fourier変換, Chebyshev多項式, 正則関数

スペクトル法(spectral method)は、偏微分方程式の解を、領域全体で滑らかな関数の有限和で近似する数値解法である。周期的な問題では三角関数 $e^{ikx}$($\lvert k\rvert\le m$)の和、区間の問題では Chebyshev多項式 の和を使う。差分法 や 有限要素法 が各点の近くの値だけを使う局所的な近似なのに対し、スペクトル法の基底は全体に広がっている。
この方法の値打ちは誤差の減り方にある。差分法では刻みを半分にすると誤差が $\tfrac14$ 倍(2 次の方法)になるといった 決まった次数 で減る。スペクトル法では、解が滑らかなほど速く減り、解が複素数の帯状の領域へ正則に延びるなら、未知数を 1 つ増やすごとに誤差が一定の比で小さくなる(指数関数的な収束)。たとえば $f(x)=1/(2-\cos x)$ を $33$ 点で補間すると最大誤差は $3.7\times10^{-10}$ である。
この記事では、誤差が Fourier 係数の減り方で決まること(主定理)を完全に証明し、係数の減り方を滑らかさ・正則性から評価する。そのうえで周期的な境界値問題の Galerkin 法と選点法の誤差を証明し、区間では $x=\cos\theta$ の置き換えで同じ結論が Chebyshev 展開に移ることを示す。

定義と使える条件

以下、$f$ は $2\pi$ 周期の関数で、$\hat f(k)=\frac1{2\pi}\int_{-\pi}^{\pi}f(x)e^{-ikx}\,dx$ はその Fourier 係数である(Fourier級数 の定義「Fourier 係数と Fourier 級数」)。$m\ge1$ について、次数 $m$ 以下の三角多項式の空間を
$$ \mathcal T_m:=\Bigl\{\sum_{\lvert k\rvert\le m}a_ke^{ikx}\Bigm|a_k\in\mathbb C\Bigr\} $$
とおく。$\dim\mathcal T_m=2m+1$ である。

打ち切りと三角補間
  1. $P_mf:=\sum_{\lvert k\rvert\le m}\hat f(k)e^{ikx}$ を $f$ の 打ち切り(Fourier 級数の部分和)という。
  2. $N:=2m+1$ とし、等間隔の格子点 $x_j:=2\pi j/N$($j=0,1,\dots,N-1$)をとる。連続な $f$ について
    $$ I_Nf(x):=\sum_{\lvert k\rvert\le m}\tilde f_ke^{ikx},\qquad\tilde f_k:=\frac1N\sum_{j=0}^{N-1}f(x_j)e^{-ikx_j} $$
    を $f$ の 三角補間 という。$\tilde f_k$ は格子点の値の 離散Fourier変換 であり、高速Fourier変換 で $O(N\log N)$ 回の演算で計算できる。

点の数を奇数 $N=2m+1$ にしたのは、$\mathcal T_m$ の次元と点の数をそろえるためである。偶数の点数を使う実装も多いが、そのときは波数 $\pm N/2$ の扱いに約束が要る。

離散の直交性と補間の一意性

$N=2m+1$、$x_j=2\pi j/N$ とする。

  1. 整数 $n$ について $\dfrac1N\sum_{j=0}^{N-1}e^{inx_j}$ は、$n$ が $N$ の倍数なら $1$、そうでなければ $0$ である。
  2. $I_Nf$ は $\mathcal T_m$ の元で、すべての格子点で $I_Nf(x_j)=f(x_j)$ を満たす。格子点で $f$ と一致する $\mathcal T_m$ の元は $I_Nf$ だけである。

要点:1 は等比数列の和である。2 は 1 を使って係数を 1 つずつ取り出す。

詳しい証明を開く

1:$\omega:=e^{2\pi in/N}$ とおくと和は $\frac1N\sum_{j=0}^{N-1}\omega^j$ である。$N\mid n$ なら $\omega=1$ で値は $1$、そうでなければ $\omega\ne1$、$\omega^N=1$ なので等比数列の和は $\frac{\omega^N-1}{\omega-1}=0$ である。

2:$p=\sum_{\lvert k\rvert\le m}a_ke^{ikx}\in\mathcal T_m$ が $p(x_j)=0$(全 $j$)を満たすとする。$\lvert l\rvert\le m$ について、1 から $$ 0=\frac1N\sum_jp(x_j)e^{-ilx_j}=\sum_{\lvert k\rvert\le m}a_k\cdot\frac1N\sum_je^{i(k-l)x_j}=a_l $$ である($\lvert k-l\rvert\le2m< N$ なので $N\mid k-l$ は $k=l$ に限る)。よって $p=0$ で、一致するものは高々 1 つである。$I_Nf(x_i)=\sum_k\frac1N\sum_jf(x_j)e^{ik(x_i-x_j)}=\sum_jf(x_j)\cdot\frac1N\sum_{\lvert k\rvert\le m}e^{ik(x_i-x_j)}$ で、内側の和は $x_i-x_j=2\pi(i-j)/N$ について 1 と同じ計算で $j=i$ のとき $1$、それ以外で $0$($\lvert k\rvert\le m$ の $N$ 個の $k$ は $N$ を法とした剰余を 1 回ずつ代表する)なので、$I_Nf(x_i)=f(x_i)$ である。$\square$

スペクトル法が速く収束するための条件を並べておく(型 H)。

  • (i) 周期性:周期的な問題では、解を周期的に延ばしたものが滑らかであること。区間 $[0,2\pi]$ の上で滑らかでも、両端の値や導関数が合わなければ周期的な延長は滑らかでない。
  • (ii) 滑らかさ:$C^s$ 級なら誤差は $m^{1-s}$ 程度(thm-sp-smooth)、帯状の領域で正則なら指数関数的(thm-sp-analytic)。
  • (iii) 非周期の区間:$[-1,1]$ では Chebyshev 展開を使い、$f$ が楕円の内部で正則なら指数関数的(thm-sp-chebyshev)。
  • (iv) 非線形の項:格子点の値の積で計算すると、帯域が広がった分が低い波数に折り返す(反例の表の 4 行目)。

公式の表

$f$ の条件係数の評価補間・打ち切りの誤差根拠
連続で $\sum_k\lvert\hat f(k)\rvert< \infty$—$\max\lvert f-I_Nf\rvert\le2\sum_{\lvert k\rvert>m}\lvert\hat f(k)\rvert$thm-sp-alias
$C^s$ 級($s\ge2$)$\lvert\hat f(k)\rvert\le\dfrac{V_s}{2\pi\lvert k\rvert^s}$$\le\dfrac{2V_s}{\pi(s-1)}\,m^{1-s}$thm-sp-smooth
帯 $\lvert\operatorname{Im}z\rvert< a$ で正則、$\lvert f\rvert\le M$$\lvert\hat f(k)\rvert\le Me^{-a\lvert k\rvert}$$\le\dfrac{4M}{e^a-1}e^{-am}$thm-sp-analytic
跳びがある$\lvert\hat f(k)\rvert$ は $1/\lvert k\rvert$ 程度最大誤差は $0$ に近づかない反例の表
$[-1,1]$、楕円 $E_\rho$ の内部で正則、$\lvert f\rvert\le M$$\lvert a_n\rvert\le2M\rho^{-n}$打ち切り $\le\dfrac{2M}{\rho-1}\rho^{-N}$thm-sp-chebyshev
境界値問題 $-u''+u=f$ の選点法—$\max\lvert u-u_N\rvert\le2\sum_{\lvert k\rvert>m}\lvert\hat f(k)\rvert$prop-sp-bvp
Fourier 微分(偶数の点数)—係数の裾 $\lvert k\rvert\lvert\hat f(k)\rvert$ の和で抑える偏微分方程式の数値解法

ここで $V_s:=\int_{-\pi}^{\pi}\lvert f^{(s)}(x)\rvert\,dx$ である。Fourier 微分(格子点の値から導関数を求める操作)の誤差は 偏微分方程式の数値解法 の定理「Fourier微分の誤差」が同じ型の論法で証明している。

主定理と証明

誤差は係数の裾で決まる

三角補間の誤差

$f$ を $2\pi$ 周期の連続関数で、$\sum_{k\in\mathbb Z}\lvert\hat f(k)\rvert< \infty$ かつ $f(x)=\sum_k\hat f(k)e^{ikx}$(すべての $x$)を満たすものとする。$N=2m+1$ のとき

  1. (折り返しの公式)$\tilde f_k=\sum_{l\in\mathbb Z}\hat f(k+lN)$($\lvert k\rvert\le m$)。
  2. $\displaystyle\max_x\lvert f(x)-I_Nf(x)\rvert\le2\sum_{\lvert k\rvert>m}\lvert\hat f(k)\rvert$。
    連続で区分的に $C^1$ 級の $2\pi$ 周期関数は、仮定をすべて満たす(Fourier級数 の定理「連続で区分的に $C^1$ 級の関数の一様収束」)。
波数を $N$ を法として数える

1:$f(x_j)=\sum_n\hat f(n)e^{inx_j}$ を $\tilde f_k$ の式に入れる。級数は絶対収束するので有限和と順序を交換でき、
$$ \tilde f_k=\sum_n\hat f(n)\cdot\frac1N\sum_{j=0}^{N-1}e^{i(n-k)x_j}=\sum_{n\equiv k\ (\mathrm{mod}\ N)}\hat f(n) $$
である(lem-sp-discrete の 1)。$n=k+lN$ と書けば主張の式になる。
2:1 から
$$ f(x)-I_Nf(x)=\sum_{\lvert k\rvert>m}\hat f(k)e^{ikx}-\sum_{\lvert k\rvert\le m}\Bigl(\sum_{l\ne0}\hat f(k+lN)\Bigr)e^{ikx} $$
である。第 1 項の絶対値は $\sum_{\lvert k\rvert>m}\lvert\hat f(k)\rvert$ 以下である。第 2 項で $n=k+lN$($\lvert k\rvert\le m$、$l\ne0$)とおくと、$\lvert n\rvert\ge N-\lvert k\rvert\ge m+1$ であり、$\lvert k\rvert\le m$ の $N$ 個の整数は $N$ を法とした剰余を 1 回ずつ代表するので、$n$ から $(k,l)$ はただ 1 通りに決まる。よって第 2 項の絶対値は $\sum_{\lvert n\rvert>m}\lvert\hat f(n)\rvert$ 以下である。2 つを足して主張を得る。$\square$

補間の誤差の上界は、打ち切りの誤差 $\max\lvert f-P_mf\rvert\le\sum_{\lvert k\rvert>m}\lvert\hat f(k)\rvert$ のちょうど $2$ 倍である。格子点の値だけから係数を求めると、捨てた高い波数が低い波数に 折り返し(aliasing)て混ざるが、その量は捨てた分の大きさを超えない。したがってスペクトル法の精度の問題は、Fourier 係数がどれだけ速く $0$ に近づくか という問題に帰着する。

滑らかさと係数の減り方

滑らかな関数の係数

$s\ge1$ とし、$f$ を $2\pi$ 周期の $C^s$ 級関数とする。$k\ne0$ について
$$ \hat f(k)=\frac{\widehat{f^{(s)}}(k)}{(ik)^s},\qquad\lvert\hat f(k)\rvert\le\frac{V_s}{2\pi\lvert k\rvert^s},\qquad V_s:=\int_{-\pi}^{\pi}\lvert f^{(s)}(x)\rvert\,dx $$
である。$s\ge2$ なら $\max\lvert f-I_Nf\rvert\le\dfrac{2V_s}{\pi(s-1)}m^{1-s}$ である。

要点:部分積分を $s$ 回行うと、周期性で境界の項が消える。

詳しい証明を開く

$g$ を $2\pi$ 周期の $C^1$ 級関数とすると、部分積分で $\int_{-\pi}^{\pi}g(x)e^{-ikx}\,dx=\Bigl[\frac{g(x)e^{-ikx}}{-ik}\Bigr]_{-\pi}^{\pi}+\frac1{ik}\int_{-\pi}^{\pi}g'(x)e^{-ikx}\,dx$ で、境界の項は $g(\pi)=g(-\pi)$、$e^{-ik\pi}=e^{ik\pi}$ から $0$ である。よって $\hat g(k)=\widehat{g'}(k)/(ik)$。これを $g=f,f',\dots,f^{(s-1)}$ に順に使えば最初の式を得る。$\lvert\widehat{f^{(s)}}(k)\rvert\le V_s/(2\pi)$ から 2 番目の式が出る。$s\ge2$ なら $f$ は $C^1$ 級なので thm-sp-alias が使え、 $$ 2\sum_{\lvert k\rvert>m}\lvert\hat f(k)\rvert\le\frac{2V_s}{\pi}\sum_{k>m}k^{-s}\le\frac{2V_s}{\pi}\int_m^\infty t^{-s}\,dt=\frac{2V_s}{\pi(s-1)}m^{1-s} $$ である($k^{-s}\le\int_{k-1}^kt^{-s}\,dt$)。$\square$

$C^\infty$ 級ならすべての $s$ で使えるので、誤差は $m$ のどんな負べきよりも速く $0$ に近づく。さらに強く、指数関数的に減るのは正則に延びる場合である。

帯で正則な関数の係数

$a>0$ とし、帯 $S_a:=\{z\in\mathbb C\mid\lvert\operatorname{Im}z\rvert< a\}$ の上の正則関数 $F$ で、実軸の上で $F=f$、$S_a$ の上で $\lvert F\rvert\le M$ となるものがあるとする($f$ は $2\pi$ 周期)。このとき
$$ \lvert\hat f(k)\rvert\le Me^{-a\lvert k\rvert}\qquad(k\in\mathbb Z),\qquad\max_x\lvert f(x)-I_Nf(x)\rvert\le\frac{4M}{e^a-1}e^{-am} $$
である。

積分路を虚軸の方向へずらす

$F(z+2\pi)-F(z)$ は $S_a$ で正則で実軸の上で $0$ なので、一致の定理 により $S_a$ 全体で $F(z+2\pi)=F(z)$ である。
$k>0$ とし、$0< b< a$ をとる。$F(z)e^{-ikz}$ に Cauchyの積分定理 を、頂点 $-\pi,\ \pi,\ \pi-ib,\ -\pi-ib$ の長方形の周に沿って使う。左右の縦の辺の積分は、$F(z)e^{-ikz}$ が $z\mapsto z+2\pi$ で変わらない($e^{-2\pi ik}=1$)ので打ち消し合う。したがって
$$ \int_{-\pi}^{\pi}f(x)e^{-ikx}\,dx=\int_{-\pi}^{\pi}F(x-ib)\,e^{-ik(x-ib)}\,dx $$
である。$\lvert e^{-ik(x-ib)}\rvert=e^{-kb}$ なので $\lvert\hat f(k)\rvert\le Me^{-kb}$。$b\to a$ として $\lvert\hat f(k)\rvert\le Me^{-ak}$ を得る。$k< 0$ では長方形を上側($x+ib$)にとれば同じである。$k=0$ では $\lvert\hat f(0)\rvert\le M$ である。
後半:$f$ は $C^1$ 級なので thm-sp-alias が使え、$2\sum_{\lvert k\rvert>m}Me^{-a\lvert k\rvert}=4M\dfrac{e^{-a(m+1)}}{1-e^{-a}}=\dfrac{4M}{e^a-1}e^{-am}$ である。$\square$

指数の $a$ は、$f$ を正則に延ばせる帯の幅、すなわち 実軸から最も近い特異点までの距離 で決まる。特異点が実軸に近いほど収束は遅い。逆に、$C^1$ 級の $f$ の係数が $\lvert\hat f(k)\rvert\le Ce^{-b\lvert k\rvert}$ を満たせば、級数 $\sum_k\hat f(k)e^{ikz}$ は帯 $S_b$ の中の各コンパクト集合で一様に収束し、$f$ は $S_b$ へ正則に延びる。指数関数的な減り方と帯での正則性は、ほぼ同じことである。

境界値問題の Galerkin 法と選点法

周期的な境界値問題 $-u''+u=f$ を考える。$f$ が連続で区分的に $C^1$ 級なら、$u:=\sum_k\frac{\hat f(k)}{1+k^2}e^{ikx}$ は $C^2$ 級の周期的な解である(係数に $k^2$ を掛けても絶対収束するので 2 回まで項別に微分でき、$-u''+u=\sum_k\hat f(k)e^{ikx}=f$)。周期的な解はこれだけである:$w$ が $-w''+w=0$ の周期的な解なら、$\overline w$ を掛けて 1 周期で積分し部分積分すると $\int(\lvert w'\rvert^2+\lvert w\rvert^2)=0$ である。

Galerkin 法と選点法

$m\ge1$、$N=2m+1$ とする。

  1. Fourier–Galerkin 法:$u_m\in\mathcal T_m$ で、すべての $\varphi\in\mathcal T_m$ について $\int_{-\pi}^{\pi}\bigl(-u_m''+u_m-f\bigr)\overline\varphi\,dx=0$ を満たすものを求める。
  2. 選点法(擬スペクトル法):$u_N\in\mathcal T_m$ で、すべての格子点で $-u_N''(x_j)+u_N(x_j)=f(x_j)$ を満たすものを求める。
Galerkin 法と選点法の誤差

$f$ が $2\pi$ 周期で連続かつ区分的に $C^1$ 級なら、def-sp-methods の $u_m$、$u_N$ はただ 1 つ存在して $u_m=P_mu$、$u_N=\sum_{\lvert k\rvert\le m}\frac{\tilde f_k}{1+k^2}e^{ikx}$ であり、
$$ \max\lvert u-u_m\rvert\le\sum_{\lvert k\rvert>m}\frac{\lvert\hat f(k)\rvert}{1+k^2},\qquad\max\lvert u-u_N\rvert\le2\sum_{\lvert k\rvert>m}\lvert\hat f(k)\rvert $$
である。

要点:$\mathcal T_m$ の上で $-\partial_x^2+1$ は係数に $1+k^2$ を掛ける対角の作用素なので、Galerkin 法は $u$ の打ち切りを、選点法は $f$ の補間についての方程式を解くことになる。

詳しい証明を開く

$v=\sum_{\lvert k\rvert\le m}b_ke^{ikx}\in\mathcal T_m$ について $-v''+v=\sum_{\lvert k\rvert\le m}(1+k^2)b_ke^{ikx}$ である。Galerkin 法の条件を $\varphi=e^{ilx}$($\lvert l\rvert\le m$)で書くと、直交性から $(1+l^2)b_l=\hat f(l)$ で、これは $u_m=P_mu$ と同値である。誤差は $u-P_mu=\sum_{\lvert k\rvert>m}\frac{\hat f(k)}{1+k^2}e^{ikx}$ から出る。

選点法の条件は、$\mathcal T_m$ の元 $-u_N''+u_N$ が格子点で $f$ と一致することなので、lem-sp-discrete の 2 から $-u_N''+u_N=I_Nf$、すなわち $(1+k^2)b_k=\tilde f_k$ と同値である。thm-sp-alias の 1 から $$ u-u_N=\sum_{\lvert k\rvert>m}\frac{\hat f(k)}{1+k^2}e^{ikx}-\sum_{\lvert k\rvert\le m}\frac1{1+k^2}\Bigl(\sum_{l\ne0}\hat f(k+lN)\Bigr)e^{ikx} $$ で、$\frac1{1+k^2}\le1$ と prf-sp-alias と同じ数え方により、絶対値は $2\sum_{\lvert k\rvert>m}\lvert\hat f(k)\rvert$ 以下である。$\square$

選点法の誤差は、$f$ の補間の誤差と同じ速さで減る。$f$ が帯で正則なら、thm-sp-analytic から誤差は $e^{-am}$ の速さで減る。

区間の上の Chebyshev 展開

$[-1,1]$ の上の関数は周期的でないので、$x=\cos\theta$ と置き換える。$g(\theta):=f(\cos\theta)$ は $2\pi$ 周期の偶関数になり、両端での周期性の問題が消える。

Chebyshev 係数と Bernstein の楕円

$f$ を $[-1,1]$ の上の連続関数とする。
$$ a_0:=\frac1\pi\int_0^\pi f(\cos\theta)\,d\theta,\qquad a_n:=\frac2\pi\int_0^\pi f(\cos\theta)\cos n\theta\,d\theta\quad(n\ge1) $$
を $f$ の Chebyshev 係数 という。$\rho>1$ について、$\pm1$ を焦点とし半軸の長さが $\frac12(\rho+\rho^{-1})$、$\frac12(\rho-\rho^{-1})$ の楕円を $E_\rho$、その内部を $D_\rho$ と書く(Bernstein の楕円)。$E_\rho=\{\frac12(w+w^{-1})\mid\lvert w\rvert=\rho\}$ である。

Chebyshev 展開の収束

$\rho>1$ とし、$f$ は $D_\rho$ の上の正則関数で $\lvert f\rvert\le M$ を満たすとする。このとき $\lvert a_n\rvert\le2M\rho^{-n}$($n\ge1$)であり、$[-1,1]$ の上で一様に $f=\sum_{n\ge0}a_nT_n$ が成り立ち、
$$ \max_{-1\le x\le1}\Bigl\lvert f(x)-\sum_{n=0}^Na_nT_n(x)\Bigr\rvert\le\frac{2M}{\rho-1}\rho^{-N} $$
である。

帯を楕円に写す

$\theta=x+iy$ について $w:=e^{i\theta}$ とおくと $\cos\theta=\frac12(w+w^{-1})$、$\lvert w\rvert=e^{-y}$ である。$\frac12(w+w^{-1})$ は $w$ と $w^{-1}$ で同じ値なので、$\cos\theta\in E_{e^{\lvert y\rvert}}$($y=0$ なら線分 $[-1,1]$)である。$1< r< \rho$ の楕円 $E_r$ は焦点が共通で半軸が $r$ について狭義に増えるので $D_\rho$ に含まれる。よって帯 $\lvert\operatorname{Im}\theta\rvert< \log\rho$ は $\cos$ で $D_\rho$ に写り、$G(\theta):=f(\cos\theta)$ はこの帯で正則で $\lvert G\rvert\le M$ である。
$g(\theta)=f(\cos\theta)$ は偶関数なので $\hat g(n)=\hat g(-n)=\frac1{2\pi}\int_{-\pi}^{\pi}g(\theta)\cos n\theta\,d\theta$ であり、定義と比べて $a_0=\hat g(0)$、$a_n=2\hat g(n)$($n\ge1$)である。thm-sp-analytic を $a=\log\rho$ で使えば $\lvert a_n\rvert\le2Me^{-n\log\rho}=2M\rho^{-n}$。$g$ は $C^1$ 級なので Fourier級数 の定理「連続で区分的に $C^1$ 級の関数の一様収束」により
$$ g(\theta)=\hat g(0)+\sum_{n\ge1}\hat g(n)\bigl(e^{in\theta}+e^{-in\theta}\bigr)=\sum_{n\ge0}a_n\cos n\theta $$
が一様に成り立つ。$x=\cos\theta$ とおき、Chebyshev多項式 の定理「余弦の $n$ 倍角の公式」$T_n(\cos\theta)=\cos n\theta$ を使えば $f(x)=\sum_na_nT_n(x)$ である。$\lvert T_n\rvert\le1$ なので打ち切りの誤差は $\sum_{n>N}\lvert a_n\rvert\le2M\sum_{n>N}\rho^{-n}=\frac{2M}{\rho-1}\rho^{-N}$ である。$\square$

Chebyshev 型の補間

thm-sp-chebyshev の仮定の下で、$N+1$ 個の点 $\xi_j:=\cos\frac{2\pi j}{2N+1}$($j=0,\dots,N$)で $f$ と一致する $N$ 次以下の多項式 $p_N$ はただ 1 つで、$\max_{[-1,1]}\lvert f-p_N\rvert\le2\sum_{n>N}\lvert a_n\rvert\le\frac{4M}{\rho-1}\rho^{-N}$ である。

要点:$g=f(\cos\theta)$ の $2N+1$ 点の三角補間は偶関数なので $\cos\theta$ の多項式になり、thm-sp-alias がそのまま使える。

詳しい証明を開く

$\xi_j$ は相異なる $N+1$ 点なので、一致する $N$ 次以下の多項式は高々 1 つである。$g=f(\cos\theta)$ の $2N+1$ 点の三角補間 $I_{2N+1}g$ を考える。格子は $\theta\mapsto2\pi-\theta$ で保たれ $g$ は偶関数なので $\tilde g_{-k}=\tilde g_k$ であり、$I_{2N+1}g=\tilde g_0+\sum_{k=1}^N2\tilde g_k\cos k\theta=p(\cos\theta)$、$p:=\tilde g_0+\sum_{k=1}^N2\tilde g_kT_k$ と書ける。$p$ は $N$ 次以下で、$\theta_j=\frac{2\pi j}{2N+1}$ で $g$ と一致するので $p(\xi_j)=f(\xi_j)$、すなわち $p=p_N$ である。thm-sp-alias から $\max\lvert f-p_N\rvert=\max_\theta\lvert g-I_{2N+1}g\rvert\le2\sum_{\lvert k\rvert>N}\lvert\hat g(k)\rvert=2\sum_{n>N}\lvert a_n\rvert$ である。$\square$

実用では端点を含む Chebyshev 点 $\cos(\pi j/N)$ での補間もよく使われる。どちらの点も端の近くに集まっている。等間隔の点の多項式補間は、正則な関数でも誤差が増えることがある(Runge現象、ex-sp-runge)。

計算の手順

周期的な問題 $u_t=\mathcal L u+\mathcal N(u)$($\mathcal L$ は定数係数の線形の微分作用素、$\mathcal N$ は非線形の項)を Fourier の選点法で解く手順である。

  1. 格子と未知数:$N=2m+1$ 点 $x_j=2\pi j/N$ をとり、未知数を格子点の値 $u_j$ か係数 $\tilde u_k$($\lvert k\rvert\le m$)にとる。両者は 離散Fourier変換 で行き来する。
  2. 線形の項:$\partial_x$ は係数に $ik$ を掛ける操作になる。$\mathcal L=\nu\partial_x^2$ なら係数ごとに $-\nu k^2$ を掛ける(prop-sp-bvp と同じ対角化)。
  3. 非線形の項:係数を格子点の値に戻し、格子点で積や関数の値を計算し、もう一度係数に変換する。折り返しを避けたいときは、係数の上 $\frac13$ を $0$ にしてから積をとる($\frac23$ 則、反例の表の後の注意)。
  4. 時間の進め方:$-\nu k^2$ は $k$ の 2 乗で大きくなるので、陽的な方法では刻み $\Delta t$ を $m^{-2}$ 程度に小さくしなければならない。線形の項を陰的に、または積分因子 $e^{-\nu k^2t}$ で厳密に扱い、非線形の項だけを陽的に進める。
  5. 精度の確認:係数 $\lvert\tilde u_k\rvert$ を $k$ について片対数で描く。端の係数が丸めの誤差の大きさ(倍精度で $10^{-14}$ 程度)まで下がっていれば解像できている。下がらなければ $m$ を増やす。
    区間の問題では、1 の格子を Chebyshev 点にとり、2 の微分を Chebyshev 係数の漸化式か微分行列で計算する。境界条件は端点の方程式を置き換えて課す。

例題

指数関数的な収束:$f(x)=1/(2-\cos x)$

使う公式:thm-sp-alias、Poisson 核の展開。
答え:$\hat f(k)=\dfrac{(2-\sqrt3)^{\lvert k\rvert}}{\sqrt3}$ で、$2-\sqrt3=e^{-a}\approx0.267949$、$a=\log(2+\sqrt3)\approx1.316958$。三角補間の最大誤差は次のとおり。

$N$$m$$\max\lvert f-I_Nf\rvert$$2\sum_{\lvert k\rvert>m}\lvert\hat f(k)\rvert$
52$3.689\times10^{-2}$$6.069\times10^{-2}$
94$2.660\times10^{-3}$$4.357\times10^{-3}$
178$1.374\times10^{-5}$$2.246\times10^{-5}$
3316$3.654\times10^{-10}$$5.968\times10^{-10}$

$m$ を 1 増やすごとに誤差はおよそ $0.268$ 倍になる。$2-\cos z=0$ の解は $z=\pm ia+2\pi\mathbb Z$ なので、$f$ は帯 $S_a$ でちょうど正則であり、減る比 $e^{-a}$ は特異点までの距離 $a$ で決まっている。

係数の計算を開く

$0< r< 1$ について、等比級数から $\sum_kr^{\lvert k\rvert}e^{ikx}=\frac{1-r^2}{1-2r\cos x+r^2}$(Poisson核)である。$\frac{1+r^2}{2r}=2$ を満たす $r=2-\sqrt3$ をとると $2-\cos x=\frac{1-2r\cos x+r^2}{2r}$ なので、$\frac1{2-\cos x}=\frac{2r}{1-r^2}\sum_kr^{\lvert k\rvert}e^{ikx}$。$1-r^2=4\sqrt3-6=2\sqrt3(2-\sqrt3)$、$2r=2(2-\sqrt3)$ から $\frac{2r}{1-r^2}=\frac1{\sqrt3}$ である。誤差の列は、補間を $20001$ 点の細かい格子で評価した最大値である。

代数的な収束:三角波

使う公式:thm-sp-alias、Fourier級数 の例「三角波 $\lvert x\rvert$」の係数 $\hat f(k)=-\frac2{\pi k^2}$($k$ 奇数)。
答え:$N=9,17,33,65,129$ で最大誤差は $0.2588,\ 0.1283,\ 0.06346,\ 0.03151,\ 0.01569$ で、$m\cdot(\text{誤差})$ は $1.035,\ 1.026,\ 1.015,\ 1.008,\ 1.004$。誤差はおよそ $1/m$ でしか減らない。上界は $2\sum_{\lvert k\rvert>m}\lvert\hat f(k)\rvert\le\frac8\pi\sum_{k>m,\ k\text{ 奇数}}\frac1{k^2}\approx\frac4{\pi m}$ である。三角波は連続だが導関数が $x=0,\pi$ で跳ぶので、$C^2$ 級でなく、thm-sp-smooth の $s=2$ は使えない。

境界値問題の選点法

問題:$-u''+u=\dfrac1{2-\cos x}$ の周期解を、def-sp-methods の選点法と、同じ格子の 2 次の中心差分で解き、格子点での最大誤差を比べよ。
答え:真の解は $u=\sum_k\frac{(2-\sqrt3)^{\lvert k\rvert}}{\sqrt3(1+k^2)}e^{ikx}$ で $u(0)\approx0.7512788744$、$u(\pi)\approx0.4373075229$。

$N$選点法中心差分
5$6.901\times10^{-3}$$2.806\times10^{-2}$
9$1.279\times10^{-4}$$6.865\times10^{-3}$
17$1.890\times10^{-7}$$1.807\times10^{-3}$
33$1.340\times10^{-12}$$4.727\times10^{-4}$

選点法の誤差は区間全体の最大値($20001$ 点で評価)、中心差分の誤差は格子点の最大値である。中心差分は点の数を 2 倍にするとおよそ $\frac14$ 倍だが、選点法は 2 倍ごとに指数が 2 倍になる。

Runge 関数の Chebyshev 補間

問題:$f(x)=\dfrac1{1+25x^2}$ を $[-1,1]$ で、cor-sp-cheb-interp の点と等間隔の点で $N$ 次の多項式補間し、最大誤差を比べよ。
答え:$f$ の特異点は $\pm\frac i5$ で、これを通る Bernstein の楕円は $\rho=\frac{1+\sqrt{26}}5\approx1.219804$。Chebyshev 係数は偶数の $n$ で符号を交互に変えながら $\lvert a_n/a_{n-2}\rvert\to\rho^{-2}\approx0.672078$ の比で減る($a_{10}\approx-5.378\times10^{-2}$、$a_{40}\approx1.387\times10^{-4}$)。

$N$Chebyshev 型の補間$2\sum_{n>N}\lvert a_n\rvert$等間隔の補間
10$1.505\times10^{-1}$$2.205\times10^{-1}$$1.916$
20$2.577\times10^{-2}$$3.023\times10^{-2}$$59.82$
40$4.874\times10^{-4}$$5.684\times10^{-4}$$1.0\times10^{5}$
80$1.740\times10^{-7}$$2.009\times10^{-7}$$7.0\times10^{12}$

楕円 $E_\rho$ の上に極があるので thm-sp-chebyshev は $\rho$ そのものでは使えないが、$1< \rho'< \rho$ の $\rho'$ で使えて、どの $\rho'< \rho$ についても誤差は $O(\rho'^{-N})$ である。等間隔の補間の列は Vandermonde 行列を倍精度で解いた値で、$N$ が大きいところでは丸めの誤差も混じっているが、増え方は Runge現象 のとおりである。

図: 三つの例で、補間の最大誤差が m とともに減るようすを片対数で描いた図。正則な周期関数は直線的に、三角波はゆっくり、Runge 関数の Chebyshev 型の補間はその中間の傾きで減る 図: 三つの例で、補間の最大誤差が m とともに減るようすを片対数で描いた図。正則な周期関数は直線的に、三角波はゆっくり、Runge 関数の Chebyshev 型の補間はその中間の傾きで減る

使える条件と反例

thm-sp-alias の仮定・thm-sp-analytic の正則性・計算の手順の前提を 1 つずつ外す。

外す条件例何が起こるか成り立たなくなる結論
周期的な延長の連続性(thm-sp-alias の連続性)$f(x)=x$($0\le x< 2\pi$)を周期的に延ばす格子点 $x=0$ で $I_Nf=0$ だが、その左では $f\approx2\pi$最大誤差は $\pi$ 以上のままで $0$ に近づかない
正則性($C^\infty$ 級のまま)$f(x)=e^{-1/\sin^2(x/2)}$($x\notin2\pi\mathbb Z$)、$f(2\pi\mathbb Z)=0$係数はどんな負べきより速く減るが、どの $b>0$ でも $\lvert\hat f(k)\rvert\le Ce^{-b\lvert k\rvert}$ にならないthm-sp-analytic の指数関数的な減り方
$[-1,1]$ の上の正則性$f(x)=\lvert x\rvert$$a_0=\frac2\pi$、$a_n=\frac4\pi\frac{(-1)^{n/2+1}}{n^2-1}$($n\ge2$ 偶数)thm-sp-chebyshev の $\rho^{-N}$ の減り方。誤差の上界 $\sum_{n>N}\lvert a_n\rvert$ は $1/N$ 程度
積の帯域が $m$ 以下(手順 3)$N=9$、$u=\cos4x$ の $u^2=\frac12+\frac12\cos8x$ を格子点で計算補間すると $\frac12+\frac12\cos x$ になる波数 $8$ の成分が波数 $1$ に化ける
反例の確かめ

反例の表の 4 つの行を確かめる。

確かめを開く

1 行目:$I_Nf$ は連続で $I_Nf(0)=f(0)=0$ である。$x< 2\pi$ を $2\pi$ に近づけると $f(x)\to2\pi$、$I_Nf(x)\to0$ なので、$\sup\lvert f-I_Nf\rvert\ge2\pi>\pi$ である。$N=9,33,129$ の実際の値も $6.28$ である。

2 行目:$f$ は $C^\infty$ 級で $x=0$ のすべての導関数が $0$ なので、thm-sp-smooth がすべての $s$ で使える。$\lvert\hat f(k)\rvert\le Ce^{-b\lvert k\rvert}$($b>0$)なら、本文の注意により $f$ は帯 $S_b$ へ正則に延び、実軸の上で実解析的になる。$x=0$ の Taylor 展開はすべて $0$ なので、一致の定理 で $f\equiv0$ となるが、$f(\pi)=e^{-1}\ne0$ で矛盾する。$k=10,40,80$ で $-\log\lvert\hat f(k)\rvert/k$ は $0.94,\ 0.52,\ 0.40$ と小さくなり続ける。

3 行目:$a_n=\frac2\pi\int_0^\pi\lvert\cos\theta\rvert\cos n\theta\,d\theta$ を $[0,\frac\pi2]$ と $[\frac\pi2,\pi]$ に分けて計算すると、$n$ 奇数で $0$、$n\ge2$ 偶数で上の値、$n=0$ で $\frac2\pi$ になる。$\sum_{n>N}\lvert a_n\rvert$ は $\frac2{\pi N}$ 程度で、$\rho^{-N}$ の形では減らない。$\lvert x\rvert$ は $x=0$ で微分できないので、どの $D_\rho$ でも正則でない。

4 行目:$x_j=2\pi j/9$ で $\cos8x_j=\cos(9x_j-x_j)=\cos x_j$ である。格子点の値だけでは $\cos8x$ と $\cos x$ を区別できない。

折り返しを避ける $\frac23$ 則は、係数を $\lvert k\rvert\le m'$($m'\approx\frac23m$)に制限してから積をとる。$\lvert k\rvert,\lvert l\rvert\le m'$ の積の波数 $k+l$ は $2m'$ 以下で、これが $N$ を法として $\lvert k\rvert\le m'$ の範囲に折り返さないための条件が $2m'+m'< N$ である。

よくある誤り

誤り正しくはなぜ
区間 $[0,2\pi]$ で滑らかなら Fourier の方法で速く収束する周期的に延ばしたものが滑らかでなければならない反例の表の 1 行目
$C^\infty$ 級なら指数関数的に収束する指数関数的なのは帯で正則な場合反例の表の 2 行目
補間の誤差は打ち切りの誤差と同じ折り返しの分だけ増え、上界は 2 倍thm-sp-alias
非線形の項は格子点の積でそのまま計算してよい帯域が広がって低い波数に折り返す反例の表の 4 行目
区間の問題でも等間隔の点で高次の多項式補間をするcor-sp-cheb-interp の点や Chebyshev 点のように端に集まった点を使うex-sp-runge
陽的な時間積分で刻みを差分法と同じにとる$\nu k^2$ が $m^2$ で大きくなるので、刻みは $m^{-2}$ 程度手順 4

補足

Galerkin 法・選点法・tau 法. 方程式の残差を基底に直交させるのが Galerkin 法、格子点で 0 にするのが選点法である。区間の境界条件を、高い次数の係数の方程式を境界条件に置き換えて課す方法を tau 法という。定数係数の問題では Galerkin 法が対角の方程式になるが、変数係数や非線形の問題では選点法のほうが実装しやすい。
基底の選び方. 周期的なら Fourier 基底、区間なら Chebyshev 多項式か Legendre多項式、球面なら 球面調和関数、全直線なら Hermite 関数を使う。複雑な領域は、小さな要素に分けて各要素で高い次数の多項式を使うスペクトル要素法で扱う。
差分法との関係. Fourier の選点法の微分は、各格子点の導関数の近似値を、すべての格子点の値の線形結合として与える。スペクトル法は「格子全体を使う差分法」とみることもできる。

関連項目

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する