1 files changed, 210 insertions, 0 deletions
diff --git a/content/know/concept/gronwall-bellman-inequality/index.pdc b/content/know/concept/gronwall-bellman-inequality/index.pdc
new file mode 100644
index 0000000..1f093ae
--- /dev/null
+++ b/content/know/concept/gronwall-bellman-inequality/index.pdc
@@ -0,0 +1,210 @@
+---
+title: "Grönwall-Bellman inequality"
+firstLetter: "G"
+publishDate: 2021-11-07
+categories:
+- Mathematics
+
+date: 2021-11-07T09:51:57+01:00
+draft: false
+markup: pandoc
+---
+
+# Grönwall-Bellman inequality
+
+Suppose we have a first-order ordinary differential equation
+for some function $u(t)$, and that it can be shown from this equation
+that the derivative $u'(t)$ is bounded as follows:
+
+$$\begin{aligned}
+    u'(t)
+    \le \beta(t) \: u(t)
+\end{aligned}$$
+
+Where $\beta(t)$ is known.
+Then **Grönwall's inequality** states that the solution $u(t)$ is bounded:
+
+$$\begin{aligned}
+    \boxed{
+        u(t)
+        \le u(0) \exp\!\bigg( \int_0^t \beta(s) \dd{s} \bigg)
+    }
+\end{aligned}$$
+
+<div class="accordion">
+<input type="checkbox" id="proof-original"/>
+<label for="proof-original">Proof</label>
+<div class="hidden">
+<label for="proof-original">Proof.</label>
+We define $w(t)$ to equal the upper bounds above
+on both $w'(t)$ and $w(t)$ itself:
+
+$$\begin{aligned}
+    w(t)
+    \equiv u(0) \exp\!\bigg( \int_0^t \beta(s) \dd{s} \bigg)
+    \quad \implies \quad
+    w'(t)
+    = \beta(t) \: w(t)
+\end{aligned}$$
+
+Where $w(0) = u(0)$.
+The goal is to show the following for all $t$:
+
+$$\begin{aligned}
+    \frac{u(t)}{w(t)} \le 1
+\end{aligned}$$
+
+For $t = 0$, this is trivial, since $w(0) = u(0)$ by definition.
+For $t > 0$, we want $w(t)$ to grow at least as fast as $u(t)$
+in order to satisfy the inequality.
+We thus calculate:
+
+$$\begin{aligned}
+    \dv{t} \bigg( \frac{u}{w} \bigg)
+    = \frac{u' w - u  w'}{w^2}
+    = \frac{u' w - u \beta w}{w^2}
+    = \frac{u' - u \beta}{w}
+\end{aligned}$$
+
+Since $u' \le \beta u$ as a condition,
+the above derivative is always negative.
+</div>
+</div>
+
+Grönwall's inequality can be generalized to non-differentiable functions.
+Suppose we know:
+
+$$\begin{aligned}
+    u(t)
+    \le \alpha(t) + \int_0^t \beta(s) \: u(s) \dd{s}
+\end{aligned}$$
+
+Where $\alpha(t)$ and $\beta(t)$ are known.
+Then the **Grönwall-Bellman inequality** states that:
+
+$$\begin{aligned}
+    \boxed{
+        u(t)
+        \le \alpha(t) + \int_0^t \alpha(s) \: \beta(s) \exp\!\bigg( \int_s^t \beta(r) \dd{r} \bigg) \dd{s}
+    }
+\end{aligned}$$
+
+<div class="accordion">
+<input type="checkbox" id="proof-integral"/>
+<label for="proof-integral">Proof</label>
+<div class="hidden">
+<label for="proof-integral">Proof.</label>
+We start by defining $w(t)$ as follows,
+which will act as shorthand:
+
+$$\begin{aligned}
+    w(t)
+    \equiv \exp\!\bigg( \!-\!\! \int_0^t \beta(s) \dd{s} \bigg) \bigg( \int_0^t \beta(s) \: u(s) \dd{s} \bigg)
+\end{aligned}$$
+
+Its derivative $w'(t)$ is then straightforwardly calculated to be given by:
+
+$$\begin{aligned}
+    w'(t)
+    &= \bigg( \dv{t}\! \int_0^t \beta(s) \: u(s) \dd{s} - \beta(t)\int_0^t \beta(s) \: u(s) \dd{s} \bigg) 
+    \exp\!\bigg( \!-\!\! \int_0^t \beta(s) \dd{s} \bigg)
+    \\
+    &= \beta(t) \bigg( u(t) - \int_0^t \beta(s) \: u(s) \dd{s} \bigg)
+    \exp\!\bigg( \!-\!\! \int_0^t \beta(s) \dd{s} \bigg)
+\end{aligned}$$
+
+The parenthesized expression it bounded from above by $\alpha(t)$,
+thanks to the condition that $u(t)$ is assumed to satisfy,
+for the Grönwall-Bellman inequality to be true:
+
+$$\begin{aligned}
+    w'(t)
+    \le \alpha(t) \: \beta(t) \exp\!\bigg( \!-\!\! \int_0^t \beta(s) \dd{s} \bigg)
+\end{aligned}$$
+
+Integrating this to find $w(t)$ yields the following result:
+
+$$\begin{aligned}
+    w(t)
+    \le \int_0^t \alpha(s) \: \beta(s) \exp\!\bigg( \!-\!\! \int_0^s \beta(r) \dd{r} \bigg) \dd{s}
+\end{aligned}$$
+
+In the initial definition of $w(t)$,
+we now move the exponential to the other side,
+and rewrite it using the above inequality for $w(t)$:
+
+$$\begin{aligned}
+    \int_0^t \beta(s) \: u(s) \dd{s}
+    &= w(t) \exp\!\bigg( \int_0^t \beta(s) \dd{s} \bigg)
+    \\
+    &\le \int_0^t \alpha(s) \: \beta(s) \exp\!\bigg( \int_0^t \beta(r) \dd{r} \bigg) \exp\!\bigg( \!-\!\! \int_0^s \beta(r) \dd{r} \bigg) \dd{s}
+    \\
+    &\le \int_0^t \alpha(s) \: \beta(s) \exp\!\bigg( \int_s^t \beta(r) \dd{r} \bigg)
+\end{aligned}$$
+
+Insert this into the condition under which the Grönwall-Bellman inequality holds.
+</div>
+</div>
+
+In the special case where $\alpha(t)$ is non-decreasing with $t$,
+the inequality reduces to:
+
+$$\begin{aligned}
+    \boxed{
+        u(t)
+        \le \alpha(t) \exp\!\bigg( \int_0^t \beta(s) \dd{s} \bigg)
+    }
+\end{aligned}$$
+
+<div class="accordion">
+<input type="checkbox" id="proof-special"/>
+<label for="proof-special">Proof</label>
+<div class="hidden">
+<label for="proof-special">Proof.</label>
+Starting from the "ordinary" Grönwall-Bellman inequality,
+the fact that $\alpha(t)$ is non-decreasing tells us that
+$\alpha(s) \le \alpha(t)$ for all $s \le t$, so:
+
+$$\begin{aligned}
+    u(t)
+    &\le \alpha(t) + \int_0^t \alpha(s) \: \beta(s) \exp\!\bigg( \int_s^t \beta(r) \dd{r} \bigg) \dd{s}
+    \\
+    &\le \alpha(t) + \alpha(t) \int_0^t \beta(s) \exp\!\bigg( \int_s^t \beta(r) \dd{r} \bigg) \dd{s}
+\end{aligned}$$
+
+Now, consider the following straightfoward identity, involving the exponential:
+
+$$\begin{aligned}
+    \dv{s} \exp\!\bigg( \int_s^t \beta(r) \dd{r} \bigg)
+    &= - \beta(s) \exp\!\bigg( \int_s^t \beta(r) \dd{r} \bigg)
+\end{aligned}$$
+
+By inserting this into Grönwall-Bellman inequality, we arrive at:
+
+$$\begin{aligned}
+    u(t)
+    &\le \alpha(t) - \alpha(t) \int_0^t \dv{s} \exp\!\bigg( \int_s^t \beta(r) \dd{r} \bigg) \dd{s}
+    \\
+    &\le \alpha(t) - \alpha(t) \bigg[ \int \dv{s} \exp\!\bigg( \int_s^t \beta(r) \dd{r} \bigg) \dd{s} \bigg]_{s = 0}^{s = t}
+\end{aligned}$$
+
+Where we have converted the outer integral from definite to indefinite.
+Continuing:
+
+$$\begin{aligned}
+    u(t)
+    &\le \alpha(t) - \alpha(t) \bigg[ \exp\!\bigg( \int_s^t \beta(r) \dd{r} \bigg) \bigg]_{s = 0}^{s = t}
+    \\
+    &\le \alpha(t) - \alpha(t) \exp\!\bigg( \int_t^t \beta(r) \dd{r} \bigg) + \alpha(t) \exp\!\bigg( \int_0^t \beta(r) \dd{r} \bigg)
+    \\
+    &\le \alpha(t) - \alpha(t) + \alpha(t) \exp\!\bigg( \int_0^t \beta(r) \dd{r} \bigg)
+\end{aligned}$$
+</div>
+</div>
+
+
+
+## References
+1.  U.H. Thygesen,
+    *Lecture notes on diffusions and stochastic differential equations*,
+    2021, Polyteknisk Kompendie.