Rate of Convergence vs Tolerance

Question

I have this confusion that if I know that a numerical method has a rate of convergence equal to $O(c^k)$ (see this link, page no .8), then how to find the number of iterations to reach a tolerance of $\epsilon$? ($O(\log(1/\epsilon))$ in the paper)

Answer 1

A sequence $\{x_n\}_{n=1}^\infty \in \mathbb{R}^m$ is just a function $g : \mathbb{N} \rightarrow \mathbb{R}^m$, such that $g(n) = x_n$. Now let $c \in [0,1)$. By definition $$g(n) = O(c^n), \quad n \rightarrow \infty, \quad n \in \mathbb{N}$$ if and only if $$\exists M > 0, \: N \in \mathbb{N} \: : \: n \ge N \Rightarrow \|g(n)\| \leq M c^n.$$ Now, let $\epsilon > 0$ be given. Then $\|g(n)\| \leq \epsilon$ if $$ n \ge N \quad \wedge \quad M c^n \leq \epsilon.$$ It follows that $$ n \ge \max\{N, \log\left(\epsilon/M\right)/\log(c)\}$$ ensures that $\|g(n)\| \leq \epsilon$.

We are primarily interested in small values of $\epsilon$. The demand that $n > N$ is automatically satisfied, when $\epsilon < \epsilon_0$, where $$\log\left(\epsilon_0/M\right)/\log(c) = N.$$ This leaves us with the statement that $$\forall \epsilon \in (0,\epsilon_0] \: : \: \forall n \in \mathbb{N} \: : \: n \geq \log\left(\epsilon/M\right)/\log(c) \quad \Rightarrow \quad\|g(n)\| \leq \epsilon.$$ In particular, if we want to be sure that $\|g(n)\| \leq \epsilon$, then we should pick $n = \lceil \log\left(\epsilon/M\right)/\log(c)\rceil$.

We can define $h(\epsilon) = \lceil \log\left(\epsilon/M\right)/\log(c)\rceil$ and it is possible to show that $h(\epsilon) = O(|\log(\epsilon)|)$, as $\epsilon \rightarrow 0_+$, but I will leave that (minor) problem open for now.

Basically, the article means well and is almost correct, but it is possible to be considerably more accurate at the cost of readability. This is a balance which is extremely difficult to achieve, especially when writing for an unknown and varied audience.