The below is a simplification of part of a proof I'm working on, in numerical analysis. It is similar to a paper that I studied some months ago, for which I got some advice here on MathOverflow.

I have non-negative sequences $A_k, B_k, C_k$ for $k=0\dots n$, a time-step $\Delta{t}$ and a positive number $p$ such that $$(1+p\Delta{t})A_n + B_n \le A_{n-1} + B_{n-1} + C_n\Delta{t} \tag{$\star$}$$ and I would like to claim that the final solution with the unknowns $A_n$ and $B_n$ is bounded by their initial solution plus a finite quantity containing the maximum value of the known quantity $C_n$ i.e. there exists a bound of the form $$A_n + B_n \le f(\Delta t) A_0 + g(\Delta t)B_0 + h(\Delta t)\max_{0 \le k \le n}C_k \tag{$\star\star$}$$ where I need to find the forms $f(\cdot)$, $g(\cdot)$ and $h(\cdot)$.

What I have tried:

  • I removed the non-negative $B_n$ on the left side of ($\star$) and got $$(1+p\Delta{t})A_n \le A_{n-1} + B_{n-1} + C_n\Delta{t} \tag{1}$$
  • Proceeding in a similar way to the linked answer, I multiplied through by $(1+p\Delta t)^{n-1}$ and set $E_n = (1+p\Delta t)^nA_n$ to get $$E_n \le E_{n-1} + B_{n-1}(1+p\Delta t)^{n-1} + C_n(1+p\Delta t)^{n-1}\Delta{t} \tag{2}$$
  • Applying recursion, $$E_n \le E_0 + \max_{0\le k \le n-1} B_k \sum_{k=0}^{n-1}(1+p\Delta t)^k + \max_{0\le k \le n} C_k \Delta{t}\sum_{k=0}^{n-1}(1+p\Delta t)^k \tag{3}$$
  • Now I divided by $(1+p\Delta t)^n$, and applied $A_0 = E_0$ $$A_n \le \frac{A_0}{(1+p\Delta t)^n} + \left(\max_{0\le k \le n-1}B_k + \max_{0\le k \le n}C_k\Delta{t}\right)\frac{1}{(1+p\Delta t)^n}\sum_{k=0}^{n-1}(1+p\Delta t)^k \tag{4}$$
  • Simplifying and bounding the below by a geometric sum to infinity, we have $$\frac{1}{(1+p\Delta t)^n}\sum_{k=0}^{n-1}(1+p\Delta t)^k = \sum_{k=1}^{n}\frac{1}{(1+p\Delta t)^k} < \frac{1}{p\Delta t} \tag{5}$$
  • Using (5) in (4) gives $$A_n \le \frac{A_0}{(1+p\Delta t)^n} + \frac{1}{p\Delta t}\max_{0\le k \le n-1}B_k + \frac{1}{p}\max_{0\le k \le n}C_k \tag{6}$$ and the problems with this approach are

(a) There is no $B_n$ term on the left since I discarded it, and (b) the $B_{k-1}$ term on the right is an unknown. Only $B_0$ can provide a useful bound here.

I think if I don't discard $B_n$ in step 1, I might find a way to use recursion and end up with $B_n$ on the left and $B_0$ on the right. I have thought about summing from $0$ to $N$ but it's unclear how to proceed. Any suggestions on how to proceed will be very much appreciated.


I eventually figured it out (see answer below), but I am not certain because @losif's answer also seems irrefutable.

  • 1
    Consider setting Dn = An + Bn, and see what you can say about the sequence D. Gerhard "Fewer Variables Make Things Simpler" Paseman, 2018.09.13. – Gerhard Paseman Sep 14 at 4:26
  • Thank you, I considered that but I hit a snag because of the $p\Delta{t}$ term that exists on the left for $A_n$ but not $B_n$. Any ideas how to approach this? I apologize if I am missing something obvious - I am a self-learner without extensive background in the field. – Cogicero Sep 14 at 11:54
  • P.S. I would like to not use an exponential bound such as Gronwall's lemma, if possible, for stability reasons. It is also possible that this can't be proved this way, and I need to start over. But I want to be sure I am not missing something. – Cogicero Sep 14 at 12:04
up vote 2 down vote accepted

$\newcommand{\de}{\delta}$

The bound ($\star\star$) that you want is impossible in general. E.g., take $A_n=0$, $C_n=1$, $B_n=n\Delta t$ for all $n$, with $\Delta t>0$. Then ($\star$) will hold, whereas ($\star\star$) will not hold for large enough $n$, for any choice of $f,g,h$.

Added: The bound ($\star\star$) will hold with $f=g=1$ and $h=b:=\frac{K+1}p$ if we additionally assume that $A_n$ dominates $B_n$ in the sense that $B_n\le KA_n$ for some real $K>0$ and all $n$. Indeed, let $\de:=\Delta t$, $S_n:=A_n+B_n$, and $M_n:=\max_{0\le k \le n}C_k$. Then, with such $f,g,h$, ($\star\star$) can be rewritten as \begin{equation} S_n\le S_0+bM_n. \tag{!!} \end{equation} On the other hand, the condition $B_n\le KA_n$ can be rewritten as $(1+p\de)A_n + B_n\ge(1+\de/b)S_n$; so, ($\star$) yields \begin{equation} (1+\de/b)S_n\le S_{n-1}+C_n\de. \end{equation} Now it is easy to to prove (!!) by induction. Indeed, for $n=0$ (!!) is trivial. Assuming (!!) holds with $n-1$ in place of $n$, we have \begin{multline} (1+\de/b)S_n\le S_{n-1}+C_n\de\le S_0+bM_{n-1}+C_n\de \le(1+\de/b)S_0+(b+\de)M_n \\ =(1+\de/b)(S_0+bM_n), \end{multline} so that (!!) indeed follows.

  • Thank you. I guess I need to start all over again, then! – Cogicero Sep 14 at 14:13
  • 1
    The bound you want will hold if $A_n$ dominates $B_n$ -- I have added details on this. – Iosif Pinelis Sep 14 at 15:21
  • Thanks for the extra context! – Cogicero Sep 14 at 17:01
  • Hello again @losif, I think I proved this eventually - could you please help me take a look? – Cogicero yesterday

Here is what I eventually did. In light of @losif's answer which I already accepted, can you please tell me what is wrong with my reasoning below? Given ($\star$), we have $$(1+pΔt)A_1+B_1 ≤ A_0 + B_0 + C_1\Delta{t} \tag{1}$$ and $$(1+pΔt)A_2+B_2 ≤ A_1 + B_1 + C_2\Delta{t} \tag{2}$$ Adding a non-negative $p\Delta{t}A_1$ to the right side of (2), we get $$(1+pΔt)A_2+B_2 ≤ (1+p\Delta{t})A_1 + B_1 + C_2\Delta{t} \tag{3}$$ and substituting (1) gives $$(1+pΔt)A_2+B_2 ≤ A_0 + B_0 + C_1\Delta{t} + C_2\Delta{t} \tag{4}$$ Continuing in this way, we will obtain $$(1+pΔt)A_n+B_n ≤ A_0 + B_0 + \sum_{k=1}^{n} C_k\Delta{t} \tag{5}$$ i.e. $$A_n + \frac{1}{1+p\Delta{t}}B_n \le \frac{1}{1+p\Delta{t}}\left(A_0 + B_0 + n\Delta{t}\max_{1\le k \le n}C_k \right)$$ which means that $$\min\left\{1,\frac{1}{1+p\Delta{t}}\right\}(A_n + B_n) \le \frac{1}{1+p\Delta{t}}\left(A_0 + B_0 + n\Delta{t}\max_{1\le k \le n}C_k \right)$$ and noting that $1 > \frac{1}{1+p\Delta{t}}$ for all $p > 0$ and $\Delta{t} >0$ leaves $$\frac{1}{1+p\Delta{t}}(A_n + B_n) \le \frac{1}{1+p\Delta{t}}\left(A_0 + B_0 + n\Delta{t}\max_{1\le k \le n}C_k \right)$$ i.e. $$ A_n + B_n \le A_0 + B_0 + n\Delta{t}\max_{1\le k \le n}C_k $$ which I set out to prove (except that the index of the max on the right, runs from 1, not 0), and this is okay in my case.

  • Yes, with the sum instead of the max and, therefore, with the extra factor $n$ before the max, there is no problem; the problem was only with the max per se. – Iosif Pinelis yesterday

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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