I've been studying on some root finding techniques including The Bisection Method, False Position, The Secant Method and Newton-Raphson Method.
I've seen proof of convergence for all of these techniques (under some assumptions on the functions of which we desire to find roots) except for the Secant Method.
I've seen proofs that shows that under the assumption that the technique does converge, it can be proved that the convergence is of linear order. However I wish to know under what assumption could we insure convergence of this method.
Thanks in advance!
Following this answer to a related question we have $$ e_{n+1} = e_n e_{n-1} \frac{f[x_{n-1},x_n,\xi]}{f[x_{n-1},x_n]}$$ where $\xi$ is the zero and $e_k = \xi - x_k$ is the error at the $k$th iteration. We want to achieve a net reduction in the size of the error, hence our goal should be to ensure that $$ \left | e_{n-1} \frac{f[x_{n-1},x_n,\xi]}{f[x_{n-1},x_n]} \right| \leq \lambda < 1$$ for some fixed $\lambda \in [0,1)$ so that the sequence will converge at least linearly. To that end, we shall deploy the mean value theorem for divided differences. Specifically, if $f$ is $C^2(\mathbb{R},\mathbb{R})$, there is at least one $\theta_n$ in the smallest interval containing $x_{n-1}, x_n, \xi$ such that $$ f[x_{n-1},x_n,\xi] = \frac{1}{2} f''(\theta_n)$$ and there is at least one $\nu_n$ between $x_{n-1}$ and $x_n$ such that $$ f[x_{n-1},x_n] = f'(\nu_n).$$ We see that in order to achieve our goal, we must gain control of the term $$\frac{1}{2} \frac{f''(\theta_n)}{f'(\nu_n)}.$$ One way to do this to first consider an arbitrary $\delta > 0$ and define $$M_\delta = \sup \left \{ \frac{1}{2} \left| \frac{f''(x)}{f'(y)}\right| \: : \: (x,y) \in [\xi-\delta,\xi+\delta]^2 \right \}. $$ It is easy to see that if $f$ is $C^2(\mathbb{R},\mathbb{R})$ and if $f'(\xi) \not = 0$, then $M_\delta$ is well-defined for $\delta$ sufficiently small and $$ M_\delta \rightarrow \frac{1}{2} \left| \frac{f''(\xi)}{f'(\xi)} \right|, \quad \delta \rightarrow 0, \quad \delta > 0.$$ Now choose $\delta$ so small that $$ \delta M_\delta < 1$$ and define $\lambda = \delta M_\delta$. Now choose $x_{0}, x_1 \in [\xi-\delta, \xi+\delta]$, then $|e_0| \leq \delta$ and $$|e_2| \leq |e_1| \delta M_{\delta} \leq |e_1| \lambda < |e_1| \leq \delta.$$ We conclude that $x_2 \in [\xi-\delta, \xi+\delta]$, and this observation allows us to proceed inductively and show that the sequence does not leave the interval $[\xi-\delta, \xi+\delta]$ and $$|e_{n+1}| \leq \lambda^n |e_1|.$$ This show that the secant method converges and that the order of convergence is at least linear. We assumed that $f$ is $C^2(\mathbb{R},\mathbb{R})$, that $f'(\xi) \not = 0$, that $\delta M_\delta < 1$ and that $\xi - \delta \leq x_0, x_1 \leq \xi + \delta$ to achieve this result.