Math 2.0

Real functions Lemma

Discrete Grönwall inequality

Builds on Grönwall's inequality

Statement

Let (uk)k≥0(u_k)_{k \ge 0} be a sequence of real numbers with u0≥0u_0 \ge 0, and let (bk)k≥0(b_k)_{k \ge 0} and (ck)k≥0(c_k)_{k \ge 0} be sequences of non-negative real numbers. Assume that uk+1≤(1+ck) uk+bku_{k+1} \le (1 + c_k)\, u_k + b_k for each k≥0k \ge 0. Then for each n≥0n \ge 0, un≤(u0+∑k=0n−1bk)exp⁡(∑k=0n−1ck).u_n \le \left( u_0 + \sum_{k=0}^{n-1} b_k \right) \exp\left( \sum_{k=0}^{n-1} c_k \right).

Remarks

Proof idea: by induction, un≤u0∏k<n(1+ck)+∑k<nbk∏k<j<n(1+cj)u_n \le u_0 \prod_{k<n} (1 + c_k) + \sum_{k<n} b_k \prod_{k<j<n} (1 + c_j). Then use 1+c≤ec1 + c \le e^{c}. It is the discrete analogue of Grönwall's inequality, with sums in place of integrals. It bounds the growth of errors in numerical methods such as the Euler method.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Interval concept
  2. Grönwall's inequality statement
  3. Discrete Grönwall inequality statement

Where this leads

8 pages build on this one.

Further reading

  1. Web https://www.ceremade.dauphine.fr/~mischler/Enseignements/M2evol2018/chap0.pdf, Lemma 5.1 and (5.4). S. Mischler, lecture notes "Chapter 0, on the Gronwall lemma", Section 5. Lemma 5.1 is the product form of the remark. With 1 + c <= e^c it gives the statement, and (5.4) is the case of a constant c_k.
  2. Web https://en.wikipedia.org/wiki/Gr%C3%B6nwall%27s_inequality, lead section
About this page
Tag0NTM3J5MFE
URIm2://0NTM3J5MFE
Kindstatement, lemma
WritingW0 stub
MSC26D15, 39A22
StatusThis copy of the site has no build data. Run m2 status 0NTM3J5MFE.
UsesGrönwall's inequality

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by