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$?
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?
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?
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)?
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”.