diff options
Diffstat (limited to 'content/know/concept/gronwall-bellman-inequality/index.pdc')
| -rw-r--r-- | content/know/concept/gronwall-bellman-inequality/index.pdc | 210 |
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. |