Fixed Points

Fixed Points

So far we have looked at the Bisection Method and Newton's Method for approximating roots of functions. We are about to introduce another root finding method know as the Fixed Point Method, but before we do so, we will need to learn about special types of points on functions known as fixed points which we define below.

 Definition: The value $\alpha$ is called a Fixed Point of the function $g$ if $\alpha$ if $\alpha = g(\alpha)$, that is $g$ maps $\alpha$ back to itself. The equation $x_{n+1} = g(x_n)$ is called the Fixed Point Iteration.

The following very simple lemma gives us a way to determine the fixed points of a function.

 Lemma 1: A value $x$ is a fixed point of the function $g$ if and only if $y = g(x)$ intersects the diagonal line $y = x$.
• Proof: $\Rightarrow$ Suppose that $x$ is a fixed point of the function $g$. Then $x = g(x)$. But $g(x) = y$, so $x = y$, and so $(x, g(x))$ lies on the line $y = x$.
• $\Leftarrow$ Suppose that $y = g(x)$ intersects the diagonal line $y = x$. Then since $y = x$, we have that $x = g(x)$ so $x$ is a fixed point of $g$. $\blacksquare$

Thus far we have not even mentioned whether a fixed point to a function is guaranteed to exist. Theorem 1 below gives us a condition that guarantees the existence fixed points while Theorem 2 gives us a condition (though not necessary) that guarantees the uniqueness of a fixed point on an interval.

 Theorem 1 (Condition for The Existence of Fixed Points): If $g$ is a continuous function on the interval $[a, b]$ and if for all $x \in [a, b]$ we have that $g(x) \in [a, b]$ then there exists at least one fixed point in $[a, b]$.
• Proof: Let $g$ be a continuous function on $[a, b]$ such that if $x \in [a, b]$ then $g(x) \in [a, b]$. Consider the following two cases.
• Case 1: If $a = g(a)$ and/or $b = g(b)$, the $g$ has a fixed point on at least one of endpoints of the interval $[a, b]$ and we are done.
• Case 2: Suppose that $a \neq g(a)$ and $b \neq g(b)$. Then $g$ does not have a fixed point on either of the endpoints of $[a, b]$. Therefore we have that $g(a) > a$ (since $a < g(x) < b$) and $g(b) < b$ (since $a < g(x) < b$. Define the function $h$ as:
(1)
\begin{equation} h(x) = g(x) - x \end{equation}
• We note that $h$ is a continuous function on $[a, b]$ since $y = g(x)$ and $y = x$ are both continuous on $[a, b]$. Now $h(a) = g(a) - x > 0$ and $h(b) = g(b) - b < 0$. By the Intermediate Value Theorem, there exists a root $\alpha \in (a, b)$ such that $h(\alpha) = 0$, and so $h(\alpha) = 0$ implies that $g(\alpha) - \alpha = 0$, thus $\alpha = g(\alpha)$ and so $\alpha$ is a fixed point of $g$. $\blacksquare$
 Theorem 2 (Condition for The Uniqueness of a Fixed Point): If $g$ is a continuous function on the interval $[a, b]$ and if for all $x \in [a, b]$ we have that $g(x) \in [a, b]$. Furthermore, if $g$ is differentiable of $(a, b)$ and there exists a number $k \in \mathbb{R}$ such that $0 < k < 1$ such that for all $x \in (a, b)$ we have that $\mid g'(x) \mid ≤ k$ , then the fixed point $\alpha \in [a, b]$ is unique.
• Proof: We are already guaranteed a fixed point $\alpha \in [a, b]$ from Theorem 1. Suppose that there exists a $k \in \mathbb{R}$ such that $0 < k < 1$ and such that $\mid g'(x) ≤ k < 1$. Suppose that $\alpha$ and $\beta$ are both fixed points in $[a,b]$ such that $\alpha \neq \beta$. By the Mean Value Theorem, there exists a real number $\xi$ between $\alpha$ and $\beta$ (and therefore $\xi \in (a, b)$) such that:
(2)
\begin{align} \quad \frac{g(\alpha) - g(\beta)}{\alpha - \beta} = g'(\xi) \\ \quad g(\alpha) - g(\beta) = g'(\xi)(\alpha - \beta) \end{align}
• Since $\xi \in (a, b)$ we have that $\mid g'(\xi) \mid ≤ 1$. Furthermore, since $\alpha$ and $\beta$ are fixed points, we have that $\mid \alpha - \beta \mid = \mid g(\alpha) - g(\beta)$ and so:
(3)
\begin{align} \quad \mid \alpha - \beta \mid = \mid g(\alpha) - g(\beta) \mid = \mid g'(\xi) \mid \mid \alpha - \beta \mid < \mid \alpha - \beta \mid \end{align}
• But this is a contradiction which comes from assuming that $\alpha \neq \beta$. Thus, the fixed point $\alpha$ is unique. $\blacksquare$

Example 1

Show that the function $f(x) = x^2$ has two fixed points. Show that $\mid f'(x) \mid ≥ 1$ for some $x \in (-1, 2)$

The function $f(x) = x^2$ intersects the line $y = x$ when $x = 0$ and $x = 1$ since $f(0) = 0^2 = 0$ and $f(1) = 1^2 = 1$. Therefore $x = 0$ and $x = 1$ are the two fixed points of $g$. Now $f'(x) = 2x$. This function is strictly increasing on $[-1, 2]$, and $f(-1) = -2$ and $f(2) = 4$ are the absolute maximum and absolute minimum (respectively) on $[-1, 2]$. Clearly there exists $x \in (-1, 2)$ such that $\mid f'(x) \mid ≥ 1$, take $x = -0.5$ for example. Then $\mid f'(-0.5) \mid = \mid 2(-0.5) \mid = 1 ≥ 1$.