§Recap

§Convergence Order

For some iteration algorithm $x^{(t+1)}=g\left( x^{(t)} \right)$ with final solution denoted $x^*$, error $\varepsilon ^{(t)}:=x^{(t)}-x^*$, its convergence order $\alpha$ and converngence rate $c$:

$$\begin{align} \lim_{t\to\infty}\dfrac{|\varepsilon ^{(t+1)}|}{|\varepsilon ^{(t)}|^\alpha }=c \end{align}$$

§Secant Interpolation for Rooting:

In rooting $f(x)$, with initial points $x^{(-1)}$, $x^{(0)}$ set, root of secant interpolation in each step $(t)$ is:

$$\begin{align} x^{(t+1)}=\dfrac{x^{(t-1)}f\left( x^{(t)} \right)-x^{(t)}f\left( x^{(t-1)} \right)}{f\left( x^{(t)} \right)-f\left( x^{(t-1)} \right)} \end{align}$$

§Deduction:

Taylor series of $f(x)$ at $x^*$ to the second order is:

$$\begin{align} f(x)=f'(x^{*})(x-x^{*})+\dfrac{1}{2}f''(x^{*})\left(x-x^{*}\right)^2 \end{align}$$

substitute in secant rooting

$$\begin{align} x^{(t+1)}=\dfrac{x^{(t-1)}f(x^{(t)})-x^{(t)}f(x^{(t-1)})}{f(x^{(t)})-f(x^{(t-1)})} \end{align}$$

to obtain

$$\begin{align} x^{(t+1)}-x^*=&\dfrac{x^{(t-1)}f(x^{(t)})-x^{(t)}f(x^{(t-1)})}{f(x^{(t)})-f(x^{(t-1)})} -x^*\\ =&\dfrac{\left( f'x^*(x^{(t)}-x^*)+\frac{1}{2}f''(x^*)(x^{(t)}-x^*)^2 \right)(x^{(t-1)}-x^*)}{f'(x^*)(x^{(t)}-x^{(t-1)})-\frac{1}{2}f''(x^*)(x^{(t)}-x^{(t-1)})(x^{(t)}+x^{(t-1)}-2x^*)}\\ &- \dfrac{\left( f'x^*(x^{(t-1)}-x^*)+\frac{1}{2}f''(x^*)(x^{(t-1)}-x^*)^2 \right)(x^{(t)}-x^*)}{f'(x^*)(x^{(t)}-x^{(t-1)})-\frac{1}{2}f''(x^*)(x^{(t)}-x^{(t-1)})(x^{(t)}+x^{(t-1)}-2x^*)} \\ =&\dfrac{\frac{1}{2}f''(x^*)(x^{(t)}-x^*)(x^{(t-1)}-x^*)}{f'(x^*)-\frac{1}{2}f''(x^*)(x^{(t)}+x^{(t-1)}-2x^*)}\\ \end{align}$$

Denote $e^{(t)}\equiv x^{(t)}-x^*$, take $t\to\infty$ to obtain

$$\begin{align} \dfrac{e^{(t+1)}}{e^{(t)}e^{(t-1)}}=\dfrac{f''(x^*)}{2f'(x^*)-f''(x^*)(e^{(t)}+e^{(t-1)})}\to \dfrac{f''(x^*)}{2f'(x^*)} \end{align}$$

Denote $e^{(t-1)}\equiv a$. We could first assume convergence order $\alpha$ and convergence rate $c$, then

$$\begin{align} \lim_{t\to\infty}\dfrac{e^{(t+1)}}{[e^{(t)}]^\alpha }= \lim_{t\to\infty}\dfrac{e^{(t)}}{[e^{(t-1)}]^\alpha }=c\Rightarrow e^{(t+1)}=c^\alpha a^{\alpha^2},\quad e^{(t)}=ca^\alpha \end{align}$$

substitute into the iteration of error

$$\begin{align} \dfrac{e^{(t+1)}}{e^{(t)}e^{(t-1)}}=\lambda ^{\alpha -1}a^{\alpha ^2-\alpha -1} =\dfrac{f''(x^*)}{2f'(x^*)}=\mathrm{const} \end{align}$$

Considering that $\lim_{t\to\infty}e^{(t-1)}=0$, there must be ${\alpha ^2-\alpha -1} =0$, thus

$$\begin{align} \alpha=\frac{\sqrt{5}+1}{2}\approx 1.618 \end{align}$$