General Iteration Method
The method is also called iteration method or method of successive approximations or fixed point iteration method.
The first step in this method is to rewrite the given equation f(x) = 0 in an equivalent form as
x = φ(x)................... 1.1
There are many ways of rewriting f(x) = 0 in this form.
For example, f(x) = x3 – 5x 1 = 0, can be rewritten in the following forms.
.......................1.2
Now, finding a root of f(x) = 0 is same as finding a number α such that α = φ(α), that is, a fixed point of φ(x). A fixed point of a function φ is a point α such that α = φ(α). This result is also called the fixed point theorem.
Using Eq.(1.1), the iteration method is written as
xK 1 = φ(xK), k = 0, 1, 2, ... ..................... 1.3
The function φ(x) is called the iteration function. Starting with the initial approximation x0, we compute the next approximations as
.........................1.4
The stopping criterion is same as used earlier. Since, there are many ways of writing f(x) = 0 as x = φ(x), it is important to know whether all or at least one of these iteration methods converges.
Note: Convergence of an iteration method xk 1 = φ(xk), k = 0, 1, 2,..., depends on the choice of the iteration function φ(x), and a suitable initial approximation x0, to the root.
Consider again, the iteration methods given in Eq.(1.12), for finding a root of the equation f(x) = x3 – 5x 1 = 0. The positive root lies in the interval (0, 1).
................................ 1.5
With x0 = 1, we get the sequence of approximations as x1 = 0.4, x2 = 0.2128, x3 = 0.20193, x4 = 0.20165, x5 = 0.20164.
The method converges and x ≈ x5 = 0.20164 is taken as the required approximation to the root.
............................1.6
With x0 = 1, we get the sequence of approximations as x1 = 1.5874, x2 = 1.9072, x3 = 2.0437, x4 = 2.0968,...
which does not converge to the root in (0, 1).
..............................1.7
With x0 = 1, we get the sequence of approximations as x1 = 2.0, x2 = 2.1213, x3 = 2.1280, x4 = 2.1284,...
which does not converge to the root in (0, 1).
Now, we derive the condition that the iteration function φ(x) should satisfy in order that the method converges.
Condition of convergence :
The iteration method for finding a root of f(x) = 0, is written as
.....................1.8
Let α be the exact root. That is,
α = φ(α). ....................... 1.9