Fixed-Point Iteration – number of iterations needed

A natural question to ask is how many iterations of the fixed-point iteration method are necessary to achieve a certain accuracy. We list the results of fixed-point iteration as applied on ${g(x)=ln(3x+1)}$ using the following piece of code written in Python:

import math

x_0 = 1 iterations = range(0,40)

for i in iterations: x_1 = math.log(3*x_0 + 1) print(x_1) x_0 = x_1

The results between the 15th and 21st iteration are:

13. 1.9037717150438356
14. 1.9037949295626633
15. 1.9038053065444669
16. 1.9038099450615822
17. 1.9038120184745679
18. 1.9038129452869204
19. 1.9038133595703104
20. 1.9038135447541562

It seems as if our solution is accurate to four decimal digits after 14 iterations. How many iterations are necessary so that our solution is accurate to 6 decimal digits?

We let ${\epsilon}$ denote the wanted accuracy. In this specific case we may let ${\epsilon = 0.5\cdot 10^{-6}}$ , because subtracting two six decimal digit numbers, where the first five are equal gives all zeros with the last number ranging from 1 to 9, e.g., ${1.234567-1.234563=0.000004=0.4\cdot 10^{-6}}$ . Since we want the same result wether we subtract by the largerst or the smallest value, we take the absolute value of the difference;

$\displaystyle |x_k - \xi|\leq \epsilon,$

where ${x_k}$ denotes the ${k^{th}}$ iteration, and ${\xi}$ denotes the fixed point of ${g}$ .

From earlier posting on Fixed-Point Iteration, we know that

$\displaystyle |x_k-\xi|\leq L^k|x_0-\xi|,\;\;k\geq 1. \ \ \ \ \ (1)$

We now do a bit of algebra,

$\displaystyle \begin{array}{rcl} |x_0-\xi| =& |x_0-x_1+x_1-\xi| \leq& |x_0-x_1|+|x_1-\xi| \\ \leq& |x_0-x_1|+L|x_0-\xi| \\ \leq& \frac{1}{(1-L)}|x_0-x_1| \end{array}$

Substituting the last result into (1) yields,

$\displaystyle |x_k-\xi|\leq \frac{L^k}{(1-L)}|x_1-x_0|.$

Solving for ${k}$ gives,

$\displaystyle k \geq \frac{ln(|x_k-\xi|(1-L)) - ln(|x_1-x_0|)}{ln(L)}.$

Multiplying by negative one turns the inequality around such that,

$\displaystyle k \leq \frac{ln(|x_1-x_0|) - ln(|x_k-\xi|(1-L))}{ln(1/L)}.$

Our final result is obtained by rewriting the last inequality as,

$\displaystyle k_0(\epsilon) \leq \left[ \frac{ln|x_1-x_0|-ln(\epsilon(1-L))}{ln(1/L)}\right] + 1$

${k_0(\epsilon)}$ is now the maximum number of iterations required such that
${|x_k-\xi|\leq\epsilon}$ . It turns out to be a somewhat pessimistic estimate.

We continue working with our initial problem.
By the Mean Value Theorem we know that for any ${x,y\in [1,2]}$ there exists a number ${\eta\in [1,2]}$ such that,

$\displaystyle |g(x)-g(y)| = |g'(\eta)(x-y)| = |g'(\eta)||x-y|$

Since ${g'(x)=\frac{3}{(3x+1)}}$ , we have that ${g'(1)=\frac{3}{4}}$ and ${g'(2)=\frac{3}{7}}$ and so,
${g'(1) \geq g'(\eta) \geq g'(2)}$ .

Since ${|g(x)-g(y)|=|g'(\eta)||x-y|}$ and ${g'(1)\geq g'(\eta) \geq g'(2)}$ we have that ${|g(x)-g(y)|\leq |g'(1)||x-y|}$ for all ${x,y\in [1,2]}$ . We therefore conclude that ${L=g'(1)=\frac{3}{4}}$ .

Calculating ${k_0(\epsilon)}$ we get that maximum ${53}$ iterations are neccessary. This is a serious overestimate as our code gives us that the solution is accurate to ${6}$ decimal digits after ${19}$ iterations.

x_0 = 1 iterations = range(0,40)

for i in iterations: x_1 = math.log(3*x_0 + 1) print(x_1) x_0 = x_1