Convergence Rates

In most schemes, we define an error and an error bound,
$e_k=|x_k-x_{\ast }|\le \mathcal{F}(k,x_k)$

Consider $\{e_k{\}}_k,e_k\ge 0$ for all $k\in \mathbb{N}$, $e_k\to 0$ as $k\to \infty$

Definition: $\{e_k{\}}_k$ is linearly convergent if ${\lim }_{k\to \infty }\frac{e_{k+1}}{e_k}=\mu$ where $0<\mu <1$
If $\mu =0$ then we call this superlinear convergence
If $\mu =1$ then we call this sublinear convergence

Definition: Likewise, our errors are convergent with order q if ${\lim }_{k\to \infty }\frac{e_{k+1}}{e_k^q}=\mu$, for $q\in \mathbb{R}$
$q=2$ corresponds to quadratic convergence

We can’t really apply these definitions to $e_k$ directly because that is not a quantity we can calculate
However, we can apply rates of convergence to error bounds ${ϵ}_k$ that we’ve established

Example:
Let’s assess the convergence rate of the bisection method

$|x_k-x_{\ast }|\le \frac{b-a}{2^{k+1}}={ϵ}_k$
${\lim }_{k\to \infty }\frac{{ϵ}_{k+1}}{{ϵ}_k}={\lim }_{k\to \infty }\frac{1}{2}=\frac{1}{2}$

So this method is at least linearly convergent

Example:
Consider the simple iteration scheme $x_{k+1}=g(x_k)$
${\lim }_{k\to \infty }\frac{|x_{k+1}-x_{\ast }|}{|x_k-x_{\ast }|}={\lim }_{k\to \infty }\frac{|g(x_k)-g(x_{\ast })|}{|x_k-x_{\ast }|}=|g^{\prime }(x_{\ast }|)$

Definition: The asymptotic rate of convergence for ${\lim }_{k\to \infty }\frac{e_{k+1}}{e_k}=\mu$ is $\rho =-{\log }_{10}\mu$