マルチグリッド法(multigrid method)とは、楕円型偏微分方程式を離散化した連立1次方程式を、細かさの違う格子の階層を行き来して解く反復法である。細かい格子では重み付き Jacobi 法などの平滑化で振動の速い誤差を減らし、残りの誤差の方程式を粗い格子へ制限して解き、補間で戻して補正する。1次元 Poisson 方程式の差分で、線形補間、その転置に比例する制限、Galerkin の粗い行列、重み $2/3$ の重み付き Jacobi 法を使うと、2格子法の誤差はエネルギーノルムで格子の幅によらず1回に $1/3$ 倍以下になり、粗い段を2回ずつ解き前平滑化だけを行う多段のサイクルの縮小率も段の数によらず $1/(2\sqrt{2})$ 以下に抑えられる。粗い段の再帰の回数が2の次元乗未満なら、1サイクルの手間は未知数の個数に比例する。
前提知識: 反復法(連立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
$$
である。
$0< \omega\le1$ とする。
要点:縮小率 $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 に近い。
以下、$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
$$
と動く。
平滑化 の反復行列 $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$ を同じ方法で近似的に解くと、多段の方法になる。
段 $\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〜3 のもとで $T=I-PA_H^{-1}RA$ とおく。
要点:$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$
モデル問題で $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$
モデル問題($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}
$$
である。特に次が成り立つ。
モードへの作用。 $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)
$$
である。よって次が成り立つ。
反復行列。 誤差 $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$
モデル問題の段 $\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 も成り立つ。
段 $\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〜3 | lem-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) |
$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$ である。
$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$ である。
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$ 以下である。
$-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 のままである。
次の表の各行は、条件を 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 の式による。
$\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 サイクルは 共役勾配法 の前処理にも使われる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する