View source for Grönwall's inequality

{{Short description|Mathematical theorem}}
In [[mathematics]], '''Grönwall's inequality''' (also called '''Grönwall's lemma''' or the '''Grönwall–Bellman inequality''') allows one to bound a function that is known to satisfy a certain [[differential inequality|differential]] or [[integral inequality]] by the solution of the corresponding differential or [[integral equation]]. There are two forms of the lemma, a differential form and an integral form. For the latter there are several variants.

Grönwall's inequality is an important tool to obtain various estimates in the theory of [[ordinary differential equation|ordinary]] and [[stochastic differential equation]]s. In particular, it provides a [[comparison theorem]] that can be used to prove [[uniqueness quantification|uniqueness]] of a solution to the [[initial value problem]]; see the [[Picard–Lindelöf theorem]].

It is named for [[Thomas Hakon Grönwall]] (1877–1932). Grönwall is the Swedish spelling of his name, but he spelled his name as Gronwall in his scientific publications after emigrating to the United States.

The inequality was first proven by Grönwall in 1919 (the integral form below with {{math|''α''}} and {{math|''β''}} being constants).<ref name="gronwall">{{Citation | last = Gronwall | first = Thomas H. | author-link = Thomas Hakon Grönwall | title = Note on the derivatives with respect to a parameter of the solutions of a system of differential equations | journal = [[Annals of Mathematics|Ann. of Math.]] | volume = 20 | issue = 2 | pages = 292–296 | year = 1919 | doi = 10.2307/1967124 | jstor = 1967124 | mr = 1502565 | jfm = 47.0399.02}}</ref>
[[Richard Bellman]] proved a slightly more general integral form in 1943.<ref>{{Citation | last = Bellman | first = Richard | author-link = Richard Bellman | title = The stability of solutions of linear differential equations | journal = [[Duke Mathematical Journal|Duke Math. J.]] | volume = 10 | issue =  4 | pages = 643–647 | year = 1943 | url = http://projecteuclid.org/euclid.dmj/1077472225 | mr = 0009408 | zbl = 0061.18502 | doi=10.1215/s0012-7094-43-01059-2}}</ref>

A nonlinear generalization of the Grönwall–Bellman inequality is known as [[Bihari–LaSalle inequality]]. Other variants and generalizations can be found in Pachpatte, B.G. (1998).<ref>{{cite book|last1=Pachpatte|first1=B.G.|title=Inequalities for differential and integral equations|date=1998|publisher=Academic Press|location=San Diego|isbn=9780080534640}}</ref>

== Differential form ==
Let <math>I</math> denote an [[Interval (mathematics)|interval]] of the [[real line]] of the form <math>[a, \infty)</math> or <math>[a, b]</math> or <math>[a, b)</math> with <math>a < b</math>. Let <math>\beta</math> and <math>u</math> be real-valued [[continuous functions]] defined on <math>I</math>. If&nbsp;<math>u</math> is [[derivative|differentiable]] in the [[Interior (topology)|interior]] <math>I^\circ</math> of <math>I</math> (the interval <math>I</math> without the end points <math>a</math> and possibly <math>b</math>) and satisfies the differential inequality

:<math>u'(t) \le \beta(t)\,u(t),\qquad t\in I^\circ,</math>

then <math>u</math> is bounded by the solution of the corresponding differential ''equation'' <math>v'(t) = \beta(t) \, v(t)</math>:

:<math>u(t) \le u(a) \exp\biggl(\int_a^t \beta(s)\, \mathrm{d} s\biggr)</math>

for all <math>t \in I</math>.

'''Remark:''' There are no assumptions on the signs of the functions <math>\beta</math> and&nbsp;<math>u</math>.

=== Proof ===

Define the function

:<math>v(t) =  \exp\biggl(\int_a^t \beta(s)\, \mathrm{d} s\biggr),\qquad t\in I.</math>

Note that <math>v</math> satisfies

:<math>v'(t) = \beta(t)\,v(t),\qquad t\in I^\circ,</math>

with <math>v(a) = 1</math> and <math>v(t) > 0</math> for all <math>t \in I</math>. By the [[quotient rule]]

:<math>\frac{d}{dt}\frac{u(t)}{v(t)} = \frac{u'(t)\,v(t)-v'(t)\,u(t)}{v^2(t)} = \frac{u'(t)\,v(t) - \beta(t)\,v(t)\,u(t)}{v^2(t)} \le 0,\qquad t\in I^\circ,</math>

Thus the derivative of the function <math>u(t)/v(t)</math> is non-positive and the function is bounded above by its value at the initial point <math>a</math> of the interval <math>I</math>:

:<math>\frac{u(t)}{v(t)}\le \frac{u(a)}{v(a)}=u(a),\qquad t\in I,</math>

which is Grönwall's inequality.

== Integral form for continuous functions ==
Let {{math|''I''}} denote an [[Interval (mathematics)|interval]] of the [[real line]] of the form {{closed-open|''a'', ∞}} or {{closed-closed|''a'', ''b''}} or {{closed-open|''a'', ''b''}} with {{math|''a'' < ''b''}}. Let {{math|''α''}}, {{math|''β''}} and {{math|''u''}} be real-valued functions defined on&nbsp;{{math|''I''}}. Assume that {{math|''β''}} and {{math|''u''}} are continuous and that the negative part of {{math|''α''}} is integrable on every closed and bounded subinterval of&nbsp;{{math|''I''}}.
* (a) If&nbsp;{{math|''β''}} is non-negative and if {{math|''u''}} satisfies the integral inequality
::<math>u(t) \le \alpha(t) + \int_a^t \beta(s) u(s)\,\mathrm{d}s,\qquad \forall t\in I,</math>
:then
::<math> u(t) \le \alpha(t) + \int_a^t\alpha(s)\beta(s)\exp\biggl(\int_s^t\beta(r)\,\mathrm{d}r\biggr)\mathrm{d}s,\qquad t\in I.</math>
* (b) If, in addition, the function {{math|''α''}} is non-decreasing, then

::<math>u(t) \le \alpha(t)\exp\biggl(\int_a^t\beta(s)\,\mathrm{d}s\biggr),\qquad t\in I.</math>

'''Remarks:'''
* There are no assumptions on the signs of the functions {{math|''α''}} and&nbsp;{{math|''u''}}.
* Compared to the differential form, differentiability of {{math|''u''}} is not needed for the integral form.
* For a version of Grönwall's inequality which doesn't need continuity of {{math|''β''}} and {{math|''u''}}, see the version in the next section.

=== Proof ===
(a) Define

:<math>v(s) = \exp\biggl({-}\int_a^s\beta(r)\,\mathrm{d}r\biggr)\int_a^s\beta(r)u(r)\,\mathrm{d}r,\qquad s\in I.</math>

Using the [[product rule]], the [[chain rule]], the derivative of the [[exponential function]] and the [[fundamental theorem of calculus]], we obtain for the derivative

:<math>v'(s) = \biggl(\underbrace{u(s)-\int_a^s\beta(r)u(r)\,\mathrm{d}r}_{\le\,\alpha(s)}\biggr)\beta(s)\exp\biggl({-}\int_a^s\beta(r)\mathrm{d}r\biggr),
\qquad s\in I,</math>

where we used the assumed integral inequality for the upper estimate. Since {{math|''β''}} and the exponential are non-negative, this gives an upper estimate for the derivative of <math>v(s)</math>. Since <math>v(a)=0</math>, integration of this inequality from {{math|''a''}} to {{math|''t''}} gives

:<math>v(t) \le\int_a^t\alpha(s)\beta(s)\exp\biggl({-}\int_a^s\beta(r)\,\mathrm{d}r\biggr)\mathrm{d}s.</math>

Using the definition of <math>v(t)</math> from the first step, and then this inequality and the property <math>e^ae^b=e^{a+b}</math>, we obtain

:<math>\begin{align}\int_a^t\beta(s)u(s)\,\mathrm{d}s
&=\exp\biggl(\int_a^t\beta(r)\,\mathrm{d}r\biggr)v(t)\\
&\le\int_a^t\alpha(s)\beta(s)\exp\biggl(\underbrace{\int_a^t\beta(r)\,\mathrm{d}r-\int_a^s\beta(r)\,\mathrm{d}r}_{=\,\int_s^t\beta(r)\,\mathrm{d}r}\biggr)\mathrm{d}s.
\end{align}</math>

Substituting this result into the assumed integral inequality gives Grönwall's inequality.

(b) If the function {{math|''α''}} is non-decreasing, then part (a), the fact {{math|''α''(''s'') ≤ ''α''(''t'')}}, and the fundamental theorem of calculus imply that

:<math>\begin{align}u(t)&
\le\alpha(t)+\alpha(t)\int_a^t\beta(s)\exp\left(\int_s^t\beta(r)dr\right)ds\\
&\le\alpha(t)+\alpha(t)\biggl({-}\exp\biggl(\int_s^t\beta(r)\,\mathrm{d}r\biggr)\biggr|^{s=t}_{s=a}\biggr)\\
&=\alpha(t)\exp\biggl(\int_a^t\beta(r)\,\mathrm{d}r\biggr),\qquad t\in I.\end{align}</math>

== Integral form with locally finite measures ==
Let {{math|''I''}} denote an [[Interval (mathematics)|interval]] of the [[real line]] of the form {{closed-open|''a'', ∞}} or {{closed-closed|''a'', ''b''}} or {{closed-open|''a'', ''b''}} with {{math|''a'' < ''b''}}. Let {{math|''α''}} and {{math|''u''}} be [[measurable function]]s defined on&nbsp;{{math|''I''}} and let {{math|''μ''}} be a continuous non-negative measure on the [[Borel σ-algebra]] of {{math|''I''}} satisfying {{math|''μ''(<nowiki>[</nowiki>''a'', ''t''<nowiki>]</nowiki>) < ∞}} for all {{math|''t'' ∈ ''I''}} (this is certainly satisfied when {{math|''μ''}} is a [[locally finite measure]]). Assume that {{math|''u''}} is integrable with respect to {{math|''μ''}} in the sense that

:<math>\int_{[a,t)}|u(s)|\,\mu(\mathrm{d}s)<\infty,\qquad t\in I,</math>

and that {{math|''u''}} satisfies the integral inequality

:<math>u(t) \le \alpha(t) + \int_{[a,t)} u(s)\,\mu(\mathrm{d}s),\qquad t\in I.</math>

If, in addition,
* the function {{math|''α''}} is non-negative or
* the function {{math|''t'' {{mapsto}} ''μ''(<nowiki>[</nowiki>''a'', ''t''<nowiki>]</nowiki>)}} is continuous for {{math|''t'' ∈ ''I''}} and the function {{math|''α''}} is integrable with respect to {{math|''μ''}} in the sense that

:: <math>\int_{[a,t)}|\alpha(s)|\,\mu(\mathrm{d}s)<\infty,\qquad t\in I,</math>

then {{math|''u''}} satisfies Grönwall's inequality

:<math>u(t) \le \alpha(t) + \int_{[a,t)}\alpha(s)\exp\bigl(\mu(I_{s,t})\bigr)\,\mu(\mathrm{d}s)</math>

for all {{math|''t'' ∈ ''I''}}, where {{math|''I<sub>s,t</sub>''}} denotes to open interval {{open-open|''s'', ''t''}}.

===Remarks===
* There are no continuity assumptions on the functions  {{math|''α''}} and {{math|''u''}}.
* The integral in Grönwall's inequality is allowed to give the value infinity.{{clarify|reason=The integral in Gronwall is easily bounded by the L^1(\mu) norm of alpha and the measure of I_{s,t}, because we have assumed mu is locally finite.|date=November 2023}}
* If {{math|''α''}} is the zero function and {{math|''u''}} is non-negative, then Grönwall's inequality implies that {{math|''u''}} is the zero function.
* The integrability of {{math|''u''}} with respect to {{math|''μ''}} is essential for the result. For a [[counterexample]], let {{math|''μ''}} denote [[Lebesgue measure]] on the [[unit interval]] {{closed-closed|0,&thinsp;1}}, define {{math|''u''(0) {{=}} 0}} and {{math|''u''(''t'') {{=}} 1/''t''}} for {{math|''t'' ∈ }}{{open-closed|0, 1}}, and let {{math|''α''}} be the zero function.
* The version given in the textbook by S.&nbsp;Ethier and T.&nbsp;Kurtz.<ref>{{Citation | last1 = Ethier | first1 = Steward N. | last2 = Kurtz | first2 = Thomas G. | title = Markov Processes, Characterization and Convergence | place = New York | publisher = [[John Wiley & Sons]] | year = 1986 | page = 498 | isbn = 0-471-08186-8 | mr = 0838085 | zbl = 0592.60049}}</ref> makes the stronger assumptions that {{math|''α''}} is a non-negative constant and {{math|''u''}} is bounded on bounded intervals, but doesn't assume that the measure {{math|''μ''}} is locally finite. Compared to the one given below, their proof does not discuss the behaviour of the remainder {{math|''R<sub>n</sub>''(''t'')}}.

===Special cases===
* If the measure {{math|''μ''}} has a density {{math|''β''}} with respect to  Lebesgue measure, then Grönwall's inequality can be rewritten as

:: <math>u(t) \le \alpha(t) + \int_a^t \alpha(s)\beta(s)\exp\biggl(\int_s^t\beta(r)\,\mathrm{d}r\biggr)\,\mathrm{d}s,\qquad t\in I.</math>
* If the function {{math|''α''}} is non-negative and the density {{math|''β''}} of {{math|''μ''}} is bounded by a constant {{math|''c''}}, then

:: <math>u(t) \le \alpha(t) + c\int_a^t \alpha(s)\exp\bigl(c(t-s)\bigr)\,\mathrm{d}s,\qquad t\in I.</math>
* If, in addition, the non-negative function {{math|''α''}} is non-decreasing, then

:: <math>u(t) \le \alpha(t) + c\alpha(t)\int_a^t \exp\bigl(c(t-s)\bigr)\,\mathrm{d}s
=\alpha(t)\exp(c(t-a)),\qquad t\in I.</math>

=== Outline of proof ===
The proof is divided into three steps. The idea is to substitute the assumed integral inequality into itself {{math|''n''}} times. This is done in Claim&nbsp;1 using mathematical induction. In Claim&nbsp;2 we rewrite the measure of a simplex in a convenient form, using the permutation invariance of product measures. In the third step we pass to the limit {{math|''n''}} to infinity to derive the desired variant of Grönwall's inequality.

=== Detailed proof ===

====Claim 1: Iterating the inequality====
For every natural number {{math|''n''}} including zero,

:<math>u(t) \le \alpha(t) + \int_{[a,t)} \alpha(s) \sum_{k=0}^{n-1} \mu^{\otimes k}(A_k(s,t))\,\mu(\mathrm{d}s) + R_n(t)</math>

with remainder

:<math>R_n(t) :=\int_{[a,t)}u(s)\mu^{\otimes n}(A_n(s,t))\,\mu(\mathrm{d}s),\qquad t\in I,</math>

where

:<math>A_n(s,t)=\{(s_1,\ldots,s_n)\in I_{s,t}^n\mid s_1<s_2<\cdots<s_n\},\qquad n\ge1,</math>

is an {{math|''n''}}-dimensional [[simplex]] and

:<math>\mu^{\otimes 0}(A_0(s,t)):=1.</math>

====Proof of Claim 1====
We use [[mathematical induction]]. For {{math|''n'' {{=}} 0}} this is just the assumed integral inequality, because the [[empty sum]] is defined as zero.

Induction step from {{math|''n''}} to {{math|''n'' + 1}}:
Inserting the assumed integral inequality for the function {{math|''u''}} into the remainder gives

:<math>R_n(t)\le\int_{[a,t)} \alpha(s) \mu^{\otimes n}(A_n(s,t))\,\mu(\mathrm{d}s) +\tilde R_n(t)</math>

with

:<math>\tilde R_n(t):=\int_{[a,t)} \biggl(\int_{[a,q)} u(s)\,\mu(\mathrm{d}s)\biggr)\mu^{\otimes n}(A_n(q,t))\,\mu(\mathrm{d}q),\qquad t\in I.</math>

Using the [[Fubini's theorem|Fubini–Tonelli theorem]] to interchange the two integrals, we obtain

:<math>\tilde R_n(t)
=\int_{[a,t)} u(s)\underbrace{\int_{(s,t)} \mu^{\otimes n}(A_n(q,t))\,\mu(\mathrm{d}q)}_{=\,\mu^{\otimes n+1}(A_{n+1}(s,t))}\,\mu(\mathrm{d}s)
=R_{n+1}(t),\qquad t\in I.</math>

Hence [[#Claim 1: Iterating the inequality|Claim 1]] is proved for {{math|''n'' + 1}}.

====Claim 2: Measure of the simplex====
For every natural number {{math|''n''}} including zero and all {{math|''s'' < ''t''}} in {{math|''I''}}

:<math>\mu^{\otimes n}(A_n(s,t))\le\frac{\bigl(\mu(I_{s,t})\bigr)^n}{n!}</math>

with equality in case {{math|''t'' {{mapsto}} ''μ''(<nowiki>[</nowiki>''a'', ''t''<nowiki>]</nowiki>)}} is continuous for {{math|''t'' ∈ ''I''}}.

====Proof of Claim 2====
For {{math|''n'' {{=}} 0}}, the claim is true by our definitions. Therefore, consider {{math|''n'' ≥ 1}} in the following.

Let {{math|''S<sub>n</sub>''}} denote the set of all [[permutation]]s of the indices in {{math|{1, 2, . . . , ''n''}}}. For every permutation {{math|''σ'' ∈ ''S<sub>n</sub>''}} define

:<math>A_{n,\sigma}(s,t)=\{(s_1,\ldots,s_n)\in I_{s,t}^n\mid s_{\sigma(1)}<s_{\sigma(2)}<\cdots<s_{\sigma(n)}\}.</math>

These sets are disjoint for different permutations and

:<math>\bigcup_{\sigma\in S_n}A_{n,\sigma}(s,t)\subset I_{s,t}^n.</math>

Therefore,

:<math>\sum_{\sigma\in S_n} \mu^{\otimes n}(A_{n,\sigma}(s,t))
\le\mu^{\otimes n}\bigl(I_{s,t}^n\bigr)=\bigl(\mu(I_{s,t})\bigr)^n.</math>

Since they all have the same measure with respect to the {{math|''n''}}-fold product of {{math|''μ''}}, and since there are {{math|''n''!}} permutations in&nbsp;{{math|''S<sub>n</sub>''}}, the claimed inequality follows.

Assume now that {{math|''t'' {{mapsto}} ''μ''(<nowiki>[</nowiki>''a'', ''t''<nowiki>]</nowiki>)}} is continuous for {{math|''t'' ∈ ''I''}}. Then, for different indices {{math|''i'', ''j'' ∈ {1, 2, . . . , ''n''}}}, the set

:<math>\{(s_1,\ldots,s_n)\in I_{s,t}^n\mid s_i=s_j\}</math>

is contained in a [[hyperplane]], hence by an application of [[Fubini's theorem]] its measure with respect to the {{math|''n''}}-fold product of {{math|''μ''}} is zero. Since

:<math>I_{s,t}^n\subset\bigcup_{\sigma\in S_n}A_{n,\sigma}(s,t) \cup \bigcup_{1\le i<j\le n}\{(s_1,\ldots,s_n)\in I_{s,t}^n\mid s_i=s_j\},</math>

the claimed equality follows.

====Proof of Grönwall's inequality====
For every natural number {{math|''n''}}, [[#Claim 2: Measure of the simplex|Claim&nbsp;2]] implies for the remainder of [[#Claim 1: Iterating the inequality|Claim&nbsp;1]] that

:<math>|R_n(t)| \le \frac{\bigl(\mu(I_{a,t})\bigr)^n}{n!} \int_{[a,t)} |u(s)|\,\mu(\mathrm{d}s),\qquad t\in I.</math>

By assumption we have {{math|''μ''(''I''<sub>''a'',''t''</sub>) < ∞}}. Hence, the integrability assumption on {{math|''u''}} implies that

:<math>\lim_{n\to\infty}R_n(t)=0,\qquad t\in I.</math>

[[#Claim 2: Measure of the simplex|Claim&nbsp;2]] and the [[Characterizations of the exponential function|series representation]] of the exponential function imply the estimate

:<math>\sum_{k=0}^{n-1} \mu^{\otimes k}(A_k(s,t))
\le\sum_{k=0}^{n-1} \frac{\bigl(\mu(I_{s,t})\bigr)^k}{k!}
\le\exp\bigl(\mu(I_{s,t})\bigr)</math>

for all {{math|''s'' < ''t''}} in&nbsp;{{math|''I''}}. If the function&nbsp;{{math|''α''}} is non-negative, then it suffices to insert these results into [[#Claim 1: Iterating the inequality|Claim&nbsp;1]] to derive the above variant of Grönwall's inequality for the function&nbsp;{{math|''u''}}.

In case {{math|''t'' {{mapsto}} ''μ''(<nowiki>[</nowiki>''a'', ''t''<nowiki>]</nowiki>)}} is continuous for {{math|''t'' ∈ ''I''}}, [[#Claim 2: Measure of the simplex|Claim&nbsp;2]] gives

:<math>\sum_{k=0}^{n-1} \mu^{\otimes k}(A_k(s,t))
=\sum_{k=0}^{n-1} \frac{\bigl(\mu(I_{s,t})\bigr)^k}{k!}
\to\exp\bigl(\mu(I_{s,t})\bigr)\qquad\text{as }n\to\infty</math>

and the integrability of the function {{math|''α''}} permits to use the [[dominated convergence theorem]] to derive Grönwall's inequality.

==See also==
* [[Stochastic Gronwall inequality]]
* [[Logarithmic norm#Original definition|Logarithmic norm]], for a version of Gronwall's lemma that gives upper and lower bounds to the norm of the state transition matrix.
* [[Halanay Inequality|Halanay inequality]]. A similar inequality to Gronwall's lemma that is used for differential equations with delay.

==References==
<references />

{{PlanetMath attribution|id=3901|title=Gronwall's lemma}}

{{DEFAULTSORT:Gronwall's inequality}}
[[Category:Lemmas in analysis]]
[[Category:Ordinary differential equations]]
[[Category:Stochastic differential equations]]
[[Category:Articles containing proofs]]
[[Category:Probabilistic inequalities]]