不連続Galerkin法

同義語:discontinuous Galerkin methodDG法DG method

概要

不連続Galerkin法(discontinuous Galerkin method)とは、要素ごとの多項式で解を近似し、要素の境目での連続性を課さずに、境目の値の受け渡しを数値流束で決める Galerkin 法で、次数 0 では有限体積法に一致し、各要素で量が局所的に保存される。周期的な格子上の一定の速さの移流方程式では、風上流束を使うと近似の $L^2$ ノルムが跳びの 2 乗に比例して減って多項式の次数によらず安定であり、等間隔の格子で初期値が $C^{k+1}$ 級なら次数 $k$ の近似の誤差は $O(h^{k+1/2})$ である。双曲型の保存則の高次の解法として、Runge–Kutta 法による時間の離散化とリミターと組み合わせて使われる。

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

前提知識: Galerkin法, 移流方程式, 有限体積法

不連続Galerkin法(discontinuous Galerkin method、DG 法)は、要素ごとの多項式で解を近似し、要素の境目での連続性を課さない Galerkin法 である。隣り合う要素は、境目での値の受け渡しを決める 数値流束 だけでつながる。連続な区分多項式を使う 有限要素法 とは近似の空間が違い、区分定数(次数 $0$)の場合は 有限体積法 に一致する。
DG 法は Reed と Hill が中性子輸送方程式の計算のために導入し(RH73)、Lesaint と Raviart が最初の誤差解析を与えた(LR74)。双曲型の方程式では情報が上流から下流へ流れるので、境目では上流側の値を使う(風上流束)のが自然である。周期的な格子上の一定の速さの移流方程式では、この選び方で、近似の $L^2$ ノルムが時間とともに増えないこと、しかも境目での跳びの 2 乗に比例して減ることが、要素の多項式の次数によらずに示せる。
この記事では、1 次元の保存則に対する DG 法を定義し、局所的な保存と有限体積法との関係を確かめ(prop-dg-conservation)、移流方程式に対する $L^2$ 安定性を証明する(thm-dg-l2)。さらに、滑らかな解に対して誤差が $O(h^{k+1/2})$ であることを完全に証明する(thm-dg-error)。

定義

$L>0$ とし、周期 $L$ の区間 $[0,L)$ を点 $x_{1/2}< x_{3/2}< \dots< x_{N+1/2}$($x_{N+1/2}=x_{1/2}+L$ と $x_{1/2}$ を同一視する)で $N$ 個の区間 $I_j:=(x_{j-1/2},x_{j+1/2})$ に分ける。$h_j$ を $I_j$ の幅、$h:=\max_jh_j$ とする。添字 $j$ は $N$ を法として読む。$k\ge0$ について
$$ V_h^k:=\{v\in L^2(0,L):\ \text{各 }j\text{ で }v|_{I_j}\text{ は次数 }k\text{ 以下の多項式}\} $$
とおく。$v\in V_h^k$ の点 $x_{j+1/2}$ での左右の極限を $v^-_{j+1/2}$、$v^+_{j+1/2}$ と書き、跳び を $[v]_{j+1/2}:=v^+_{j+1/2}-v^-_{j+1/2}$、平均 を $\{v\}_{j+1/2}:=\frac12(v^+_{j+1/2}+v^-_{j+1/2})$ とする。

不連続 Galerkin 法

$f\in C^1(\mathbb{R})$ を流束とする保存則 $u_t+f(u)_x=0$ を考える。2 変数の関数 $\widehat f(u^-,u^+)$ で $\widehat f(w,w)=f(w)$ を満たすものを 数値流束 といい、$\widehat f_{j+1/2}:=\widehat f(u^-_{j+1/2},u^+_{j+1/2})$ と書く。すべての $j$ と、$I_j$ の上で次数 $k$ 以下のすべての多項式 $v$ について
$$ \int_{I_j}\partial_tu_h\,v\,dx-\int_{I_j}f(u_h)\,v_x\,dx+\widehat f_{j+1/2}\,v^-_{j+1/2}-\widehat f_{j-1/2}\,v^+_{j-1/2}=0 $$
を満たす $u_h(t)\in V_h^k$ を求める方法を、次数 $k$ の 不連続 Galerkin 法(空間の半離散化)という。初期値は $u_h(0)=P_hu_0$ とする。ここで $P_h$ は $L^2$ での $V_h^k$ への直交射影である。

この式は、方程式に試験関数 $v$ を掛けて $I_j$ の上で部分積分し、境界での $f(u)$ を数値流束に置き換えたものである。$V_h^k$ の元は要素ごとに独立に選べるので、質量行列は要素ごとの大きさ $k+1$ のブロックに分かれ、$u_h$ の時間発展は、隣の要素と数値流束だけでつながる常微分方程式の系になる。
一定の速さ $a\in\mathbb{R}$ の移流方程式 $f(u)=au$ では、$c\ge0$ について
$$ \widehat f(u^-,u^+)=a\,\frac{u^-+u^+}2-\frac c2\,(u^+-u^-) $$
の形の数値流束を考える。$c=\lvert a\rvert$ のとき $a>0$ なら $\widehat f=au^-$、$a< 0$ なら $\widehat f=au^+$ で、上流側の値をとる。これを 風上流束 という。$c=0$ を 中心流束 という。

局所的な保存と有限体積法
  1. DG 法の解は $\displaystyle\frac{d}{dt}\int_{I_j}u_h\,dx=-\bigl(\widehat f_{j+1/2}-\widehat f_{j-1/2}\bigr)$ を満たし、全体の量 $\int_0^Lu_h\,dx$ は時間によらない。
  2. $k=0$ では、$u_h|_{I_j}=u_j(t)$ とおくと DG 法は $h_j\,u_j'=-\bigl(\widehat f(u_j,u_{j+1})-\widehat f(u_{j-1},u_j)\bigr)$ で、数値流束 $\widehat f$ の有限体積法の空間の半離散化である。
  3. $f\in C^1$ で $u$ が $C^1$ 級の古典解なら、$u$ はすべての $v\in V_h^k$ について DG 法の式を満たす。
試験関数を選ぶ

1:$v=1$ とおくと $v_x=0$、$v^\pm=1$ なので式そのものである。$j$ について足すと流束の差が打ち消し合う。2:$k=0$ では $\partial_xu_h=0$、$v=1$ で、$u^-_{j+1/2}=u_j$、$u^+_{j+1/2}=u_{j+1}$ である。3:$u$ は連続なので $u^-=u^+=u$、$\widehat f(u,u)=f(u)$ である。$I_j$ の上で部分積分すると、左辺は $\int_{I_j}(u_t+f(u)_x)v\,dx=0$ になる。$\square$

流束 $f$ と数値流束 $\widehat f$ がともに線形なら(次の節の移流方程式と数値流束)、3 から誤差 $u-u_h$ も DG 法の式を満たす(Galerkin 直交性。thm-dg-error の証明で使う)。

風上流束と安定性

以下、移流方程式 $u_t+au_x=0$($a$ は定数)と上の形の数値流束を考え、$\|\cdot\|$ を $L^2(0,L)$ のノルムとする。

風上流束の $L^2$ 安定性

$c\ge0$ とし、$u_h$ を次数 $k$ の DG 法の解とする。このとき
$$ \frac{d}{dt}\|u_h(t)\|^2=-c\sum_{j=1}^N[u_h]_{j+1/2}^2\le0 $$
であり、とくに $\|u_h(t)\|\le\|u_h(0)\|\le\|u_0\|$ である。風上流束($c=\lvert a\rvert$)では、跳びがある限り $L^2$ ノルムは真に減り、中心流束($c=0$)では保たれる。

試験関数に解そのものをとる

各 $j$ で $v=u_h|_{I_j}$ とおき、$j$ について足す。第 1 項の和は $\int_0^L\partial_tu_h\,u_h\,dx=\frac12\frac{d}{dt}\|u_h\|^2$ である。第 2 項は、$I_j$ の上で $u_h\,\partial_xu_h=\frac12\partial_x(u_h^2)$ なので
$$ -a\int_{I_j}u_h\,\partial_xu_h\,dx=-\frac a2\Bigl((u^-_{j+1/2})^2-(u^+_{j-1/2})^2\Bigr) $$
である。第 2 項と流束の項を、各 $j$ の点 $x_{j+1/2}$ に属する項ごとにまとめ直す(周期性により添字をずらしてよい)。点 $x_{j+1/2}$ には、$I_j$ から $-\frac a2(u^-)^2+\widehat fu^-$、$I_{j+1}$ から $\frac a2(u^+)^2-\widehat fu^+$ が来る(添字 $j+1/2$ を省いた)。和は
$$ \frac a2\bigl((u^+)^2-(u^-)^2\bigr)-\widehat f\,(u^+-u^-)=\bigl(a\{u\}-\widehat f\bigr)[u]=\frac c2\,[u]^2 $$
である。最後の等号は $\widehat f=a\{u\}-\frac c2[u]$ による。よって
$$ \frac12\frac{d}{dt}\|u_h\|^2+\frac c2\sum_j[u_h]_{j+1/2}^2=0 $$
で、主張の等式を得る。$\|u_h(0)\|=\|P_hu_0\|\le\|u_0\|$ は直交射影の性質である。$\square$

厳密解は $u(x,t)=u_0(x-at)$ で $\|u(t)\|=\|u_0\|$ である。風上流束の DG 法は、解の跳びに比例する量だけ $L^2$ ノルムを失う。この散逸は、跳びが小さい滑らかな部分ではほとんど働かず、格子の幅の振動を減衰させる(ex-dg-checker)。

誤差評価

誤差の評価

格子は等間隔($h_j=h=L/N$)とし、$a\ne0$、風上流束($c=\lvert a\rvert$)とする。周期 $L$ の $u_0$ が $C^{k+1}$ 級で $M:=\max\lvert u_0^{(k+1)}\rvert$ とすると、$u(x,t)=u_0(x-at)$ と次数 $k$ の DG 法の解 $u_h$ について
$$ \|u(t)-u_h(t)\|\le A_k\,M\sqrt L\,\bigl(h^{k+1}+\sqrt{\lvert a\rvert t}\;h^{k+1/2}\bigr),\qquad A_k:=\frac{1+(k+1)^2}{(k+1)!} $$
が $t\ge0$ で成り立つ。

射影の誤差と離散の誤差に分ける

$a>0$ の場合を示す($a< 0$ は $x\mapsto-x$ で移る)。風上流束は $\widehat f=au^-$ である。
1. 射影の誤差の各点評価。 区間 $I$(幅 $h$)の上の $C^{k+1}$ 級の関数 $w$ について、$I$ の上での $L^2$ 射影 $P$(次数 $k$ 以下の多項式へ)は
$$ \max_I\lvert w-Pw\rvert\le A_kh^{k+1}\max_I\lvert w^{(k+1)}\rvert $$
を満たす。実際、$I$ の左端での次数 $k$ の Taylor 多項式を $T$ とすると $\max_I\lvert w-T\rvert\le\frac{h^{k+1}}{(k+1)!}\max_I\lvert w^{(k+1)}\rvert$ で、$PT=T$ から $w-Pw=(w-T)-P(w-T)$ である。$I$ を $[-1,1]$ に 1 次の変換で移すと、Legendre多項式 $L_m$ で $Pg=\sum_{m=0}^k\frac{2m+1}2\bigl(\int_{-1}^1gL_m\bigr)L_m$ と書け、$\lvert L_m\rvert\le1$ と $\bigl\lvert\int_{-1}^1gL_m\bigr\rvert\le2\max\lvert g\rvert$ から $\max\lvert Pg\rvert\le\sum_{m=0}^k(2m+1)\max\lvert g\rvert=(k+1)^2\max\lvert g\rvert$ である。合わせて主張を得る。
2. 誤差の方程式。 $\eta:=u-P_hu$、$\xi:=P_hu-u_h\in V_h^k$ とおく。$u$ と $u_h$ はともに DG 法の式を満たし(prop-dg-conservation の 3)、式は線形なので、$e:=u-u_h=\eta+\xi$ について、各 $j$ と $v$ で
$$ \int_{I_j}\partial_te\,v-a\int_{I_j}e\,v_x+a\,e^-_{j+1/2}v^-_{j+1/2}-a\,e^-_{j-1/2}v^+_{j-1/2}=0 $$
である。$v=\xi$ とおいて $j$ について足す。$\xi$ の部分は prf-dg-l2 の計算そのもので、$\frac12\frac{d}{dt}\|\xi\|^2+\frac a2\sum_j[\xi]^2$ になる。$\eta$ の部分では、$P_h$ は時間によらない直交射影なので $\partial_t\eta=\partial_tu-P_h\partial_tu$ は $V_h^k$ に直交し、$\int_{I_j}\partial_t\eta\,\xi=0$ である。$\xi_x$ は $I_j$ の上で次数 $k-1$ 以下なので $\int_{I_j}\eta\,\xi_x=0$ である。流束の項は点ごとにまとめると $\sum_ja\,\eta^-_{j+1/2}(\xi^-_{j+1/2}-\xi^+_{j+1/2})=-\sum_ja\,\eta^-_{j+1/2}[\xi]_{j+1/2}$ である。よって
$$ \frac12\frac{d}{dt}\|\xi\|^2+\frac a2\sum_j[\xi]^2=a\sum_j\eta^-_{j+1/2}[\xi]_{j+1/2}\le\frac a2\sum_j[\xi]^2+\frac a2\sum_j\bigl(\eta^-_{j+1/2}\bigr)^2 $$
で、$\frac{d}{dt}\|\xi\|^2\le a\sum_j(\eta^-_{j+1/2})^2$ である。
3. 積分する。 $u(\cdot,t)$ は $u_0$ の平行移動なので $\max\lvert\partial_x^{k+1}u\rvert=M$ で、1 から $\lvert\eta^-_{j+1/2}\rvert\le A_kh^{k+1}M$ である。$N=L/h$ 個の点について足すと $\frac{d}{dt}\|\xi\|^2\le aLA_k^2M^2h^{2k+1}$ である。$\xi(0)=P_hu_0-P_hu_0=0$ なので $\|\xi(t)\|\le A_kM\sqrt{aLt}\,h^{k+1/2}$ である。また 1 から $\|\eta(t)\|\le\sqrt L\,A_kh^{k+1}M$ である。三角不等式 $\|e\|\le\|\eta\|+\|\xi\|$ で主張を得る。$\square$

証明で失った $h^{1/2}$ は、境目での射影の誤差を $N\approx L/h$ 個足したことによる。多次元の定常な問題 $\beta\cdot\nabla u+\sigma u=f$($\beta$ はベクトル場)に対する風上流束の DG 法の安定性と誤差評価は、Lesaint–Raviart(LR74)と Johnson–Pitkäranta(JP86)による。

例

次数 0 と次数 1

$a>0$、風上流束、等間隔の格子とする。

  1. $k=0$ では prop-dg-conservation の 2 から $u_j'=-\frac ah(u_j-u_{j-1})$ で、風上差分の空間の半離散化である。
  2. $k=1$ では $I_j$ の中心を $x_j$ として $u_h=c_{0,j}+c_{1,j}\,\frac{2(x-x_j)}h$ と書く。$\int_{I_j}1\,dx=h$、$\int_{I_j}\bigl(\frac{2(x-x_j)}h\bigr)^2dx=\frac h3$ で、右端の値は $c_{0,j}+c_{1,j}$、左端の試験関数の値は $\pm1$ である。$v=1$、$v=\frac{2(x-x_j)}h$ を代入すると
    $$ h\,c_{0,j}'=-a\bigl(c_{0,j}+c_{1,j}-c_{0,j-1}-c_{1,j-1}\bigr),\qquad\frac h3\,c_{1,j}'=2a\,c_{0,j}-a\bigl(c_{0,j}+c_{1,j}\bigr)-a\bigl(c_{0,j-1}+c_{1,j-1}\bigr) $$
    である(第 2 式の $2ac_{0,j}$ は $a\int_{I_j}u_h\,v_x\,dx$ から来る)。$c_{1,j}=0$ なら第 1 式は 1 の風上差分になる。
格子の幅の振動

$k=0$、$N$ は偶数、$a>0$ とし、初期値を $u_j(0)=(-1)^j$ とする。風上流束では $u_j'=-\frac ah\bigl((-1)^j-(-1)^{j-1}\bigr)=-\frac{2a}h(-1)^j$ なので $u_j(t)=(-1)^je^{-2at/h}$ で、振動は減衰する。跳びは各点で $\pm2e^{-2at/h}$ で、thm-dg-l2 の等式 $\frac{d}{dt}\|u_h\|^2=-a\cdot N\cdot4e^{-4at/h}=-\frac{4a}hL\,e^{-4at/h}$ と一致する。中心流束では $u_j'=-\frac a{2h}(u_{j+1}-u_{j-1})=0$ で、$u_j(t)=(-1)^j$ は動かない。厳密解は速さ $a$ で平行移動する(周期 $2h$ の関数を移すので、時刻 $h/a$ ごとに符号が反転する)ので、中心流束の解はこの振動を正しく運ばず、しかも減衰させない。

非線形の保存則と時間の離散化

一般の流束 $f$ では、DG 法は 有限体積法 の数値流束(Godunov、Lax–Friedrichs、Engquist–Osher など)をそのまま使う。非線形の場合の安定性の解析としては、要素ごとのエントロピー不等式についての Jiang と Shu の研究がある(JS94)。時間は Runge–Kutta 法で離散化し(Runge–Kutta法)、衝撃波の近くの振動は要素の中の多項式の傾きを制限する操作(リミター)で抑える。この組み合わせは Cockburn と Shu の一連の研究で整えられた(CS89、CS01)。陽的な時間の離散化には CFL条件 の形の時間幅の制限がある。

反例:仮定を外すと成り立たないこと

各行は左の定理から、示した仮定 1 つだけを外している。

定理外す仮定例成り立たなくなる結論
thm-dg-l2$c\ge0$$c=-a$(下流側の値をとる流束)、$a>0$、$k=0$、$N$ は偶数、$u_j(0)=(-1)^j$$\|u_h(t)\|\le\|u_h(0)\|$
thm-dg-l2周期性区間 $(x_{1/2},x_{N+1/2})$ で左端の流束を流入の値 $a\cdot1$ にし、$a>0$、$k=0$、$u_h(0)=0$$\|u_h(t)\|\le\|u_h(0)\|$
thm-dg-error$u_0$ が $C^{k+1}$ 級$L=1$、$k=1$、$N$ は奇数、$u_0=1$($0\le x< \frac12$)、$0$($\frac12\le x< 1$)誤差が $O(h^{k+1/2})$(ここでは $O(h^{3/2})$)であること
反例の確かめ

1 行目:流束は $\widehat f=au^+$ で、$h\,u_j'=-a(u_{j+1}-u_j)$ である。$u_j=(-1)^j\phi(t)$ を代入すると $h\phi'=2a\phi$ で、$\|u_h(t)\|=\sqrt L\,e^{2at/h}$ は増える。prf-dg-l2 の計算で $c=-a$ とおくと $\frac{d}{dt}\|u_h\|^2=a\sum_j[u_h]^2>0$ である。
2 行目:$h\,u_1'=-a(u_1-1)$、$h\,u_j'=-a(u_j-u_{j-1})$($j\ge2$)で、$u_1(t)=1-e^{-at/h}>0$($t>0$)なので $\|u_h(t)\|>0=\|u_h(0)\|$ である。流入境界から量が入ってくるので、評価には境界の項が要る。
3 行目:$x=\frac12$ は中央の要素 $I$(幅 $h$)の中点である。$I$ の上の 1 次式による $L^2$ の最良近似の誤差を、$I$ を $[-\frac12,\frac12]$ に移して計算する。段の関数は $\frac12-\frac12\operatorname{sgn}(y)$ で、$\operatorname{sgn}$ の $\{1,y\}$ への射影は $3y$($\int\operatorname{sgn}=0$、$\int y\operatorname{sgn}=\frac14$、$\int y^2=\frac1{12}$)、残差の 2 乗は $1-\frac{(1/4)^2}{1/12}=\frac14$ である。よって $I$ の上で $\|u_0-P_hu_0\|^2=\frac14\cdot\frac14\cdot h$ で、$t=0$ ですでに $\|u(0)-u_h(0)\|\ge\frac14h^{1/2}$ となり、$O(h^{3/2})$ にならない。

補足

文献

DG 法がはじめ双曲型の問題のために作られたこと、境目の数値流束が弱形式の一部として組み立てられることは LMW12 の Kirby–Logg–Rognes–Terrel の章(p. 105)にある。導入は Reed–Hill(RH73)、最初の誤差解析は Lesaint–Raviart(LR74)、多次元の定常な問題の解析は Johnson–Pitkäranta(JP86)、非線形の保存則への Runge–Kutta 法とリミターの組み合わせは Cockburn–Shu(CS89、CS01)による。

関連項目

参考文献

[2]
P. Lesaint, P.-A. Raviart, On a finite element method for solving the neutron transport equation, Mathematical Aspects of Finite Elements in Partial Differential Equations (C. de Boor ed.), Academic Press, 1974, pp. 89–123, 1974
[3]
C. Johnson, J. Pitkäranta, An analysis of the discontinuous Galerkin method for a scalar hyperbolic equation, Mathematics of Computation 46 (1986), no. 173, pp. 1–26, 1986
[4]
Bernardo Cockburn, Chi-Wang Shu, TVB Runge-Kutta local projection discontinuous Galerkin finite element method for conservation laws. II. General framework, Mathematics of Computation 52 (1989), no. 186, pp. 411–435, 1989
[5]
Bernardo Cockburn, Chi-Wang Shu, Runge–Kutta discontinuous Galerkin methods for convection-dominated problems, Journal of Scientific Computing 16 (2001), no. 3, pp. 173–261, 2001
[6]
Guang Shan Jiang, Chi-Wang Shu, On a cell entropy inequality for discontinuous Galerkin methods, Mathematics of Computation 62 (1994), no. 206, pp. 531–538, 1994

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