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, known as the Babylonian method, uses a function to repeatedly improve an estimate until it reaches the square root.

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

Attracting fixed points

An attracting fixed point of a function is a special point where, if you start close enough to it and repeatedly apply the function, you get closer and closer to that point. For example, the cosine function has one attracting fixed point. If you take any real number and repeatedly apply the cosine function (making sure your calculator is in radians mode), the numbers will eventually get very close to a special value called the Dottie number, which is about 0.739085133.

However, not all fixed points are attracting. For instance, zero is a fixed point of the function that doubles its input, but if you start with any number other than zero and keep applying this function, the numbers move away from zero instead of getting closer to it. The Banach fixed-point theorem tells us that certain conditions guarantee the existence of attracting fixed points. Specifically, if a function is a contraction mapping on a complete metric space, it has exactly one fixed point, and repeated applications of 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 a set of rules called an iterated function system (IFS). You start with any point and then pick one of the rules randomly to move to a new point. By repeating this many times, you can draw shapes like the Sierpinski triangle, which is a type of fractal. This process helps show the overall shape of these interesting patterns by moving step by step toward a fixed point.