Simple Iteration
by Michal Grézl, Aley Keprt and Jindřich Pospíšil @ UPOL 1999

Simple description of the simple iteration:

Simple iteration is numerical method that can be used for solving equations of type

If the equation has different type we can change order of terms in equation or we can use following modification: x = x + k(x) g(x) (where k(x) must be continuous function).

Simple iteration uses approximations xn.

 

Conditions for g(x) and Calculation of the Root

- g(x) is in <a,b> for all x from <a,b>

- g(x) matches Lipschitz's condition:

Than x = g(x) has the only root in <a,b>, xn tends and the root can be obtained as the limit of approximations xn:

- x0 is arbitrary number from <a,b>

-

 

Using the Lipschitz's condition is not very comfortable. Better is to use following condition:

When g(x) matches this condition, it matches Lipschitz's condition too. Both of these conditions are sufficient but not necessary.

 

Accelerateing of Sequences

Sometimes xn tends too slowly and that's why it can take longer time to calculate the root of g(x). There is the method that can accelerate xn sequence. We can use new sequence (yn) that tends to the same number but faster. Formula for obtaining yn from xn is here:

Following table shows sequence xn and accelerated sequence yn for

n xn yn
0 0  
1 -0.693144  
2 -0.418411 -0.496394
3 -0.601539 -0.528295
4 -0.493564 -0.533614
5 -0.563259 -0.535920
6 -0.520419 -0.536728
7 -0.547635 -0.537062
8 -0.530681 -0.537188
9 -0.541377 -0.537240
10 -0.534682 -0.537259

 

Error Estimation

Let x* is the root of equation x = g(x). Than error can be estimated as:

Sometimes it can be difficult to select appropriate L. We can use following approximation:

The source code of the above Java applet is enclosed here.

Click to go to authors' home pages: Michal Grézl , Aley Keprt , Jindřich Pospíšil