Orders of Convergence

Convergent Sequences: suppose you're solving an integral by an iterative technique... program produces a sequence of real numbers $x_1, x_2, x_3 \cdots$ approaching the correct answer.

Write $$\lim_{n\to\infty}x_n=L$$

if there corresponds to each $\varepsilon >0$ a real number $r$ such that $\vert x_n-L\vert<\varepsilon$ whenever $n>r$ (here $n$ integer)

Example $$\lim_{n\to\infty}\displaystyle \frac{n+1}{n}=1$$

because $\vert\frac{n+1}{n}-1\vert<\varepsilon$ whenever $n>\displaystyle \frac{1}{\varepsilon }$ $\Box$

Example $x_n=\left(1+\frac{1}{n}\right)^n$

$\begin{array}{ll} x_1 & =2.0\\ x_{10} & =2.593742\\ x_{30} & =2.674319\\ x_{50} & =2.691588\\ x_{1000}& = 2.716924 \end{array}$

Show $\left\vert\displaystyle \frac{x_{n+1}-e}{x_n-e}\right\vert\to 1$ worse than linear convergence.

$\Box$

$x_{n+1}=x_n-\displaystyle \frac{x^2_n}{x^2_n+x^2_{n-1}}$

$\begin{array}{ll} x_0 & =20.0\\ x_1 & =15.0\\ x_2 & =14.64\\ x_{33} & =0.54\\ x_{34} & =0.27 \end{array}$

Rapid

$$\frac{\left\vert x_{n+1}\right\vert}{\vert x_n\vert}\to 0$$ super linear convergence. $\Box$

$\begin{array}{ll} x_1=2 & x_1=2\\ x_{n+1}=\displaystyle \frac{1}{2}x_n+\frac... ...\ge 1 & x_2=1.5\\ L=\sqrt{2} & x_3=1.416667\\ & x_4=1.414216\\ \end{array}$

$$\frac{x_{n+1}-\sqrt{2}}{(x_n-\sqrt{2})^2}\le 0.36$$    quadratic convergence. $\Box$

Orders of Convergence

Linear

$$\left\vert x_{n+1}-x^*\right\vert\le c\vert x_n-x^*\vert\quad n\ge N\in {\mathbb{Z}}, \mbox {here }c<1$$

Superlinear $\left\vert x_{n+1}-x^{*}\right\vert\le \varepsilon _n\vert x_n-x^{*}\vert\quad n\ge N$

$$\varepsilon _n\to 0$$

$$\left\vert x_{n+1}-x^{*}\right\vert\le C\vert x_n-x^*\vert^2, \mbox {have $c$\ not necessarily less than $1$\ }$$

Generally: $\vert x_{n+1}-x^{*}\vert\le C\vert x_n-x^{*}\vert^{\alpha}$

$$\mbox {we say \lq\lq at least $\alpha$-order convergent''}$$

$\Box$