Confusion about Big O-Notation in convergence proof for differential algebraic equations

Question

I understand almost all of this proof. But the part I can't find an explanation for is how they get the result for $r$ with the sums over the $\mathcal{O}(h^{\nu})$ all the way at the end of the proof. Can someone please explain this?

Page 1

Page 2

My problem is the following:

They define the global error as $\triangle z_{n+1} = \rho \triangle z_n + \delta_{n+1}$ with $\delta_{n+1} = \mathcal{O}{(h^{\min\lbrace p , q+1 \rbrace})}$ and $\rho = 1 - b^{T}A^{-1}\mathbb{1}$ (where $\rho$ is the stability function of the runge kutta method) then after repeated use of this formula they get:

$$\triangle z_{n} = \sum \limits_{i=1}^{n} \rho^{n-i} \delta_i$$

and from this alone they follow

$1) \triangle z_{n} = \mathcal{O}{(h^{\min\lbrace p , q+1 \rbrace})} \mbox{ for } -1 \leq \rho < 1$

$2) \triangle z_{n} = \mathcal{O}{(h^{\min\lbrace p-1 , q \rbrace})} \mbox{ for } \rho = 1$

$3) \mbox{The solution diverges} \mbox{ for } \rho > 1$

And I don't understand how they get these answers.

Answer 1

Note that $$|\Delta z_n| \le C h^{\min\{p, q+1\}} \left|\sum_{i=1}^n \rho^{n-i}\right|.$$

• If $|\rho| < 1$, then the sum can be bounded by the geometric series $1 + \rho + \rho^2 + \cdots = \frac{1}{1-\rho}$.
• If $\rho = -1$, then the sum can be bounded by $1$.
• If $\rho = 1$, then the sum equals $n \le C/h$ (the relationship between $n$ and $h$ is an assumption stated in the theorem).