2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ $f(x)=\frac{x^2+3}{5}$. Your turn. $\endgroup$ – André Nicolas Feb 11 '14 at 2:08
  • $\begingroup$ How did you know to do that? $\endgroup$ – michael straws Feb 11 '14 at 2:09
  • 1
    $\begingroup$ Fixed point iteration is $x_n=f(x_{n-1})$. $\endgroup$ – André Nicolas Feb 11 '14 at 2:12
  • $\begingroup$ So this would be used to find a zero of the function $g(x) = \frac{x^2 + 3}{5} - x$? $\endgroup$ – michael straws Feb 11 '14 at 2:13
  • $\begingroup$ Yes, for example. $\endgroup$ – Roland Feb 11 '14 at 2:15
2
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.