When does $p_{n+1} = g(p_n)$ converge to a fixed point of $g$ and how quickly does it approach the fixed point?
The next theorem provides some guarantees.
When does this sequence converge to a fixed point of $g$? How quickly can it provide a good approximation?
Let $g$ be a continuous function on $[a,b]$ with $g:[a,b]\to[a,b]$ and suppose $g$ is continuously differentiable on $(a,b)$ with $|g'(x)|\leq k < 1$ for all $x\in(a,b)$ and some fixed $k$. Then
  1. The sequence $p_n=g(p_{n-1})$ converges to the unique fixed point $p$ of $g$ for any $p_0\in[a,b]$.
  2. $|p_n-p_{n-1}|\leq k^{n-1}\max(p_0-a,b-p_0)$.
  3. $|p_n-p| \leq \frac{k^n}{1-k}|p_1-p_0|$.
Let $g$ be a continuous function on $[a,b]$ with $g:[a,b]\to[a,b]$ and suppose $g$ is continuously differentiable on $(a,b)$ with $|g'(x)|\leq k < 1$ for all $x\in(a,b)$ and some fixed $k$.
Then
  1. The sequence $p_n=g(p_{n-1})$ converges to the unique fixed point $p$ of $g$ for any $p_0\in[a,b]$.
  2. $|p_n-p_{n-1}|\leq k^{n-1}\max(p_0-a,b-p_0)$.
  3. $|p_n-p| \leq \frac{k^n}{1-k}|p_1-p_0|$.
The hypotheses guarantee the existence of unique fixed point by our last theorem, so we are justified in referring to the fixed point of $g$. The hypotheses here are sufficient, but not necessary.
Let $g$ be a continuous function on $[a,b]$ with $g:[a,b]\to[a,b]$ and suppose $g$ is continuously differentiable on $(a,b)$ with $|g'(x)|\leq k < 1$ for all $x\in(a,b)$ and some fixed $k$.
Then
  1. The sequence $p_n=g(p_{n-1})$ converges to the unique fixed point $p$ of $g$ for any $p_0\in[a,b]$.
  2. $|p_n-p_{n-1}|\leq k^{n-1}\max(p_0-a,b-p_0)$.
  3. $|p_n-p| \leq \frac{k^n}{1-k}|p_1-p_0|$.
To prove (1), we must show that $|p_n-p|\to 0$ as $n\to 0$ for any $p_0\in [a,b]$. In order to define to define $p_n=g{(p_{n-1})}$, it is crucial that $g:[a,b]\to[a,b]$. Since $p$ is fixed, and $|g'(x)| < 1$, distance to the fixed point decreases: \begin{align} |p_n-p|&=|g(p_{n-1})-g(p)| \\ &=|g'(c_1)||p_{n-1}- p|\\ &\leq k |p_{n-1} -p|\\ &= k |g'(c_2)|p_{n-2}-p|\\ &\leq k^2 |p_{n-2}-p| \\ &\quad \vdots \\ &\leq k^n|p_0-p|\to0 \end{align} as $n\to\infty$ because $0 < k < 1$.
(2) Proceeding as above we may show that $$|p_n-p_{n-1}|\leq k|p_{n-1}-p_{n-2}|\leq\cdots\leq k^{n-1}|p_1-p_0|.$$ Since $p_1 \in [a,b]$, we have $|p_-p_0|\leq \max(p_0-a,b-p_0)$, giving the second bound.
(3) Let $m>n$. Then \begin{align} |p_m-p_n|&=|p_m- p_{m-1}+p_{m-1}-p _{m-2}+p_{m-2}+\cdots+p_{n+1}-p_n|\\ &\leq |p_m-p_{m-1}|+|p_{m-1}-p_{m-2}|+\cdots+|p_{n=1}-p_n|\\ &\leq k^{m-1}|p_1-p_0|+k^{m-2}|p_1-p_0|+\cdots+k^n|p_1-p_0|\\ &=k^n|p_1-p_0|(1+k+k^2+\cdots+k^{m-n-1}). \end{align} In (1) we proved that $p_m\to p$ as $m\to\infty$, so taking the limit with respect to $m$ above gives $$|p-p_n|\leq k^n|p_1-p_0| \sum_{i=0}^\infty k^i=\frac{k^n}{1-k}|p_1-p_0|$$ as claimed.
So when should we stop iterating?
The absolute error bound provided by our convergence theorem is not practical, unlike the one we used to implement the bisection method.
For any root finding procedure and a given tolerance $\epsilon$, there are at least three possibilities:
  • Test for a root: $|f(p_n)| \leq \epsilon$.
  • $|p_n - p_{n-1}|\leq\epsilon$.
  • $|p_n - p_{n-1}|\leq \epsilon |p_n|$.

Stopping criteria

Congratulations! You reached the end of this lecture.
Take me home