Is it possible to construct a Newton sequence $x_{n+1} := x_{n} - f(x_n)/f'(x_{n})$ such that $\{x_{n}\}$ is a Cauchy sequence converging to $x^*$, but $x^{*}$ is not a root of $f$? (Perhaps because $f$ has no roots?)
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
It is not possible if we assume that $x^\star$ lies in the domain of definition of $f$ and that $f$ and $f'$ are continuous at that point. For a counterexample where $f'$ is not continuous at $x^\star$ see the nice answer by Oscar Lanzi.
In my setting we use $$ f(x_n) = f'(x_n) (x_n - x_{n+1}) $$ and take the limit (I assume $f'$ to be continuous at $x^*$).
If we take the limit in the equation above we get (using the continuity of $f'$ and $f$ at $x^\star$) $$ f(x^\star) = f(\lim_{n\rightarrow \infty} x_n) = \lim_{n\rightarrow \infty} f(x_n) = \lim_{n\rightarrow \infty} f'(x_n) (x_n - x_{n+1}) = \lim_{n\rightarrow \infty} f'(x_n) \cdot \lim_{n\rightarrow \infty} (x_n - x_{n+1}) = f'(x^\star) \cdot (x^\star - x^\star) = 0.$$
answered Nov 28, 2018 at 21:59
-
$\begingroup$ It looks like this can be weakened from "continuous derivative" to "derivative exists and is bounded in a neighborhood of $x^{*}$". $\endgroup$ Nov 28, 2018 at 22:39
-
$\begingroup$ Indeed, we could do that. But I like to have some a priori regularity (I love my $C^1$-functions) :) $\endgroup$ Nov 28, 2018 at 22:44
$\begingroup$
$\endgroup$
8
Try this function:
$f(x)=\max(1-\sqrt{|x|},|x|)$
For most initial guesses, and for all initial guesses more than one-half in absolute value, you converge to zero. But the function has no real zeroes.
answered Nov 28, 2018 at 22:00
-
$\begingroup$ That sounds interesting. Is it easy to see that it converges indeed to zero? $\endgroup$ Nov 28, 2018 at 22:10
-
1$\begingroup$ Truly fabulous example. Both of the answers given are required for full understanding, so I'm accepting @SeverinSchraven's answer as accepted (because it looks like Oscar is well beyond the range of caring about the point system). $\endgroup$ Nov 28, 2018 at 22:20
-
$\begingroup$ I'm now wondering if a more classical derivative discontinuity can cause the problem; say $f'$ has a pole at $x^{*}$ but $f$ still the restriction to the real line of a meromorphic function. $\endgroup$ Nov 28, 2018 at 22:25
-
$\begingroup$ In fact, I am not sure you can say this converges to zero. If you start in the range of the absolute value you are in one step at zero, but there the scheme fails to work, as you have no derivative there. $\endgroup$ Nov 28, 2018 at 22:37
-
$\begingroup$ @SeverinSchraven: The question was intentionally ambiguous regarding the function spaces--defining the function space is half the fun. $\endgroup$ Nov 28, 2018 at 22:41
$\begingroup$
$\endgroup$
An idea to construct such a function $f(x)$:
First, find a sequence $\{ x_n \}$ increasingly convergent to $x^*$. Let $f(x_n)=1$ and $f(x^*)=1$. (This $\{x_n\}$ will be the sequence found by the newton method's iteration, and the point $x^*$ will be the converging point which is not a root of $f(x)$)
Second, linearly connect point $(x_n,f(x_n))$ and $(x_{n+1},0)$ and take a small enough neighbor for each $x_n$ as a part of function $f(x)$. (This step makes newton method iterate from $x_n$ to $x_{n+1}$)
Third, smoothly connect the neighbors of $x_n$s.
Note: when the neighbors are small enough the value of $\frac{f(x^*)-f(x)}{x^*-x}$ in the neighbor can be arbitrary small and therefore we can construct the function $f(x)$ be differentiable at $x^*$ as well.
