---
title: "Grönwall-Bellman inequality"
sort_title: "Gronwall-Bellman inequality" # sic
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" markdown="1">
<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" markdown="1">
<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" markdown="1">
<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.