Fixed-point iteration

Fixed-point iteration is an important idea in numerical analysis. It is a way to find special numbers called fixed points of a function. A fixed point is a number where, when you put it into the function, the function gives the same number back.

To use fixed-point iteration, you start with any number, called x₀, and then keep applying the function over and over. This creates a sequence of numbers. If everything goes well, this sequence gets closer and closer to the fixed point.

This method works for functions defined on real numbers, but it can also be used in more general spaces. Because of this, fixed-point iteration is useful in many areas of mathematics and computer science.

: /w/0 : /w/1 : /w/2 : /w/3 : /w/4 : /w/5 : /w/6 : /w/7

Examples

One simple example of fixed-point iteration is used to find the square root of a number. This method is called the Babylonian method. It uses a function to make a guess better and better until it finds the square root.

Another example uses the function cos(x) to find a value where the function equals its input. This method works from any starting point and gets closer to the answer each time. These examples show how fixed-point iteration can solve problems by following a clear rule over and over.

Attracting fixed points

An attracting fixed point of a function is a special point. If you start close to it and keep using the function again and again, you get closer to that point.

For example, the cosine function has one attracting fixed point. If you take any real number and keep using the cosine function (make sure your calculator is in radians mode), the numbers will get very close to a special value called the Dottie number. This number is about 0.739085133.

Not all fixed points are attracting. For example, zero is a fixed point of the function that doubles its input. But if you start with any number that is not zero and keep using this function, the numbers move away from zero instead of getting closer to it. The Banach fixed-point theorem tells us that certain conditions make sure attracting fixed points exist. If a function is a contraction mapping on a complete metric space, it has exactly one fixed point. Repeating the function will always lead to that point, no matter where you start.

Chaos game

Main article: Chaos game

The chaos game is a fun way to find special points using rules called an iterated function system (IFS). You start with any point and then pick a rule randomly to move to a new point. By doing this many times, you can draw shapes like the Sierpinski triangle, which is a type of fractal. This shows the shape of these patterns by moving step by step toward a fixed point.