3.3 Section 1.2 Order of convergence, linear, superlinear, quadratic

3.3.1 convergent sequence, limit definition

definition: A sequence of numbers $x_n$ converges to limit $x^{\ast }$, if for every positive number $ϵ$ there exist a number $r$ such that $|x_n-x^{\ast }|<ϵ$ for all $n>r$

Figure 3.8:example

note: Hence to show a sequence converges to $x^{\ast }$, all what we have to do is find $r$ such that for any given $ϵ$, we get $|x_n-x^{\ast }|<ϵ$ whenever $n>r$

Example: to show that $x_n=\frac{n+1}{n}$ converges to $1$, need to show that there exist a number $r$ such that $|\frac{n+1}{n}-1|<ϵ$ whenever $n>r$. Rewrite we have $\left|\frac{1}{n}\right|<ϵ$, hence we see that $r={ϵ}^{-1}$, because whenever $n>r$, then $\left|\frac{1}{n}\right|<ϵ$. For example, assume $ϵ=0.1,$ then $r=10,$ and whenever $n>10$, we have $\frac{1}{n}<0.1$

It is clear that $\underset{n->\mathrm{\infty }}{lim}\frac{n+1}{n}=1$.

3.3.2 order of convergence

The order of the convergence of a sequence is the largest number $q$ s.t. $\underset{n\to \mathrm{\infty }}{lim}\frac{|x_{n+1}-x^{\ast }|}{{|x_n-x^{\ast }|}^q}$ exist

This is the same as writing $\underset{n\to \mathrm{\infty }}{lim}\frac{\left|e_{n+1}\right|}{{\left|e_n\right|}^q}$ where $e_n$ is the error at $x_n$

Figure 3.9:example

3.3.2.1 Linear

The rate of convergence is linear if we can find constant $c<1$ and integer $N$ s.t. $$\left|e_{n+1}\right|\le c\left|e_n\right|n\ge N$$

3.3.2.2 superlinear

The rate of convergence is superlinear if we can find sequence ${\epsilon }_n$ tending to zero and integer $N$ s.t.

$$\left|e_{n+1}\right|\le {\epsilon }_n\left|e_n\right|n\ge N$$

question: I do not understand this definition Can I say it as the linear, but an exponent $1<\alpha <2$, and write

The rate of convergence is superlinear if we can find constant $c<1$ and integer $N$ s.t. $$\left|e_{n+1}\right|\le c{\left|e_n\right|}^{\alpha }n\ge N$$

3.3.2.3 quadratic

The rate of convergence is quadratic if we can find constant $c$ NOT Necessarily less than 1, and integer $N$ s.t. $$\left|e_{n+1}\right|\le c{\left|e_n\right|}^{2}n\ge N$$

idea: To show that a sequence converges quadratically to some limit, start with the expression for $e_{n+1}$ and manipulate it to show that that is it $\le$ some constant $\times e_n$

3.3.3 Big O and little o

These are means by which to compare 2 sequences to each others.

def: big O: One sequence $x_n$ is bounded by a linear scaled version of a second sequence

we say that $x_n=O{\alpha }_n$ if there is a constant $C$ and $N$, s.t. $x_n\le C{\alpha }_n$ for all $n>N$

Figure 3.10:example

How to find if $x_n=O\left({\alpha }_n\right)$? start with $x_n$ expression and manipulate it so that it has only terms that contain ${\alpha }_n$ with some multipliers (the constant).

Or, easier, just look to see if $x_n$ is bigger or smaller than ${\alpha }_n$, if it is bigger, then it goes to zero AFTER ${\alpha }_n$, hence use BIG O. if it is smaller, then it goes to zero BEFORE ${\alpha }_n$, hence us little o.

def: little o: we say $x_n=o\left({\alpha }_n\right)$ if $\underset{n\to \mathrm{\infty }}{lim}\frac{x_n}{{\alpha }_n}=0$

Figure 3.11:example

To test the above, given $x_n=\frac{n+1}{n^2}$ and ${\alpha }_n=\frac{1}{n}$, what is the relation between them? we see that $x_n=\frac{1}{n}+\frac{1}{n^2}$, so it is BIGGER than ${\alpha }_n$, so it goes to zero AFTER. Hence $x_n=O{\alpha }_n$

given $x_n=\frac{1}{n\ln n}$, we see that this is SMALLER than ${\alpha }_n$, hence it will go to zero BEFORE ${\alpha }_n$, hence $x_n=o\left({\alpha }_n\right)$

question: verify I can do this reasoning all the time.