Editing Newton's method (section)

==Examples==
===Use of Newton's method to compute square roots===
Newton's method is one of many known [[methods of computing square roots]]. Given a positive number {{mvar|a}}, the problem of finding a number {{mvar|x}} such that {{math|''x''<sup>2</sup> {{=}} ''a''}} is equivalent to finding a root of the function {{math|''f''(''x'') {{=}} ''x''<sup>2</sup> − ''a''}}. The Newton iteration defined by this function is given by
:<math>x_{n+1} = x_n-\frac{f(x_n)}{f'(x_n)} = x_n-\frac{x_n^2-a}{2x_n} = \frac{1}{2}\left(x_n+\frac{a}{x_n}\right).</math>
This happens to coincide with the [[Methods of computing square roots#Heron's method|"Babylonian" method of finding square roots]], which consists of replacing an approximate root {{math|''x''<sub>''n''</sub>}} by the [[arithmetic mean]] of {{math|{{var|x}}{{sub|{{var|n}}}}}} and {{math|{{frac|{{var|a}}|{{var|x}}{{sub|{{var|n}}}}}}}}. By performing this iteration, it is possible to evaluate a square root to any desired accuracy by only using the basic [[arithmetic operations]].

The following three tables show examples of the result of this computation for finding the square root of 612, with the iteration initialized at the values of 1, 10, and −20. Each row in a "{{math|''x''<sub>''n''</sub>}}" column is obtained by applying the preceding formula to the entry above it, for instance
:<math>306.5 = \frac{1}{2} \left( 1+\frac{612}{1} \right).</math>

{| class=wikitable style="border: none;"
! scope=col | {{math|''x''<sub>''n''</sub>}}
! scope=col | {{math|''f''(''x''<sub>''n''</sub>)}}
| rowspan=7 style="border: none;"|
! scope=col | {{math|''x''<sub>''n''</sub>}}
! scope=col | {{math|''f''(''x''<sub>''n''</sub>)}}
| rowspan=6 style="border: none;"|
! scope=col | {{math|''x''<sub>''n''</sub>}}
! scope=col | {{math|''f''(''x''<sub>''n''</sub>)}}
|-
| 1 || −611 || 10 || −512 || <u>−2</u>0 || −212
|-
| 306.5 || 9.3330 × 10<sup>4</sup> || 35.6 || 655.36 || <u>−2</u>5.3 || 28.09 
|-
| 154.2483686786 || 2.3180 × 10<sup>4</sup> || <u>2</u>6.3955056180 || 84.722 || <u>−24.7</u>448616601 || 0.30818 
|-
| 79.1079978644 || 5.6461 × 10<sup>3</sup> || <u>24.7</u>906354925 || 2.5756 || <u>−24.73863</u>45374 || 3.8777 × 10<sup>−5</sup>
|- 
| 43.4221286822 || 1.2735 × 10<sup>3</sup> || <u>24.7386</u>882941 || 2.6985 × 10<sup>−3</sup> || <u>−24.7386337537</u> || 6.1424 × 10<sup>−13</sup>
|-
| <u>2</u>8.7581624288 || 215.03 || <u>24.738633753</u>8 || 2.9746 × 10<sup>−9</sup> || style="border-style:none;" | 
|-
| <u>2</u>5.0195385369 || 13.977
|-
| <u>24.7</u>402106712 || 7.8024 × 10<sup>−2</sup>
|-
| <u>24.738633</u>8040 || 2.4865 × 10<sup>−6</sup>
|-
| <u>24.7386337537</u> || 2.5256 × 10<sup>−15</sup>
|}

The correct digits are underlined. It is seen that with only a few iterations one can obtain a solution accurate to many decimal places. The first table shows that this is true even if the Newton iteration were initialized by the very inaccurate guess of {{math|1}}.

When computing any nonzero square root, the first derivative of {{mvar|f}} must be nonzero at the root, and that {{mvar|f}} is a smooth function. So, even before any computation, it is known that any convergent Newton iteration has a quadratic rate of convergence. This is reflected in the above tables by the fact that once a Newton iterate gets close to the root, the number of correct digits approximately doubles with each iteration.

=== Solution of {{math|1=cos({{var|x}}) = {{var|x}}{{sup|3}}}} using Newton's method ===
Consider the problem of finding the positive number {{mvar|x}} with {{math|1=cos {{var|x}} = {{var|x}}{{sup|3}}}}. We can rephrase that as finding the zero of {{math|1={{var|f}}({{var|x}}) = cos({{var|x}}) &minus; {{var|x}}{{sup|3}}}}. We have {{math|1={{var|{{prime|f}}}}({{var|x}}) = &minus;sin({{var|x}}) &minus; 3{{var|x}}{{sup|2}}}}. Since {{math|cos({{var|x}}) ≤ 1}} for all {{mvar|x}} and {{math|{{var|x}}{{sup|3}} > 1}} for {{math|{{var|x}} > 1}}, we know that our solution lies between 0 and 1. 

A starting value of 0 will lead to an undefined result which illustrates the importance of using a starting point close to the solution. For example, with an initial guess {{math|1={{var|x}}{{sub|0}} = 0.5}}, the sequence given by Newton's method is:

<math display="block">\begin{matrix}
 x_1 & = & x_0 - \dfrac{f(x_0)}{f'(x_0)} & = & 0.5 - \dfrac{\cos 0.5 - 0.5^3}{-\sin 0.5 - 3 \times 0.5^2} & = & 1.112\,141\,637\,097\dots \\
 x_2 & = & x_1 - \dfrac{f(x_1)}{f'(x_1)} & = & \vdots & = & \underline{0.}909\,672\,693\,736\dots \\
 x_3 & = & \vdots & = & \vdots & = & \underline{0.86}7\,263\,818\,209\dots \\
 x_4 & = & \vdots & = & \vdots & = & \underline{0.865\,47}7\,135\,298\dots \\
 x_5 & = & \vdots & = & \vdots & = & \underline{0.865\,474\,033\,1}11\dots \\
 x_6 & = & \vdots & = & \vdots & = & \underline{0.865\,474\,033\,102}\dots
\end{matrix}
</math>

The correct digits are underlined in the above example. In particular, {{math|{{var|x}}{{sub|6}}}} is correct to 12 decimal places. We see that the number of correct digits after the decimal point increases from 2 (for {{math|{{var|x}}{{sub|3}}}}) to 5 and 10, illustrating the quadratic convergence.