Order of convergence of false position method is the golden ratio.

Question

I'm reading about the order of convergence of the method of false position and there is one tricky point in the proof I don't understand. The method itself for finding the minimum $x^*$ of a function $f(x)$ is:

$$x_{k+1} = x_k-g(x_k)\left[ \frac{x_k-x_{k-1}}{g(x_k)-g(x_{k-1})} \right],$$

where $g(x) := f'(x)$. The proposition is the following:

Proposition:

Let $g$ have a continuous second derivative and suppose $x^*$ is such that $g(x^*)=0, g'(x^*)\neq 0$. Then for $x_0$ sufficiently close to $x^*$, the sequence $\{x_k\}_{k=0}^{\infty}$ generated by the method of false position above converges to $x^*$ with order $\tau_1 \simeq 1.618$, which is the golden mean.

In the following I have written the proof from the part I start having troubles:

Defining $\epsilon = x_k-x^*$ we have, in the limit ($k\rightarrow \infty$),

$$\epsilon_{k+1} = M\epsilon_{k}\epsilon_{k-1},\;\;\;\;\;\;(1)$$

where $\displaystyle M=\frac{g''(x^*)}{2g'(x^*)}$. Taking logarithm of both sides of $(1)$, we have with $y_k = \log M\epsilon_{k}$,

$$y_{k+1} = y_k + y_{k-1},\;\;\;\;\;\;(2)$$

which is the Fibonacci difference equation. A solution to this equation will satisfy

$$y_{k+1}-\tau_1y_k \rightarrow 0.\;\;\;\;\;\;(3)$$

Thus

$$\log M\epsilon_{k+1}-\tau_1\log M\epsilon_{k}\rightarrow 0$$

or

$$\log \frac{M\epsilon_{k+1}}{(M\epsilon_k)^{\tau_1}} \rightarrow 0,$$

and hence

$$\frac{\epsilon_{k+1}}{\epsilon_{k}^{\tau_1}} \rightarrow M^{\tau_1 -1 }. \blacksquare$$

This is taken from: Linear and Nonlinear programming, 3rd edition by David Luenberger, page 224.

My questions:

1. How did $(2)$ follow from $(1)$?

2. Explanation for $(3)$?

My try:

If I take the logarithm of $(1)$ myself I get:

$$\log \epsilon_{k+1}=\log M\epsilon_k + \log\epsilon_{k-1},$$

so what am I doing wrong here?...

Thank you for any help!

Answer 1

This is for part A. Multiply the equation with M:

$$\epsilon_{k+1} = M\epsilon_{k}\epsilon_{k-1}$$ $$\Longrightarrow M\epsilon_{k+1} = (M\epsilon_{k})(M\epsilon_{k-1})$$ $$\Longrightarrow \log\left(M\epsilon_{k+1}\right) = \log\left((M\epsilon_{k})(M\epsilon_{k-1})\right)$$ Apply the functional equation for the $\log$ of a product $$\Longrightarrow \log\left(M\epsilon_{k+1}\right) = \log(M\epsilon_{k})+\log(M\epsilon_{k-1})$$ and substitute the definition of $y_k$ $$\Longrightarrow y_{k+1} = y_{k}+y_{k-1}$$