Editing Newton's method (section)

===Divergence even when initialization is close to the root===

Consider the problem of finding a root of {{math|''f''(''x'') {{=}} ''x''<sup>1/3</sup>}}. The Newton iteration is
:<math>x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-\frac{x_n^{1/3}}{\frac{1}{3}x_n^{-2/3}}=-2x_n.</math>
Unless Newton's method is initialized at the exact root 0, it is seen that the sequence of iterates will fail to converge. For example, even if initialized at the reasonably accurate guess of 0.001, the first several iterates are −0.002, 0.004, −0.008, 0.016, reaching 1048.58, −2097.15, ... by the 20th iterate. This failure of convergence is not contradicted by the analytic theory, since in this case {{mvar|f}} is not differentiable at its root.

In the above example, failure of convergence is reflected by the failure of {{math|''f''(''x''<sub>''n''</sub>)}} to get closer to zero as {{mvar|n}} increases, as well as by the fact that successive iterates are growing further and further apart. However, the function {{math|''f''(''x'') {{=}} ''x''<sup>1/3</sup>e<sup>−''x''<sup>2</sup></sup>}} also has a root at 0. The Newton iteration is given by
:<math>x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n\left(1-\frac{3}{1-6x_n^2}\right).</math>
In this example, where again {{mvar|f}} is not differentiable at the root, any Newton iteration not starting exactly at the root will diverge, but with both {{math|''x''<sub>''n'' + 1</sub> − ''x''<sub>''n''</sub>}} and {{math|''f''(''x''<sub>''n''</sub>)}} converging to zero.<ref name="judd">Kenneth L. Judd. Numerical methods in economics. MIT Press</ref> This is seen in the following table showing the iterates with initialization 1:
{| class=wikitable style="border: none;"
! scope=col | {{math|''x''<sub>''n''</sub>}}
! scope=col | {{math|''f''(''x''<sub>''n''</sub>)}}
|-
| 1 || 0.36788
|-
| 1.6 || 9.0416 × 10<sup>−2</sup> 
|-
| 1.9342 || 2.9556 × 10<sup>−2</sup>
|-
| 2.2048 || 1.0076 × 10<sup>−2</sup>
|- 
| 2.4396 || 3.5015 × 10<sup>−3</sup>
|-
| 2.6505 || 1.2307 × 10<sup>−3</sup> 
|-
| 2.8437 || 4.3578 × 10<sup>−4</sup>
|-
| 3.0232 || 1.5513 × 10<sup>−4</sup>
|}

Although the convergence of {{math|''x''<sub>''n'' + 1</sub> − ''x''<sub>''n''</sub>}} in this case is not very rapid, it can be proved from the iteration formula. This example highlights the possibility that a stopping criterion for Newton's method based only on the smallness of {{math|''x''<sub>''n'' + 1</sub> − ''x''<sub>''n''</sub>}} and {{math|''f''(''x''<sub>''n''</sub>)}} might falsely identify a root.