I'm having some trouble understanding the following:
The point of this exercise is to computationally approximate a value for $\sqrt 5$. My textbook does the following:
$\sqrt 5$ is the solution of the equation:
$$x^2 = 5$$
This can be re-written as:
$$x = \frac{5}{x}$$
So we can analyse the dynamical discrete system: $$y_{n+1} = \frac{5}{y_n}\tag 1$$
and try to find the fixed point.
It is easy to notice that, for any starting value, $y_0 \neq \sqrt{5}$, we will be stuck in a cycle with period $2$:
$$\left\{ y_0, \frac{5}{y_0}, y_0, \frac{5}{y_0},... \right\}$$
So, to escape that cycle, we can use the mid-point:
$$y_{n+1} = \frac{1}{2} \left( y_n + \frac{5}{y_n}\right) \tag 2$$
And then they set the initial condition as $y_0 = 1$ and compute $y_7=2.23606797749979$ using Maxima, so they conclude that $$\sqrt 5 \simeq2.23606797749979$$
My question is: I don't quite understand what they mean by "using the mid-point" and why that would work. I also don't understand how they got $(2)$ and how we can find the fixed point of $(1)$ by finding one in $(2)$. Thank you.
When they say "use the midpoint," they are treating each $y_n$ as an estimate of $\sqrt{5}$, and so in order to avoid the periodicity, they are attenuating the movement toward the next estimate $y_{n+1}$ by averaging the previous estimate with the next. So if the original recursion was $y_{n+1} = 5/y_n$, then we can reduce this oscillatory behavior by instead choosing $$y_{n+1} = \frac{y_n + \frac{5}{y_n}}{2}.$$ That's the basic idea. Of course, one does not need to choose the midpoint; we can choose some other weighting, but in this case, the midpoint is very efficient.
Now let's look at a numeric example in action. Consider the original recursion, with the initial choice $y_1 = 2$. Then $$y_2 = \frac{5}{2}, \quad y_3 = 2, \quad y_4 = \frac{5}{2}, \ldots.$$ So the forward orbit bounces between $\{2, 2.5\}$. The real value of $\sqrt{5}$ being somewhere in between, this motivates the attenuation of the recursion relation in such a way that it doesn't "overshoot" so much. So if we remember that $5/y_n = y_n$ is the condition that our $n^{\rm th}$ estimate is supposed to satisfy, then averaging these two things should achieve the desired attenuation of the overshooting phenomenon, and indeed it does: $$y_1 = 2, \\ y_2 = \frac{2 + \frac{5}{2}}{2} = \frac{9}{4} = 2.25, \\ y_3 = \frac{\frac{9}{4} + \frac{5}{9/4}}{2} = \frac{161}{72} \approx 2.23611, \\ y_4 = \frac{\frac{161}{72} + \frac{5}{161/72}}{2} = \frac{51841}{23184} \approx 2.23607,$$ and so forth.
It is worth playing around with the weighting as we alluded to earlier. Consider the generalized recursion $$y_{n+1} = (1 - \lambda) y_n + \lambda \frac{5}{y_n}, \quad 0 \le \lambda \le 1.$$ Then the case $\lambda = 1/2$ is the midpoint method we have already discussed, and $\lambda = 1$ is the original recursion that exhibits periodic behavior. Of course, $\lambda = 0$ is the trivial identity recurrence where every point is its own fixed point.
So what we can intuitively see is that for values of $\lambda$ "close to" $0$, we become increasingly resistant to updating our previous guess, and when $\lambda$ is "close to" $1$, we become very "trusting" of $5/y_n$ as the next estimate. Try fixing an initial guess $y_1$ and then seeing what happens to the sequence of iterates for varying choices of $\lambda$. For what subset of the interval $\lambda \in (0,1)$ does the sequence become strictly increasing for the initial guess $y_1 = 2$?