第9回:BDFとconvolution quadratureは何を離散化しているのか

はじめに――BDF convolution quadratureは何を離散化するのか

memory term \[ (k*u)(t) = \int_0^t k(t-s)u(s)\,ds \] を見ると,時間区間を分割して台形則や長方形則を適用したくなります. しかし,convolution quadrature(CQ)の出発点は,この積分を直接近似することではありません.

CQが離散化するのは,Laplace領域における \[ \widehat k(z) \] というtransfer function,より正確には \[ \widehat k(\partial_t) \] として表されるcausal operatorです. 時間微分 \(\partial_t\) をBDF symbolで置き換えることにより, kernelの作用全体を離散化します.

今回の結論
BDF convolution quadratureは, \[ \partial_t \quad\longmapsto\quad \frac{\delta_q(\xi)}{\Delta t} \] という置換をtransfer functionの内部で行う離散operational calculusである.

この見方を採ると,CQ weights,内部変数,A-stability,G-stability, starting correction,kernel singularityが一つの構造として理解できます.

1.causal convolutionはtransfer functionで特徴付けられる

causal kernel \(k\) のLaplace transformを \[ \widehat k(z) := \int_0^\infty e^{-zt}k(t)\,dt, \qquad \operatorname{Re}z>0 \tag{1} \] とします.

指数入力 \[ u(t)=e^{zt}u_* \] を形式的に考えると,十分過去から作用している定常的なconvolution operatorは \[ k*u = \widehat k(z)e^{zt}u_* \] と応答します. つまり \(\widehat k(z)\) は,時間周波数 \(z\) に対するmemory operatorの応答です.

このため,causal convolutionを \[ K(\partial_t)u := k*u, \qquad K(z):=\widehat k(z) \tag{2} \] と記述できます. CQはこのoperator-valued notationを離散化します.

2.第2回のdynamic Schur complementとの関係

未解像状態 \[ \partial_tz+Cz=Du \] を消去すると, \[ K(t)=Be^{-tC}D \] というmemory kernelが現れました. Laplace領域では \[ \widehat K(z) = B(zI+C)^{-1}D. \tag{3} \]

これはdynamic Schur complementです. 従ってCQは,単なるscalar kernelだけでなく, \[ B(zI+C)^{-1}D \] のようなoperator-valued transfer functionにも適用できます. CQが離散化しているのは,未解像generatorのresolventを含む縮約作用素全体です.

3.BDF symbolは時間微分の離散transfer functionである

一様時間刻み \[ t_n=n\Delta t \] を取り,BDF1・BDF2の生成多項式を \[ \delta_1(\xi)=1-\xi, \tag{4} \] \[ \delta_2(\xi) = \frac32-2\xi+\frac12\xi^2 \tag{5} \] とします.

離散指数列 \[ u^n=e^{zt_n}u_* \] にBDFを作用させると,時間微分 \(z\) の代わりに \[ \frac{\delta_q(e^{-z\Delta t})}{\Delta t} \tag{6} \] が現れます. \(\Delta t\downarrow0\) では \[ \frac{\delta_q(e^{-z\Delta t})}{\Delta t} = z+O(\Delta t^q), \qquad q\in\{1,2\}, \tag{7} \] です.

従ってBDF symbol \[ \frac{\delta_q(\xi)}{\Delta t} \] は,Laplace variable \(z\),すなわち時間微分 \(\partial_t\) の離散版です.

4.CQ weightsの定義

BDF convolution quadratureのweights \[ \omega_n^{(q)}, \qquad n\ge0 \] は,生成関数 \[ \widehat k \left( \frac{\delta_q(\xi)}{\Delta t} \right) = \sum_{n=0}^{\infty} \omega_n^{(q)}\xi^n \tag{8} \] によって定義されます.

離散convolution operatorは \[ (K_{\Delta t}^{(q)}v)^n := \sum_{j=0}^{n} \omega_{n-j}^{(q)}v^j. \tag{9} \]

重要な点
\(\omega_n^{(q)}\) は一般に \(k(n\Delta t)\Delta t\) ではない.
kernel valuesを数値積分して作るのではなく, transfer functionへBDF symbolを代入した後のTaylor係数である.

従って,kernelが弱特異でも,Laplace transformが扱えれば CQ weightsを定義できます.

5.CQは何を近似しているのか

連続operatorは \[ \widehat k(\partial_t) \] であり,BDF-CQは \[ \widehat k \left( \frac{\delta_q(\mathsf S)}{\Delta t} \right) \tag{10} \] と読むことができます. ここで \(\mathsf S\) は一step backward shiftです.

つまり,近似の順序は

\[ \text{kernelを時間格子で標本化} \quad\text{ではなく}\quad \partial_t \longmapsto \frac{\delta_q(\mathsf S)}{\Delta t} \longmapsto \widehat k \left( \frac{\delta_q(\mathsf S)}{\Delta t} \right) \tag{11} \]

です. このoperational calculusが,CQを通常のtime quadratureと区別します.

6.一つの指数kernelで確認する

\[ k_\lambda(t)=e^{-\lambda t}, \qquad \lambda\ge0 \] なら \[ \widehat k_\lambda(z) = \frac{1}{z+\lambda}. \tag{12} \] CQ generating functionは \[ \frac{1}{ \delta_q(\xi)/\Delta t+\lambda }. \tag{13} \]

一方,内部変数 \[ \partial_t\zeta+\lambda\zeta=v, \qquad \zeta(0)=0 \tag{14} \] をBDFで離散化すると \[ \overline\partial_{\Delta t}^{(q)} \zeta^n + \lambda\zeta^n = v^n. \tag{15} \] 生成関数を取れば \[ Z(\xi) = \frac{1}{ \delta_q(\xi)/\Delta t+\lambda } V(\xi). \tag{16} \]

式 (13) と式 (16) は同じです.ただし,生成関数の式 (16) では,負の添字の内部状態を0とし,\(n=0\) を含む離散列を同じBDF relationで定める開始規約を用いています.したがって,一つの指数kernelに対するBDF-CQは,開始規約が整合する場合に,relaxation ODEのBDF realisationと一致します.

開始時刻の扱いは単なる細部ではありません.例えば \(\Delta t=1\),\(\lambda=1\),\(v^0=0,\ v^1=1\) とすると,内部変数を \(\zeta^0=0\) からBDF1で開始した値は \(\zeta^1=1/2\) です.一方,無補正BDF2-CQの初回の値は \(\omega_0v^1=(3/2+1)^{-1}=2/5\) です.したがってBDF1 startとBDF2-CQを無条件に同一視してはいけません.

7.finite Prony kernelは有限個のlocal recursionになる

\[ k_L(t) = \sum_{\ell=1}^{L} c_\ell e^{-\lambda_\ell t}, \qquad c_\ell>0 \tag{17} \] なら \[ \widehat k_L(z) = \sum_{\ell=1}^{L} \frac{c_\ell}{z+\lambda_\ell}. \tag{18} \]

各mode \[ \overline\partial_{\Delta t}^{(q)} \zeta_\ell^n + \lambda_\ell\zeta_\ell^n = v^n \tag{19} \] を更新すれば \[ (K_{\Delta t,L}^{(q)}v)^n = \sum_{\ell=1}^{L} c_\ell\zeta_\ell^n. \tag{20} \]

直接convolutionを計算するとhistory lengthとともにcostが増えますが, 開始規約が整合したfinite Prony realisationでは各stepで \(L\) 個のlocal stateを更新すればよく, \(N\) stepsに対して基本costは \(O(LN)\) です.

8.一般のcompletely monotone kernelにもhidden internal variablesがある

completely monotone kernelは \[ k(t) = \int_{[0,\infty)} e^{-\lambda t}\,d\nu(\lambda) \tag{21} \] と表され, \[ \widehat k(z) = \int_{[0,\infty)} \frac{1}{z+\lambda}\,d\nu(\lambda). \tag{22} \]

有限Bernstein mass \[ M_0:=\nu([0,\infty))<\infty \tag{23} \] のもとで,式 (8) に式 (22) を代入すると \[ \begin{aligned} \widehat k \left( \frac{\delta_q(\xi)}{\Delta t} \right) &= \int_{[0,\infty)} \frac{1}{ \delta_q(\xi)/\Delta t+\lambda } \,d\nu(\lambda). \end{aligned} \tag{24} \]

従って \[ (K_{\Delta t}^{(q)}v)^n = \int_{[0,\infty)} \zeta^n(\lambda)\,d\nu(\lambda), \tag{25} \] \[ \overline\partial_{\Delta t}^{(q)} \zeta^n(\lambda) + \lambda\zeta^n(\lambda) = v^n. \tag{26} \]

hidden internal-variable identity
一般のcompletely monotone kernelに対するBDF-CQは, 有限Prony近似をしなくても, \(\nu\)-連続個のBDF内部変数を重ね合わせたものと正確に一致する.

implementationではCQ weightsを使い, energy proofではhidden internal variablesを使うことができます. これは有限 \(M_0\) と互換な開始規約のもとでのexact identityです.start-up correctionや異なる初回stepを加えた場合は,対応する補正項を別に含める必要があります.

9.BDF1・BDF2だけが現れる理由

BDF-CQ自体は高次BDFからも形式的に構成できます. しかし,本連載で用いる無条件のgraph-energy恒等式は,BDF1・BDF2の具体的なG-stability恒等式に基づいています.両法はA-stableでもありますが,一般のCQにおいてA-stabilityだけから同じgraph-energy恒等式が自動的に得られると主張しているわけではありません.

BDF familyでA-stableなのはorders 1 and 2だけです. これはDahlquistのsecond barrierと整合します. 従って \[ q\in\{1,2\} \] という制限は,単なる計算上の選択ではなく, ここで使うBDF1・BDF2の無条件energy解析を選ぶ根拠です.

method natural energy unconditional graph-energy identity
BDF1 one-step standard energy yes
BDF2 two-step G-energy yes
higher BDF 一般に同じunconditional G-energyはない no

10.BDF2 weightsの各項が正である必要はない

positive-type kernelだから \[ \omega_n^{(2)}\ge0 \] がすべての \(n\) で必要だと思うかもしれません. しかし,structure-preserving analysisは coefficientwise positivityを仮定しません.

必要なのは,weight列が作るquadratic formのpositivityです. hidden internal-variable representationとBDF2のG-stabilityにより, 各weightの符号を個別に調べなくても, two-step memory graph energyを制御できます.

区別
各CQ weightが非負であること:coefficientwise property.
離散convolutionが非負のenergy quadratic formを作ること:structural property.

後者がenergy analysisに必要な性質です.

11.zeroth CQ weightが各time stepを解けるようにする

zeroth weightは \[ \omega_0^{(q)} = \widehat k \left( \frac{\delta_q(0)}{\Delta t} \right) = \int_{[0,\infty)} \frac{1}{ \delta_q(0)/\Delta t+\lambda } \,d\nu(\lambda). \tag{27} \]

\[ \delta_1(0)=1, \qquad \delta_2(0)=\frac32, \] かつ \(\nu\) は非負なので,非自明kernelに対して \[ \omega_0^{(q)}>0. \tag{28} \]

memory equationをfully discrete化すると,現在値 \(u_h^n\) には \[ \omega_0^{(q)}a_{1,h}(u_h^n,v_h) \] が作用します. \(a_{1,h}\) がcoerciveなら,この正のzeroth weightが 各time stepの離散elliptic problemにcoercivityを与えます.

従って,瞬時形式 \(a_{0,h}\) が非負に退化していても, 各stepのsolvabilityにその正のlower boundを使う必要はありません.

12.fractional kernelでは何が起こるか

\[ k_\alpha(t) = \frac{t^{-\alpha}}{\Gamma(1-\alpha)}, \qquad 0<\alpha<1 \] では \[ \widehat k_\alpha(z) = z^{\alpha-1}. \tag{29} \] 従ってBDF-CQ weightsは \[ \left( \frac{\delta_q(\xi)}{\Delta t} \right)^{\alpha-1} = \sum_{n=0}^{\infty} \omega_{\alpha,n}^{(q)}\xi^n \tag{30} \] から生成されます.

時間kernelは \(t=0\) で弱特異ですが, CQはkernel valueを直接積分せず,transfer functionのfractional powerを使うため, 同じ定義が可能です.

ただし,fractional kernelではBernstein mass \(M_0\) が無限大なので, 第6回・第8回で使ったfinite-mass memory graph spaceへ そのまま入るわけではありません. CQの定義可能性と,finite-\(M_0\) graph-energy certificateの成立は別問題です.

13.uncorrected CQとstarting correction

BDFのformal orderが \(q\) でも, non-smooth initial dataや \(t=0\) で特異なkernelに対して, uncorrected CQが常にglobal order \(q\) を達成するとは限りません. 初期層によりorder reductionが起こり得ます.

starting correctionは,最初の数stepのweightsや右辺を修正し, 低正則性データに対する高次精度を回復するために使われます. しかし,causal weightsを変更すると,

\[ \text{CQ} = \text{modewise BDF internal variables} \tag{31} \]

というexact identityが同じ形では残らない可能性があります. その結果,第8回のmodewise graph-energy identityも再検討が必要です.

構造と精度のtrade-off
uncorrected CQ:exact hidden-state identityとgraph energyを優先.
starting-corrected CQ:non-smooth dataに対する高次精度を優先するが,energy構造を再設計する必要がある.

現在のstructure-preserving programmeでは,まずuncorrected BDF1・BDF2を用いて coercivity-robustな離散構造を確立し,corrected variantsは別問題として扱います.

14.CQと通常のtime quadratureの違い

観点 direct time quadrature convolution quadrature
出発点 時間積分 \(\int_0^t k(t-s)u(s)\,ds\) transfer function \(\widehat k(z)\)
weights kernel valuesと積分公式から構成 \(\widehat k(\delta_q(\xi)/\Delta t)\) の係数
弱特異kernel 特異積分への個別処理が必要 Laplace transformを通して統一的に定義
stability inheritance quadratureごとに解析 underlying time integratorのA-stabilityと結び付く
hidden-state interpretation 通常は直接見えない completely monotone kernelではBDF内部変数とexactly一致

15.implementationはweights,proofはinternal variables

一般kernelに対する実装では \[ (K_{\Delta t}^{(q)}v)^n = \sum_{j=0}^{n} \omega_{n-j}^{(q)}v^j \] を用いるのが直接的です. weightsはcontour integral,FFT-based coefficient extraction, または専用recursionで計算できます.

一方,energy proofでは \[ (K_{\Delta t}^{(q)}v)^n = \int_{[0,\infty)} \zeta^n(\lambda)\,d\nu(\lambda) \] を用いると,continuous theoryと同じcross-term cancellationが見えます.

従って役割分担は

\[ \boxed{ \text{implementation uses CQ weights} \qquad \text{proof uses hidden internal variables} } \tag{32} \]

です. finite positive Prony approximationを採用する場合には, proofで使った内部状態をそのままimplementationにも使えます.

16.CQ weightの計算誤差も独立した誤差源である

理論上のCQ weightsを数値的に計算する場合, fully discrete errorには

\[ \begin{aligned} \text{total error} \le{}& \text{space discretisation error} \\ &+ \text{BDF-CQ consistency error} \\ &+ \text{starting error} \\ &+ \text{CQ-weight computation error} \\ &+ \text{linear solver error}. \end{aligned} \tag{33} \]

が現れます. さらにpositive Prony realisationを用いるなら, relaxation-spectrum quadrature errorも加わります.

どのerrorをmodel-reduction errorと呼び, どのerrorをstate-discretisation errorと呼ぶかを明確に分けることが, 次回の課題です.

17.異方性CR法との接続

CQは時間方向のmemory operatorを離散化します. 異方性Crouzeix–Raviart法は空間方向の非適合近似です. 両者を結び付けるときには,同じbroken form \[ a_{1,h} \] をprincipal memory termとhidden internal-variable equationsに使います.

すると要素形状にかかわらずcoupling cancellationは代数的に成立します. その後に,semi-regularity,CR–RT relation,離散Poincaré inequalityを用いて, nonconforming consistencyと異方性補間誤差を評価します.

時間構造と空間幾何の役割は

  • BDF-CQとG-stability:離散memory graph energyを作る.
  • 共通の \(a_{1,h}\):cross-term cancellationを保存する.
  • CR–RT anisotropic analysis:空間consistency errorを制御する.

と分離できます.

18.CQが保存するもの,保存しないもの

構造的に保存されるもの

  • BDF time integratorのcausality.
  • completely monotone kernelのhidden relaxation structure.
  • BDF1のstandard graph energy.
  • BDF2のG-type graph energy.
  • 同じ離散形式を用いたときのcross-term cancellation.

自動的には保存されないもの

  • 各BDF2 CQ weightのcoefficientwise positivity.
  • non-smooth dataに対するformal order \(q\).
  • starting correction後のexact modewise energy identity.
  • kernel approximation,space discretisation,time discretisationの各極限の可換性.
  • fractional kernelに対するfinite-\(M_0\) graph-space certificate.

19.今回の問いへの答え

「BDFとconvolution quadratureは何を離散化しているのか」という問いには, 三段階で答えられます.

  1. operator level: causal convolution operator \(\widehat k(\partial_t)\) を離散化している.
  2. Laplace-domain level: transfer function \(\widehat k(z)\) の \(z\) を \(\delta_q(\xi)/\Delta t\) へ置き換えている.
  3. hidden-state level: completely monotone kernelを構成する各relaxation modeを 同じBDF法で離散化し,それらをBernstein measureで重ね合わせている.

この三つは別々の説明ではなく,同じCQ operatorの三つの表現です.

Conclusion

BDF convolution quadratureは,履歴積分を格子点上で直接積分する方法ではありません. Laplace-domain transfer functionへBDF symbolを代入し, causal operator全体を離散化するoperational calculusです.

\[ \widehat k(\partial_t) \quad\longrightarrow\quad \widehat k \left( \frac{\delta_q(\mathsf S)}{\Delta t} \right) \]

completely monotone kernelでは,互換な開始規約を用いる限り,この離散operatorはBDFで更新されたhidden internal variablesの連続的重ね合わせと一致します. このidentityが,第8回のcross-term cancellationと離散graph-energy lawの根拠です.

BDF1・BDF2が特別なのは,orders 1 and 2だからだけではありません. BDF familyの中でA-stable,従ってG-stableであり, unconditionalなgraph-energy identityを支えられる方法だからです.

次回: 第10回:model-reduction errorをどう分解するか
lag measureのfinite-atomic approximation,relaxation spectrumのProny approximation, space-time discretisation,solver toleranceを分離し, どの誤差をどのnormでcertifyすべきかを整理します.

前の記事: 第8回:離散内部変数でcross-term cancellationを保存する

関連ページ: Publications(S3–S5,A3), Research Visions(Vision 11,18), Supplementary Visions(履歴依存型発展方程式とmemory kernel)

ページの先頭へ