Convergence of Bisection, Secant and Newton's method when there is no root

Question

If there is no root to a function can the bisection, secant or Newton's method still converge to some number e.g. $f(x) = \frac{1}{x}$ on interval $[-1,1]$?

Answer 1

Just try them. Bisection and secant fail because they want to evaluate $f(0)$ on the first step. This happens because of the symmetry of the problem. For Newton, you work from just one point. If you start by evaluating at the center of the interval, you have the same problem.

If you apply them to $g(x)=\frac 1{x+\frac 1\pi}$ bisection and secant will converge nicely to the discontinuity, assuming that for the secant method you maintain your bracket by replacing the old point where the function value has the same sign as the new point. The methods cannot tell this $g(x)$ with its discontinuity at $-\frac 1\pi$ from a function that is continuous, following $g(x)$ to the computer real just below $-\frac 1\pi$, then dropping to hit $g(x)$ at the real just above $-\frac 1\pi$. I didn't try Newton, but would expect it to go off to infinity, looking for the root that is "there".

Answer 2

Can the algorithms know as bisection, the secant method or Newton's method converge when there is no root? Under very mild assumptions the answer is always no.

Specifically, if an algorithm converges, then there is a root. Equivalently, if there is no root, none of the algorithms can converge.

Analysis: We will assume that $f : I \rightarrow \mathbb{R}$ for some close and bounded interval $I$, say, $I = [0,1]$.

Newton's method takes the form $$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.$$ Suppose the sequence $\{x_n\}_{n=0}^\infty$ is defined and converges to some finite value $x \in I$. Now $f$ is continuous because we have implicitly assumed that $f$ is differentiable because we need the derivative in order to apply Newton's method. If $f'$ is also continuous with $f'(x) \not = 0$, then we can conclude that $$ x = x - \frac{f(x)}{f'(x)}$$ or equivalently that $f(x) = 0$. We simply exploit the fact that $$x_{n+1} \rightarrow x, \quad f(x_n) \rightarrow f(x), \quad f'(x_n) \rightarrow f'(x)$$ as $n$ tends to infinity.

The secant method takes the form $$ x_{n+1} = x_n - f(x_n) \left( \frac{f(x_n) - f(x_{n-1})}{x_n - x_{n-1}} \right)^{-1}$$ Suppose the sequence $\{x_n\}_{n=0}^\infty$ is defined and converges to some finite value $x \in I$. If $f$ is differentiable and $f'$ is continuous with $f'(x) \not = 0$, then the previous reasoning still applies and we can still conclude that $f(x) = 0$. We use the mean value theorem to write $$ \frac{f(x_n) - f(x_{n-1})}{x_n - x_{n-1}} = f'(\xi_n)$$ for at least one $\xi_n$ between $x_n$ and $x_{n-1}$, and since $\xi_n \rightarrow x$ by the squeeze lemma, we have $f'(\xi_n) \rightarrow f'(x)$, but this is the only difference.

Finally, suppose the bisection algorithm has produces an infinite sequence of intervals $\{[a_n,b_n]\}_{n=0}^\infty$. By design, we have $b_n - a_n = 2^{-n} (b_0-a_0)$. It follows that the sequence of left endpoints and the sequence of right endpoints are both convergent to the same limit, call it $c$. Moreover, we have $f(a_n) f(b_n) < 0$. If $f$ is continuous, then it follows that $$ f(a_n) f(b_n) \rightarrow f(c)^2 \leq 0, \quad n \rightarrow \infty.$$ We conclude that $f(c) = 0$.

If the bisection algorithm terminates after a finite number of steps, then one of the endpoints of the final interval is a root and there is nothing to show.