1

enter image description here

This image was taken from this youtube video https://www.youtube.com/watch?v=OLqdJMjzib8

Since only one of them converges, how do we know in advance which formula to work with?

stackdsewew
  • 1,047
  • They are just guesses that they came up with. I imagine $1.6$ was chosen for the second one to emphasize that the second method doesn't converge even when you pick an initial guess which is quite close to the desired solution. As for knowing what to use, you can't; there is no 100% general recipe for fixed point iterations. (Newton's method is a very powerful type of fixed point iteration but it too has its limitations.) – Ian Apr 28 '16 at 01:29
  • 2
    For knowing what not to use, you can use the main theorem about fixed point iteration: fixed point iteration converges locally provided the iteration function has a derivative which is less than $1$ in magnitude at the solution. This can easily inform you that you should not use the second method as soon as you know that the solution is less than $2$. It will also inform you that the first method will work, but it would not tell you how to come up with it in the first place. – Ian Apr 28 '16 at 01:30

2 Answers2

2

It's know that the FPI $x^{t+1} = g(x^{t})$ where $g$ is continuously differentiable, will converge (locally) to the fixed point $r = g(r)$, iff $\ |g'(r)| < 1$.

In your case, the first FPI has $g(x)=1 + \frac{1}{x} \rightarrow g'(x) = \frac{-1}{x^2}$, and evaluating it at $r=1.6\ldots$ gives $|g'(r)|<1$. In the second case $g(x)=\frac{1}{x-1} \rightarrow g'(x)=\frac{-1}{(x-1)^2}$ and $|g'(r)| = \left|\frac{-1}{0.6\ldots^2}\right|>1$.

mavillan
  • 483
  • 3
  • 13
1

It's all about contracting intervals.

If the image of an interval is a subinterval, you are sure to stay confined in the subinterval. If in addition the subinterval shrinks are every iteration by a factor smaller than one, you are sure to converge.

For instance, $f(x)=1+\dfrac1x$ maps $[1,2]$ to $[\dfrac32,2]$, then $[\dfrac32,2]$ to $[\dfrac32,\dfrac53]$, and so on. You can check that the interval size is more than halved every time, so that starting from any value in $[1,2]$ you will converge.

Close to the solution we have $$f(\phi+\epsilon)=1+\dfrac1{\phi+\epsilon}\approx1+\dfrac1\phi(1-\dfrac\epsilon\phi)=\phi-\dfrac\epsilon{\phi^2},$$ which shows that the contraction ratio is about $\phi^2$.

On the opposite, with $f(x)=\dfrac1{x-1}$, the size of the intervals goes growing.

$$f(\phi+\epsilon)=\frac1{\phi+\epsilon-1}\approx\frac1{\phi-1}(1-\frac\epsilon{\phi-1})=\phi-\frac\epsilon{(\phi-1)^2}$$ and there is an expansion ratio equal to $\dfrac1{(\phi-1)^2}=\phi^2$, and convergence isn't possible.

As you see, a key factor is the slope of the curve at the solution point, as $$f(\phi+\epsilon)\approx f(\phi)+f'(\phi)\epsilon=\phi+f'(\phi)\epsilon.$$