Fixed Point Iteration

Subjects: Numerical Analysis
Links: Solutions of Equations of One Variable

The number $p$ is a fixed point for a given function $g$ if $g (p) = p$

Given a root finding problem $f (p) = 0$ , we can define function $g$ with a fixed point at $p$ , as

g (x) = x + λ f (x)

for $λ \in R$ . Conversely, ik a function $g$ has a fixed point at $p$ , then the function defined by

f (x) = x - g (x)

has a zero at $p$

Th:

If a function $g \in C [a, b]$ and $Im g \subseteq [a, b]$ , then $g$ has at least one fixed point in $[a, b]$
If, in addition, $g$ is Lipschitz continuous with a Lipschitz constant $k < 1$ , then there is exactly one fixed point in $[a, b]$ .

Fixed Point of Functional Iteration

def fixed_point_iteration(g, x0, tolerance:float = 1e-6, max_iterations = 1_000):
	x_current = x0
	
	for _ in range(max_iterations):
		x_next = g(x_current)
		
		if abs(x_next - x_current) < tolerance:
			return x_next
		x_current = x_next
	
	print('Did not converge within the maximum iterations')
	return x_current

g = lambda x: 0.5 * (x + 2 / x)
print(fixed_point_iteration(g, 1))

Fixed Point Theorem

Let $g \in C [a, b]$ be such that $Im g \subseteq [a, b]$ . Suppose that $g$ is Lipscitz continuous with Lipschitz constant $k < 1$ . Then for any $p_{0} \in [a, b]$ , the sequence defined by

p_{n + 1} = g (p_{n}) n \in N

converges to the unique fixed point $p$ , in $[a, b]$

Cor: Let $g \in C [a, b]$ be such that $Im g \subseteq [a, b]$ . Suppose that $g$ is Lipschitz continuous with Lipschitz constant $k < 1$ , then the bounds for the error involved in using $p_{n}$ to approximate $p$ are given by

| p_{n} - p | \leq k^{n} max {p_{0} - a, b - p_{0}}

and

| p_{n} - p | \leq \frac{k^{n}}{1 - k} | p_{1} - p_{0} | for all n \geq 1

Meaning that $p_{n} = p + O (k^{n})$ . With this we can construct given a tolerance $ε > 0$ , we can construct, the least $n$ necessary to have a precision of $ε$ . We have that

\log_{k} (\frac{ε (1 - k)}{| p_{1} - p_{0} |}) < n

We have a that if $g \in C [a, b]$ , with $| g^{'} (p) | > 1$ , then there’s a $δ > 0$ such that if $0 < | p_{0} - p | < δ$ , then $| p_{0} - p | < | p_{1} - p |$ . Thus, no matter how close the initial approximation $p_{0}$ is to $p$ , the next iterate $p_{1}$ is farther away, so the fixed-point iteration does not converge if $p_{0} \neq p$ . This is where the definition of unstable fixed points comes from

Similarly, let $g$ be continuously differentiable on some interval $(c, d)$ that contains the fixed point $p$ of $g$ . Then if $| g^{'} (p) | < 1$ , then there’s a $δ > 0$ , such that if $| p_{0} - p | \leq δ$ , then the fixed point iteration converges.