Fixed point

A common algorithm for solving nonlinear equations is the fixed point iteration. For this the following sequence is calculated $x_{n} = f(x_{n-1}) = \underbrace{f(f(\dots f(}_{n \text{ times}}x_0)\dots)) = (f^n)(x_0), \quad n \in \mathbb{N}$ where $x_0$ is a suitable starting value. When this sequence converges, we can break the iteration and have found our fixpoint. The fact that this sequence converges for the cosine can be proved by the Banach fixed point theorem. The criteria for convergence are accordingly:

• Choose a closed interval $I$ with $f (I) \subset I$
• For all points $x \in I$ is $| f '(x) | <1$

Then the fixed point iteration converges for a starting value $x_0 \in I$ . These criteria are fulfilled in the case $f(x) = \cos(x)$ and $I = [0,1]$ .

With a few lines of code you can therefore solve a non-linear equation, if the starting value has been chosen appropriately and the fixed point is stable:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

from math import *

def fixedPoint(f, x):
    y = f(x)
    while(y != x):
        x = y
        y = f(x)
    return y

print(fixedPoint(cos, 0.5))