If $g(x):=21^{1/2}x^{-1/2}$, then $21^{1/3}$ is a fixed point of $g$.

Question: Using the Fixed Point Iteration Method, are there conditions on the starting point $x_0$ in order for the method to converge? Justify.

So it seems like any $x_0>0$ should be such that we have convergence. However, how to justify it? Geometrically, this seems plausible because of the curvature of $g$. Is there a criterion based on the second derivative of $g$?

In theory one could solve the recurrence relation $$ x_{n+1}=21^{1/2}x_n^{-1/2} $$ and find, according to WolframAlpha, $$ x_n=21^{\frac{1}{3}(1-(-\frac{1}{2})^n)}e^{c(-(-1)^n)2^{1-n}} $$ where $c$ is a parameter depending on $x_0$, so that $x_n\to21^{1/3}$ no matter what $x_0>0$ we choose. However, in practice, I have no idea how to solve this type of recurrence relation...


This is a bit problem-specific, but this trick appears to work. Suppose $x_0=a 21^{1/3}$ for some $a>0$. Then $x_1=21^{1/2} a^{-1/2} 21^{-1/6}=a^{-1/2} 21^{1/3}$. Can you now solve the recurrence by induction? What does your solution tell you?

As for trying to do something more general, I think you might be able to show that if $f$ is $C^1$, decreasing, convex, has a fixed point, and its derivative is bigger than $-1$ at its fixed point, then the fixed point iteration will spiral inward toward the root. The idea of that would be to show that the even and odd subsequences are bounded and monotone.

  • 1
    $\begingroup$ Yes I think I can solve the recurrence by induction now: $x_n=a^{(-\frac{1}{2})^n}21^{1/3}$ so that $x_n\to a^0 21^{1/3}=21^{1/3}$. Since $a>0$ was arbitrary, so was $x_0>0$. Very clever. $\endgroup$ – Guest Oct 23 '15 at 1:14

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.