I'm studying a paper (see citation below) on numerical analysis, and came across this estimate. I am unable to figure out what was done in the final step, and I am not certain if this was just a typo in the paper.

Preliminary information: $\Delta{t}$ is the time step, $n$ is the iteration count from $0$ to final iteration $(N+1)$ such that $T=N\Delta{t}$ is the final time at $n=N+1$, $\vec{u}$ is a solution vector, $\vec{f}$ is a vector of forcing functions, and $E_k$ is the energy at iteration $n = k$. We also have various positive constants $C_1, C_2, C_3, C_a$.

Here is the estimate in the text:

$E_n + \frac{C_a\Delta{t}^2(C_1+C_2)}{1+(C_1+C_2)\Delta{t}}\|\nabla\vec{u}^{n+1}\|^2+\frac{C_a\Delta{t}^2(C_1+C_2)}{3(1+(C_1+C_2)\Delta{t})}\|\nabla\vec{u}^n\|^2$

$\le C_3\|\vec{f}^{n+1}\|^2\Delta{t} + (1 + (C_1 + C_2)\Delta{t})E_{n-1}$

$\le e^{(C_1+C_2)T}E_0 + \frac{C_3}{C_1+C_2}e^{(C_1+C_2)T} \max\limits_{n}\|\vec{f}^{n+1}\|^2$

Paper: Chen, Wenbin; Gunzburger, Max; Sun, Dong; Wang, Xiaoming, Efficient and long-time accurate second-order methods for the Stokes-Darcy system, SIAM J. Numer. Anal. 51, No. 5, 2563-2584 (2013). ZBL1282.76094.


Here is my attempt at what happened at the last step, before the final inequality:

EDIT: Most recent attempt, just as the answer below came in:

For clarity, take $X_n = \frac{C_a\Delta{t}^2(C_1+C_2)}{1+(C_1+C_2)\Delta{t}}\|\nabla\vec{u}^{n+1}\|^2+\frac{C_a\Delta{t}^2(C_1+C_2)}{3(1+(C_1+C_2)\Delta{t})}\|\nabla\vec{u}^n\|^2$

I will use following prelimary estimates $\forall\ x,n\in\mathbb{R}_+$. The second employs the first. $(1+x)^n \le e^{nx}$ and $\sum_{k=1}^n(1+x)^k \le n(1+x)^n \le n e^{nx}$

So the estimate was $$E_n + X_n \le C_3\Delta{t}\|\vec{f}^{n+1}\|^2+(1 +\ (C_1+C_2)\Delta{t})E_{n-1}$$ $$\le C_3\Delta{t}\left(\frac{1+(C_1+C_2)\Delta{t}}{(C_1+C_2)\Delta{t}}\right)\|\vec{f}^{n+1}\|^2+(1 +\ (C_1+C_2)\Delta{t})E_{n-1}$$ i.e. $$E_n + X_n \le \left(1+(C_1+C_2)\Delta{t}\right)\left(\frac{C_3}{C_1+C_2}\|\vec{f}^{n+1}\|^2+E_{n-1}\right) \tag{1}$$ Since $X_n \ge 0$ we also have $$E_n \le \left(1+(C_1+C_2)\Delta{t}\right)\left(\frac{C_3}{C_1+C_2}\|\vec{f}^{n+1}\|^2+E_{n-1}\right) \tag{2}$$ Using (2) in (1), $$E_n + X_n \le \Bigl(1+(C_1+C_2)\Delta{t}\Bigr)$$ $$\cdot\left(\frac{C_3}{C_1+C_2}\|\vec{f}^{n+1}\|^2 + \Bigl(1+(C_1+C_2)\Delta{t}\Bigr)\left(\frac{C_3}{C_1+C_2}\|\vec{f}^{n}\|^2+E_{n-2}\right)\right)$$ Repeating the process $n-1$ times, $$E_n + X_n \le \frac{C_3}{C_1+C_2}\sum_{k=1}^n \|\vec{f}^{k+1}\|^2 \Bigl(1+(C_1+C_2)\Delta{t}\Bigr)^k+ \Bigl(1+(C_1+C_2)\Delta{t}\Bigr)^n E_0$$ i.e. $$E_n + X_n \le \frac{C_3}{C_1+C_2}\max_n\|\vec{f}^{n+1}\|^2\sum_{k=1}^n \Bigl(1+(C_1+C_2)\Delta{t}\Bigr)^k+ \Bigl(1+(C_1+C_2)\Delta{t}\Bigr)^n E_0$$ Using the first preliminary estimate, $$E_n + X_n \le \frac{C_3}{C_1+C_2}\max_n\|\vec{f}^{n+1}\|^2 n \Bigl(1+(C_1+C_2)\Delta{t}\Bigr)^n+ \Bigl(1+(C_1+C_2)\Delta{t}\Bigr)^n E_0$$ And using the second preliminary estimate, $$E_n + X_n \le \frac{nC_3}{C_1+C_2}\max_n\|\vec{f}^{n+1}\|^2 e^{(C_1+C_2)T}+ e^{(C_1+C_2)T} E_0$$

There is a certain $n$ multiplying the first term, which is not present in the paper.

  • $\begingroup$ where in the cited paper did you find that inequality? $\endgroup$ – Carlo Beenakker Feb 5 '18 at 13:11
  • $\begingroup$ Hi Carlo, it is at the bottom of page 7. I have also tried working at this, but my result had an extra $n$ multiplying the $\|f^{n+1}\|^2$ max norm. Thanks $\endgroup$ – Cogicero Feb 5 '18 at 17:48

It looks to me like a discrete version of Gronwall's inequality.

If you have a sequence of numbers satisfying

$$ E_n \leq k \Delta t + (1 + \ell \Delta t) E_{n-1} $$

You can rewrite

$$ A_n = (1 + \ell \Delta t)^{-n} E_n $$

to get

$$ A_n \leq \frac{k \Delta t}{(1 + \ell \Delta t)^n} + A_{n-1} $$

which implies

$$ A_n \leq A_0 + k\Delta t \sum_{m = 1}^n \frac{1}{(1 + \ell \Delta t)^m} $$

The sum is a geometric series bounded by $\dfrac{1}{\ell \Delta t}$ (see comment below for the computation)

So you conclude

$$ A_n \leq A_0 + \frac{k}{\ell} $$

This gives

$$ E_n \leq (1 + \ell \Delta t)^n ( E_0 + \frac{k}{\ell} ) $$

which is exactly what is claimed, using that in the above derivation you can use

$$ k = C_3 \max \| f^{n+1} \|^2 $$


$$ \ell = C_1 + C_2 $$

  • $\begingroup$ Thanks! I have updated the answer with my attempt. I am trying to use a similar method for a more difficult problem, so I want to ensure I understand all that happened here. Please see my updated question - including my attempt. What is wrong with the method I used? As I can't seem to obtain this answer from the paper. $\endgroup$ – Cogicero Feb 7 '18 at 18:00
  • $\begingroup$ For your answer above, I think I would need a sufficiently large value of $n$ to ensure that the geometric series is bounded as described. Is this so? It makes me uncertain, because in the problem, $n$ doesn't need to be a large value. Please let me know what you think. $\endgroup$ – Cogicero Feb 7 '18 at 18:05
  • 1
    $\begingroup$ (Re: second comment) No, you have that $$ \sum_{m = 1}^n \frac{1}{(1+x)^m} \leq \sum_{m = 1}^\infty \frac{1}{(1+x)^m} = \frac{1}{1+x} \frac{1}{1 - 1/(1+x)} = 1/x $$ independently of $n$. $\endgroup$ – Willie Wong Feb 7 '18 at 18:10
  • 1
    $\begingroup$ (Re your attempt) in the large $n$ limit the estimate $$ \sum_{k = 1}^n (1+x)^k \leq n(1+x)^n $$ is not sharp. The geometric progression can be summed to give $$ \sum_{k = 1}^n (1+x)^k = \frac{1}{x} [ (1+x)^{n+1} - (1+x) ] \leq \frac{1+x}{x} (1+x)^{n} $$ You see that when $n \gg \frac{1+x}{x}$ the upper bound by $n (1+x)^n$ would be too generous. $\endgroup$ – Willie Wong Feb 7 '18 at 18:18
  • 1
    $\begingroup$ (Re your reply) No, smallness of $x$ is not required. For the convergence of the geometric series you only need $x \geq 0$. I rewrote the argument concerning your attempt to show you that the issue is mainly when the number of iterations $n$ is much larger than the size of the inverse time-step that you begin to lose stuff. $\endgroup$ – Willie Wong Feb 7 '18 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.