Notes - Continuous Mathematics HT23, Convergence


Flashcards

Given an iterative numerical algorithm that attempts to approximate a true value $x^\star$, where $x _ n = f(x _ {n-1})$, what is the expression for the error $\epsilon$ at step $n$?


\[\epsilon_n = x_n - x^\star\]

In an iterative numerical algorithm, the error at step $n$ is given by

\[\epsilon_n = x_n - x^\star\]

What is the goal of any iterative algorithm?


\[\lim_{n \to \infty} \epsilon_n \to 0\]

Can you compare what it means for an iterative numerical algorithm to converge ($\epsilon _ n \to 0$) linearly or converge sublinearly?


Linearly:

\[\lim_{n \to \infty} \frac{|\epsilon_{n+1}|}{|\epsilon_n|} = a\]

where $0 < a < 1$. Sublinearly:

\[\lim_{n \to \infty} \frac{|\epsilon_{n+1}|}{|\epsilon_n|} = 1\]

What special case of an iterative numerical algorithm converging sublinearly, i.e.

\[\lim_{n \to \infty} \frac{|\epsilon_{n+1}|}{|\epsilon_n|} = 1\]

exists that means it is very slow?


Logarithmic convergence,

\[\lim_{n \to \infty} \frac{|\epsilon_{n+2} - \epsilon_{n+1}|}{|\epsilon_{n+1} - \epsilon_n|} = 1\]

What does it mean for a iterative numerical algorithm to converge ($\epsilon _ n \to 0$) superlinearly?


\[\lim_{n \to \infty} \frac{|\epsilon_{n+1}|}{|\epsilon_n|} = 0\]

What does it mean for a iterative numerical algorithm to converge ($\epsilon _ n \to 0$) with order $q$ convergence (careful; this definition is slightly different)?


\[\lim_{n \to \infty} \frac{|\epsilon_{n+1}|}{|\epsilon_n|^q} > a\]

where $a > 0$ and $q > 1$.

What does it mean for an iterative numerical algorithm to have quadratic convergence?


It has order-2 convergence.

If $x _ n$ converges with order-$q$ converges, how fast does $x _ {2n}$ converge?


Order-$q^2$.

What is the region around with an iterative algorithm tends towards a solution called?


The “basin of convergence”.




Related posts