In the bisection method, a sequence of closed partitions $\{I_{n}\}_{n}$ of size $(b-a)2^{-n}$ are obtained, which converge (in the sense of intersection) to $\{r\}$ where $f(r)=0$. The only requirements for this method to converge are that $r\in I_{0}=[a,b]$ and that $f$ be continuous. The fixed-point method employs essentially the same methodology, but on the range of $f$ (this is analogous to Riemann vs. Lebesgue integration). Unfortunately, rather stringent requirements are required for this method to converge; on the other hand, the method is far more general than the bisection method and is the basis for many of the methods we will subsequently study.
The fixed-point iteration method is an iterative method that solves the problem of finding an $x'\in\mathbb{R}$ such that
$$(1)\;\;\;\;F(x')=x'.$$
Such an $x'$ is said to be a fixed-point of $F$ (the definition of course generalizes to arbitrary maps defined on arbitrary spaces). The fixed-point method begins with an initial guess $x_{0}$ and generates a sequence $\{x_{n}\}_{n}$ defined by $x_{n+1}=F(x_{n})$. If $F$ is continuous and $\{x_{n}\}_{n}$ converges to $x'$, then
$$x'=\lim_{n\to\infty}x_{n}=\lim_{n\to\infty}F(x_{n-1})=F(\lim_{n\to\infty} x_{n-1})=F(x')$$
and so if the method succeeds, it yields a fixed point of $F$. In practice, we usually want to find an $x'$ that solves
$$G(x)=0.$$
If we define
$$F(x)=x+\phi(x)G(x)$$
where $\phi(x)\not0$, then if $x'$ is a fixed-point of $F$, we have
$$x'=F(x')=x'+\phi(x')G(x')\Longrightarrow G(x')=0,$$
and so $x'$ is simultaneously a solution to the original root-finding problem. The nature of $\phi$ is to expedite the rate of convergence of the fixed-point algorithm $\{F(x_{n})\}_{n}$. Chosen judiciously, the convergence can be dramatically faster. We shall return to this point in the next post when we discuss convergence of iterative methods (a concept quite different from numerical analysis of differential equations!).
Returning to (1), we seek to determine under what conditions the fixed-point iteration converges. The most general conditions are presented in the following theorem.
Theorem 1. Convergence of Fixed Point Iteration Algorithm. Suppose $F\in\mathcal{C}([a,b])$ and that for some $[c,d]\subset[a,b]$, $F:[c,d]\mapsto[c,d]$ (i.e., $F$ maps $[c,d]$ surjectively onto $[c,d]$). Then $F$ has at least one fixed point in $[c,d]$. Furthermore, if $x_{0}\in[c,d]$ and $x_{n}:=F(x_{n-1})$, then $$x_{n}\to x'=F(x')\in[c,d]$$ where $x'$ is one of the fixed-points of $F$.
