第13回:Crouzeix–Raviart要素を本当に実装する — edge DoF・assembly・broken gradient

ChatGPTで作る有限要素プログラム入門 Season 2 第1回(通算第13回)

はじめに――Season 2では「自由度の構造」からコードを書く

Season 1では,連続P1 Lagrange要素を中心に, 弱形式,Jacobian,assembly,3次元,異方性mesh,debugging,誤差解析まで扱いました.

Season 2では,P1の延長として高次化するのではなく, 有限要素空間そのものの構造を変える方向へ進みます. 最初に扱うのはCrouzeix–Raviart(CR)要素です.

P1 LagrangeからCRへ
P1:vertex valueをglobal DoFにする.
CR:edge meanをglobal DoFにする.
したがってassemblyの中心も \[ \text{element-to-vertex} \quad\longrightarrow\quad \text{element-to-edge} \] へ変わる.

1.モデル問題とCR離散空間

単位正方形 \[ \Omega=(0,1)^2 \] でPoisson問題 \[ -\Delta u=f \qquad\text{in }\Omega, \tag{1} \] \[ u=0 \qquad\text{on }\partial\Omega \tag{2} \] を考えます.

三角形分割を \(\mathcal T_h\),内部辺集合を \(\mathcal E_h^i\),境界辺集合を \(\mathcal E_h^\partial\) とします. homogeneous CR spaceを \[ V_h^{CR} = \left\{ v_h\in L^2(\Omega): v_h|_T\in P_1(T),\ \int_E[v_h]\,ds=0\ \forall E\in\mathcal E_h^i,\ \int_Ev_h\,ds=0\ \forall E\in\mathcal E_h^\partial \right\} \tag{3} \] とします.

ここで \([v_h]\) は内部辺上のjumpです. 一般に \[ V_h^{CR}\not\subset H_0^1(\Omega), \] なのでCRはnonconforming finite elementです.

2.自由度はedge mean

三角形 \(T\) の辺を \(E_0,E_1,E_2\) とし, \(E_i\) は頂点 \(p_i\) の反対側の辺とします. local DoFは \[ \boxed{ m_i(v) = \frac1{|E_i|} \int_{E_i}v\,ds. } \tag{4} \]

隣接する二三角形が内部辺 \(E\) を共有するとき, 両側のlocal edge meanを一つのglobal unknownとして共有します. この一つの設計だけで \[ \int_E[v_h]\,ds=0 \] が自動的に実装されます.

3.reference triangle上のCR basis

reference triangle \[ \widehat T = \operatorname{conv} \{(0,0)^{\top},(1,0)^{\top},(0,1)^{\top}\} \] のbarycentric coordinatesを \[ \widehat\lambda_0=1-\xi-\eta, \qquad \widehat\lambda_1=\xi, \qquad \widehat\lambda_2=\eta \] とすると,CR basisは \[ \boxed{ \widehat\psi_i = 1-2\widehat\lambda_i. } \tag{5} \]

従って \[ \widehat\psi_0=-1+2\xi+2\eta, \qquad \widehat\psi_1=1-2\xi, \qquad \widehat\psi_2=1-2\eta. \tag{6} \] そのgradientは \[ \widehat\nabla\widehat\psi_0=(2,2)^{\top}, \qquad \widehat\nabla\widehat\psi_1=(-2,0)^{\top}, \qquad \widehat\nabla\widehat\psi_2=(0,-2)^{\top}. \tag{7} \]

linear functionのedge averageはedge midpoint valueに等しいので, reference triangleでは \[ m_j(\widehat\psi_i)=\delta_{ij} \tag{8} \] をmidpoint evaluationでも確認できます. ただしCR DoFの定義そのものはedge meanです.

4.local matrixはP1と同じJacobian変換で作れる

affine map \[ F_T(\widehat x)=p_0+J_T\widehat x \] に対してscalar CR basisは \[ \psi_i = \widehat\psi_i\circ F_T^{-1}. \] 従って \[ \boxed{ \nabla\psi_i = J_T^{-\top} \widehat\nabla\widehat\psi_i. } \tag{9} \]

local stiffness matrixは \[ K^{(T)}_{ij} = \int_T\nabla\psi_j\cdot\nabla\psi_i\,dx = |T| \nabla\psi_j\cdot\nabla\psi_i. \tag{10} \]

reference triangle自身では \[ K^{(\widehat T)} = \begin{pmatrix} 4&-2&-2\\ -2&2&0\\ -2&0&2 \end{pmatrix}. \tag{11} \]

ここでも \[ K^{(T)}\mathbf1=0 \tag{12} \] です. なぜなら \[ \psi_0+\psi_1+\psi_2=1 \] だからです.

5.CR離散問題ではbroken gradientを使う

CR functionはglobal \(H^1\) functionではないので, gradientはelementwiseに取ります.

\[ (\nabla_hv_h)|_T := \nabla(v_h|_T). \tag{13} \]

discrete bilinear formは \[ a_h(u_h,v_h) = \sum_{T\in\mathcal T_h} \int_T \nabla_hu_h\cdot\nabla_hv_h\,dx. \tag{14} \]

CR approximation \(u_h\in V_h^{CR}\) は \[ \boxed{ a_h(u_h,v_h) = (f,v_h) \qquad \forall v_h\in V_h^{CR}. } \tag{15} \]

対応するbroken \(H^1\)-seminormは \[ \boxed{ |v_h|_{1,h}^2 = \sum_{T\in\mathcal T_h} \|\nabla v_h\|_{L^2(T)}^2. } \tag{16} \]

6.最重要データ構造はelement-to-edge connectivity

P1 Lagrange要素では \[ \texttt{tri=[v0,v1,v2]} \] そのものがlocal-to-global mapでした. CRではlocal DoFが \[ E_0=[v_1,v_2], \qquad E_1=[v_2,v_0], \qquad E_2=[v_0,v_1] \tag{17} \] なので,global edge numberを作る必要があります.

local_edges = [
    (1, 2),
    (2, 0),
    (0, 1)
]


def build_edges(triangles):
    edge_dict = {}
    element_edges = np.empty(
        (len(triangles), 3),
        dtype=int
    )

    counts = []

    for t, tri in enumerate(triangles):
        for le, (a, b) in enumerate(
            local_edges
        ):
            key = tuple(sorted((
                tri[a],
                tri[b]
            )))

            if key not in edge_dict:
                edge_dict[key] = len(edge_dict)
                counts.append(0)

            eid = edge_dict[key]

            element_edges[t, le] = eid
            counts[eid] += 1

    edges = np.empty(
        (len(edge_dict), 2),
        dtype=int
    )

    for key, eid in edge_dict.items():
        edges[eid] = key

    return (
        edges,
        element_edges,
        np.array(counts)
    )

scalar CRではedge orientationによる符号反転はありません. したがって sorted したvertex pairをglobal edge keyに使えます. RT・Nédélecではこの点が変わります.

7.boundary DoFはboundary edgeそのもの

conforming P1ではboundary vertexを探しました. CRではboundary edgeを探します. manifold triangulationなら, 一つのtriangleにしか属さないedgeがboundary edgeです.

boundary_edges = np.where(
    edge_counts == 1
)[0]

interior_edges = np.where(
    edge_counts == 2
)[0]

homogeneous Dirichlet conditionでは \[ u_E=0 \qquad (E\in\mathcal E_h^\partial) \tag{18} \] です. ここで \(u_E\) はboundary edge mean DoFです.

一般の非同次条件 \(u=g\) なら \[ u_E = \frac1{|E|} \int_Eg\,ds. \tag{19} \] 単にboundary midpointで \(g\) を評価する方法は, \(g\) がaffineなら厳密ですが,一般の \(g\) ではedge quadratureになります.

8.assemblyはvertex番号ではなくedge番号へ足す

一要素のglobal edge番号を \[ (e_0,e_1,e_2) \] とすると,

\[ A_{e_a,e_b} \mathrel{+}=K^{(T)}_{ab}, \qquad b_{e_a}\mathrel{+}=F^{(T)}_a. \tag{20} \]

Pythonでは

eids = element_edges[t]

for a in range(3):
    rhs[eids[a]] += Fe[a]

    for b in range(3):
        A[eids[a], eids[b]] += Ke[a, b]

です. CR実装でvertex indexをそのまま使ってしまうのは, 最も起こりやすい構造的bugの一つです.

9.load vectorはCR basisを積分する

local loadは \[ F_i^{(T)} = \int_Tf\psi_i\,dx. \tag{21} \]

今回はSeason 1と同じ \[ u(x,y)=\sin(\pi x)\sin(\pi y), \qquad f=2\pi^2\sin(\pi x)\sin(\pi y) \tag{22} \] を使い,7点triangle quadratureでloadを評価します. このquadratureは有限次数の多項式には高次精度を持ちますが,今回の三角関数loadを数学的に厳密積分するものではありません. したがって収束表は「exactly integrated CR method」そのものではなく,quadratureを含む実装の検証結果です. 今回のmesh rangeではquadrature errorはCR discretisation errorより高次で,期待するrateを損なっていないことを数値的に確認しています.

CR basisは要素内で符号を変えるので, 「P1 nodal basisと同じload vectorになる」 とは考えてはいけません.

10.CR solverの中心部分

grad_hat_cr = np.array([
    [ 2.0,  2.0],
    [-2.0,  0.0],
    [ 0.0, -2.0]
])


def cr_basis(xi, eta):
    return np.array([
        -1.0 + 2.0 * xi + 2.0 * eta,
         1.0 - 2.0 * xi,
         1.0 - 2.0 * eta
    ])


for t, tri in enumerate(triangles):
    P = nodes[tri]

    J = np.column_stack((
        P[1] - P[0],
        P[2] - P[0]
    ))

    detJ = np.linalg.det(J)

    if detJ <= 0.0:
        raise ValueError(
            "Use positive triangle orientation"
        )

    grads = np.linalg.solve(
        J.T,
        grad_hat_cr.T
    ).T

    area = 0.5 * detJ

    Ke = area * (
        grads @ grads.T
    )

    Fe = np.zeros(3)

    for xi, eta, w in quad:
        x = (
            P[0]
            + J @ np.array([xi, eta])
        )

        f = (
            2.0 * np.pi**2
            * np.sin(np.pi * x[0])
            * np.sin(np.pi * x[1])
        )

        Fe += (
            w
            * detJ
            * f
            * cr_basis(xi, eta)
        )

    eids = element_edges[t]

    for a in range(3):
        rhs[eids[a]] += Fe[a]

        for b in range(3):
            A[eids[a], eids[b]] += Ke[a, b]

11.global matrixの数学監査

boundary conditionをまだ課していないfull matrixでは, global constant CR functionに対応して \[ A_{\mathrm{full}}\mathbf1=0. \tag{23} \]

boundary edge DoFを除去したmatrix \(A_{II}\) は, connected triangulation上のhomogeneous CR spaceについて \[ A_{II}=A_{II}^{\top}, \qquad z^{\top}A_{II}z>0 \quad(z\neq0) \tag{24} \] となります. これはdiscrete Poincaré inequalityと対応します.

従ってCRでも

\[ \text{symmetry} \to \text{full row sum} \to \text{Dirichlet-reduced SPD} \]

というSeason 1のmatrix auditを引き継げます.

12.CR patch testは非同次edge meanで行う

affine harmonic function \[ u(x,y)=1+2x-3y \tag{25} \] を使います. 各boundary edge \(E\) には \[ u_E = \frac1{|E|} \int_Eu\,ds \tag{26} \] を与えます. affine functionなのでこれはedge midpoint valueに一致します.

この \(u\) は各要素でP1であり, CR continuity conditionも満たします. さらにCR test functionのedge mean continuityを使うと discrete integration by partsのinterior edge termsが消えるため, exact arithmeticでは \[ \boxed{ u_h=u. } \tag{27} \]

13.patch testの数値結果

\(n\) max edge-DoF error
23.9320e-17
44.4409e-16
82.2204e-15
164.5519e-15
323.3973e-14

理論上のdiscretisation errorは0であり, 表はfloating-point / linear-solver errorの水準です.

14.誤差normもCR用に変更する

CR solutionはglobal \(H^1\) functionではないため, energy errorにはbroken seminormを使います.

\[ E_{L^2}^{\mathrm{rel}} = \frac{ \|u-u_h\|_{L^2(\Omega)} }{ \|u\|_{L^2(\Omega)} }, \tag{28} \] \[ \boxed{ E_{1,h}^{\mathrm{rel}} = \frac{ \left( \sum_T \|\nabla u-\nabla_hu_h\|_{L^2(T)}^2 \right)^{1/2} }{ |u|_{H^1(\Omega)} }. } \tag{29} \]

CRで単に \[ |u-u_h|_{H^1(\Omega)} \] と書くのは,\(u_h\notin H^1(\Omega)\) なので正確ではありません.

15.CRの誤差評価は「補間誤差」と「整合性誤差」に分ける

CR要素はnonconformingなので,誤差評価の核心は broken \(H^1\)-誤差を二つに分けることです. Second Strang lemmaの形では, \[ \boxed{ |u-u_h|_{1,h} \le C \left[ \inf_{v_h\in V_h^{CR}} |u-v_h|_{1,h} + \sup_{0\neq w_h\in V_h^{CR}} \frac{ |a_h(u,w_h)-(f,w_h)| }{ |w_h|_{1,h} } \right]. } \tag{30} \]

第一項は \[ \boxed{ \text{interpolation / approximation error} } \] であり,たとえばCR interpolation \(I_h^{CR}u\) を使えば \[ \inf_{v_h\in V_h^{CR}} |u-v_h|_{1,h} \le |u-I_h^{CR}u|_{1,h}. \tag{31} \] これは「exact solutionをCR finite-element functionsがどれだけよく近似できるか」を測ります.

第二項は \[ \boxed{ \text{consistency error} } \] であり, \[ a_h(u,w_h)-(f,w_h) \tag{32} \] がnonconforming test functionに対してどれだけ残るかを測ります. conforming P1ではGalerkin orthogonalityに吸収される部分が, CRでは独立した誤差成分として現れます.

CR誤差解析の最重要ポイント
\[ \boxed{ \text{CR error} = \text{interpolation error} + \text{consistency error} } \] と分けて考える.

異方性meshでは,第一項はCR interpolation error estimateで扱えます. 難しいのは第二項です. shape-regularityに依存するstandard scaling argumentとtrace estimateをそのまま使うと, anisotropic meshで期待するorderを失うことがあります. そこでCR–RTの離散部分積分とlowest-order RT interpolationを使って consistency termを評価する,というのが重要な構造です.

つまりRTは,CR法の「別の近似法」としてだけでなく, CR consistency errorを制御するための解析道具として現れます.

16.smooth solutionの収束結果

uniform triangulation上で式 (22) のsolutionを解くと, 次の相対誤差が得られます.

\(n\) \(L^2\) relative error rate broken \(H^1\) relative error rate
46.0478e-2—2.8736e-1—
81.5449e-21.9691.4568e-10.980
163.8836e-31.9927.3091e-20.995
329.7226e-41.9983.6577e-20.999

unit squareのsmooth solutionとregular meshという今回の条件では, \[ L^2:O(h^2), \qquad |\cdot|_{1,h}:O(h) \tag{33} \] が明瞭に現れます. broken \(H^1\) 1次はstandard CR approximation/consistency estimateから得られ,\(L^2\) 2次にはさらにdual problemのregularityを使う議論が必要です. 今回のunit squareではそのregularityを期待できる設定を使っています.

ただしCRはnonconforming methodなので, このrateは「P1だからCéaで直ちに得られる」と説明してはいけません. Strang型評価によるapproximation errorとconsistency errorの両方の制御が必要です.

17.CR interpolationのcommuting identityもunit testにできる

十分なtrace regularityを持つ \(u\) に対し,CR interpolation \(I_T^{CR}\) は \[ \int_E I_T^{CR}u\,ds = \int_Eu\,ds \tag{34} \] で定義されます. Gaussの公式から \[ \boxed{ \nabla I_T^{CR}u = \Pi_T^0(\nabla u), } \tag{35} \] ここで \(\Pi_T^0\) はelementwise constantへの \(L^2\)-projectionです.

したがって数値積分を十分正確に行えば,

\[ \text{gradient of CR interpolant} \quad\text{vs}\quad \text{cell average of exact gradient} \]

を比較するunit testを作れます. これはnodal P1にはないCR固有の構造監査です.

18.CRで起こりやすいChatGPTの実装ミス

mistake 何が壊れるか 検出test
vertex DoFとしてassembly別のspaceになるelement-to-edge map
boundary vertexを0にするCR boundary conditionにならないboundary-edge count
edge midpoint値を一般のDoF定義と思う非affine boundary dataで誤差edge integral test
global \(H^1\)-seminormでerrorを書くnonconformityを無視broken norm definition
Céaだけでrateを説明consistency errorが抜けるStrang audit
edge orientation signをP1のように追加不要な符号反転scalar edge-mean DoF確認

19.P1とCRの違いをコード構造で整理する

item P1 Lagrange CR
local polynomial\(P_1(T)\)\(P_1(T)\)
DoFvertex valueedge mean
global conformity\(H^1\)nonconforming \(H^1\)
connectivityelement-to-vertexelement-to-edge
gradientelementwise constantelementwise constant
energy normglobal \(H^1\)broken \(H^1\)
error frameworkCéaStrang-type

20.ChatGPTへのCR implementation audit prompt

Audit prompt
この2次元Crouzeix–Raviart Poisson codeを監査してください.
(1) local DoFがvertex valueではなくedge meanになっているか,
(2) reference basis \(1-2\lambda_i\) がedge-mean Kronecker propertyを満たすか,
(3) element-to-edge connectivityが正しいか,
(4) boundary conditionをboundary edge meanへ課しているか,
(5) physical gradientが \(J^{-\top}\widehat\nabla\widehat\psi_i\) になっているか,
(6) full stiffness matrixがconstant null modeを持つか,
(7) reduced matrixがSPDか,
(8) nonhomogeneous affine patch testを通るか,
(9) errorをbroken \(H^1\)-seminormで測っているか,
(10) smooth solutionでbroken \(H^1\) 1次・\(L^2\) 2次が得られるか
を順に確認してください. CRはnonconformingなので,Céaの補題だけでerror estimateを説明しないでください.

21.第13回の結論

CR要素はlocal polynomialだけを見ればP1です. しかしglobal finite-element methodとしてはP1 Lagrangeとは別物です. さらに誤差解析でも,conforming P1のようにbest approximationだけを見るのではなく, interpolation / approximation errorとconsistency errorを分離することが本質です.

\[ \boxed{ \text{same local }P_1 \quad+\quad \text{different DoF} \quad=\quad \text{different finite element}. } \tag{36} \]

実装の中心は,

\[ \text{vertex} \to \text{edge}, \qquad \nabla \to \nabla_h, \qquad H^1 \to \text{broken }H^1, \qquad \text{Céa} \to \text{Strang-type analysis}. \]

へ切り替わります.

Season 2の最初の原則
finite elementを実装するときは, basis functionの数式だけでなく, DoF・continuity・connectivity・norm・error theoryを一つの構造として実装する.

次回はRaviart–Thomas要素を本当に実装し, normal-flux DoF,global edge orientation, contravariant Piola transform,divergence commuting propertyをコードで確認します.

参考文献・関連ページ

ページの先頭へ