Random Walker Log's Log

二度と見ない系ログファイル

離散Gronwallの不等式についてメモ

Gronwallの不等式について、微分が差分商に、積分が和に変わった形の定理が成り立つ。


Prop.1(Gronwallの不等式の微分形・離散バージョン)
実数 \lambdaと正の実数 \Delta t 1+\lambda \Delta t > 0をみたしており、実数列 \{a_n\}, \{g_n\}について
\[ \frac{a_{n+1} - a_n}{\Delta t} \leq g_n + \lambda a_n \quad , \quad n = 0,1,\dots \]
が成り立つとする。このとき、
\[ a_n \leq (1 + \lambda \Delta t )^n \left( a_0 + \Delta t \sum_{j=0}^{n-1} (1+\lambda \Delta t )^{-(j+1)} g_j \right) \]
さらに、 \{ g_n \}が非減少ならば
\[ a_n \leq (1 + \lambda \Delta t )^n a_0 + \frac{1}{\lambda} \left( (1 + \lambda \Delta t)^n - 1 \right) g_{n-1} \]

proof.
 b_n := (1 + \lambda \Delta t )^{-n} a_nとおくと、
\begin{eqnarray*}
\frac{b_{n+1} - b_n}{\Delta t} &=& \frac{1}{\Delta t} (1 + \lambda \Delta t ) ^{-(n+1)} (a_{n+1} - (1 + \lambda \Delta t ) a_n)\\
&=& (1 + \lambda \Delta t ) ^{-(n+1)} \left( \frac{a_{n+1}-a_n}{\Delta t} - \lambda a_n \right)\\
&\leq& (1 + \lambda \Delta t )^{-(n+1)} g_n
\end{eqnarray*}
 0から n-1まで足し合わせれば、
\[ \frac{b_n - b_0}{\Delta t} \leq \sum_{j=0}^{n-1} (1 + \lambda \Delta t )^{-(j+1)} g_j \]
これより結論を得る。また、 \{ g_n \}が非減少の場合は、 g_j \leq g_{n-1}であることと、
\[ \sum_{j=0}^{n-1} (1 + \lambda \Delta t )^{-(j+1)} = \frac{1}{\lambda \Delta t} \left( 1 - (1+\lambda \Delta t) ^{-n} \right) \]
よりいえる。■

昨日の記事の不等式は、Prop.1の \{ g_n \}が非減少の場合から出る。

Prop.2 (Gronwallの不等式の積分形・離散バージョン)
非負数列 \{ y_n \}, \{ f_n \}, \{ g_n \}
\[ y_n \leq f_n + \sum_{0 \leq k \lt n} g_k y_k \quad , \quad n\geq 0 \]
をみたしているとき
\[ y_n \leq f_n + \sum _{0 \leq k \lt n} f_k g_k \prod _{k \lt j \lt n} (1 + g_j ) \quad , \quad n \geq 0 \]
が成り立つ。

proof.
 nに関する数学的帰納法で示す。

 n=0のときは、両方とも右辺は f_0になるので成り立つ。

 m \gt 0とし、
 0 \leq m < nのときに下の不等式が成り立っていると仮定する。
上の不等式と帰納法の仮定より、

\begin{eqnarray*}
y_m &\leq& f_m + \sum_{0\leq k < m}g_ky_k \\
&\leq& f_m + \sum_{0\leq k < m} g_k \left( f_k + \sum_{0\leq j < k} f_j g_j \prod _{j < i < k} (1+g_i) \right) \\
&=& f_m + \sum_{0\leq j < m} f_j g_j + \sum_{0\leq j < m} \sum_{j < k < m} f_j g_j g_k \prod _{j < i < k} (1 + g_i)\\
&=& f_m + \sum_{0\leq j < m} f_j g_j \left( 1 + \sum _{j < k < m} g_k \prod _{j < i < k} (1 + g_i) \right)\\
&=& f_m + \sum_{0\leq j < m} f_j g_j \left( 1 + g_{j + 1} \cdot 1 + g_{j + 2} (1 + g_{j + 1}) + \cdots + g_{m - 1} (1 + g_{j + 1}) \cdots (1 + g_{m - 2}) \right)\\
&=& f_m + \sum_{0\leq j < m} f_j g_j \left( (1 + g_{j + 1}) (1 + g_{j +2} + \cdots + g_{m - 1} (1 + g_{j + 2} \cdots (1 + g_{m - 2})) \right)\\
&=& \cdots \\
&=& f_m + \sum_{0\leq j < m} f_j g_j \prod_{j < i < m}(1 + g_i)\\
\end{eqnarray*}
よって n=mの場合にも成り立つ。■

 1 + x \leq e^xを用いると、結論の不等式から、それぞれ
\[ a_n \leq e^{ n \lambda \Delta t } a_0 + \sum_{j = 0} ^{n - 1} e^{(n - j - 1) \lambda \Delta t} g_j \Delta t \]

\[ y_n \leq f_n + \sum_{0 \leq k < n} f_k g_k \exp \left( \sum_{k < j < n} g_j \right) \]

この形ならGronwallの不等式との対応は明らか。

はてなtex機能を試そうとしただけなのに時間がかかってしまった。はてなブログではhtmlタグと地の文が混在しているので、数式を書くときには注意が要る。例えば、不等号とマイナスを使うときは両隣にスペースを開けておかないとタグの一部だと認識されて消えてしまったりtexに変換されなかったりする。他にもまだ何かあるかもしれない。