8.2: Newton's Method

Last updated

Jun 15, 2022
Save as PDF
- 8.1: Absolute Extrema and Optimization
- 8.3: Analyzing the Graphs of Functions

$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$

$\newcommand{\id}{\mathrm{id}}$ $\newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$ $\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$ $\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$ $\newcommand{\AA}{\unicode[.8,0]{x212B}}$

$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vectorC}[1]{\textbf{#1}}$

$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$

$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$

$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$

$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$

$\newcommand{\avec}{\mathbf a}$

$\newcommand{\bvec}{\mathbf b}$

$\newcommand{\cvec}{\mathbf c}$

$\newcommand{\dvec}{\mathbf d}$

$\newcommand{\dtil}{\widetilde{\mathbf d}}$

$\newcommand{\evec}{\mathbf e}$

$\newcommand{\fvec}{\mathbf f}$

$\newcommand{\nvec}{\mathbf n}$

$\newcommand{\pvec}{\mathbf p}$

$\newcommand{\qvec}{\mathbf q}$

$\newcommand{\svec}{\mathbf s}$

$\newcommand{\tvec}{\mathbf t}$

$\newcommand{\uvec}{\mathbf u}$

$\newcommand{\vvec}{\mathbf v}$

$\newcommand{\wvec}{\mathbf w}$

$\newcommand{\xvec}{\mathbf x}$

$\newcommand{\yvec}{\mathbf y}$

$\newcommand{\zvec}{\mathbf z}$

$\newcommand{\rvec}{\mathbf r}$

$\newcommand{\mvec}{\mathbf m}$

$\newcommand{\zerovec}{\mathbf 0}$

$\newcommand{\onevec}{\mathbf 1}$

$\newcommand{\real}{\mathbb R}$

$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$

$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$

$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$

$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$

$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$

$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$

$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$

$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$

$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$

$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$

$\newcommand{\bcal}{\cal B}$

$\newcommand{\ccal}{\cal C}$

$\newcommand{\scal}{\cal S}$

$\newcommand{\wcal}{\cal W}$

$\newcommand{\ecal}{\cal E}$

$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$

$\newcommand{\gray}[1]{\color{gray}{#1}}$

$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$

$\newcommand{\rank}{\operatorname{rank}}$

$\newcommand{\row}{\text{Row}}$

$\newcommand{\col}{\text{Col}}$

$\renewcommand{\row}{\text{Row}}$

$\newcommand{\nul}{\text{Nul}}$

$\newcommand{\var}{\text{Var}}$

$\newcommand{\corr}{\text{corr}}$

$\newcommand{\len}[1]{\left|#1\right|}$

$\newcommand{\bbar}{\overline{\bvec}}$

$\newcommand{\bhat}{\widehat{\bvec}}$

$\newcommand{\bperp}{\bvec^\perp}$

$\newcommand{\xhat}{\widehat{\xvec}}$

$\newcommand{\vhat}{\widehat{\vvec}}$

$\newcommand{\uhat}{\widehat{\uvec}}$

$\newcommand{\what}{\widehat{\wvec}}$

$\newcommand{\Sighat}{\widehat{\Sigma}}$

$\newcommand{\lt}{<}$

$\newcommand{\gt}{>}$

$\newcommand{\amp}{&}$

$\definecolor{fillinmathshade}{gray}{0.9}$

We want to look at finding the roots of a polynomial. Sometimes the polynomial cannot be easily factored, and other algebraic methods (e.g., the quadratic equation) are not applicable, or do not work. When faced with a mathematical problem that cannot be solved with simple algebraic means, calculus sometimes provides a way of finding approximate solutions.

Newton's Method

A simple example will help introduce Newton’s Method for approximating the roots of a polynomial equation.

Let's say you want to compute $\sqrt{5} \nonumber$ without using a calculator or a table. Any ideas how this could be done? Try thinking about this problem in a different way, so that you make use of linearization.

Assume that we are interested in solving the quadratic equation:

$f(x)=x^2−5=0 \nonumber$

We know this equation has the roots $x=± \sqrt{5} \nonumber$ .

The idea here is to find the linearization of f(x) at an appropriate point, and then solve the linear equation for x. This is an added twist to the linearization problem!

How to choose the linearization point? Since $\sqrt{4}<\sqrt{5}<\sqrt{9} \nonumber$ , this mean $2<\sqrt{5}<3 \nonumber$ .

We choose the linear approximation of f(x) to be near $x_0=2 \nonumber$ (but, $x_0=3 \nonumber$ could also could be selected).

$f(x)=x^2−5 \mbox{ and } f(2)=−1 \nonumber$

$f′(x)=2x \mbox{ and } f′(2)=4 \nonumber$

Using the linear approximation formula,

$f(x)≈f(x_0)+f′(x_0)(x−x_0) \nonumber$

$≈−1+(4)(x−2) \nonumber$

$≈−1+4x−8 \nonumber$

$≈4x−9 \nonumber$

Notice that this equation is much easier to solve than $f(x)=x^2−5=0 \nonumber$ .

Setting f(x)=0 and solving for x, we obtain,

$4x−9=0 \nonumber$

$x=\frac{9}{4} \nonumber$

$=2.25 \nonumber$

This is a fairly good approximation, since a calculator would give x=2.23607, lower by 0.014. We can actually make this approximation to the root of f(x) even better by repeating what we have just done but using the latest estimate $x_1=2.25= \frac{9}{4} \nonumber$ , a number that is even closer to the actual value of $\sqrt{5} \nonumber$ .

$f(x)=x^2−5 \mbox{ and } f(2.25)=\frac{1}{16} \nonumber$

$f′(x)=2x \mbox{ and } f′(2)= \frac{9}{2} \nonumber$

Using the linear approximation again,

$f(x)≈f(x_1)+f′(x_1)(x−x_1) \nonumber$

$≈ \frac{1}{16}+\frac{9}{2}(x−\frac{9}{4}) \nonumber$

$≈\frac{9}{2}x−\frac{161}{16} \nonumber$ .

Solving for x by setting f(x)=0, we obtain

$x=x_2=\frac{161}{72}=2.23611 \nonumber$

which is an even better approximation than

$x_1=\frac{9}{4} \nonumber$ .

We could continue this process generating a better approximation to $\sqrt{5} \nonumber$ , as shown in the table, where the last estimate approximates the correct answer to 5 places. Thank goodness for calculators!

n	$x_n \nonumber$	$f(x_n) \nonumber$	$f′(x-n) \nonumber$	$\frac{f(x_n)}{f′(x_n)} \nonumber$	$x_n−\frac{f(x_n)}{f′(x_n)} \nonumber$
1	2	-1	4	-0.25	2.25
2	2.25	0.0625	4.5	0.01389	2.23611
3	2.23611	0.00019	4.47222	0.00004	2.23607
4	2.23607	--	--	--	--

This is the basic idea of Newton’s Method. Here is a summary of the method:

Given the function f(x), find f′(x).
Estimate the first approximation, x₀, to a solution of the equation f(x)=0. Use a graph to help in finding the first approximation if necessary (see Figure below).
Use the current approximation x_n to find the next approximation, x_n+1, by using the recursion relation.

$x_{n+1}=x_n−\frac{f(x_n)}{f′(x_n)} \nonumber$ .

Repeat the previous step until the desired level of convergence occurs.

Note that in some cases, Newton’s Method does not converge.

Screen Shot 2021-01-07 at 1.04.48 PM.png

CC BY-NC-SA

Examples

Example 1

Compare the solutions to f(x)=5x2+7x−52 in the interval [2, 3] from using the Quadratic formula and using Newton’s Method.

The function is shown in the figure.

For f(x)=5x2+7x−52=0, use of the quadratic formula gives the exact solution x=2.6 in the interval.

Screen Shot 2021-01-07 at 1.05.36 PM.png

CC BY-NC-SA

Use of Newton’s Method with an initial estimate of x₀=3, yields the results shown in the table.

n	$x_n \nonumber$	$f(x_n) \nonumber$	$f′(x-n) \nonumber$	$\frac{f(x_n)}{f′(x_n)} \nonumber$	$x_n−\frac{f(x_n)}{f′(x_n)} \nonumber$
1	3	14	37	0.3784	2.6216
2	2.6216	0.7151	33.216	0.0215	2.6001
3	2.6001	0.0033	33.001	0.0001	2.6000
4	2.6000	--	--	--	--

The technique rapidly converges to a solution.

Example 2

Use Newton’s method to find the roots of the polynomial $f(x)=x^3+x−1 \nonumber$ .

The problem is to solve the equation $f(x)=x^3+x−1=0 \nonumber$ .

The equations we need are:

$f(x)=x^3+x−1 \nonumber$

$f′(x)=3x^2+1 \nonumber$ .

Using the recursion relation,

$x_{n+1}=x_n−\frac{f(x_n)}{f′(x_n)} \nonumber$

$=x_n−\frac{x^3_n+x_n−1}{3x^2_n+1} \nonumber$ .

To help us find the first approximation, we make a graph of f(x). As the figure suggests, set $x_1=0.6 \nonumber$ .

Screen Shot 2021-01-07 at 1.26.08 PM.png

CC BY-NC-SA

Then using the recursion relation, we can generate x1:

$x_{n+1}=x_n−\frac{x^3_n+x_n−1}{3x^2_n+1} \nonumber$

$x_2=0.6−\frac{(0.6)^3+(0.6)−1}{3(0.6)^2+1} \nonumber$

$=0.6884615 \nonumber$ .

By using the recursion relation several times, we can find x3 and x4 as shown in the table.

n	$x_n \nonumber$	$f(x_n) \nonumber$	$f′(x-n) \nonumber$	$\frac{f(x_n)}{f′(x_n)} \nonumber$	$x_n−\frac{f(x_n)}{f′(x_n)} \nonumber$
1	0.6	-0.184	2.08	-0.0884615	0.6884615
2	0.6884615	0.01477796	2.4219377	0.0061017	0.6823598
3	0.6823598	0.00007669	2.3968445	0.0000320	0.6823278
4	0.6823278	--	--	--	--

We conclude that the solution to the equation

$x^3+x−1=0 \nonumber$ is about 0.6823.

Example 3

Use Newton’s Method to show to find the root of $f(x)=cos(2x)−x \nonumber$ .

The equations we need are:

$f(x)=cos(2x)−x \nonumber$

$f(x)=−2sin(2x)−1 \nonumber$

Using the recursion relation,

x_{n+1}=x_n\frac{f(x_n)}{f′(x_n)} \nonumber\)

$=x_n−\frac{cos(2x_n)−x_n}{−2sin(2x_n)−1} \nonumber$

To help us find the first approximation, we make a graph of f(x). As the figure suggests, set the first estimate at 0.5.

Screen Shot 2021-01-08 at 10.49.52 AM.png

CC BY-NC-SA

Using the recursion relation several times gives the table values:

n	$x_n \nonumber$	$f(x_n) \nonumber$	$\frac{f(x_n)}{f′(xn)} \nonumber$
1	0.500000	0.0403023	-0.015216_8
2	0.515022	-0.0002400	0.0000884
3	0.514933	-0.0000000	0.0000000
4	0.514933	--	--

We conclude that the solution to the equation cos(2x)−x=0 is 0.514933.

Review

For all the problems, use Newton’s Method to find the roots.

$x^3+3=0 \nonumber$ .
$−x+3\sqrt{−1+x}=0 \nonumber$ .
$4x^2−x−2 \mbox{ in the interval } [-1, 0] \nonumber$ .
$4x^3−6x^2−1 \nonumber$ .
$5e^{−x}+x^3 \nonumber$ .
$cosx−x \nonumber$ .
$x^5−7x^2+2 \mbox{ in the interval} [-1, 0] \nonumber$ .
$x^5−7x^2+2 \mbox{ in the interval } [0, 1] \nonumber$ .
$x^2cosx−x \mbox{ in the interval } [4, 5] \nonumber$ .
$x^2cosx−x \mbox{ in the interval } [7, 8] \nonumber$ .
$f(x)=x−2sin(x) \mbox{ to five decimal places, starting with initial guess } x_0=3 \nonumber$ .
$f(x)=6x^3−4x+1 \nonumber$ to three decimal places, starting with initial guess $x_0=1.2 \nonumber$ .
$f(x)=ln(x)×(ln(x)+4)+1 \nonumber$ to five decimal places, starting with initial guess $x_0=1 \nonumber$ .
$f(x)=tan(x)−csc(x) \nonumber$ to six digits of accuracy, starting with initial guess $x_0=0.7 \nonumber$ .
$f(x)=tan^{−1}(x)+cos(x) \nonumber$ to four digits of accuracy, starting with initial guess $x_0=−2 \nonumber$ .

Review (Answers)

To see the Review answers, open this PDF file and look for section 4.11.

Vocabulary

Term	Definition
Newton's method	Newton’s method is an iterative procedure for computing the root of an equation.

Additional Resources

PLIX: Play, Learn, Interact, eXplore - Newton's Method

Video: Newton's Method for Solving Equations

Practice: Newton's Method

Real World: Getting to the Root of Things

Search

Text Color

Text Size

Margin Size

Font Type

Newton's Method

Examples

Example 1

Example 2

Example 3

Review

Review (Answers)

Vocabulary

Additional Resources

Support Center

How can we help?