0
$\begingroup$

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]$?

$\endgroup$
3
  • $\begingroup$ @whpowell96 : bisection fails with "division by zero" in the first step, there will be no sequence to diverge. $\endgroup$ Aug 18, 2019 at 16:23
  • $\begingroup$ If we exclude 0 from the domain f: R\{0} then the function 1/x will be continuous. I think the bisection method will converge to zero but why? $\endgroup$
    – Maddie
    Aug 19, 2019 at 6:30
  • $\begingroup$ @Maddie: you are correct. As long as you avoid evaluating at the root and getting a divide by zero you converge to the discontinuity. Really what you are looking for is a sign change and the discontinuity provides that. In the computer you can't tell a function with a discontinuity from a continuous one that crosses the axis between two neighboring floating point numbers. $\endgroup$ Aug 21, 2019 at 21:00

2 Answers 2

2
$\begingroup$

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".

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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