マルチグリッド法

同義語:多重格子法multigrid method

概要

マルチグリッド法(multigrid method)とは、楕円型偏微分方程式を離散化した連立1次方程式を、細かさの違う格子の階層を行き来して解く反復法である。細かい格子では重み付き Jacobi 法などの平滑化で振動の速い誤差を減らし、残りの誤差の方程式を粗い格子へ制限して解き、補間で戻して補正する。1次元 Poisson 方程式の差分で、線形補間、その転置に比例する制限、Galerkin の粗い行列、重み $2/3$ の重み付き Jacobi 法を使うと、2格子法の誤差はエネルギーノルムで格子の幅によらず1回に $1/3$ 倍以下になり、粗い段を2回ずつ解き前平滑化だけを行う多段のサイクルの縮小率も段の数によらず $1/(2\sqrt{2})$ 以下に抑えられる。粗い段の再帰の回数が2の次元乗未満なら、1サイクルの手間は未知数の個数に比例する。

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

前提知識: 反復法(連立1次方程式), 差分法, 正定値行列, 直交射影

マルチグリッド法(multigrid method、多重格子法)は、楕円型の偏微分方程式を差分法や有限要素法で離散化した連立 1 次方程式を、細かさの違う複数の格子を行き来して解く反復法である。
重みを $\frac23$ にした Jacobi 法(prop-mg-smoothing)を細かい格子でそのまま使うと、誤差のうち格子の目で振動する成分(高周波)は数回で減るが、ゆるやかな成分(低周波)は 1 回に $1-O(h^2)$ 倍しか減らない($h$ は格子の幅)。ゆるやかな誤差は粗い格子でも表せる。そこで細かい格子では高周波だけを減らし(平滑化)、残った誤差の方程式を粗い格子で解いて補間で戻す(粗い格子の補正)。これを何段もの格子で再帰的に行う。
この記事では 1 次元の Poisson 方程式の差分で、2 格子法の縮小率が格子の幅によらず $1/3$ であること、W サイクルの縮小率が段の数によらず抑えられることなどを証明する。

モデル問題と平滑化

区間 $(0,1)$ で $-u''=f$、$u(0)=u(1)=0$ を考える。奇数 $n=2m+1$ をとり、$h=1/(n+1)$、格子点を $x_j=jh$($j=0,\dots,n+1$)とする。2 階の中心差分で近似すると、内部の値 $u=(u_1,\dots,u_n)^{\mathsf T}$ についての方程式
$$ A_hu=f,\qquad A_h=\frac1{h^2}\begin{pmatrix}2&-1&&\\-1&2&\ddots&\\&\ddots&\ddots&-1\\&&-1&2\end{pmatrix} $$
を得る(差分法)。$A_h$ は $n$ 次の対称な 正定値行列 である。

モデル問題のモード

$k=1,\dots,n$ について、$\theta_k=k\pi h$、$s_k=\sin(\theta_k/2)$、$c_k=\cos(\theta_k/2)$ とおき、ベクトル $w_k\in\mathbb{R}^n$ を $(w_k)_j=\sin(j\theta_k)$ で定める。$w_k$ を モード といい、$k\le m$ のものを 低周波、$k\ge m+1$ のものを 高周波 という。

モデル行列の固有値

$A_hw_k=\lambda_kw_k$、$\lambda_k=\dfrac{4s_k^2}{h^2}$($k=1,\dots,n$)である。$w_1,\dots,w_n$ は互いに直交し、$w_k^{\mathsf T}w_k=\frac{n+1}2$ である。

固有値の計算を開く

加法定理から $\sin((j-1)\theta)+\sin((j+1)\theta)=2\cos\theta\sin(j\theta)$ なので、$-(w_k)_{j-1}+2(w_k)_j-(w_k)_{j+1}=2(1-\cos\theta_k)(w_k)_j=4s_k^2(w_k)_j$ である。$j=1$ と $j=n$ では、$\sin(0)=0$ と $\sin((n+1)\theta_k)=\sin(k\pi)=0$ により境界の値 $0$ と整合する。固有値 $4s_k^2/h^2$ は相異なるので、対称行列の固有ベクトルとして互いに直交する。$\sum_{j=1}^n\sin^2(j\theta_k)=\frac{n+1}2$ は $\sin^2=\frac12(1-\cos)$ と $\sum_{j=0}^{n}\cos(2j\theta_k)=0$($0< k< n+1$)による。$\square$

$A_h$ の対角部分は $D=\frac2{h^2}I$ である。$0< \omega$ について
$$ S_\omega=I-\omega D^{-1}A_h=I-\frac{\omega h^2}2A_h $$
を反復行列とする反復 $u\mapsto u+\omega D^{-1}(f-A_hu)$ を 重み付き Jacobi 法 という($\omega=1$ が Jacobi 法)。誤差 $e=u_\ast-u$($u_\ast$ は解)は $e\mapsto S_\omega e$ と動き、
$$ S_\omega w_k=(1-2\omega s_k^2)\,w_k $$
である。

重み付き Jacobi 法の平滑化

$0< \omega\le1$ とする。

  1. $S_\omega$ のスペクトル半径は $1-2\omega\sin^2(\pi h/2)=1-\frac{\omega\pi^2}2h^2+O(h^4)$ である。
  2. 高周波のモード $w_k$($k\ge m+1$)の縮小率は $\lvert1-2\omega s_k^2\rvert\le\max\{1-\omega,\ \lvert1-2\omega\rvert\}$ を満たす。右辺は $\omega=\frac23$ のとき最小で、値は $\frac13$ である。
縮小率は $s_k^2$ の 1 次関数である

要点:縮小率 $1-2\omega t$ は $t=s_k^2$ の 1 次関数なので、絶対値の最大は $t$ の範囲の端でとる。

詳しい証明を開く

$t=s_k^2$ は $k$ について単調に増え、$s_1^2=\sin^2(\pi h/2)$、$s_n^2=\cos^2(\pi h/2)=1-s_1^2$ である。$g(t)=1-2\omega t$ とおくと、$\lvert g\rvert$ の最大は $t=s_1^2$ か $t=s_n^2$ でとる。$g(s_1^2)=1-2\omega s_1^2>0$ で、$\lvert g(s_n^2)\rvert=\lvert1-2\omega+2\omega s_1^2\rvert$ である。$1-2\omega+2\omega s_1^2\le1-2\omega s_1^2$ は $s_1^2\le\frac12$ から、$2\omega-1-2\omega s_1^2\le1-2\omega s_1^2$ は $\omega\le1$ から従う。よって 1 を得る。

高周波では $t\in[\frac12,1)$ なので、$\lvert g(t)\rvert\le\max\{\lvert g(\frac12)\rvert,\lvert g(1)\rvert\}=\max\{1-\omega,\lvert1-2\omega\rvert\}$ である。$\omega\le\frac23$ では $1-\omega\ge\frac13$、$\omega\ge\frac23$ では $\lvert1-2\omega\rvert=2\omega-1\ge\frac13$ で、等号はともに $\omega=\frac23$ のときである。$\square$

$\omega=\frac23$ でも低周波はほぼ減らない(図 1)。$\omega=1$ では最も高周波の $w_n$ の縮小率も $-\cos(\pi h)$ である。
n=63 のモデル問題で、重み付き Jacobi 法の各モード w_k の縮小率 1-2ω sin^2(kπh/2) を k に対して描いたもの。ω=1、2/3、1/2 の 3 本の曲線。右半分の網掛けが高周波(k≥32)。ω=2/3 の曲線は高周波の範囲で点線の ±1/3 の間に収まる。どの曲線も k=1 の近くでは 1 に近い。 n=63 のモデル問題で、重み付き Jacobi 法の各モード w_k の縮小率 1-2ω sin^2(kπh/2) を k に対して描いたもの。ω=1、2/3、1/2 の 3 本の曲線。右半分の網掛けが高周波(k≥32)。ω=2/3 の曲線は高周波の範囲で点線の ±1/3 の間に収まる。どの曲線も k=1 の近くでは 1 に近い。

定義と使える条件

以下、$A$ を $n$ 次の対称な 正定値行列 とし、$A$ による内積とノルム
$$ (x,y)_A=y^{\mathsf T}Ax,\qquad \|x\|_A=\sqrt{x^{\mathsf T}Ax} $$
を使う(エネルギーノルム)。行列 $M$ の $\|\cdot\|_A$ についての作用素ノルムを $\|M\|_A$ と書く。

補間と制限

$n_H< n$ とする。列が 1 次独立な $n\times n_H$ 行列 $P$ を 補間(延長)、$n_H\times n$ 行列 $R$ を 制限 という。$A_H=RAP$ を Galerkin の粗い行列 という。
モデル問題($n=2m+1$、$n_H=m$、$H=2h$)では、粗い格子の点 $x_{2j}$($j=1,\dots,m$)の値 $v=(v_1,\dots,v_m)^{\mathsf T}$ に対し、$v_0=v_{m+1}=0$ として
$$ (Pv)_{2j}=v_j,\qquad (Pv)_{2j+1}=\tfrac12(v_j+v_{j+1}) $$
とおく(線形補間)。$R=\frac12P^{\mathsf T}$ は
$$ (Ru)_j=\tfrac14\bigl(u_{2j-1}+2u_{2j}+u_{2j+1}\bigr) $$
で、全重み(full weighting)の制限という。

誤差 $e=u_\ast-u$ は $Ae=r$($r=f-Au$)を満たす。$A_He_H=Rr$ を解いて $u\leftarrow u+Pe_H$ と直すことを 粗い格子の補正 といい、誤差は
$$ e\ \mapsto\ Te,\qquad T=I-PA_H^{-1}RA $$
と動く。

2 格子法

平滑化 の反復行列 $S$(例えば重み付き Jacobi 法の $S_\omega$)と回数 $\nu_1,\nu_2\ge0$ を定める。近似解 $u$ に $\nu_1$ 回の平滑化(前平滑化)を行い、残差 $r=f-Au$ から $r_H=Rr$ を作り、$A_He_H=r_H$ を解いて $u\leftarrow u+Pe_H$ とし、最後に $\nu_2$ 回の平滑化(後平滑化)を行う。この 1 回を 2 格子法 という。誤差の反復行列は $S^{\nu_2}TS^{\nu_1}$ である。

$A_He_H=r_H$ を同じ方法で近似的に解くと、多段の方法になる。

マルチグリッドの 1 サイクル

段 $\ell=0,\dots,L$ に $n_\ell$ 次の行列 $A_\ell$、段 $\ell\ge1$ に補間 $P_\ell$・制限 $R_\ell$・平滑化 $S_\ell$ があり、$A_{\ell-1}=R_\ell A_\ell P_\ell$ とする。整数 $\gamma\ge1$ について $\mathrm{MG}_\ell(u,f)$ を再帰的に定める。$\ell=0$ なら $A_0u=f$ の解を返す。$\ell\ge1$ なら、$\nu_1$ 回の前平滑化、$r_H=R_\ell(f-A_\ell u)$、$e_H=0$ から $e_H\leftarrow\mathrm{MG}_{\ell-1}(e_H,r_H)$ を $\gamma$ 回、$u\leftarrow u+P_\ell e_H$、$\nu_2$ 回の後平滑化を行った値を返す。
$\gamma=1$ を V サイクル、$\gamma=2$ を W サイクル という。$\mathrm{MG}_L$ を繰り返す反復を マルチグリッド法 という。

モデル問題では $n_\ell=2^{\ell+1}-1$、$h_\ell=2^{-(\ell+1)}$ とし、最も粗い段は未知数 1 個である。定理で使う条件は次のとおりである。

  1. 対称正定値性:各 $A_\ell$ は対称な正定値行列である。
  2. 補間の階数:各 $P_\ell$ の列は 1 次独立である。
  3. Galerkin の関係:ある $c_\ell>0$ について $R_\ell=c_\ell P_\ell^{\mathsf T}$、$A_{\ell-1}=R_\ell A_\ell P_\ell$ である。
  4. 平滑化の安定性:$\|S_\ell\|_{A_\ell}\le1$ である。
  5. 2 格子法の一様な収束:2 格子法の縮小率 $\sigma$ が格子の幅によらず $1$ 未満である。
    条件 1〜3 から $A_H=cP^{\mathsf T}AP$ は正定値で($x^{\mathsf T}P^{\mathsf T}APx=\|Px\|_A^2$)、粗い格子の方程式はただ 1 つの解をもつ。

主定理と証明

粗い格子の補正は射影である

粗い格子の補正

条件 1〜3 のもとで $T=I-PA_H^{-1}RA$ とおく。

  1. $T^2=T$、$(Tx,y)_A=(x,Ty)_A$ で、$T$ は $c$ によらない。
  2. $T$ の核は $P$ の像、$T$ の像は $\{e:P^{\mathsf T}Ae=0\}$($P$ の像の $A$ 直交補空間)である。
  3. $\|e\|_A^2=\|Te\|_A^2+\|(I-T)e\|_A^2$、$\|Te\|_A=\min_v\|e-Pv\|_A$ である。
    つまり $T$ は内積 $(\cdot,\cdot)_A$ についての 直交射影 である。
正規方程式の形に書く

要点:$Q=I-T=P(P^{\mathsf T}AP)^{-1}P^{\mathsf T}A$ は最小二乗法の正規方程式の解の形で、$Q^2=Q$ と $AQ$ の対称性が直接に分かる。

詳しい証明を開く

$R=cP^{\mathsf T}$、$A_H=cP^{\mathsf T}AP$ から $c$ が約されて $Q=P(P^{\mathsf T}AP)^{-1}P^{\mathsf T}A$ である。これから $Q^2=Q$ で、$AQ=AP(P^{\mathsf T}AP)^{-1}P^{\mathsf T}A$ は対称なので $(Qx,y)_A=y^{\mathsf T}AQx=x^{\mathsf T}AQy=(x,Qy)_A$ である。$T=I-Q$ も同じ性質をもち、1 を得る。

$QP=P$ なので $P$ の像は $Q$ の像に含まれ、逆の包含は $Q$ の形から明らかである。$Te=0$ は $Qe=e$ と同値なので、$T$ の核は $P$ の像である。$P^{\mathsf T}AT=P^{\mathsf T}A-P^{\mathsf T}AP(P^{\mathsf T}AP)^{-1}P^{\mathsf T}A=0$ なので $T$ の像は $\{e:P^{\mathsf T}Ae=0\}$ に含まれ、逆に $P^{\mathsf T}Ae=0$ なら $Qe=0$ で $Te=e$ である。これで 2 を得る。

$TQ=Q-Q^2=0$ なので $(Te,Qe)_A=(e,TQe)_A=0$ で、3 の前半を得る。任意の $v$ について $e-Pv=Te+(Qe-Pv)$ で、第 2 項は $P$ の像にあり $Te$ と $A$ 直交するので、$\|e-Pv\|_A^2=\|Te\|_A^2+\|Qe-Pv\|_A^2\ge\|Te\|_A^2$ である。等号は $Pv=Qe$ のときに成り立つ。$\square$

$P$ の像に $A$ 直交する誤差は補正で減らない($\|T\|_A=1$)。それを減らすのが平滑化である。

モデル問題のモード

$k=1,\dots,m$ について $k'=n+1-k$ とおき、粗い格子のモード $v_k\in\mathbb{R}^m$ を $(v_k)_j=\sin(2j\theta_k)$ で定める。$\theta_{k'}=\pi-\theta_k$ なので $s_{k'}=c_k$、$c_{k'}=s_k$、$(w_{k'})_j=(-1)^{j+1}(w_k)_j$ である。

補間と制限のモードへの作用

モデル問題で $k=1,\dots,m$ とし、$s=s_k$、$c=c_k$ と書く。
$$ Pv_k=c^2w_k-s^2w_{k'},\qquad P^{\mathsf T}w_k=2c^2v_k,\qquad P^{\mathsf T}w_{k'}=-2s^2v_k,\qquad P^{\mathsf T}w_{m+1}=0 $$
である。

加法定理で偶数番と奇数番を分けて計算する

要点:$\sin((i-1)\theta)+\sin((i+1)\theta)=2\cos\theta\sin(i\theta)$ を、偶数番と奇数番の成分に分けて使う。

詳しい証明を開く

$P$ の定義から $(P^{\mathsf T}u)_j=\frac12u_{2j-1}+u_{2j}+\frac12u_{2j+1}$ である。$u=w_k$ なら、加法定理で $(P^{\mathsf T}w_k)_j=(1+\cos\theta_k)\sin(2j\theta_k)=2c^2(v_k)_j$ である。$w_{k'}$ では $\theta_k$ を $\pi-\theta_k$ に替えて $(1-\cos\theta_k)\cdot(-\sin(2j\theta_k))=-2s^2(v_k)_j$ である。$w_{m+1}$ は $\theta=\frac\pi2$ で、$1+\cos\theta=1$、$\sin(2j\cdot\frac\pi2)=0$ なので $0$ である。

$Pv_k$ の偶数番 $2j$ の成分は $\sin(2j\theta_k)$、奇数番 $i=2j+1$ の成分は $\frac12(\sin(2j\theta_k)+\sin((2j+2)\theta_k))=\cos\theta_k\sin(i\theta_k)$ である($(v_k)_0=(v_k)_{m+1}=0$ は $\sin(k\pi)=0$ による)。一方 $c^2w_k-s^2w_{k'}$ の第 $i$ 成分は $(c^2+(-1)^is^2)\sin(i\theta_k)$ で、$i$ が偶数なら $\sin(i\theta_k)$、奇数なら $(c^2-s^2)\sin(i\theta_k)=\cos\theta_k\sin(i\theta_k)$ である。両者は一致する。$\square$

モデル問題の Galerkin の行列

モデル問題で $R=\frac12P^{\mathsf T}$(全重み)とすると、$RA_hP=A_{2h}$、すなわち幅 $H=2h$ の格子で同じ差分を作った $m$ 次の行列に等しい。

粗い格子のモードで比べる

要点:両辺が粗い格子のモード $v_k$ に同じ固有値で作用することを示す。

詳しい証明を開く

fml-mg-eigen と lem-mg-modes から $$P^{\mathsf T}A_hPv_k=c^2\lambda_k\cdot2c^2v_k+s^2\lambda_{k'}\cdot2s^2v_k=\frac{8s^2c^2}{h^2}v_k=\frac{2\sin^2\theta_k}{h^2}v_k$$ で、$RA_hPv_k=\frac{\sin^2\theta_k}{h^2}v_k$ である。$v_k$ は幅 $2h$ の格子の角 $2\theta_k$ のモードなので、fml-mg-eigen から $A_{2h}v_k=\frac{4\sin^2\theta_k}{(2h)^2}v_k$ である。$v_1,\dots,v_m$ は基底なので 2 つの行列は等しい。$\square$

2 格子法の縮小率

モデル問題の 2 格子法

モデル問題($n=2m+1$、$m\ge1$)で、$P$ を線形補間、$R=\kappa P^{\mathsf T}$($\kappa>0$)、$A_H=RA_hP$、$T=I-PA_H^{-1}RA_h$ とし、平滑化を重み付き Jacobi 法 $S=S_\omega$($\omega>0$)とする。このとき
$$ \|S_\omega T\|_{A_h}=\|TS_\omega\|_{A_h}=\max_{1\le k\le m+1}\sqrt{(1-2\omega)^2+\omega(2-3\omega)\sin^2\theta_k} $$
である。特に次が成り立つ。

  1. $\omega=\frac23$ なら、すべての $n$ について $\|S_\omega T\|_{A_h}=\frac13$ である。
  2. $0< \omega\le\frac23$ なら $\|S_\omega T\|_{A_h}=1-\omega$ である。
  3. $\omega=1$ なら $\|S_\omega T\|_{A_h}=\cos(\pi h)$ で、$h\to0$ で $1$ に近づく。
2 次元の不変部分空間ごとに計算する

モードへの作用。 $k\le m$ とし、$s=s_k$、$c=c_k$、$g=\frac{2\sin^2\theta_k}{h^2}>0$ とおく。prf-mg-galerkin-1d の計算から $A_Hv_k=\kappa gv_k$($\kappa$ は $R=\kappa P^{\mathsf T}$ の定数)である。lem-mg-modes と $\lambda_k=\frac{4s^2}{h^2}$、$\lambda_{k'}=\frac{4c^2}{h^2}$ から
$$ RA_hw_k=\kappa\lambda_k\cdot2c^2v_k=\kappa g\,v_k,\qquad RA_hw_{k'}=-\kappa\lambda_{k'}\cdot2s^2v_k=-\kappa g\,v_k $$
なので、$A_H^{-1}RA_hw_k=v_k$、$A_H^{-1}RA_hw_{k'}=-v_k$ である。再び lem-mg-modes により
$$ Tw_k=w_k-(c^2w_k-s^2w_{k'})=s^2(w_k+w_{k'}),\qquad Tw_{k'}=w_{k'}+(c^2w_k-s^2w_{k'})=c^2(w_k+w_{k'}) $$
である。$k=m+1$ では $P^{\mathsf T}w_{m+1}=0$ から $RA_hw_{m+1}=0$ で、$Tw_{m+1}=w_{m+1}$ である。また $S_\omega w_k=(1-2\omega s^2)w_k$、$S_\omega w_{k'}=(1-2\omega c^2)w_{k'}$、$S_\omega w_{m+1}=(1-\omega)w_{m+1}$ である。
直交分解。 固有ベクトル $w_1,\dots,w_n$ は $A_h$ 直交でもある。$W_k=\operatorname{span}\{w_k,w_{k'}\}$($k\le m$)と $W_{m+1}=\operatorname{span}\{w_{m+1}\}$ は互いに $A_h$ 直交し、$\mathbb{R}^n$ はその直和で、どれも $S_\omega$ と $T$ で不変である。よって $\|S_\omega T\|_{A_h}$ は各 $W_k$ の上のノルムの最大である。
各ブロック。 $w_k^{\mathsf T}w_k=w_{k'}^{\mathsf T}w_{k'}$ なので $\|w_k\|_{A_h}:\|w_{k'}\|_{A_h}=\sqrt{\lambda_k}:\sqrt{\lambda_{k'}}=s:c$ である。ある $\rho>0$ で $w_k=\rho s\,\epsilon_1$、$w_{k'}=\rho c\,\epsilon_2$ となる $A_h$ 正規直交基底 $\epsilon_1,\epsilon_2$ をとると、上の式は
$$ T\epsilon_1=s\,(s\epsilon_1+c\epsilon_2),\qquad T\epsilon_2=c\,(s\epsilon_1+c\epsilon_2) $$
となる。単位ベクトル $q=s\epsilon_1+c\epsilon_2$ について $Tx=(x,q)_{A_h}\,q$ で、$W_k$ の上の $T$ は $q$ への直交射影である。$S_\omega$ はこの基底で $\operatorname{diag}(1-2\omega s^2,1-2\omega c^2)$ なので、$W_k$ の上で
$$ \|S_\omega T\|^2=\|S_\omega q\|_{A_h}^2=s^2(1-2\omega s^2)^2+c^2(1-2\omega c^2)^2 $$
である。$t=s^2$、$1-t=c^2$ として展開すると
$$ t(1-2\omega t)^2+(1-t)\bigl(1-2\omega+2\omega t\bigr)^2=(1-2\omega)^2+4\omega(2-3\omega)\,t(1-t) $$
で(両辺の $t$ の 0 次・1 次・2 次・3 次の係数は $(1-2\omega)^2$、$8\omega-12\omega^2$、$12\omega^2-8\omega$、$0$ で一致する)、$4t(1-t)=4s^2c^2=\sin^2\theta_k$ である。$W_{m+1}$ では値は $(1-\omega)^2$ で、これは $\theta_{m+1}=\frac\pi2$ の式の値 $(1-2\omega)^2+\omega(2-3\omega)$ に等しい。これで $\|S_\omega T\|_{A_h}$ の式を得る。
順序の交換。 $A_hS_\omega=A_h-\frac{\omega h^2}2A_h^2$ は対称なので $S_\omega$ は $(\cdot,\cdot)_{A_h}$ について自己共役で、lem-mg-projector から $T$ もそうである。よって $TS_\omega$ は $S_\omega T$ の随伴で、ノルムは等しい。
特別な場合。 $\omega=\frac23$ では $2-3\omega=0$ で値は $\frac13$ である。$0< \omega\le\frac23$ では最大は $\sin^2\theta_{m+1}=1$ のときの $(1-\omega)^2$ である。$\omega=1$ では値は $\cos^2\theta_k$ で、最大は $k=1$ の $\cos^2(\pi h)$ である。$\square$

多段への再帰

マルチグリッドのサイクルの縮小率

def-mg-cycle で各段が条件 1〜4 を満たし、前平滑化 $\nu\ge1$ 回、後平滑化 $0$ 回とする。$T_\ell=I-P_\ell A_{\ell-1}^{-1}R_\ell A_\ell$ について $\|T_\ell S_\ell^\nu\|_{A_\ell}\le\sigma< 1$($\ell\ge1$)とする。$\mathrm{MG}_\ell$ の誤差の反復行列 $M_\ell$ について $\delta_\ell=\|M_\ell\|_{A_\ell}$ とおくと、$\delta_0=0$ で
$$ \delta_\ell^2\le\sigma^2+(1-\sigma^2)\,\delta_{\ell-1}^{2\gamma}\qquad(\ell\ge1) $$
である。よって次が成り立つ。

  1. V サイクル($\gamma=1$):$\delta_L^2\le1-(1-\sigma^2)^L$ である。
  2. W サイクル($\gamma=2$)で $\sigma^2< \frac12$ なら、段の数 $L$ によらず $\delta_L\le\sigma/\sqrt{1-\sigma^2}$ である。
誤差を $A$ 直交な 2 つに分ける

反復行列。 誤差 $e$ は前平滑化で $e_1=S_\ell^\nu e$ になり、残差は $A_\ell e_1$ である。粗い段の方程式の解は $y=A_{\ell-1}^{-1}R_\ell A_\ell e_1$ で、$0$ から $\mathrm{MG}_{\ell-1}$ を $\gamma$ 回行うと($\ell$ についての帰納法で)誤差 $y-e_H$ は $M_{\ell-1}^\gamma y$ になる。よって新しい誤差は
$$ e_1-P_\ell e_H=T_\ell e_1+P_\ell M_{\ell-1}^\gamma y $$
である。
評価。 2 つの項は $T_\ell$ の像と $P_\ell$ の像にあり、lem-mg-projector により $A_\ell$ 直交する。$R_\ell=c_\ell P_\ell^{\mathsf T}$ から $\|P_\ell z\|_{A_\ell}^2=z^{\mathsf T}P_\ell^{\mathsf T}A_\ell P_\ell z=c_\ell^{-1}\|z\|_{A_{\ell-1}}^2$ で、$P_\ell y=(I-T_\ell)e_1$ なので
$$ \|P_\ell M_{\ell-1}^\gamma y\|_{A_\ell}^2\le\delta_{\ell-1}^{2\gamma}\,c_\ell^{-1}\|y\|_{A_{\ell-1}}^2=\delta_{\ell-1}^{2\gamma}\|(I-T_\ell)e_1\|_{A_\ell}^2 $$
である。$d=\delta_{\ell-1}^{2\gamma}\le1$(帰納的に成り立つ)とし、lem-mg-projector の 3、条件 4 の $\|e_1\|\le\|e\|$、$\|T_\ell e_1\|\le\sigma\|e\|$ を使うと
$$ \|M_\ell e\|_{A_\ell}^2\le\|T_\ell e_1\|^2+d\bigl(\|e_1\|^2-\|T_\ell e_1\|^2\bigr)=(1-d)\|T_\ell e_1\|^2+d\|e_1\|^2\le\bigl(\sigma^2+(1-\sigma^2)d\bigr)\|e\|^2 $$
である(ノルムは $A_\ell$ のもの)。
1 と 2。 $x_\ell=\delta_\ell^2$ とおく。$\gamma=1$ では $x_\ell\le1-(1-\sigma^2)^\ell$ が帰納法で従う:$\sigma^2+(1-\sigma^2)(1-(1-\sigma^2)^{\ell-1})=1-(1-\sigma^2)^\ell$ である。$\gamma=2$ では $x_\ast=\sigma^2/(1-\sigma^2)$ は $(1-\sigma^2)x^2-x+\sigma^2=0$ の根で、$\sigma^2< \frac12$ なら $x_\ast< 1$ である。$x_{\ell-1}\le x_\ast$ なら $x_\ell\le\sigma^2+(1-\sigma^2)x_\ast^2=x_\ast$ で、$x_0=0$ から帰納法で $x_\ell\le x_\ast$ を得る。$\square$

モデル問題の W サイクル

モデル問題の段 $\ell$($n_\ell=2^{\ell+1}-1$)を線形補間と全重みで結び、$\omega=\frac23$ の重み付き Jacobi 法の前平滑化 1 回とする。W サイクルの誤差の反復行列は、段の数によらず $\|M_L\|_{A_L}\le\frac1{2\sqrt2}\approx0.3536$ を満たす。V サイクルについてこの記事で示せるのは $\|M_L\|_{A_L}^2\le1-(\frac89)^L$ である。

prop-mg-galerkin-1d により各段はモデル問題で、thm-mg-twogrid により $\sigma=\frac13$ である。$S_{2/3}$ は $A_\ell$ の多項式で固有値の絶対値が $1$ 未満なので条件 4 も成り立つ。

1 サイクルの手間

1 サイクルの手間

段 $\ell$ の平滑化・残差・補間・制限の手間が $Cn_\ell$ 以下、最も粗い段の手間が $C_0$ 以下で、$n_{\ell-1}\le n_\ell/2^d$ とする。$\gamma< 2^d$ なら、1 サイクルの手間 $W_L$ は
$$ W_L\le\Bigl(\frac{C}{1-\gamma/2^d}+C_0\Bigr)n_L $$
を満たす。

等比級数で抑える

要点:$W_\ell\le Cn_\ell+\gamma W_{\ell-1}$ を繰り返し、等比級数で抑える。

詳しい証明を開く

定義から $W_\ell\le Cn_\ell+\gamma W_{\ell-1}$、$W_0\le C_0$ である。繰り返すと $W_L\le C\sum_{j=0}^{L-1}\gamma^jn_{L-j}+\gamma^LC_0$ で、$n_{L-j}\le2^{-dj}n_L$ から第 1 項は $Cn_L\sum_j(\gamma/2^d)^j\le Cn_L/(1-\gamma/2^d)$ である。$1\le n_0\le2^{-dL}n_L$ から $\gamma^L\le(\gamma/2^d)^Ln_L\le n_L$ である。$\square$

$d$ は空間の次元である。1 次元の W サイクルは $\gamma=2^d$ で、手間は $O(n_L\log n_L)$ である。

公式の表

モデル問題($n=2m+1$、$h=\frac1{n+1}$、$\theta_k=k\pi h$、$s_k=\sin\frac{\theta_k}2$、$c_k=\cos\frac{\theta_k}2$、$k'=n+1-k$)と一般の場合の式を並べる。

量式使える条件根拠
差分の行列の固有値$A_hw_k=\frac{4s_k^2}{h^2}w_k$モデル問題fml-mg-eigen
重み付き Jacobi 法の縮小率$S_\omega w_k=(1-2\omega s_k^2)w_k$モデル問題、$D=\frac2{h^2}I$fml-mg-eigen
Jacobi 法のスペクトル半径$\rho(S_\omega)=1-2\omega\sin^2\frac{\pi h}2$$0< \omega\le1$prop-mg-smoothing
高周波の縮小率$\max_{k>m}\lvert1-2\omega s_k^2\rvert\le\max\{1-\omega,\lvert1-2\omega\rvert\}$、$\omega=\frac23$ で $\frac13$$0< \omega\le1$prop-mg-smoothing
補間・全重みのモードへの作用$Pv_k=c_k^2w_k-s_k^2w_{k'}$、$\frac12P^{\mathsf T}w_k=c_k^2v_k$$k\le m$lem-mg-modes
Galerkin の行列$\frac12P^{\mathsf T}A_hP=A_{2h}$1 次元、線形補間prop-mg-galerkin-1d
粗い格子の補正$T=I-P(P^{\mathsf T}AP)^{-1}P^{\mathsf T}A$ は $A$ 直交射影条件 1〜3lem-mg-projector
2 格子法の縮小率$\Vert S_\omega T\Vert_A^2=\max_{k\le m+1}\bigl[(1-2\omega)^2+\omega(2-3\omega)\sin^2\theta_k\bigr]$モデル問題、$\omega>0$thm-mg-twogrid
最適な重み$\omega=\frac23$ で $\Vert S_\omega T\Vert_A=\frac13$モデル問題thm-mg-twogrid
サイクルの漸化式$\delta_\ell^2\le\sigma^2+(1-\sigma^2)\delta_{\ell-1}^{2\gamma}$条件 1〜4、前平滑化だけthm-mg-cycle
W サイクルの一様な評価$\delta_L\le\sigma/\sqrt{1-\sigma^2}$$\gamma=2$、$\sigma^2< \frac12$thm-mg-cycle
1 サイクルの手間$W_L\le\bigl(\frac C{1-\gamma/2^d}+C_0\bigr)n_L$$\gamma< 2^d$prop-mg-cost
平滑化の性質と近似の性質による評価$\Vert ST\Vert_A\le\sqrt{1-\alpha/\beta}$条件 1〜3、rem-mg-sa の 2 つの不等式rem-mg-sa(Saa03 Theorem 13.3)

計算の手順

  1. 段を作る。 幅を 2 倍ずつにした格子を直接法で解ける大きさまで作り、$P_\ell$ を線形補間、$R_\ell=cP_\ell^{\mathsf T}$、$A_{\ell-1}=R_\ell A_\ell P_\ell$ とする。
  2. 平滑化を選ぶ。 重み付き Jacobi 法(1 次元 $\omega=\frac23$、2 次元の 5 点公式 $\omega=\frac45$)か Gauss–Seidel 法を前後に 1〜2 回。
  3. サイクルを繰り返す。 def-mg-cycle のとおりに行う。
  4. 止める。 $\|f-Au\|_2\le\varepsilon\|f\|_2$ で止め、回数に上限を置く。離散化の誤差は $O(h^2)$ なので、$\varepsilon$ を極端に小さくしても解の精度は上がらない。
  5. 確かめる。 残差の比が格子を細かくしても変わらないことを見る。

例題

$n=7$ のモードと平滑化

$n=7$($h=\frac18$)で、各モードの固有値と縮小率を求める。
使う公式:fml-mg-eigen、prop-mg-smoothing、lem-mg-modes。
答え:

$k$$1$$2$$3$$4$$5$$6$$7$
$h^2\lambda_k=4s_k^2$$0.15224$$0.58579$$1.23463$$2$$2.76537$$3.41421$$3.84776$
$\omega=\frac23$ の縮小率$0.94925$$0.80474$$0.58846$$0.33333$$0.07821$$-0.13807$$-0.28259$
$\omega=1$ の縮小率$0.92388$$0.70711$$0.38268$$0$$-0.38268$$-0.70711$$-0.92388$
全重みの係数 $c_k^2$$0.96194$$0.85355$$0.69134$

高周波の縮小率の絶対値の最大は、$\omega=\frac23$ で $\frac13$、$\omega=1$ で $0.92388$ である。

2 格子法の 1 回

$n=7$、$\omega=\frac23$ で、誤差 $e_0=w_1+w_7$ に前平滑化 1 回と粗い格子の補正を行う。
使う公式:prf-mg-twogrid のモードへの作用。
答え:

誤差$\Vert\cdot\Vert_{A_h}$
はじめ$w_1+w_7$$32$
平滑化の後$0.94925\,w_1-0.28259\,w_7$$\frac{32}3\approx10.667$
補正の後$-\frac{\sqrt2}6(w_1+w_7)$$\frac{16\sqrt2}3\approx7.5425$

縮小率は $\frac{\sqrt2}6\approx0.2357\le\frac13$ である。

途中の計算を開く

$s^2=\sin^2\frac\pi{16}$、$c^2=1-s^2$ とする。$\Vert w_1\Vert_{A_h}^2=\lambda_1w_1^{\mathsf T}w_1=256s^2\cdot4=1024s^2$、同様に $\Vert w_7\Vert_{A_h}^2=1024c^2$ で、$\Vert e_0\Vert_{A_h}^2=1024$ である。平滑化で $w_1,w_7$ はそれぞれ $a=1-\frac43s^2$、$b=1-\frac43c^2$ 倍になり、$\Vert aw_1+bw_7\Vert_{A_h}^2=1024(a^2s^2+b^2c^2)=1024\cdot\frac19$(prf-mg-twogrid の恒等式で $\omega=\frac23$)である。$T(aw_1+bw_7)=(as^2+bc^2)(w_1+w_7)$ で、$as^2+bc^2=1-\frac43(s^4+c^4)=1-\frac43\bigl(1-\frac12\sin^2\frac\pi8\bigr)=1-\frac43\cdot\frac{6+\sqrt2}8=-\frac{\sqrt2}6$ である。

V サイクルと W サイクルの縮小率

cor-mg-model の設定で $\Vert M_L\Vert_{A}$ を求める($n=2^{L+1}-1$)。
答え(数値計算による値):

$L$$1$$2$$3$$4$$5$$6$$7$$8$
V サイクル$0.33333$$0.40559$$0.43538$$0.43538$$0.43680$$0.44008$$0.44073$$0.44136$
V の評価 $\sqrt{1-(8/9)^L}$$0.33333$$0.45812$$0.54559$$0.61295$$0.66714$$0.71185$$0.74936$$0.78119$
W サイクル$0.33333$$0.34156$$0.34156$$0.34156$$0.34156$$0.34156$$0.34156$$0.34156$

W サイクルは評価 $0.35355$ 以下、V サイクルも $0.45$ 以下である。

Poisson 方程式を解く

$-u''=\pi^2\sin\pi x$(解 $\sin\pi x$)を $u=0$ から V(1,1) サイクル(前後に 1 回ずつ平滑化、$\omega=\frac23$)で相対残差 $10^{-8}$ まで解く。2 次元の $-\Delta u=13\pi^2\sin2\pi x\sin3\pi y$ は 5 点公式、双線形補間、$R=\frac14P^{\mathsf T}$、Galerkin の行列、$\omega=\frac45$ で解く。
答え(数値計算による値。Jacobi 法の回数は $\ln10^{-8}/\ln\cos\pi h$ による目安):

問題未知数サイクルの回数解との最大誤差Jacobi 法の目安の回数
1 次元$63$$12$$2.008\times10^{-4}$$15283$
1 次元$255$$13$$1.255\times10^{-5}$$244627$
1 次元$1023$$13$$7.843\times10^{-7}$$3914129$
2 次元$961$$14$$6.013\times10^{-3}$
2 次元$3969$$15$$1.500\times10^{-3}$
2 次元$16129$$14$$3.746\times10^{-4}$

回数は格子によらずほぼ一定である(図 2)。誤差は離散化の誤差である。

n=255 の 1 次元モデル問題で、相対残差を反復の回数に対して片対数で描いたもの。V(1,1) サイクルは 1 回ごとに約 1/5 に減り、15 回で 10^{-10} 程度に達する。Jacobi 法(ω=1)は 15 回でほとんど 1 のままである。 n=255 の 1 次元モデル問題で、相対残差を反復の回数に対して片対数で描いたもの。V(1,1) サイクルは 1 回ごとに約 1/5 に減り、15 回で 10^{-10} 程度に達する。Jacobi 法(ω=1)は 15 回でほとんど 1 のままである。

使える条件と反例

次の表の各行は、条件を 1 つだけ外す(4・5 行目では、その結果として条件 5 も満たされなくなる)。$\omega=\frac23$、$n=2^L-1$ とする(外す条件が $\omega$ のときを除く)。

外す条件例起こること
平滑化($\nu\ge1$)粗い格子の補正 $T$ だけ$\Vert T\Vert_{A}=1$。中央のモードは $Tw_{m+1}=w_{m+1}$ で全く減らない
粗い格子の補正重み付き Jacobi 法だけ縮小率 $1-\frac43\sin^2\frac{\pi h}2$:$n=7$ で $0.94925$、$n=255$ で $0.99995$
2 格子法の一様な収束(条件 5)$\omega=1$$\Vert S_1T\Vert_A=\cos\pi h$:$n=7$ で $0.92388$、$n=255$ で $0.99992$
平滑化の安定性(条件 4)$\omega=\frac65$$\Vert S_\omega T\Vert_A$:$n=7$ で $1.29569$、$n=255$ で $1.39990$($1$ を超える)
Galerkin の関係の $R=cP^{\mathsf T}$(条件 3)単射 $(Ru)_j=u_{2j}$ と $A_H=RA_hP$$T$ は射影だが $A$ 直交でない。$\Vert TS\Vert_A$:$n=7$ で $0.87104$、$n=31$ で $3.40077$、$n=255$ で $27.16313$

1〜4 行目は thm-mg-twogrid と prop-mg-smoothing の式による。

5 行目の補足を開く

$\Vert T\Vert_A$ は $n=255$ で $81.489$ と $n$ とともに増え、thm-mg-cycle の評価の前提が成り立たない。ただし $TS$ のスペクトル半径はこの例では $\frac13$ のままである(数値計算による値)。

よくある誤り

誤り正しくはなぜ
Jacobi 法を $\omega=1$ のまま平滑化に使う1 次元では $\omega=\frac23$、2 次元の 5 点公式では $\omega=\frac45$ 程度にする(Saa03 §13.2.2、p. 432)最も高周波の縮小率が $-\cos\pi h$ で、2 格子法の率も $\cos\pi h\to1$(thm-mg-twogrid の 3)
単射の制限と再離散化の粗い行列をそのまま組む$R=cP^{\mathsf T}$ と Galerkin の行列にするか、補正の係数を合わせる1 次元では $R_{\mathrm{inj}}A_hP=2A_{2h}$ で、補正が 2 倍になる。$n=255$ で $\rho(TS)\approx0.577$(Galerkin なら $\frac13$)
粗い段で $f$ を制限して解く残差 $f-Au$ を制限して誤差の方程式を解く粗い段の未知数は誤差である(def-mg-twogrid)
後平滑化のないサイクルで、残差の 2 ノルムが増えたので発散と判断するエネルギーノルムで見るか、後平滑化を入れる補間で高周波の残差が生じる。$n=1023$ の V(1,0) では 1 回目の残差の比が $16.2$ だが、$A$ ノルムでは縮む(thm-mg-cycle)
2 次元でも Galerkin の行列が 5 点公式になると考える9 点の行列になる全重みと双線形補間では一致しない(Saa03 Example 13.2、p. 440)

補足

平滑化の性質と近似の性質

モードを使わない評価として、平滑化の性質と近似の性質から $\Vert ST\Vert_A\le\sqrt{1-\alpha/\beta}$ が出る(Saa03 Theorem 13.3、p. 453)。

主張と証明、モデル問題の定数を開く

$D$ を $A$ の対角部分とする。条件 1〜3 のもとで、$\Vert Se\Vert_A^2\le\Vert e\Vert_A^2-\alpha\,(Ae)^{\mathsf T}D^{-1}(Ae)$(平滑化の性質)と $\min_v(e-Pv)^{\mathsf T}D(e-Pv)\le\beta\Vert e\Vert_A^2$(近似の性質)がすべての $e$ で成り立てば、$\Vert ST\Vert_A\le\sqrt{1-\alpha/\beta}$ である。

証明:$e$ が $T$ の像にあれば、lem-mg-projector により $\Vert e\Vert_A^2=(Ae,e-Pv)$(任意の $v$)で、Cauchy–Schwarz の不等式から $\Vert e\Vert_A^2\le\sqrt{(Ae)^{\mathsf T}D^{-1}Ae}\sqrt\beta\Vert e\Vert_A$、すなわち $(Ae)^{\mathsf T}D^{-1}Ae\ge\Vert e\Vert_A^2/\beta$ である。これを $Te$ に使い、$\Vert STe\Vert_A^2\le(1-\alpha/\beta)\Vert Te\Vert_A^2\le(1-\alpha/\beta)\Vert e\Vert_A^2$ を得る。

モデル問題の $S_\omega$ では、$y=D^{-1/2}Ae$、$B=D^{-1/2}AD^{-1/2}$(固有値は $\mu:=\rho(D^{-1}A)=2\cos^2\frac{\pi h}2< 2$ 以下)として $\Vert S_\omega e\Vert_A^2=\Vert e\Vert_A^2-2\omega y^{\mathsf T}y+\omega^2y^{\mathsf T}By\le\Vert e\Vert_A^2-\omega(2-\omega\mu)y^{\mathsf T}y$ なので $\alpha=\omega(2-\omega\mu)$ で、$\omega=\frac23$ なら $\alpha>\frac49$ である(Saa03 Example 13.8、p. 454)。$v_j=e_{2j}$ とおくと $e-Pv$ は偶数番で $0$、奇数番 $2j+1$ で $\frac12(a_j-b_j)$($a_j=e_{2j+1}-e_{2j}$、$b_j=e_{2j+2}-e_{2j+1}$)なので、$(\frac{a-b}2)^2\le\frac{a^2+b^2}2$ と $e^{\mathsf T}A_he=h^{-2}\sum_{i=0}^n(e_{i+1}-e_i)^2$($e_0=e_{n+1}=0$)から $\beta=1$ がとれる。よって $\Vert S_{2/3}T\Vert_A\le\frac{\sqrt5}3\approx0.745$ で、thm-mg-twogrid の値 $\frac13$ より粗い。$\square$

粗い段の解を補間して初期値にする 完全マルチグリッド の誤差の評価は Saa03 Theorem 13.2(p. 448)、行列の成分だけから段を作る 代数的マルチグリッド は同書 §13.6(p. 455)にある。1 サイクルは 共役勾配法 の前処理にも使われる。

関連項目

参考文献

[1]
Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003, 第 13 章(p. 423〜)、§13.2.2(pp. 431–432)、Example 13.2(p. 440)、Lemma 13.1(p. 442)、Theorem 13.2(p. 448)、Theorem 13.3(p. 453)、Example 13.8(p. 454)、§13.6(p. 455〜)

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