Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Newton's method"

(Definition and derivation.)
 
Line 3: Line 3:
 
==Derivation==
 
==Derivation==
 
At each step of the recursion, we have <math>x_i</math> and seek a root of <math>f(x)</math>. Since all nonconstant [[Linear function|linear functions]] have exactly one root, as long as <math>f'(x_i) \neq 0</math> we can construct a [[Taylor polynomial#Tangent-line approximation|tangent-line approximation]] to <math>f(x)</math> and find its root as an approximation. The tangent-line approximation of <math>f(x)</math> about <math>x_i</math> is <cmath>f(x_i) + (x - x_i)f'(x_i).</cmath> We seek the value <math>x = x_{i+1}</math> such that the above expression equals <math>0</math>; hence, <cmath>f(x_i) + (x_{i+1} - x_i)f'(x_i) = 0.</cmath> Dividing by <math>f'(x_i)</math> (as long as <math>f'(x_i) \neq 0</math>), <cmath>\frac{f(x_i)}{f'(x_i)} + x_{i+1} - x_i = 0.</cmath>  Therefore, the desired value of <math>x_{i+1}</math> is <cmath>x_{i+1} = x_i - \frac{f(x_i)}{f'(x_{i})}.</cmath>
 
At each step of the recursion, we have <math>x_i</math> and seek a root of <math>f(x)</math>. Since all nonconstant [[Linear function|linear functions]] have exactly one root, as long as <math>f'(x_i) \neq 0</math> we can construct a [[Taylor polynomial#Tangent-line approximation|tangent-line approximation]] to <math>f(x)</math> and find its root as an approximation. The tangent-line approximation of <math>f(x)</math> about <math>x_i</math> is <cmath>f(x_i) + (x - x_i)f'(x_i).</cmath> We seek the value <math>x = x_{i+1}</math> such that the above expression equals <math>0</math>; hence, <cmath>f(x_i) + (x_{i+1} - x_i)f'(x_i) = 0.</cmath> Dividing by <math>f'(x_i)</math> (as long as <math>f'(x_i) \neq 0</math>), <cmath>\frac{f(x_i)}{f'(x_i)} + x_{i+1} - x_i = 0.</cmath>  Therefore, the desired value of <math>x_{i+1}</math> is <cmath>x_{i+1} = x_i - \frac{f(x_i)}{f'(x_{i})}.</cmath>
 +
 +
==Worked example==
 +
Problem: Find the values of the roots of <math>f(x) = x^2 - x - 1</math>.
 +
 +
Solution: We could use the [[quadratic formula]] to find that the roots are <math>\frac{1 \pm \sqrt 5}{2}</math>, but this approach does not immediately yield a decimal value.
 +
 +
To form a guess, we note that <math>\sqrt 5</math> is slightly larger than <math>2</math>, so a suitable guess for the greater root is <math>\frac{1 + 2}{2} = 1.5</math>.
 +
 +
The derivative of <math>x^2 - x - 1</math> is <math>2x - 1</math> by the [[Derivative/Formulas|power rule]] for derivatives. Therefore, the recursive formula is
 +
 +
<cmath>x_{i+1} = x_i - \frac{x_i^2 - x_i - 1}{2x_i - 1} = \frac{x_i^2 + 1}{2x_i - 1}.</cmath>
 +
 +
Starting at <math>x_0 = 1.5</math>, we apply this formula repeatedly:
 +
<cmath>\begin{align*} x_1 &= \frac{1.5^2 + 1}{2 * 1.5 - 1} &= 1.625, \\
 +
x_2 &= \frac{1.625^2 + 1}{2 * 1.625 - 1}  &= 1.6180556, \\
 +
x_3 &= \frac{1.6180556^2 + 1}{2 * 1.6180556 - 1} &= 1.6180340, \\
 +
x_4 &= \frac{1.6180340^2 + 1}{2 * 1.6180340 - 1} &= 1.6180340. \\ \end{align*}</cmath>
 +
 +
Because <math>x_4 = x_3</math> as calculated, the ratio <math>\frac{f(x_3)}{f'(x_3)}</math> must be very close to <math>0</math>. Since <math>f'(x_3) = 2.2360680</math> is not too large, <math>f(x_3)</math> must be quite close to <math>0</math>, so <math>x_3 = 1.6180340</math> is a very good estimate of the greater root.
 +
 +
The sum of the roots is <math>1</math> by [[Vieta's formulas]], so the lesser root is simply <math>1 - 1.6180340 = -0.6180340</math>.
 +
 +
==Failure cases==
 +
Although powerful, Newton's method is delicate and can be very sensitive to the initial guess and type of function, even when the function is differentiable everywhere.
 +
 +
===Zero derivative===
 +
 +
Suppose in the above example of finding a root of <math>x^2 - x - 1</math>, we had started with <math>x_0 = 0.5</math>. In the process of calculating <math>x_1</math>, then, we would have to divide by <math>f'(x_0) = 2x_0 - 1 = 0</math>, creating an undefined result.
 +
 +
===Wrong root===
 +
Suppose we try to estimate the greater root as before, but start with <math>x_0 = -0.5</math>. Applying Newton's method to <math>x^2 - x - 1</math> yields the following sequence of estimates:
 +
 +
<cmath>\begin{align*} x_1 &= \frac{-0.5^2 + 1}{2 * (-0.5) - 1} &= -0.625, \\
 +
x_2 &= \frac{(-0.625)^2 + 1}{2 * (-0.625) - 1}  &= -0.6180556, \\
 +
x_3 &= \frac{(-0.6180556)^2 + 1}{2 * (-0.6180556) - 1} &= -0.6180340, \\
 +
x_4 &= \frac{(-0.6180340)^2 + 1}{2 * (-0.6180340) - 1} &= -0.61803395. \\
 +
x_5 &= \frac{(-0.61803395)^2 + 1}{2 * (-0.61803395) - 1} &= -0.61803406. \\
 +
x_6 &= \frac{(-0.61803406)^2 + 1}{2 * (-0.61803406) - 1} &= -0.61803395. \\ \end{align*}</cmath>
 +
 +
These estimates converge to the lesser root, in this case because the initial estimate was closer to the lesser root than the greater root. In general, predicting which root Newton's method will finally converge to is difficult, and Newton's method may converge to a farther root even if a closer root is available within the interval between the initial estimate and the root.
 +
 +
===Periodic behavior without finding a root===
 +
When finding roots of <math>x^2 - x - 1</math> as above, the estimates eventually stabilize into a predictable pattern: in the <math>x_0 = 1.5</math> case, <math>x_4 = x_3</math>, so every subsequent estimate will equal <math>x_3</math>; in the <math>x_0 = -0.5</math> case, <math>x_6 = x_4</math>, so the subsequent estimates will oscillate, with every even estimate equal to <math>x_4</math> and every odd estimate equal to <math>x_5</math>. These behaviors are due to the limited precision of the calculations; with indefinite precision, the estimates would continue to approach the root without becoming periodic.
 +
 +
However, for some functions, Newton's method can cycle without coming close to a root.
 +
 +
===No root (divergent)===
 +
The function <math>f(x) = e^x</math> is always positive, so it has no roots. Attempting to apply Newton's method yields a divergent sequence: since <math>f(x) = e^x</math> satisfies the differential equation <math>f(x) = f'(x)</math> for all <math>x</math>, the ratio <math>\frac{f(x)}{f'(x)}</math> is always <math>1</math>, so the sequence of estimates becomes <math>x_{i+1} = x_i - 1</math>, diverging in the negative direction.
  
 
{{stub}}
 
{{stub}}
  
 
[[Category: Calculus]]
 
[[Category: Calculus]]

Revision as of 13:11, 24 April 2022

Newton's method uses the derivative of a differentiable function to approximate its real or complex roots. For a function $f(x)$, the approximations are defined recursively by \[x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}.\] To begin the recursion, an initial guess $x_0$ must be chosen. Often the choice of $x_0$ determines which of several possible roots is found, and in some cases the initial guess can cause the recursion to cycle or diverge instead of converging to a root.

Derivation

At each step of the recursion, we have $x_i$ and seek a root of $f(x)$. Since all nonconstant linear functions have exactly one root, as long as $f'(x_i) \neq 0$ we can construct a tangent-line approximation to $f(x)$ and find its root as an approximation. The tangent-line approximation of $f(x)$ about $x_i$ is \[f(x_i) + (x - x_i)f'(x_i).\] We seek the value $x = x_{i+1}$ such that the above expression equals $0$; hence, \[f(x_i) + (x_{i+1} - x_i)f'(x_i) = 0.\] Dividing by $f'(x_i)$ (as long as $f'(x_i) \neq 0$), \[\frac{f(x_i)}{f'(x_i)} + x_{i+1} - x_i = 0.\] Therefore, the desired value of $x_{i+1}$ is \[x_{i+1} = x_i - \frac{f(x_i)}{f'(x_{i})}.\]

Worked example

Problem: Find the values of the roots of $f(x) = x^2 - x - 1$.

Solution: We could use the quadratic formula to find that the roots are $\frac{1 \pm \sqrt 5}{2}$, but this approach does not immediately yield a decimal value.

To form a guess, we note that $\sqrt 5$ is slightly larger than $2$, so a suitable guess for the greater root is $\frac{1 + 2}{2} = 1.5$.

The derivative of $x^2 - x - 1$ is $2x - 1$ by the power rule for derivatives. Therefore, the recursive formula is

\[x_{i+1} = x_i - \frac{x_i^2 - x_i - 1}{2x_i - 1} = \frac{x_i^2 + 1}{2x_i - 1}.\]

Starting at $x_0 = 1.5$, we apply this formula repeatedly: \begin{align*} x_1 &= \frac{1.5^2 + 1}{2 * 1.5 - 1} &= 1.625, \\ x_2 &= \frac{1.625^2 + 1}{2 * 1.625 - 1} &= 1.6180556, \\ x_3 &= \frac{1.6180556^2 + 1}{2 * 1.6180556 - 1} &= 1.6180340, \\ x_4 &= \frac{1.6180340^2 + 1}{2 * 1.6180340 - 1} &= 1.6180340. \\ \end{align*}

Because $x_4 = x_3$ as calculated, the ratio $\frac{f(x_3)}{f'(x_3)}$ must be very close to $0$. Since $f'(x_3) = 2.2360680$ is not too large, $f(x_3)$ must be quite close to $0$, so $x_3 = 1.6180340$ is a very good estimate of the greater root.

The sum of the roots is $1$ by Vieta's formulas, so the lesser root is simply $1 - 1.6180340 = -0.6180340$.

Failure cases

Although powerful, Newton's method is delicate and can be very sensitive to the initial guess and type of function, even when the function is differentiable everywhere.

Zero derivative

Suppose in the above example of finding a root of $x^2 - x - 1$, we had started with $x_0 = 0.5$. In the process of calculating $x_1$, then, we would have to divide by $f'(x_0) = 2x_0 - 1 = 0$, creating an undefined result.

Wrong root

Suppose we try to estimate the greater root as before, but start with $x_0 = -0.5$. Applying Newton's method to $x^2 - x - 1$ yields the following sequence of estimates:

\begin{align*} x_1 &= \frac{-0.5^2 + 1}{2 * (-0.5) - 1} &= -0.625, \\ x_2 &= \frac{(-0.625)^2 + 1}{2 * (-0.625) - 1} &= -0.6180556, \\ x_3 &= \frac{(-0.6180556)^2 + 1}{2 * (-0.6180556) - 1} &= -0.6180340, \\ x_4 &= \frac{(-0.6180340)^2 + 1}{2 * (-0.6180340) - 1} &= -0.61803395. \\ x_5 &= \frac{(-0.61803395)^2 + 1}{2 * (-0.61803395) - 1} &= -0.61803406. \\ x_6 &= \frac{(-0.61803406)^2 + 1}{2 * (-0.61803406) - 1} &= -0.61803395. \\ \end{align*}

These estimates converge to the lesser root, in this case because the initial estimate was closer to the lesser root than the greater root. In general, predicting which root Newton's method will finally converge to is difficult, and Newton's method may converge to a farther root even if a closer root is available within the interval between the initial estimate and the root.

Periodic behavior without finding a root

When finding roots of $x^2 - x - 1$ as above, the estimates eventually stabilize into a predictable pattern: in the $x_0 = 1.5$ case, $x_4 = x_3$, so every subsequent estimate will equal $x_3$; in the $x_0 = -0.5$ case, $x_6 = x_4$, so the subsequent estimates will oscillate, with every even estimate equal to $x_4$ and every odd estimate equal to $x_5$. These behaviors are due to the limited precision of the calculations; with indefinite precision, the estimates would continue to approach the root without becoming periodic.

However, for some functions, Newton's method can cycle without coming close to a root.

No root (divergent)

The function $f(x) = e^x$ is always positive, so it has no roots. Attempting to apply Newton's method yields a divergent sequence: since $f(x) = e^x$ satisfies the differential equation $f(x) = f'(x)$ for all $x$, the ratio $\frac{f(x)}{f'(x)}$ is always $1$, so the sequence of estimates becomes $x_{i+1} = x_i - 1$, diverging in the negative direction.

This article is a stub. Help us out by expanding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Newton%27s_method&oldid=173567"