2

Given the fixed point iteration

$$ p_n = \frac{p_{n - 1}^2 + 3}{5}, $$

which converges for any initial $p_0 \in [0, 1]$, estimate how many iterations $n$ are required to obtain an absolute error $\left| p_n - p \right|$ less than $10^{-4}$ when $p_0 = 1$. No numerical value needed, just give an expression for $n$.

I know that the bound is given by

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

where $[a, b]$ is the interval in which the function lives and $k$ is the bound on the derivative of the function for the interval $[a, b]$. However, I'm not sure what to do since there is no explicit function given. Can anyone help me?

michael straws
  • 515

1 Answers1

2

This problem is an application of Banach's Fixed-Point Theorem, which, stated for real functions which are continuously differentialble, goes like this:

If there's an interval $[a,b]$ such that $f$ maps $[a,b]$ to $[a,b]$ and $f'$ is bounded by some $k<1$ in that interval, then the fixed-point iteration $x_{n+1}=f(x_n), \ n=0, \dots$ converges for every $x_n \in [a,b]$ towards an unique fixed point $x^*$. Furthermore, we have $$\vert x - x^* \vert \leq \frac{k}{1-k}\vert x_{n+1} - x_{n}\vert\leq \frac{k^n}{1-k}\vert x_1 - x_0\vert.$$

In your case, we have $f(x)=\frac{x^2 +3}{5}$, which maps indeed $[0,1]$ into itself (as $f$ is strictly increasing and $f(1)=\frac{4}{5}<1$). We have $f'(x)=\frac{2}{5}x$, i.e. $k = \max_{x\in [0,1]} \vert f'(x)\vert = \frac{2}{5}$. Since $x_0 \in [0,1]$ and $x_1\in [0,1]$, the last term of the equation above is bounded by $$\frac{(2/5)^n}{3/5}*1=\frac{5}{3}\left( \frac{2}{5}\right)^n.$$ In order to make this sma ller than $10^{-4}$, let's look for the $n$ where $5/3*(2/5)^n=10^{-4}$ or $(0.4)^n=0.0006$, i.e. $$n=\frac{\ln(0.0006)}{\ln(0.4)}\approx 8.1,$$

i.e. you're going to need 9 iterations to guarantee that your error is less than $10^{-4}$.

Roland
  • 6,064