---
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}$$

<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.