2.2 Fixed Point Iteration

{\begin{cases} y = \cos (x) \\ y = x \end{cases}

Pasted image 20250213160742.webp|224 $${\left{\begin{array}{l l}{y=x^{2}}\ {y=x}\end{array}\right.}$$
Pasted image 20250213160918.webp|209

Clearly:
If $h (x)$ is differentiable on $(a, b)$ with $| h' (x) | < 1$ for all $x \in (a, b)$ , then whenever $x_{1}, x_{2} \in (a, b)$ ,

| h (x_{2}) - h (x_{1}) | < | x_{2} - x_{1} |

Conceptually:
Moreover, a function whose derivative has magnitude less than 1 can only cross the line $y = x$ one time. Once it has crossed, it can never “catch up” because that would require a slope greater than 1, the slope of the line $y = x$ .

Suppose $h (x)$ is continuous on $[a, b]$ , differentiable on $(a, b)$ with $| h' (x) | < 1$ for all $x \in (a, b)$ , and $h ([a, b]) \subseteq [a, b]$ Then $h$ has a unique fixed point in $[a, b]$ .

Fixed Point Convergence Theorem Given a function $f (x)$ with continuous first derivative and fixed point $\hat{x}$ , if $| f^{'} (\hat{x}) | < 1$ then there exists a neighbourhood of $\hat{x}$ in which fixed point iteration converges to the fixed point for any initial value in the neighbourhood.

If $| f^{'} (\hat{x}) | < 1$ , then fixed point iteration converges to $\hat{x}$ for any initial value in some neighbourhood of $\hat{x}$ .

If $| f^{'} (\hat{x}) | > 1$ , then fixed point iteration escapes some neighbourhood of $\hat{x}$ for any initial value in the neighbourhood other than $\hat{x}$ .

Otherwise inconclusive.

We can find bounds on the largest such interval by solving the equation $$|f′(x)|= 1$$

Comparison To Root Finding

$f (x) = x$ has exactly the same solutions as the equation $f (x) - x = 0$ , so finding fixed points of $f (x)$ is equivalent to finding roots of $g (x) = f (x) - x$ .

Algorithm

Input: A differentiable function $f$ with fixed point $\hat{x}$ an initial point $x_{0}$ in a neighbourhood $(\hat{x} - δ, \hat{x} + δ)$ where $| f^{'} (x) | < 1$ , a desired tolerance $ε$ , max iterations $N$ .
Output: An approximate $x$ close to a fixed point of the function $f$ , or failure.

*Key observation: $| x_{k + 1} - x_{k} | = | f (x_{k}) - x_{k} |$ , so $x_{k}$ is close to a fixed point if $x_{k + 1}$ is close to $x_{k}$ .

Outline:

Given $x_{0}$ , evaluate $f (x_{0})$ and check tolerance.
- If tolerance is achieved, output $x_{0}$ .
- Otherwise, set $x_{0} \leftarrow f (x_{0}) .$
Repeat this either until the desired tolerance is achieved (and return the iterate) or until the maximum iterations N is reached (print method failed).

Important note: Here we are using $| x_{k + 1} - x_{k} | = | f (x_{k}) \to x_{k} |$ as a proxy for error (but the actual error may exceed this in reality)