Fixed-Point Iteration

1. Background

Fixed-point iteration is a type of numerical approximation method for function’s root finding. One application is that, in the distortion of pinhole camera model, fixed-point iteration is used when facing high order polynomial solution to recover the undistorted ray. In this blog, we will elaborate the standard fixed-point iteration method, as well as its extensions. We will also visualize the methodology for a better presentation. Demo code is in the Github repo.

2. Theory

2.1. The Basic Idea

Finding the zero of is equivalent to finding the root of , where .

A fixed-point of a function is where , and is the fixed-point of function . The idea of fixed-point iteration is to approximate the fixed-point of by repetetively utilize the recursion function below.

Eventually, the recursion will converge to the fixed-point of function , i.e., . The root of function is thus as well.

2.2. Convergence Properties

But does the root of any function can be found via such approach? Some prerequisites should be fulfilled in order to guarantee the convergence.

In above figures, we illustrates the two types of convergence and two types of divergence, which are monotone and oscillatory. Together, they intuitively reveal the secret of convergence——gradient of . Given different signs of , whether the algorithm evole monotonically or in oscillation is also determined. But there’s more than that.

2.3. Derivation of Fixed-Point Iteration

The goal to prove the convergence, is to prove that

Suppose that

, when .

An positive , and , .

We can prove that as long as the above two conditions suffice, .

2.3.1. Existance of a fixed-point in the interval

Given and , we have and , which exactly shows and . Since , we know that and . This gives at least a zero for , equivallently, a fixed-point of .

2.3.2. Uniqueness of a fixed-point in the interval

Given , we have . This indicates the monotonicity of . Therefore, only has one zero in the interval, and thus has only one fixed-point.

2.3.3. Convergence

By Mean Value Theorem, we have

Since the right hand side given , we prove the convergence that

3. Extensions

3.1. From to

A great thing about visualization is the intuitiveness it gives through graphs. We cannot help notice that, when the condition for , the slope of the line is exactly , i.e., . Is that a coincidence? Does the convergence hold, when , and given the slope as , i.e., ?

In the images above, we use . It turns out that we can still have the convergence, as long as and when . We can prove the convergence similarly.

Since , the convergence is guaranteed.

3.2. From to

Extending the above disscussion, we can also showcase that as long as the conditions suffice, any form of the function can be served as a root-finding helper.

We can try to extend that as long as , it will converge as well.

Although and are visually different, but one can always derive that

Therefore, the extension falls back to the original problem.

3.3. The Banach Fixed-Point Theorem (in a nutshell)

We’ve shown the extension of fixed-point iteration from the standard to any function , as long as some criteria suffice. The underlying idea is the Banach Fixed-Point Theorem. Although the original theorem is rigorous, the key idea is the contraction mapping. No matter the form of or , as long as is a contraction mapping, it will always converge to the solution. The domain is the contraction region, and is the Lipschitz constant of this contraction mapping.

3.4. Attracting Fixed-Points

One might have noticed that, even when , there are still chances that converges to its fixed point. An example is the exact same setting of Fig 1.1, with only the adjustment of . It is obvious that , but it converges to the fixed point at somehow.

In the example, we have two fixed-points at and . Since , is called the attracting fixed-point. Vise versa, is called the repelling fixed-point with a derivative greater than .

An attracting fixed-point attracts the points toward itself within its neighboring domain. And a repelling fixed-point does exactly the opposite thing. Therefore, any starting points lie between the neighboring two fixed-points (one attracting, one repelling) will converge to the attracting fixed-point.

This shows that the Banach conditions are only sufficient, but not necessary. In fact, in the whole basin of attraction, convergence is guaranteed.

4. Examples

4.1. Babylonian Method

The well-known Babylonian method for root finding of a positive number can be proven global convergence, since it fulfills the requirements of the contraction mapping. If we formulate the original problem as , the iteration equation is

We can prove the derivative of always smaller than . Simply take the derivative, we have

One trivial fact is that for any positive , . Therefore for any , we always have . This gives any . And for any , we have . The domain is then

Since we find the contraction domain and the Lipschitz constant we can say that Babylonian method always converge with a starting point .

4.2. Newton’s Method

Newton’s approximation for root finding of is based on Taylor expansion of

We can formulate the iteration as

If the right hand side is put in a , this is also viewed as a fixed-point iteration.

5. Conclusion & Reference

In this article, we focused on how and why fixed-point iteration works. We also discussed some extensions and background information of the method, as well as its relation to Newton’s method. One major aspect of the method is not covered, which is the convergence rate. We also only disscussed the basin of attraction superficially. For readers who are willing to learn more about the method, there are some good materials that I referred:

Slides from University of Notre Dame

James Zhan's Blog

Slides from East China Normal University