4
$\begingroup$

I'm currently working on Newton's Method, and my instructor gave three 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$
6
$\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 '20 at 5:37
  • $\begingroup$ No, a point where $f'(x) = 0$ $\endgroup$ Dec 16 '20 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 '20 at 6:26
  • $\begingroup$ $f(x) = x^2 +1$ :) $\endgroup$ Dec 16 '20 at 9:54
2
$\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 '20 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 '21 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.