Math 441

Fixed-point Methods

Function iteration

Given $g\colon [a,b] \to [a,b]$ such that $g \in \mathcal{C}([a,b])$.

Pick $p_0 \in (a,b)$, and generate the recursive sequence $p_{n} = g(p_{n-1})$ for $n \ge 1$.

The sequence $\{p_n\}$ either diverges or converges.

If it converges to $p$, then

\[\begin{aligned} p = \lim_{n\to\infty} p_n &= \lim_{n\to\infty} g(p_{n-1}) \\ & \class{fragment}{{} = g\left(\lim_{n\to\infty} p_{n-1}\right) \text{ since $f$ is continuous}} \\ & \class{fragment}{{}= g\left(\lim_{n\to\infty} p_{n}\right)} \\ & \class{fragment}{{}= g(p)} \end{aligned}\]

Connection to equation solving

If the sequence converges to $p$, then $p$ is a solution for the equation $g(x) = x$.

Is there a solution?

A solution of the equation $g(x) = x$ is called a fixed point of $g$.

Theorem:

Given a function $g\colon [a,b] \to [a,b]$ such that $g \in \mathcal{C}([a,b])$, then $g$ has at least one fixed point in $[a,b]$.
If, in addition, $g$ is a contraction, which means there is $\lambda \in (0,1)$ such that $\left\lvert g(x) - g(y)\right\rvert \le \lambda \left\lvert x - y\right\rvert$ for every $x \in [a,b]$ and $y \in [a,b]$, the fixed point is unique.

Proof: Either $g(a) = a$, or $g(b) = b$, or $g(a) > a$ and $g(b) < b$. Consider the third case.

Define $f(x) = g(x) - x$. Then $f(a) > 0$, $f(b) < 0$, and $f$ is continuous $\longrightarrow$ part 1.

For part 2, suppose $p$ and $q$ are two fixed points…

Convergence

Given a continuous function $g\colon [a,b] \to [a,b]$ that is a contraction, that is there exists $\lambda \in (0,1)$ such that $\left\lvert g(x) - g(y)\right\rvert \le \lambda \left\lvert x - y\right\rvert$ for every $x \in [a,b]$ and $y \in [a,b]$, then for any $p_0 \in [a,b]$, the sequence $\{p_n\}$ defined recursively by $p_n = g(p_{n-1})$ for $n \ge 1$ converges to the unique fixed point of $g$ on $[a,b]$.

Suppose $g$ is differentiable on $[a,b]$, and suppose there is a $k < 1$ such that $\left\lvert g'(x)\right\rvert \le k$ for every $x \in (a,b)$. Then $g$ is a contraction on $[a,b]$, with $\lambda = k$.

Error estimates

Suppose $g$ is a continuous contraction on $[a,b]$, and $p_0 \in [a,b]$.

Let $p$ be the unique fixed point of $g$ on $[a,b]$.

Then the following inequalities hold for all $n > 0$:

$\displaystyle\left\lvert p_n - p\right\rvert \le \frac{\lambda^n}{1-\lambda}\left\lvert p_1 - p_0\right\rvert$
$\displaystyle\left\lvert p_n - p\right\rvert \le \frac{1}{1-\lambda}\left\lvert p_{n+1} - p_n\right\rvert$
$\displaystyle\left\lvert p_{n+1} - p\right\rvert \le \frac{\lambda}{1-\lambda}\left\lvert p_{n+1} - p_n\right\rvert$
$\displaystyle\left\lvert p_n - p\right\rvert \le \lambda^n \max\{p_0 - a, b - p_0\}$