1
$\begingroup$

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!

$\endgroup$
7
  • 1
    $\begingroup$ Normally, the order of convergence for the secant method is the golden ratio or approximately 1.6. This is significantly faster then linear convergence. $\endgroup$ Commented Dec 19, 2022 at 16:38
  • 1
    $\begingroup$ I vaguely remember once doing a proof that the secant method converges if both initial points are inside the region of quadratic convergence of the Newton method. Outside such a region you have the same problems as in the global convergence of Newton's method, perhaps even a little bit worse as the two support points of the current secant can also diverge from each other. $\endgroup$ Commented Dec 19, 2022 at 18:06
  • $\begingroup$ @LutzLehmann I have not been able to understand what you meant when you wrote that the two support point of the current secant can diverge from each other. Would you add a few words about this? $\endgroup$ Commented Dec 20, 2022 at 22:05
  • 1
    $\begingroup$ I mean the two current points that the secant is computed for that gives the next iteration point as its root. If the secant is nearly horizontal so that the next iteration point is far away, then the next after that need not be close to any of the last two points. $\endgroup$ Commented Dec 20, 2022 at 22:43
  • $\begingroup$ @LutzLehmann Now I understand what you meant. My thanks. $\endgroup$ Commented Dec 21, 2022 at 0:31

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ It is worth noting that this proof is exceedingly similar to the analysis of Newton's method. See this answer $\endgroup$ Commented Dec 21, 2022 at 14:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .