ASE 211: Tutorial: Fixed-point iteration

ASE 211: Tutorial
Fixed-point iteration method for solving nonlinear equations

Problem summary

Find the values of x where a given nonlinear function f(x) has its zeroes [i.e., f(x) = 0].

Solution method

The key idea here is to algebraically rearrange f(x) = 0 into the form x = g(x), where g(x) denotes a function of x.

Then we simply start with some initial guess, x₀, and apply the iteration formula

_n-1

Examples

(1) Find the roots of x² - 2x - 3 = 0.

Solution: There are several ways to rewrite this into the form x = g(x). Consider the following

x = (2x + 3) ^1/2 --------------- (1)

Now suppose we start with the initial guess x₀ = 4, and iterate using x_n = (2x_n-1 + 3) ^1/2[which comes from (1)]. We get the following sequence of iterates

x₁ = (2*4 + 3)^1/2 = 11^1/2= 3.32
x₂ = (9.63325)^1/2= 3.1
x₃ = 3.01144
x₄ = etc. ...

The sequence converges to x = 3. Observe that the two exact roots for the given problem are at x = -1 and x = 3.
The figure below shows a plot of g(x), and illustrates the geometric progression of the above iterative process.

Suppose, instead of using (1), we had decided to rearrange the original problem as

x = (x²- 3) / 2 -------------- (2)

Now if we start with the initial guess x₀ = 4, and iterate x_n = (x²_n-1 - 3) / 2 what do we get?

x₁ = (16 - 3) / 2 = 6.5
x₂ = 19.625
x₃ = 191.07, etc.

Note that the iterates are getting bigger and bigger ==> the method is diverging!

The figure below shows a plot of this g(x) and the geometric progression of the iterations.

On the other hand, if we change the initial guess to x₀ = 0, and iterate using (2), we get x₁= -1.5, x₂ = -0.375, x₃ = -1.4297, ... etc. The iterates now converge (very slowly) to x = -1, which is one of the roots of this problem.

Back to index