6
$\begingroup$

I'm currently working on Newton's Method, and my instructor gave four instances where Newton's Method will fail.

(A) Newton's method converges to another solutions x=b such that f(b)=0 instead of converging to the desired solution x=a.

(B) Newton's method eventually gets into the never ending cycle, bouncing between the same two approximations $x_i$ and $x_{i+1}$.

(C) Eventually, each next approximation $x_{i+1}$ falls further from desired solution $x_a$ than the previous approximation $x_i$ determined by the Newton's method.

(D) Newton's method is not able to find the next approximation $x_{i+1}$ because f'($x_i$)=0 or f'($x_i$) Does Not Exist.

However, there aren't any examples of when this happens. Would anyone be willing to provide examples of these instances?

$\endgroup$

3 Answers 3

10
$\begingroup$

Example for Case (A): $$f(x) = \frac{1}{1+x^2} - \frac{1}{2},$$ which has roots at $x \in \{-1,1\}$. The initial choice $x_0 = 2$ converges to the negative root.

Example for Case (B): $$f(x) = \begin{cases}\sqrt{x}, & x \ge 0 \\ -\sqrt{-x}, & x < 0 \end{cases}$$ has the peculiar property that for any initial guess $x_0 \ne 0$, the orbit is trapped in a cycle of period $2$, with $x_k = -x_{k-1}$. This is quite easy to prove and is left as an exercise for the reader.

Example for Case (C): $$f(x) = x^{1/3}.$$ The Newton's method recursion has no fixed point except for the initial guess $x_0 = 0$.

$\endgroup$
4
$\begingroup$

For $A$, suppose you have a function with multiple zeros like $f(x) = \sin x$. Depending on your starting point, you will see that you could converge to any of the roots ($x = n\pi$), even if you want it to converge to a particular $x = \pi$ for example - say you start with $x_0 = 7\pi / 4$

For $B$, imagine a function whose gradient is very sharp - almost vertical. Then there is a chance that the tangent will cut at a point beyond the root, and then when you repeat at the new point, it will come back to the original point (Something like $f(x) = \arctan x$ at $x = 0$)

For $C$, if your starting point is too close to a stationary point, the next point is very far away, and will keep pushing the point further and further from the root

$\endgroup$
4
  • $\begingroup$ When you say too close to a stationary point, does that mean too close to another root? $\endgroup$ Dec 16, 2020 at 5:37
  • $\begingroup$ No, a point where $f'(x) = 0$ $\endgroup$ Dec 16, 2020 at 6:01
  • $\begingroup$ Sorry, I added in another instance that I forgot to put in. Would you mind looking at it? $\endgroup$ Dec 16, 2020 at 6:26
  • $\begingroup$ $f(x) = x^2 +1$ :) $\endgroup$ Dec 16, 2020 at 9:54
3
$\begingroup$

(A) $f(x) = x^2-1$ and start near $x=-1$ when you 'want' $x=1$.

(B) $f(x) = \sqrt{1+x^2}$ and start at $x=1$.

(C) $f(x) = \arctan x$ and $x_0>2$ (needs a little work to show that the Newton iteration diverges).

(D) $f(x) = x^3-1$ with $x_0 = 0$.

$\endgroup$
2
  • $\begingroup$ Why the downvote? $\endgroup$
    – copper.hat
    Dec 20, 2020 at 17:32
  • $\begingroup$ @LutzLehmann The first example was missing a $-1$, the second was to illustrate the Newton iteration bouncing between the same two approximations. $\endgroup$
    – copper.hat
    Mar 25, 2021 at 16:22

You must log in to answer this question.

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