How to find the number of iteration in Fixed point iteration method?

Question

I want to know how to find the number of iterations in fixed point method.

The book that i have, gives me 2 ways to find the number of iterations.

The first one:

$|p_n - p| \leq k^n max ${ $p_0 - a$,$b - p_0$}

The second one:

$|p_n - p| \leq \frac {k^n}{1-k} |p_1 - p_0$| , for all n>=1

I don't know how to find the value of k, and which one of them i should use to find the number of iterations, because there give different results.

For example in this function:

$f(x)= 2 + sin (x) - x = 0 $, in [a=2, b=3]

Tolerance = $10^-5$

$p_0=2$

What is the value of k and n?

Answer 1

Correction: probably you want to write $\lvert p_1-p_0\rvert$ on the right-hand side of the second inequality.

Since $f'(x)=\cos x -1$, one can take $$ k=\max\bigl\{\lvert\cos x -1|:x\in[2,3]\bigr\}, $$ which is a Lipschitz constant for $f$ in the interval $[2,3]$. In order to determine $n$ you need to solve, respectively, $$ k^n \max \{ p_0 - a,b - p_0\}=10^{-5} $$ and $$ \frac{k^n}{1-k} |p_1-p_0|=10^{-5}. $$

Answer 2

Both formulas are valid, so you can use one or the other. In general, the number of iterations you get is not the same in both formulas, which is ok: each formula will produce a number of iterations that guarantees the required precision.

As it was pointed out by John B, the constant $k$ is the maximum of $|g'(x)|$, assuming the equation is written in the form $g(x)=x$. More precisely, $$ k = \max_{x\in [2,3]} |\cos x| = |\cos 3| < 1. $$

Since $g(x)$ is invariant and contractive in $[2,3]$, we can apply the fixed point theorem and the mentioned estimates are valid. In this case, since $k$ is very close to 1, the convergence is slow and the number of required iterations may be large.