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:
-
How did $(2)$ follow from $(1)$?
-
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!
Best Answer
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}$$