A theorem in my book states:

Let $g$ be a function and $r$ a number fixed by the function (i.e. $g(r) = r$). Assume $g$ is continuously differentiable, $g(r) = r$ and $|g'(r)| < 1$, then the fixed point iteration is locally convergent to $r$.

In other words, the sequence defined by $g(r_i) = r_{i+1}$ converges to $r$.

Let $g(x) = 0.5x^2 + 0.5x$

First I try to find the fixed points. I would like to find $x$ such that:

$x = 0.5x^2 + 0.5x$

Upon simplifying and solving I get that $x = 0, 1$.

By testing it on a calculator, I find that both values are the limit of the sequences of numbers I get by repeated iteration. However, when I try to apply the theorem, I find that they shouldn't be!

By the theorem:

$g'(x)$ is continuous, thus the function $g(x)$ is continuously differentiable. Next, $g(0) = 0$ and $g(1) = 1$. BUT, $|g'(0)| = 1$ and $|g'(1)| = 2$. Neither are less than $1$, like I expected.

What am I doing wrong?

  • $\begingroup$ Isn't $g'(0)=1/2$? As for the other point, it might depend on your starting point. $\endgroup$ – Mark McClure Jan 29 '17 at 19:43

A small first remark : this theorem is a sufficient contition to have convergence, not a necessary one.

Now, as others have said, $|g'(0)| = \frac{1}{2} < 1$ so you have convergence.

For the second fixed point, it's easy to show that there isn't local convegence :

$\psi(x) = g(x)-x$ is strictly increasing on $[1,+\infty[$, so for every $\epsilon > 0$, $g(1+\epsilon) > 1+ \epsilon$, and by a quick induction, $\forall n > 0, g^n(1+\epsilon) > 1+ \epsilon$ (here it is the n-th composition) : it prove that starting from $1+\epsilon$, you cannot converge to $1$.

Hence no matter what neighborhood of $1$ you take, you'll find an $x=1+\epsilon$ such that the iteration will not converge to $1$


I guess you have made a mistake in your differentiation: $g'(x) = x + 0.5$, so $g'(0) = 0.5$, but $g'(1) = 1.5$ which is indeed not smaller than 1

Moreover the theorem says it converges only locale, so for some starting value in a neighbourhood of the fixed Point. It just says that given a starting point close to the fixed point the method is garanteed tot converge.

So in this case it Will only converge in a neighbourhood of 0 and not for a neighbourhood of 1


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.