有限要素解は収束しているのに正解へ収束しない
――最大角条件とBabuška–Aziz反例

古典的パラドックスから現代の研究課題へ 第2回

はじめに――最大角条件を破ると何が起こるのか

有限要素法でメッシュを細かくし,粗いメッシュの解と細かいメッシュの解が近づいていれば, 計算は正しい解へ収束しているように見えます.しかし,その二つの数値解が 同じ誤った極限へ向かっているなら,数値解同士の差は小さくなっても,厳密解との差は消えません.

数値解同士は近づく: \[ \lVert u_{\mathrm{fine}}-u_h\rVert_{H^1(\Omega)}\longrightarrow0, \] それでも,厳密解には近づかない: \[ u_h\longrightarrow\widetilde u, \qquad \widetilde u\neq u. \]

Thomas Apel,Leon Eckardt,Christof Haubner,Volker Kempfによる The maximal angle condition on finite elements: useful or not?は, この危険をBabuška–Aziz型メッシュ上の数値実験で明確に示しています. 本稿で強調したいのは,最大角条件を「必要か不要か」という二者択一で理解してはいけないことです. 最大角条件を破っても正しく収束する特殊なメッシュ族は存在します.一方で,同じ条件を破る別のメッシュ族では, 有限要素解が真の解ではない別の極限へ収束することがあります.したがって本稿では, 最大角条件を,個々の特殊構造を仮定せずに標準的な有限要素計算の収束を保証する「安全側の十分条件」 として捉え直し,どのメッシュ族で,どの誤差指標を用いて,何への収束を確認しているのかを検証します.

1.最大角条件をどう理解すべきか――「必要条件」ではなく安全側の十分条件

二次元の三角形要素\(T\)の最大内角を\(\theta_{\max,T}\)とします. メッシュ族\(\{\mathcal T_h\}\)が最大角条件を満たすとは,ある\(\gamma_0<\pi\)が存在して,

\[ \theta_{\max,T}\leq\gamma_0 \qquad \forall T\in\mathcal T_h, \quad\forall h \]

となることです.最小角を一様に正から離すshape-regularityより弱く, 細長い三角形を許しますが,最大角が\(\pi\)へ近づくほど潰れた三角形は排除します. 一次Lagrange補間については,この条件の下で

\[ |u-I_hu|_{H^1(\Omega)} \leq C h |u|_{H^2(\Omega)} \]

という標準的な一様評価が得られ,Céaの補題を通じて有限要素誤差を制御できます. ここで重要なのは,この条件の役割を「必要条件かどうか」だけで判断しないことです.

1.1 最大角条件を満たせば,特殊な相殺構造を調べなくても収束を保証できる

最大角条件の最も実用的な意味は,個々のメッシュ族に固有の対称性,相殺,patch構造を逐一解析しなくても, 標準的な補間誤差評価と有限要素収束を一様に保証できることです.この意味で,本稿では最大角条件を 「計算を安全側で行うための幾何学的十分条件」と呼びます.

最大角条件の役割
最大角条件は,「満たさなければ必ず失敗する」という論理的な必要条件ではありません.
むしろ,「満たしていれば,少なくとも最大角の退化に起因する標準的な近似理論の破綻を避けられる」という, 安全側の十分条件です.

1.2 最大角条件を破っても,特殊な構造の下では正しく収束する場合がある

一方,最大角条件は有限要素収束の論理的な必要条件ではありません. Hannukainen–Korotov–Křížekは,最大角条件を満たさないsimplicial meshでも, 楕円型問題に対する有限要素近似が最適収束次数を保ち得ることを示しています. したがって,

\[ \text{最大角条件を破る} \quad\not\Longrightarrow\quad \text{有限要素法が非収束} \]

です.例えば,細長い長方形をバッテン(criss-cross)型に分割するような, 強い対称性や大域的な接続構造を持つメッシュ族では,個々の三角形の最大角が悪化しても, 要素間の相殺やメッシュ全体の構造によって正しい収束が保たれる場合があります. このような例は,「最大角条件は必要条件ではない」ことを理解するうえで重要です.

ただし,ここでのポイントは「条件を外せる場合がある」ことであって, 「条件を自由に外してよい」ことではありません. 最大角条件を使わないなら,代わりに何が収束を支えているのかを別の解析で示す必要があります.

1.3 Babuška–Azizの “in some sense necessary” をどう読むか

Babuška–Azizは1976年の論文で,最小角条件は本質的ではなく,重要なのは角が\(180^\circ\)に近づきすぎないことだと論じました. そのうえで最大角条件について,

“the maximum angle condition is sufficient and also, in some sense necessary.”

と述べています.ここでの“in some sense necessary”は, 「収束するすべてのメッシュ族が最大角条件を満たさなければならない」という意味の必要条件ではありません. 実際,後の研究によって最大角条件を破っても収束する例が知られています. むしろ,最大角が\(\pi\)へ近づく退化を無制限に許すと,有限要素近似が破綻するメッシュ族を構成できる, という意味での必要性として読むのが適切です.

したがって,歴史的なBabuška–Azizの主張と, 「最大角条件は収束の必要条件ではない」という後の結果は矛盾しません. 前者は安全性を失う退化が実際に存在することを示し,後者は特殊な構造まで含めれば条件を外せる場合があることを示しています.

1.4 Apelらの警告――条件を外したとき,数値解は「別の解」へ収束することがある

Apel–Eckardt–Haubner–Kempfが改めて強調したのは, 「最大角条件は必要条件ではない」という正しい事実が,実務上は危険な形で誤解され得ることです. 彼らは結論で,少なくともLagrange要素について最大角条件を課せば安全側に立てる, 条件を外すなら注意が必要であり,そのメッシュ列が正しく働くことを理解しておくべきだと述べています.

“One is at the safe side if the maximal angle condition is requested, at least for Lagrangian elements. Otherwise: caution!”

最大角条件を破るメッシュ族を使ったとき,有限要素解列が発散して明らかに壊れるとは限りません.

\[ u_h\longrightarrow\widetilde u, \qquad \widetilde u\neq u \]

のように,有限要素解列そのものは収束しているのに,その極限が厳密解ではないことがあります. さらに,同じ不適切なメッシュ族上で得たfine-mesh solutionをreferenceとして使えば, 粗い解との差は零へ向かうため,「計算は収束している」と誤認する可能性があります.

この点から,本記事で採用する立場は次の通りです.

  • 最大角条件を満たす:標準理論による安全側の収束保証が得られる.
  • 最大角条件を破る:それだけでは収束・非収束のどちらも結論できない.
  • 条件を外して使う:特殊な対称性,mesh topology,別の幾何条件,問題依存解析など,代替となる収束保証が必要である.
  • 数値解同士だけを比較する:誤った極限への偽収束を見逃す可能性がある.

したがって,最大角条件は「最弱の条件」ではありません.しかし, 特殊事情を仮定せずに有限要素計算を安全に進めるための,簡潔で堅牢な十分条件として,現在でも重要です.

1.5 異方性メッシュでは「最小角」「最大角」「異方性」を分けて考える

ここは特に注意が必要です.異方性メッシュであることと,最大角条件を破ることは同じではありません. この区別を曖昧にすると,細長い要素を見ただけで「危険なメッシュ」と判断したり,逆に 「異方性メッシュでは角度条件は不要」と誤解したりします.

二次元三角形では,最小角条件はshape-regularityと本質的に同じ強さを持ちます. 最小角を一様に正から離すと,極端なaspect ratioを持つ細長い三角形は排除されます. したがって,境界層や方向性の強い解に合わせて非常に細長い要素を使う古典的な異方性有限要素法では, 最小角条件を満たさないこと自体は珍しくありません.

一方,最大角条件はこれより弱く,

\[ \theta_{\max,T}\leq\gamma_0<\pi \]

だけを要求します.例えば,幅に比べて高さが非常に小さい長方形を対角線で二分してできる直角三角形は, 最小角が0へ近づき,aspect ratioは発散しても,最大角は\(\pi/2\)付近に保たれます. この意味で,最大角条件はかなり強い異方性を許す条件です.

見る量 何を排除するか 異方性要素との関係
最小角条件 小さい角が0へ近づく退化 強いaspect ratioを持つ要素を基本的に排除する.二次元ではshape-regularityと同程度の条件.
最大角条件 最大角が\(\pi\)へ近づく扁平化 最小角が0へ近づく細長い要素を許す.異方性解析の標準的な安全条件.
aspect ratio 方向ごとのスケール差を測る 大きいこと自体は非収束を意味しない.解の方向性に合えば有効である.
\(H_T/h_T\) 最大角型の退化を角度を直接使わず測る 二次元ではcircumradius型量に対応し,二・三次元でsemi-regularityは最大角条件と対応する.

したがって,異方性メッシュは少なくとも

\[ \text{aspect ratioの大きさ},\qquad \text{最小角},\qquad \text{最大角},\qquad \frac{H_T}{h_T},\qquad \text{mesh topology} \]

を分けて分類する必要があります.さらに,単一要素の形だけではなく, これらの量が精密化に伴ってどう変化するかも重要です.

1.6 semi-regularity,\(H(h)\to0\),mesh topologyを区別する

本サイトのBlogにある 「異方性有限要素法の幾何学的基礎」では,この区別を独立した系列として整理しています. 特に,なぜ幾何条件が必要なのか, 正則性と準正則性を角度を使わずに表す, 異方性メッシュの二つの現れ方, 長方形の三角形分割を幾何指標で調べる と本記事は直接つながっています.

まず,このページで使う二つの量を区別します.各要素 \(T\) の幾何学的flatness parameterを \(H_T\), 要素径を \(h_T\) とします.semi-regular conditionは

\[ \frac{H_T}{h_T}\leq C \qquad \text{uniformly in }T\text{ and }h \]

という無次元量の一様有界性です.二次元では \(H_T\) はcircumradiusと同程度の量であり, \(H_T/h_T\) の一様有界性は最大角条件と同値です.三次元でも,対応するsemi-regular conditionは 面角・二面角に対する最大角条件と同値です.

一方,文献や本サイトの過去の記事では

\[ H(h):=\max_{T\in\mathcal T_h} H_T \]

というメッシュ全体で最も大きい \(H_T\)も用います.したがって

\[ H(h)\longrightarrow0 \]

とは,「メッシュを細かくしたとき,最も悪い要素についてもcircumradius型の長さスケール \(H_T\) が0へ向かう」 という意味です.これは最大角条件そのものではありません.

ここは混同しないことが重要です.

最大角条件/semi-regularity:\(H_T/h_T\) を一様に抑える条件.
\(H(h)\to0\):\(H_T\) そのものの最大値が0へ向かうという極限条件.

もし \(h:=\max_{T\in\mathcal T_h}h_T\to0\) かつsemi-regularityが成り立てば, \[ H(h) =\max_{T\in\mathcal T_h}H_T \leq C\max_{T\in\mathcal T_h}h_T =Ch \longrightarrow0 \] です.したがって,通常の精密化を仮定すれば

\[ \text{semi-regular / maximum-angle condition} \quad\Longrightarrow\quad H(h)\to0. \]

しかし逆は成り立ちません.\(H(h)\to0\) であっても,\(H_T/h_T\) は発散し得ます. この差が,本記事のBabuška–Aziz型メッシュを理解する鍵になります.

実際,Apelらの記号に合わせて \[ n=m^\beta,\qquad h_T\asymp m^{-1},\qquad H_T\asymp \frac{n}{m^2}=m^{\beta-2} \] と見ると, \[ \frac{H_T}{h_T}\asymp\frac{n}{m}=m^{\beta-1}. \] したがって \(1<\beta<2\) では \[ \frac{H_T}{h_T}\to\infty, \qquad H(h)\to0 \] が同時に起こります.つまり,最大角条件は破れているが,circumradius型の量そのものは0へ向かる領域です. 二次元の一次適合Lagrange有限要素法では,このような最大角条件より弱いcircumradius型の条件の下でも 収束が残る場合があることが知られています.

ただし,ここから「\(H(h)\to0\) なら任意の有限要素法で安全」と結論してはいけません. Raviart–Thomas,Crouzeix–Raviart,Morley,Nitsche法,DG法などでは,補間安定性,consistency, discrete Sobolev inequality,trace estimateなど,必要となる幾何条件がそれぞれ異なります. したがって本サイトでは,要素の局所幾何,メッシュ族としての極限,mesh topology,有限要素空間と問題の構造を 分けて扱います.

分類 代表的条件 何が分かるか
shape-regular / minimum-angle level 最小角を0から一様に離す 強いaspect ratioを基本的に排除する,最も保守的な幾何条件.
semi-regular / maximum-angle level \(H_T/h_T\le C\) 強い異方性を許しながら,標準的な異方性FEM理論を安全側で使える.
circumradius-type limit \(H(h)=\max_T H_T\to0\) 最大角条件より弱い.二次元P1 Lagrangeなどでは収束を支える場合があるが,万能条件ではない.
maximum-angleを越える構造依存領域 patch symmetry,cancellation,mesh topologyなど 収束する場合も,別の極限へ収束する場合もあり,個別解析が必要.

この分類で見ると,Babuška–Aziz反例が示しているのは「異方性メッシュは危険」ということではありません. 最大角条件という安全側の条件を外した後は,退化速度とメッシュ全体の接続構造,さらに用いる有限要素法まで見なければ, 正しい解への収束を判断できないということです.

2.検証するPoisson問題

Babuška–Aziz/Oswaldの反例で用いられる基本問題は,単位正方形 \(\Omega=(0,1)^2\)上のPoisson方程式です.上下端は周期的に同一視し, 左右端に零Dirichlet条件を課します.

\[ -\Delta u=1 \quad\text{in }\Omega, \] \[ u(0,y)=u(1,y)=0, \qquad u(x,0)=u(x,1), \qquad \partial_yu(x,0)=\partial_yu(x,1). \]

厳密解は\(y\)に依存しない二次関数

\[ u(x,y)=\frac12x(1-x) \]

です.解は滑らかで,領域も単純です.したがって,非収束の原因を 解の特異性や曲線境界へ押しつけることはできません.原因は,メッシュ族の幾何と接続にあります.

3.Babuška–Aziz型メッシュ

論文の記号に合わせ,水平方向の分割数を\(m\),鉛直方向の分割数を

\[ n=m^\beta, \qquad \beta\geq1 \]

とします.代表的な要素幅は

\[ h_x\asymp m^{-1}, \qquad h_y\asymp n^{-1}=m^{-\beta} \]

です.重要なのは,単純な長方形格子へ同じ向きの対角線を入れるのではなく, 行ごとに節点列を半ステップずらすことです.偶数行では

\[ x_i=\frac{i}{m}, \qquad i=0,\ldots,m, \]

とし,奇数行では

\[ 0, \quad \frac{i+1/2}{m}\quad(i=0,\ldots,m-1), \quad 1 \]

を節点に取ります.したがって,奇数行では内部節点が半ステップずれるだけでなく, 左右境界の端点を別に追加します.この追加端点を使って左右端に三角形を一枚ずつ置くため, 境界付近にも隙間や交差のない適合三角形分割ができます.

Babuška–Aziz型staggered-rowメッシュの模式図 偶数行は通常格子,奇数行は半ステップずれた格子で,左右境界には端点を追加して三角形分割を閉じる。上端と下端の節点列は一致し,周期条件では対応節点を同一視する。 even rows: x_i = i/m odd rows: 0, (i+1/2)/m, 1 top: y = 1 bottom: y = 0

模式図:\(m=6\),\(n=18\).赤点は奇数行の節点です.左右端の赤点を含めて境界要素を閉じています.

この構成は, 異方性メッシュ族をPythonで再構成する で用いた mesh1_style_rows と build_mesh1_style_mesh の接続そのものです. 上下端に周期条件を課す場合も,図を円筒のように曲げて描く必要はありません. \(n\)を偶数に取れば上端と下端はいずれも通常格子となり, 有限要素空間の組立時に対応する節点自由度を同一視します.

\(\beta>1\)では\(h_y/h_x\to0\)となり,各三角形の最大内角は\(\pi\)へ近づきます. さらに,この扁平要素が行ごとに向きを変えながら領域全体を覆うため, 局所的な角度退化が大域的な近似障害へつながります.

4.circumradiusが臨界指数を見せる

底辺が\(h_x\),高さが\(h_y\)程度の扁平な二等辺三角形では,外接円半径\(R_T\)は

\[ R_T\asymp\frac{h_x^2}{h_y} \asymp\frac{n}{m^2} =m^{\beta-2} \]

となります.したがって,最大角条件が既に破れている\(\beta>1\)の範囲でも, \(R_T\)の極限は三つに分かれます.

範囲 \(R_T\asymp m^{\beta-2}\) 期待される挙動
\(1<\beta<2\) \(R_T\to0\) 最大角条件は破るが,収束し得る
\(\beta=2\) \(R_T\asymp1\) 臨界.誤差が零へ行かない
\(\beta>2\) \(R_T\to\infty\) 強い非収束が起こり得る

ここで既に,最大角条件が必要条件ではない理由と,条件を無視すると危険な理由が同時に見えます. 最大角条件は\(\beta>1\)で破れますが,有限要素収束の臨界は\(\beta=2\)に現れます.

5.有限要素誤差の臨界則

OswaldによるBabuška–Azizメッシュの再解析では,一次適合有限要素近似\(u_h\)について, エネルギー誤差が本質的に

\[ \lvert u-u_h\rvert_{H^1(\Omega)} \asymp \min\left\{1,\frac{n}{m^2}\right\} \]

で支配されることが示されます.\(n=m^\beta\)を代入すると,

\[ \lvert u-u_h\rvert_{H^1(\Omega)} \asymp \min\left\{1,m^{\beta-2}\right\}. \]

したがって,\(\beta<2\)では遅くても誤差は零へ向かいます. 一方,\(\beta\geq2\)では誤差は零へ向かわず,有限要素空間を増やし続けても 正しい解を近似できません.これは単に節点補間が悪いだけではなく, 有限要素空間におけるbest approximationそのものが失敗する現象です.

6.「収束している」の主語を確認する

Apelらが強調するのは,\(u_h\)が無秩序に発散するとは限らないことです. 数値解列は

\[ u_h\longrightarrow\widetilde u \]

と落ち着いて見えます.しかし,その極限が厳密解\(u\)とは限りません. ここで,十分細かい同じメッシュ族上の解を\(u_{\mathrm{fine}}\)とすると,

\[ \lvert u_{\mathrm{fine}}-u_h\rvert_{H^1(\Omega)} \approx \lVert\widetilde u-u_h\rVert_{H^1(\Omega)} \longrightarrow0 \]

となります.この量だけを見れば,きれいな収束次数さえ観測できます. しかし,測っているのは\(u\)への誤差ではなく,誤った極限\(\widetilde u\)への距離です.

厳密解が既知
\(\lVert u-u_h\rVert\)
正しい非収束を検出する.
信頼できる事後評価
\(\eta_h\approx\lVert u-u_h\rVert\)
誤差が消えないことを示す.
同じ族のfine solution
\(\lvert u_{\mathrm{fine}}-u_h\rvert_{H^1(\Omega)}\)
偽の収束を示し得る.

7.事後誤差評価量は何を検出したか

論文では,異方性メッシュ向けに要素・辺の長さを注意深く選んだ残差型評価量を用いています. 模式的には

\[ \eta_h^2 = \sum_{T\in{\mathcal T}_h} h_T^2\lVert f+\Delta u_h\rVert_{L^2(T)}^2 + \sum_{E\in{\mathcal E}_h} h_E\lVert[\partial_n u_h]\rVert_{L^2(E)}^2 \]

という要素残差と法線微分jumpの和です.ここでの\(h_T\),\(h_E\)は, 異方性を無視して単にdiameterを入れればよいわけではありません. Apelらの計算では,この評価量のeffectivity index

\[ \frac{\eta_h}{\lvert u-u_h\rvert_{H^1(\Omega)}} \]

が安定し,真の誤差が零へ行かないことを追跡しました. 一方,同一メッシュ族のfine solutionとの差は減少し,反対の結論を与えました.

検証の教訓: 参照解を細かくするだけでは不十分です.参照計算が正しい極限へ向かうこと,または 誤差評価量のreliabilityが対象メッシュ族で保証されることが必要です.

8.\(H_T/h_T\)で見ると何が分かるか

私たちの異方性補間理論では,三角形のflatnessを表す量として\(H_T\)を用い,

\[ A_T:=\frac{H_T}{h_T} \]

をsemi-regular parameterとします.二次元では,\(H_T\)は外接円半径\(R_T\)と同値な量であり, \(A_T\)の一様有界性は最大角条件と同値です.Babuška–Aziz型要素では

\[ h_T\asymp m^{-1}, \qquad H_T\asymp R_T\asymp\frac{n}{m^2}, \qquad \frac{H_T}{h_T}\asymp\frac{n}{m}=m^{\beta-1}. \]

したがって,\(\beta>1\)では\(H_T/h_T\to\infty\)となり,semi-regularityは破れます. しかし,\(H_T\to0\)自体は\(\beta<2\)なら成立します.ここから,二つの異なる問いを区別できます.

  • 一様な最適次数評価を保証できるか:\(H_T/h_T\)の有界性が安全な十分条件になる.
  • この特定のメッシュ族で誤差が零へ行くか:\(H_T\to0\)の速度や大域的接続も関係する.

最大角条件を破る要素が存在するという局所情報だけで,収束・非収束のどちらも断定できません. 逆に,aspect ratioが大きいというだけでも不十分です. 必要なのは,幾何因子の大きさ,その細分化に対する極限,悪い要素の接続構造を同時に見ることです.

なお,私たちの2021年の一般理論では任意要素上の幾何因子を明示する局所評価を導きましたが, 標準的な異方性評価やRaviart–Thomas補間の大域安定性には追加条件が必要であることを, 後続の論文で修正・明確化しています.この反例は,幾何因子を残した評価と, 因子を一様定数へ吸収した評価を区別しなければならない理由を端的に示します.

9.数値計算では何が起きているのか

ここでは,Appendix 1 の完全コードを実際に実行して得られる結果を, 「どの数値を見れば,収束しているのか,していないのかが分かるのか」という順序で整理します. 出力される量は多いですが,最初に見るべき量は次の四つだけです.

量 意味 何を判断するか
\(\lvert u-u_h\rvert_{H^1(\Omega)}\) 厳密解との差 これが零へ行くかどうかが本当の収束判定
\(\max u_h\) 数値解の大きさ 厳密解の最大値 \(\max u=1/8=0.125\) に近づくか
\(\lvert u_{\mathrm{fine}}-I_{\mathrm{fine}}u_h\rvert_{H^1(\Omega)}\) 同じメッシュ族の粗い解とfine solutionとの差 小さくなっても,厳密解への収束は保証しない
\(\max_T R_T\) メッシュ退化を表す幾何量 \(R_T\to0\),\(R_T\asymp1\),\(R_T\to\infty\) のどの領域にいるか

今回の厳密解は

\[ u(x,y)=\frac12x(1-x), \qquad \max_{\Omega}u=\frac18=0.125, \]

であり,その\(H^1\)半ノルムは

\[ \lvert u\rvert_{H^1(\Omega)} =\left(\int_0^1\left(\frac12-x\right)^2\,dx\right)^{1/2} =\frac1{\sqrt{12}} \approx0.288675. \]

この二つの値,\(0.125\)と\(0.288675\)を覚えておくと,以下の数値結果が読みやすくなります.

9.1 \(\beta=1.5\):最大角条件を失っても,この族では正しく収束する

まず \[ n=m^{1.5} \] とした場合です.理論上は \[ \lvert u-u_h\rvert_{H^1(\Omega)} \asymp m^{-1/2} \] なので,最大角条件を族として失っても,真の誤差は零へ向かうはずです.実際の計算結果は次の通りです.

\(m\) \(n\) \(\lvert u-u_h\rvert_{H^1}\) \(\max u_h\) 最大角 \(\max R_T\)
480.075830.1224090.00°0.1250
8240.051000.12313112.62°0.06771
16640.032740.12410126.87°0.03906
241180.026310.12438135.73°0.02984

ここでは最大角が次第に大きくなっていますが,\(\max R_T\)は\(0\)へ減少しています. それと同時に,真の\(H^1\)誤差も\(0.0758\to0.0263\)と減少し, \(\max u_h\)は厳密解の最大値\(0.125\)へ近づいています.

このケースの結論:
最大角条件を満たさないメッシュ族だからといって,必ず非収束になるわけではありません. \(\beta=1.5\)では最大角は悪化しますが,\(R_T\to0\)であり,実際に有限要素解は厳密解へ収束しています.

9.2 \(\beta=2\):臨界領域では,メッシュを細かくしても誤差が残る

次に \[ n=m^2 \] とします.この場合は \[ R_T\asymp1 \] となる臨界領域です.計算結果を見ると,真の誤差が途中からほとんど減らなくなります.

\(m\) \(n\) \(\lvert u-u_h\rvert_{H^1}\) \(\max u_h\) fine-solution gap \(\max R_T\)
4160.118010.111030.23370.1563
8640.110840.110210.16710.1328
162560.108920.110010.098960.1270
245760.108560.109980.048360.1259

\(m=8\)以降を見ると,真の\(H^1\)誤差は\(0.1108,0.1089,0.1086\)で,ほぼ一定です. つまり,要素数を大幅に増やしているのに,厳密解への距離はほとんど縮まっていません. また,\(\max u_h\)も約\(0.110\)で止まり,厳密解の最大値\(0.125\)へ近づきません.

一方,fine-solution gapは\(0.2337\to0.0484\)と減っています. したがって,粗い解とfine solutionだけを比べると「順調に収束している」と判断してしまう可能性があります. しかし,真の誤差を見れば,すでに\(\beta=2\)で収束が止まっていることが分かります.

このケースの結論:
\(\beta=2\)は臨界です.\(R_T\)が零へ行かず,真の誤差も零へ行きません. 「メッシュサイズが小さくなっている」ことと「有限要素解が厳密解へ収束する」ことは同じではありません.

9.3 \(\beta=3\):真の誤差は悪化するのに,fine solutionとの差は小さくなる

最も分かりやすい反例が \[ n=m^3 \] です.この場合,\(R_T\)は増大し,最大角は急速に\(180^\circ\)へ近づきます.

\(m\) \(n\) \(\lvert u-u_h\rvert_{H^1}\) \(\max u_h\) fine-solution gap 最大角 \(\max R_T\)
280.198340.080282.569126.87°0.3125
4640.246260.036830.9498165.75°0.5078
85120.275430.011790.2164176.42°1.001
1217280.282500.005530.06590178.41°1.500

ここでは,二つの量が逆方向へ動いていることが最重要です.

  • 真の誤差:\(0.198\to0.283\)と増加している.
  • fine-solution gap:\(2.569\to0.0659\)と急速に減少している.

したがって,fine solutionとの差だけを見ると,計算は非常によく収束しているように見えます. しかし,厳密解との差を見ると,実際には逆に悪化しています.これが本記事で最も重要な「偽収束」です.

さらに,\(\max u_h\)は \[ 0.0803\to0.0368\to0.0118\to0.00553 \] と零へ近づいています.一方,厳密解の最大値は\(0.125\)です. また真の\(H^1\)誤差は\(0.288675=\lvert u\rvert_{H^1(\Omega)}\)へ近づいています. この計算結果は,この強く退化した族では数値解そのものが零に近い状態へ押しつぶされていることを示しています.

ここで見るべき対比

メッシュを細かくする
\(\Downarrow\)
fine solutionとの差は小さくなる
\(\Downarrow\)
一見すると「収束」

しかし同時に

\(\lvert u-u_h\rvert_{H^1}\)は零へ行かない
\(\max u_h\)も厳密解の\(0.125\)へ行かない

したがって,収束しているのは厳密解\(u\)への距離ではない.

9.4 三つの\(\beta\)を並べると臨界が見える

領域 幾何量 真の誤差 数値的に見える現象
\(\beta=1.5<2\)\(R_T\to0\)零へ減少最大角は悪化するが正しく収束
\(\beta=2\)\(R_T\asymp1\)正の値で停滞臨界的な非収束
\(\beta=3>2\)\(R_T\to\infty\)\(\lvert u\rvert_{H^1}\)付近へ増加fine solutionとの差だけは減るという偽収束

この比較から,この記事の主張を一文でまとめると次のようになります.

最大角条件を破ったという事実だけでは収束・非収束は決まらない. 特殊な構造の下では条件を外しても収束し得る一方,追加の保証なしに外すのは危険である. このBabuška–Aziz型メッシュでは,\(R_T\)の極限,すなわち\(n/m^2\)の大きさが臨界を捉え, \(\beta=2\)を境に真の有限要素誤差の挙動が変わる.

9.5 fine-solution gapの数値は「誤差」ではない

上の表で使ったfine solutionは,\(\beta=1.5,2\)では\(m_{\mathrm{fine}}=32\), \(\beta=3\)では計算量を抑えるため\(m_{\mathrm{fine}}=17\)です. したがってfine-solution gapの絶対値や見かけの減少率を,厳密な収束次数として解釈してはいけません. この量を載せる目的はただ一つ,同じ不適切なメッシュ族のfine solutionとの差が減っても, 真の誤差は減らない場合があることを確認するためです.

特に\(\beta=3\)では,真の誤差が増加しているのと同時にfine-solution gapが減少しています. この逆向きの挙動こそが,fine solutionを無条件にreference solutionとして使う危険性を最も明瞭に示しています.

9.6 残差指標は補助出力として扱う

Appendixのコードは,デバッグと比較のために標準的なdiameter/edge-length重みを使った残差指標も出力します. ただし,これはApelらが用いた異方性事後誤差評価量そのものではありません. したがって,本記事の収束・非収束の結論にはこの残差指標を使いません. 結論は,厳密解から直接計算した\(H^1\)半ノルム誤差,\(\max u_h\),fine-solution gap, および\(R_T\)の挙動から判断しています.

9.7 完全コードの実行

Appendix 1のコードは,NumPy,SciPy,Matplotlibだけで動作します.現在の版では, 上で示した\(\beta=1.5\),\(\beta=2\),\(\beta=3\)の三つをすべて実行するようにしてあります. 処理内容は次の通りです.

  1. staggered-row型Babuška–Azizメッシュを生成する.
  2. 要素面積,向き,上下端の周期対応を検査する.
  3. 上下端の周期自由度を同一視し,左右端に零Dirichlet条件を課す.
  4. P1有限要素の剛性行列・荷重ベクトルを疎行列として組み立てる.
  5. 厳密解との差から\(L^2\),\(H^1\)半ノルム,full \(H^1\)誤差を計算する.
  6. 最大角,外接円半径\(R_T\),\(H_{T0}/h_T\)などの幾何量を計算する.
  7. 粗い解をfine meshへ補間してfine-solution gapを計算する.
  8. 表と両対数グラフを出力する.

原論文と同じ\(m_{\mathrm{fine}}=31\)を\(\beta=3\)で使うと,\(n=31^3=29791\)となるため, 通常のPCでは計算量がかなり大きくなります.そのため,ブログの標準設定では\(m_{\mathrm{fine}}=17\)としています.

10.現代の研究課題

10.1 局所条件からmesh topologyへ

同じ扁平三角形でも,孤立している場合と,交互の帯として長く連結する場合では影響が異なります. 最大角や外接円半径だけでなく,悪い要素のcluster size,band length,patch connectivityを含む 必要条件・十分条件の隙間は,現在も完全には閉じていません.

10.2 異方性a posteriori estimatorのreliability

誤差評価量が数値解と同じ誤った極限を追跡してしまってはcertificateになりません. 要素残差,flux jump,equilibrated fluxのどれが,最大角条件を破るメッシュ上でも 幾何に頑健な上界・下界を与えるかを整理する必要があります.

10.3 \(L^\infty\)誤差とDMP

エネルギー誤差が収束しても,pointwise errorや離散最大値原理は別の幾何・接続条件に依存します. 同じ局所要素形状を持つメッシュでも,対角線の向きやpatch topologyにより\(L^\infty\)収束次数が変わり得ます.

10.4 非適合・混合有限要素では何が変わるか

本反例は適合一次Lagrange要素のものです.Crouzeix–Raviart要素,Raviart–Thomas要素, Nédélec要素では,自由度,Piola変換,可換性,離散Poincaré・Sobolev不等式が異なります. 最大角条件の役割を要素族ごとに分けて検証する必要があります.

10.5 AI生成メッシュと偽のreference solution

学習型メッシュ生成やsurrogate modelでは,高解像度計算を教師データとして使います. しかし教師計算が同じ不適切なメッシュ族上で作られていれば,モデルは誤った極限を高精度に学習します. 幾何certificateと独立な誤差保証を教師データ作成に組み込むことが必要です.

11.結論――最大角条件は「安全に計算するための十分条件」と考える

本記事の結論は,「最大角条件は必要か,不要か」という二択ではありません. 最大角条件を破っても,criss-cross型のような特殊な対称性・接続構造を持つメッシュ族では, 正しい収束が保たれる場合があります.したがって,最大角条件は有限要素収束の論理的な必要条件ではありません.

しかし,その事実から「最大角条件を無条件に外してよい」と結論することはできません. Babuška–Aziz型メッシュでは,最大角が\(\pi\)へ近づく要素が特定の仕方で領域全体に連結されると, 収束が遅くなり,臨界を越えると真の解への収束そのものが失われます. さらにApelらが示したように,数値解列がある極限へ収束していても,その極限が元の問題の厳密解とは限りません.

最大角条件をどう使うべきか

最大角条件は,「これを満たさなければ必ず失敗する」という必要条件ではありません.
一方で,これを満たしていれば,特殊なメッシュ構造や問題依存の相殺を仮定せずに,標準的な有限要素収束を保証できます.

したがって,最大角条件は,有限要素計算を安全側で行うための代表的な幾何学的十分条件と理解するのが適切です.

最大角条件を外すこと自体は可能です.ただし,その場合には, 「異方性有限要素法の幾何学的基礎」で整理しているように,最小角条件,最大角条件,semi-regularity,aspect ratio,\(H_T\)の極限,mesh topologyを区別したうえで,

  • そのメッシュ族に固有の対称性や相殺,
  • mesh topologyやpatch構造,
  • circumradius conditionや別の幾何条件,
  • 対象問題に依存した誤差解析,
  • 真の誤差または信頼できるa posteriori certificate,

のいずれかによって,最大角条件に代わる収束保証を与える必要があります.

そして数値検証では,

\[ \lVert u_{h_{\mathrm{fine}}}-u_h\rVert\to0 \]

だけを見てはいけません.同じメッシュ族が同じ誤った極限を追っていれば,この差は零へ向かいます. 重要なのは,「数値解列が収束しているか」ではなく,「元の連続問題の解へ収束しているか」です.

Babuška–Azizの “in some sense necessary” と, 最大角条件を破っても収束する特殊例,そしてApelらの偽収束の数値実験を並べて見ると, 最大角条件の本当の役割が見えてきます.それは最弱の条件を主張することではなく, メッシュ退化による見えにくい失敗を避けるための,明確で検査可能な安全条件を与えることです.

Appendix 1.NumPy・SciPyによる完全実行コード

次のコードを一つのセルまたは一つのPythonファイルとして実行できます. 必要なパッケージはNumPy,SciPy,Matplotlibです. メッシュ生成,周期自由度の縮約,疎行列組立て,誤差積分,幾何量,残差指標, fine meshへの補間,表とグラフの出力をすべて含みます.

完全コードを開く/閉じる
"""Babuska--Aziz staggered-row P1 FEM experiment.

Requirements:
    numpy, scipy, matplotlib

The code solves
    -Delta u = 1 in (0,1)^2,
    u = 0 on x=0 and x=1,
    periodic conditions in y,
with exact solution u(x,y)=x(1-x)/2.
"""
from __future__ import annotations

from dataclasses import dataclass
from math import ceil
from typing import Callable

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.tri as mtri
from scipy.sparse import coo_matrix, csr_matrix
from scipy.sparse.linalg import spsolve

Array = np.ndarray


@dataclass
class Mesh:
    m: int
    n: int
    nodes: Array
    elements: Array
    row_starts: Array
    row_lengths: Array


@dataclass
class FEMSolution:
    mesh: Mesh
    values: Array
    element_areas: Array
    basis_gradients: Array
    element_gradients: Array
    stiffness: csr_matrix


def even_ceil(value: float) -> int:
    """Smallest even integer greater than or equal to value."""
    return max(2, 2 * int(ceil(float(value) / 2.0)))


def babuska_aziz_mesh(m: int, n: int) -> Mesh:
    """Construct the conforming staggered-row triangulation of (0,1)^2.

    Even rows contain x=i/m, i=0,...,m.
    Odd rows contain 0, (i+1/2)/m, i=0,...,m-1, and 1.
    The top and bottom rows have the same nodes when n is even, which is
    required for the periodic identification used below.
    """
    if m < 2:
        raise ValueError("m must be at least 2")
    if n < 2 or n % 2 != 0:
        raise ValueError("n must be an even integer at least 2")

    x_even = np.linspace(0.0, 1.0, m + 1)
    x_mid = 0.5 * (x_even[:-1] + x_even[1:])
    x_odd = np.concatenate(([0.0], x_mid, [1.0]))

    nodes: list[tuple[float, float]] = []
    row_starts: list[int] = []
    row_lengths: list[int] = []

    for j in range(n + 1):
        xs = x_even if j % 2 == 0 else x_odd
        row_starts.append(len(nodes))
        row_lengths.append(len(xs))
        y = j / n
        nodes.extend((float(x), float(y)) for x in xs)

    node_array = np.asarray(nodes, dtype=float)
    row_starts_array = np.asarray(row_starts, dtype=int)
    row_lengths_array = np.asarray(row_lengths, dtype=int)

    def nid(row: int, local_index: int) -> int:
        return int(row_starts_array[row] + local_index)

    elements: list[list[int]] = []
    for j in range(n):
        if j % 2 == 0:
            # even row (m+1 nodes) below odd row (m+2 nodes)
            for i in range(m):
                elements.append([nid(j, i), nid(j, i + 1), nid(j + 1, i + 1)])
                elements.append([nid(j, i), nid(j + 1, i + 1), nid(j + 1, i)])
            # right boundary triangle
            elements.append([nid(j, m), nid(j + 1, m + 1), nid(j + 1, m)])
        else:
            # odd row (m+2 nodes) below even row (m+1 nodes)
            # left boundary triangle
            elements.append([nid(j, 0), nid(j, 1), nid(j + 1, 0)])
            for i in range(m):
                elements.append([nid(j, i + 1), nid(j, i + 2), nid(j + 1, i + 1)])
                elements.append([nid(j, i + 1), nid(j + 1, i + 1), nid(j + 1, i)])

    element_array = np.asarray(elements, dtype=int)

    # Enforce counter-clockwise orientation.
    pts = node_array[element_array]
    signed_double_area = (
        (pts[:, 1, 0] - pts[:, 0, 0]) * (pts[:, 2, 1] - pts[:, 0, 1])
        - (pts[:, 1, 1] - pts[:, 0, 1]) * (pts[:, 2, 0] - pts[:, 0, 0])
    )
    negative = signed_double_area < 0.0
    tmp = element_array[negative, 1].copy()
    element_array[negative, 1] = element_array[negative, 2]
    element_array[negative, 2] = tmp

    mesh = Mesh(
        m=m,
        n=n,
        nodes=node_array,
        elements=element_array,
        row_starts=row_starts_array,
        row_lengths=row_lengths_array,
    )
    validate_mesh(mesh)
    return mesh


def triangle_data(mesh: Mesh) -> tuple[Array, Array]:
    """Return element areas and gradients of the three local P1 basis functions."""
    pts = mesh.nodes[mesh.elements]
    x = pts[:, :, 0]
    y = pts[:, :, 1]
    double_area = (
        (x[:, 1] - x[:, 0]) * (y[:, 2] - y[:, 0])
        - (x[:, 2] - x[:, 0]) * (y[:, 1] - y[:, 0])
    )
    if np.any(double_area <= 0.0):
        raise ValueError("All elements must be counter-clockwise and nondegenerate")
    area = 0.5 * double_area

    b = np.stack(
        [y[:, 1] - y[:, 2], y[:, 2] - y[:, 0], y[:, 0] - y[:, 1]],
        axis=1,
    )
    c = np.stack(
        [x[:, 2] - x[:, 1], x[:, 0] - x[:, 2], x[:, 1] - x[:, 0]],
        axis=1,
    )
    gradients = np.stack([b, c], axis=2) / double_area[:, None, None]
    return area, gradients


def validate_mesh(mesh: Mesh, tolerance: float = 1.0e-12) -> None:
    """Check area, orientation, index range and periodic row compatibility."""
    if mesh.elements.min() < 0 or mesh.elements.max() >= len(mesh.nodes):
        raise ValueError("Element connectivity contains an invalid node index")

    area, _ = triangle_data_without_validation(mesh)
    if np.any(area <= 0.0):
        raise ValueError("The mesh contains a degenerate or inverted element")
    if abs(float(area.sum()) - 1.0) > tolerance:
        raise ValueError(f"Element areas sum to {area.sum()}, not 1")

    bottom_start = int(mesh.row_starts[0])
    top_start = int(mesh.row_starts[mesh.n])
    bottom_length = int(mesh.row_lengths[0])
    top_length = int(mesh.row_lengths[mesh.n])
    if bottom_length != top_length:
        raise ValueError("Top and bottom rows are incompatible for periodicity")
    xb = mesh.nodes[bottom_start : bottom_start + bottom_length, 0]
    xt = mesh.nodes[top_start : top_start + top_length, 0]
    if not np.allclose(xb, xt, rtol=0.0, atol=tolerance):
        raise ValueError("Top and bottom x-coordinates do not match")


def triangle_data_without_validation(mesh: Mesh) -> tuple[Array, Array]:
    """Internal triangle-data routine used during mesh validation."""
    pts = mesh.nodes[mesh.elements]
    x = pts[:, :, 0]
    y = pts[:, :, 1]
    double_area = (
        (x[:, 1] - x[:, 0]) * (y[:, 2] - y[:, 0])
        - (x[:, 2] - x[:, 0]) * (y[:, 1] - y[:, 0])
    )
    area = 0.5 * double_area
    b = np.stack(
        [y[:, 1] - y[:, 2], y[:, 2] - y[:, 0], y[:, 0] - y[:, 1]],
        axis=1,
    )
    c = np.stack(
        [x[:, 2] - x[:, 1], x[:, 0] - x[:, 2], x[:, 1] - x[:, 0]],
        axis=1,
    )
    gradients = np.stack([b, c], axis=2) / double_area[:, None, None]
    return area, gradients


def periodic_dirichlet_dof_map(mesh: Mesh) -> Array:
    """Map physical nodes to reduced unknowns.

    Top nodes are identified with the corresponding bottom nodes. Nodes on
    x=0 and x=1 are Dirichlet nodes and receive index -1.
    """
    number_of_nodes = len(mesh.nodes)
    master = np.arange(number_of_nodes, dtype=int)

    bottom_start = int(mesh.row_starts[0])
    top_start = int(mesh.row_starts[mesh.n])
    row_length = int(mesh.row_lengths[0])
    bottom = bottom_start + np.arange(row_length, dtype=int)
    top = top_start + np.arange(row_length, dtype=int)
    master[top] = bottom

    x = mesh.nodes[:, 0]
    is_dirichlet = np.isclose(x, 0.0) | np.isclose(x, 1.0)

    representative = master.copy()
    representative[is_dirichlet] = -1
    # A top Dirichlet node maps to a bottom Dirichlet node; the following also
    # catches that case explicitly.
    for i in range(number_of_nodes):
        if representative[i] >= 0 and is_dirichlet[representative[i]]:
            representative[i] = -1

    active_representatives = np.unique(representative[representative >= 0])
    representative_to_dof = np.full(number_of_nodes, -1, dtype=int)
    representative_to_dof[active_representatives] = np.arange(
        len(active_representatives), dtype=int
    )

    dof = np.full(number_of_nodes, -1, dtype=int)
    active = representative >= 0
    dof[active] = representative_to_dof[representative[active]]
    return dof


# Three-point degree-two quadrature on a triangle.
BARYCENTRIC_QUADRATURE = np.asarray(
    [
        [2.0 / 3.0, 1.0 / 6.0, 1.0 / 6.0],
        [1.0 / 6.0, 2.0 / 3.0, 1.0 / 6.0],
        [1.0 / 6.0, 1.0 / 6.0, 2.0 / 3.0],
    ]
)


def right_hand_side(points: Array) -> Array:
    return np.ones(points.shape[0], dtype=float)


def exact_solution(points: Array) -> Array:
    x = points[:, 0]
    return 0.5 * x * (1.0 - x)


def exact_gradient(points: Array) -> Array:
    x = points[:, 0]
    return np.column_stack((0.5 - x, np.zeros_like(x)))


def assemble_and_solve(
    mesh: Mesh,
    forcing: Callable[[Array], Array] = right_hand_side,
) -> FEMSolution:
    """Assemble and solve the conforming P1 Poisson problem."""
    area, basis_gradients = triangle_data(mesh)
    dof = periodic_dirichlet_dof_map(mesh)
    number_of_dofs = int(dof.max() + 1)

    local_stiffness = area[:, None, None] * np.einsum(
        "tik,tjk->tij", basis_gradients, basis_gradients
    )

    element_points = mesh.nodes[mesh.elements]
    local_load = np.zeros((len(mesh.elements), 3), dtype=float)
    for barycentric_point in BARYCENTRIC_QUADRATURE:
        physical_points = np.einsum(
            "i,tij->tj", barycentric_point, element_points
        )
        f_values = forcing(physical_points)
        local_load += (
            area[:, None]
            * f_values[:, None]
            * barycentric_point[None, :]
            / 3.0
        )

    matrix_rows: list[Array] = []
    matrix_columns: list[Array] = []
    matrix_values: list[Array] = []
    load = np.zeros(number_of_dofs, dtype=float)

    for local_i in range(3):
        global_i = dof[mesh.elements[:, local_i]]
        active_i = global_i >= 0
        np.add.at(load, global_i[active_i], local_load[active_i, local_i])

        for local_j in range(3):
            global_j = dof[mesh.elements[:, local_j]]
            active = active_i & (global_j >= 0)
            matrix_rows.append(global_i[active])
            matrix_columns.append(global_j[active])
            matrix_values.append(local_stiffness[active, local_i, local_j])

    stiffness = coo_matrix(
        (
            np.concatenate(matrix_values),
            (np.concatenate(matrix_rows), np.concatenate(matrix_columns)),
        ),
        shape=(number_of_dofs, number_of_dofs),
    ).tocsr()
    stiffness.sum_duplicates()

    reduced_values = spsolve(stiffness, load)
    values = np.zeros(len(mesh.nodes), dtype=float)
    active_nodes = dof >= 0
    values[active_nodes] = reduced_values[dof[active_nodes]]

    element_gradients = np.einsum(
        "ti,tik->tk", values[mesh.elements], basis_gradients
    )

    return FEMSolution(
        mesh=mesh,
        values=values,
        element_areas=area,
        basis_gradients=basis_gradients,
        element_gradients=element_gradients,
        stiffness=stiffness,
    )


def h1_errors(solution: FEMSolution) -> tuple[float, float, float]:
    """Return L2 error, H1 seminorm error and full H1 norm error."""
    mesh = solution.mesh
    element_points = mesh.nodes[mesh.elements]
    l2_squared = 0.0
    h1_semi_squared = 0.0

    for barycentric_point in BARYCENTRIC_QUADRATURE:
        points = np.einsum("i,tij->tj", barycentric_point, element_points)
        exact_u = exact_solution(points)
        exact_grad = exact_gradient(points)
        discrete_u = np.einsum(
            "i,ti->t", barycentric_point, solution.values[mesh.elements]
        )
        gradient_difference = exact_grad - solution.element_gradients

        l2_squared += np.sum(
            solution.element_areas * (exact_u - discrete_u) ** 2
        ) / 3.0
        h1_semi_squared += np.sum(
            solution.element_areas
            * np.einsum(
                "ij,ij->i", gradient_difference, gradient_difference
            )
        ) / 3.0

    l2_error = float(np.sqrt(l2_squared))
    h1_seminorm_error = float(np.sqrt(h1_semi_squared))
    h1_norm_error = float(np.sqrt(l2_squared + h1_semi_squared))
    return l2_error, h1_seminorm_error, h1_norm_error


def geometry_indicators(mesh: Mesh) -> dict[str, float]:
    """Compute maximal geometric quantities over all elements.

    H0_T = h_T^2 * min_edge(T) / |T| is the directly computable parameter
    H_{T0} used in the cited anisotropic interpolation paper. It is equivalent
    to both H_T and the circumradius in two dimensions.
    """
    pts = mesh.nodes[mesh.elements]
    e01 = np.linalg.norm(pts[:, 1] - pts[:, 0], axis=1)
    e12 = np.linalg.norm(pts[:, 2] - pts[:, 1], axis=1)
    e20 = np.linalg.norm(pts[:, 0] - pts[:, 2], axis=1)
    lengths = np.column_stack((e01, e12, e20))
    lengths_sorted = np.sort(lengths, axis=1)
    h_min = lengths_sorted[:, 0]
    h_max = lengths_sorted[:, 2]
    area, _ = triangle_data(mesh)

    a = lengths[:, 0]
    b = lengths[:, 1]
    c = lengths[:, 2]
    circumradius = a * b * c / (4.0 * area)
    h0 = h_max**2 * h_min / area

    # Angles opposite a, b and c.
    angle_a = np.arccos(np.clip((b**2 + c**2 - a**2) / (2.0 * b * c), -1.0, 1.0))
    angle_b = np.arccos(np.clip((c**2 + a**2 - b**2) / (2.0 * c * a), -1.0, 1.0))
    angle_c = np.pi - angle_a - angle_b
    maximum_angle = np.maximum.reduce([angle_a, angle_b, angle_c])

    return {
        "max_angle_deg": float(np.degrees(maximum_angle.max())),
        "max_circumradius": float(circumradius.max()),
        "max_H0": float(h0.max()),
        "max_H0_over_h": float((h0 / h_max).max()),
        "max_diameter": float(h_max.max()),
        "min_altitude": float((2.0 * area / h_max).min()),
    }


def edge_adjacency(mesh: Mesh) -> dict[tuple[int, int], list[int]]:
    adjacency: dict[tuple[int, int], list[int]] = {}
    for triangle_index, triangle in enumerate(mesh.elements):
        a, b, c = map(int, triangle)
        for edge in ((a, b), (b, c), (c, a)):
            key = tuple(sorted(edge))
            adjacency.setdefault(key, []).append(triangle_index)
    return adjacency


def residual_indicator_standard_weights(solution: FEMSolution) -> float:
    """Compute a fully specified residual indicator.

    The weights used here are

        h_T = diam(T),    h_E = |E|.

    Thus

        eta^2 = sum_T h_T^2 ||f + Delta u_h||_T^2
              + sum_E h_E ||[partial_n u_h]||_E^2.

    Periodic top/bottom edges are paired and treated as interior edges. This
    quantity is included as a transparent computational diagnostic. It is not
    claimed to be numerically identical to the Kunert estimator used by Apel
    et al., because their proceedings article refers the precise anisotropic
    definitions of h_T and h_E to another paper. The exact H1 seminorm error is
    the primary verification quantity below.
    """
    mesh = solution.mesh
    area = solution.element_areas
    points = mesh.nodes[mesh.elements]
    edge_lengths = np.stack(
        [
            np.linalg.norm(points[:, 1] - points[:, 0], axis=1),
            np.linalg.norm(points[:, 2] - points[:, 1], axis=1),
            np.linalg.norm(points[:, 0] - points[:, 2], axis=1),
        ],
        axis=1,
    )
    diameter = edge_lengths.max(axis=1)

    # Since f=1 and Delta u_h=0 elementwise for P1 elements,
    # ||f + Delta u_h||^2_{L2(T)} = |T|.
    element_part = float(np.sum(diameter**2 * area))

    adjacency = edge_adjacency(mesh)
    edge_part = 0.0
    top_edges: dict[tuple[float, float], tuple[tuple[int, int], int]] = {}
    bottom_edges: dict[tuple[float, float], tuple[tuple[int, int], int]] = {}

    for edge, triangles in adjacency.items():
        p0, p1 = mesh.nodes[list(edge)]
        length = float(np.linalg.norm(p1 - p0))
        if length == 0.0:
            raise ValueError("Zero-length edge")

        if len(triangles) == 2:
            t0, t1 = triangles
            tangent = (p1 - p0) / length
            normal = np.asarray([-tangent[1], tangent[0]])
            jump = float(
                np.dot(
                    solution.element_gradients[t0]
                    - solution.element_gradients[t1],
                    normal,
                )
            )
            edge_part += length**2 * jump**2
            continue

        if len(triangles) != 1:
            raise ValueError("An edge must have one or two adjacent elements")

        # Periodic top and bottom edges are paired by their x interval.
        if np.isclose(p0[1], 0.0) and np.isclose(p1[1], 0.0):
            key = tuple(np.round(np.sort([p0[0], p1[0]]), 14))
            bottom_edges[key] = (edge, triangles[0])
        elif np.isclose(p0[1], 1.0) and np.isclose(p1[1], 1.0):
            key = tuple(np.round(np.sort([p0[0], p1[0]]), 14))
            top_edges[key] = (edge, triangles[0])
        else:
            # x=0 or x=1 is a Dirichlet boundary: no Neumann residual term.
            if not (
                (np.isclose(p0[0], 0.0) and np.isclose(p1[0], 0.0))
                or (np.isclose(p0[0], 1.0) and np.isclose(p1[0], 1.0))
            ):
                raise ValueError("Unexpected unpaired boundary edge")

    if set(top_edges) != set(bottom_edges):
        raise ValueError("Periodic top and bottom edge partitions do not match")

    for key in top_edges:
        top_edge, top_triangle = top_edges[key]
        bottom_edge, bottom_triangle = bottom_edges[key]
        top_points = mesh.nodes[list(top_edge)]
        bottom_points = mesh.nodes[list(bottom_edge)]
        length = float(np.linalg.norm(top_points[1] - top_points[0]))
        if not np.isclose(
            length, np.linalg.norm(bottom_points[1] - bottom_points[0])
        ):
            raise ValueError("Paired periodic edges have different lengths")

        # A fixed upward normal gives a sign-independent squared jump.
        jump = float(
            solution.element_gradients[top_triangle, 1]
            - solution.element_gradients[bottom_triangle, 1]
        )
        edge_part += length**2 * jump**2

    return float(np.sqrt(element_part + edge_part))

def interpolate_p1_to_nodes(
    coarse_solution: FEMSolution,
    target_nodes: Array,
) -> Array:
    """Evaluate a coarse P1 function at arbitrary target nodes."""
    coarse_mesh = coarse_solution.mesh
    triangulation = mtri.Triangulation(
        coarse_mesh.nodes[:, 0],
        coarse_mesh.nodes[:, 1],
        coarse_mesh.elements,
    )
    interpolator = mtri.LinearTriInterpolator(
        triangulation, coarse_solution.values
    )
    values = interpolator(target_nodes[:, 0], target_nodes[:, 1])
    values = np.ma.asarray(values)

    if np.any(np.ma.getmaskarray(values)):
        # Numerical point-location can classify boundary points as exterior.
        shifted = target_nodes.copy()
        eps = 1.0e-12
        shifted[:, 0] = np.clip(shifted[:, 0], eps, 1.0 - eps)
        shifted[:, 1] = np.clip(shifted[:, 1], eps, 1.0 - eps)
        replacement = interpolator(shifted[:, 0], shifted[:, 1])
        values = np.ma.where(np.ma.getmaskarray(values), replacement, values)

    if np.any(np.ma.getmaskarray(values)):
        raise RuntimeError("Some target nodes could not be located in the coarse mesh")

    result = np.asarray(values, dtype=float)
    result[np.isclose(target_nodes[:, 0], 0.0)] = 0.0
    result[np.isclose(target_nodes[:, 0], 1.0)] = 0.0
    return result


def same_family_fine_gap(
    coarse_solution: FEMSolution,
    fine_solution: FEMSolution,
) -> float:
    """Compute |u_fine - I_fine u_coarse|_{H1}."""
    interpolated_coarse_values = interpolate_p1_to_nodes(
        coarse_solution, fine_solution.mesh.nodes
    )
    interpolated_coarse_gradient = np.einsum(
        "ti,tik->tk",
        interpolated_coarse_values[fine_solution.mesh.elements],
        fine_solution.basis_gradients,
    )
    gradient_difference = (
        fine_solution.element_gradients - interpolated_coarse_gradient
    )
    squared = np.sum(
        fine_solution.element_areas
        * np.einsum("ij,ij->i", gradient_difference, gradient_difference)
    )
    return float(np.sqrt(squared))


def plot_mesh(mesh: Mesh, title: str = "Babuska--Aziz mesh") -> None:
    plt.figure(figsize=(6.2, 6.2))
    plt.triplot(
        mesh.nodes[:, 0],
        mesh.nodes[:, 1],
        mesh.elements,
        linewidth=0.7,
    )
    plt.gca().set_aspect("equal")
    plt.xlabel("x")
    plt.ylabel("y")
    plt.title(f"{title}: m={mesh.m}, n={mesh.n}")
    plt.tight_layout()
    plt.show()


def run_experiment(
    beta: float,
    m_values: tuple[int, ...] = (2, 4, 8, 12),
    reference_m: int | None = None,
) -> list[dict[str, float]]:
    """Solve one mesh family and print all verification quantities."""
    if reference_m is None:
        reference_m = max(m_values) + 5
    if reference_m <= max(m_values):
        raise ValueError("reference_m must be larger than all m_values")

    reference_n = even_ceil(reference_m**beta)
    print(
        f"Computing same-family reference: beta={beta}, "
        f"m_ref={reference_m}, n_ref={reference_n}"
    )
    reference_solution = assemble_and_solve(
        babuska_aziz_mesh(reference_m, reference_n)
    )

    results: list[dict[str, float]] = []
    for m in m_values:
        n = even_ceil(m**beta)
        solution = assemble_and_solve(babuska_aziz_mesh(m, n))
        l2_error, h1_semi_error, h1_error = h1_errors(solution)
        geometry = geometry_indicators(solution.mesh)
        estimator = residual_indicator_standard_weights(solution)
        fine_gap = same_family_fine_gap(solution, reference_solution)

        row = {
            "beta": float(beta),
            "m": float(m),
            "n": float(n),
            "nodes": float(len(solution.mesh.nodes)),
            "L2_error": l2_error,
            "H1_semi_error": h1_semi_error,
            "H1_error": h1_error,
            "max_uh": float(np.max(solution.values)),
            "residual_indicator": estimator,
            "indicator_effectivity": estimator / h1_semi_error,
            "fine_gap": fine_gap,
            **geometry,
        }
        results.append(row)

    print_results(results)
    plot_results(results)
    return results


def print_results(results: list[dict[str, float]]) -> None:
    header = (
        " beta    m      n     nodes   |e|_H1      max(u_h)    fine_gap    "
        "max_angle    max_R      eta_res    eta/err    max_H0/h"
    )
    print(header)
    print("-" * len(header))
    for row in results:
        print(
            f"{row['beta']:5.2f} "
            f"{int(row['m']):4d} "
            f"{int(row['n']):6d} "
            f"{int(row['nodes']):9d} "
            f"{row['H1_semi_error']:10.3e} "
            f"{row['max_uh']:10.3e} "
            f"{row['fine_gap']:10.3e} "
            f"{row['max_angle_deg']:10.4f} "
            f"{row['max_circumradius']:10.3e} "
            f"{row['residual_indicator']:10.3e} "
            f"{row['indicator_effectivity']:9.3f} "
            f"{row['max_H0_over_h']:10.3e}"
        )


def plot_results(results: list[dict[str, float]]) -> None:
    m = np.asarray([row["m"] for row in results])
    true_error = np.asarray([row["H1_semi_error"] for row in results])
    fine_gap = np.asarray([row["fine_gap"] for row in results])
    circumradius = np.asarray([row["max_circumradius"] for row in results])

    plt.figure(figsize=(6.2, 4.5))
    plt.loglog(m, true_error, "o-", label=r"$|u-u_h|_{H^1}$")
    plt.loglog(m, fine_gap, "s--", label=r"$|u_{fine}-I_{fine}u_h|_{H^1}$")
    plt.xlabel("m")
    plt.ylabel("error measure")
    plt.grid(True, which="both")
    plt.legend()
    plt.tight_layout()
    plt.show()

    plt.figure(figsize=(6.2, 4.5))
    plt.loglog(m, circumradius, "o-")
    plt.xlabel("m")
    plt.ylabel(r"$\max_T R_T$")
    plt.grid(True, which="both")
    plt.tight_layout()
    plt.show()


if __name__ == "__main__":
    # A small mesh for visual inspection.
    plot_mesh(babuska_aziz_mesh(m=6, n=18))

    # Three regimes are run explicitly so that the tables in the blog can be
    # reproduced without editing the program.
    #
    # beta = 1.5 : the maximal angle condition is violated, but the true H1
    #              error still tends to zero.
    results_beta_15 = run_experiment(
        beta=1.5,
        m_values=(4, 8, 16, 24),
        reference_m=32,
    )

    # beta = 2.0 : critical regime.  The circumradius remains O(1), and the
    #              true H1 error levels off instead of tending to zero.
    results_beta_2 = run_experiment(
        beta=2.0,
        m_values=(4, 8, 16, 24),
        reference_m=32,
    )

    # beta = 3.0 : strong failure.  The numerical solution becomes very small,
    #              the true H1 error approaches |u|_{H1}=1/sqrt(12), while the
    #              gap to a fixed fine solution from the same mesh family
    #              decreases.  The original paper used m_ref=31; reference_m=17
    #              is a lighter default for a laptop or Colab session.
    results_beta_3 = run_experiment(
        beta=3.0,
        m_values=(2, 4, 8, 12),
        reference_m=17,
    )

References

  1. T. Apel,L. Eckardt,C. Haubner,V. Kempf, The maximal angle condition on finite elements: useful or not?, PAMM 20 (2020),e202000116. DOI
  2. I. Babuška,A. K. Aziz, On the angle condition in the finite element method, SIAM Journal on Numerical Analysis 13 (1976),214–226. DOI
  3. P. Oswald, Divergence of FEM: Babuška–Aziz triangulations revisited, Applications of Mathematics 60 (2015),473–484. DOI
  4. A. Hannukainen,S. Korotov,M. Křížek, The maximum angle condition is not necessary for convergence of the finite element method, Numerische Mathematik 120 (2012),79–88. DOI
  5. K. Kobayashi,T. Tsuchiya, A Babuška–Aziz type proof of the circumradius condition, Japan Journal of Industrial and Applied Mathematics 31 (2014),193–210. DOI
  6. H. Ishizaka,K. Kobayashi,T. Tsuchiya, General theory of interpolation error estimates on anisotropic meshes, Japan Journal of Industrial and Applied Mathematics 38 (2021),163–191. DOI
  7. H. Ishizaka,K. Kobayashi,T. Tsuchiya, Anisotropic interpolation error estimates using a new geometric parameter, Japan Journal of Industrial and Applied Mathematics 40 (2023),475–512. DOI
  8. V. Kučera, On necessary and sufficient conditions for finite element convergence, preprint,2016. arXiv

ページの先頭へ