From 6ce0bb9a8f9fd7d169cbb414a9537d68c5290aae Mon Sep 17 00:00:00 2001
From: Prefetch
Date: Fri, 14 Oct 2022 23:25:28 +0200
Subject: Initial commit after migration from Hugo
---
.../concept/gronwall-bellman-inequality/index.md | 204 +++++++++++++++++++++
1 file changed, 204 insertions(+)
create mode 100644 source/know/concept/gronwall-bellman-inequality/index.md
(limited to 'source/know/concept/gronwall-bellman-inequality')
diff --git a/source/know/concept/gronwall-bellman-inequality/index.md b/source/know/concept/gronwall-bellman-inequality/index.md
new file mode 100644
index 0000000..5fd9f38
--- /dev/null
+++ b/source/know/concept/gronwall-bellman-inequality/index.md
@@ -0,0 +1,204 @@
+---
+title: "Grönwall-Bellman inequality"
+date: 2021-11-07
+categories:
+- Mathematics
+layout: "concept"
+---
+
+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}$$
+
+
+
+
+
+
+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.
+
+
+
+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}$$
+
+
+
+
+
+
+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.
+
+
+
+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}$$
+
+
+
+
+
+
+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}$$
+