Newton’s Method
October 14, 2013
Math 151 (Pelsmajer)

Introduction

Newton’s Method finds approximate roots of a function.  
That is, given a function f(x), Newton’s method find approximate solutions to f(x) = 0.  

You must tell it where to start looking, though.

Try running this Mathematica code (and all subsequent bits of code):

f[x_]:=(x^3)-x^2-x -7;
Plot[f[x],{x,0,4},PlotStyle->Green]

In the above example, clearly there is a root between x=2 and x=3.  

The core idea of Newton’s method: 
Start with a rough guess, say (Subscript[x, 0])=3.
Find the tangent line at (Subscript[x, 0]). 
Find where it crosses the x-axis (the “x-intercept”):  x=(Subscript[x, 1]).
Hopefully, (Subscript[x, 1]) is closer to the root than (Subscript[x, 0]).

Run the following, then drag the slider to the right to demonstrate:

f[x_]:=(x^3)-x^2-x -7;
x0=3;
frames0=ConstantArray[0,4];
thecurve0=Plot[f[x],{x,0,4},PlotStyle->Green];
firstguess0=Graphics[{PointSize[Large],Blue,Point[{x0,0}]}];
frames0[[1]]=Show[thecurve0,firstguess0];
xline0=Graphics[{Dashed,Gray,Line[{{x0,0},{x0,f[x0]}}]}];
pointoncurve0=Graphics[{PointSize[Large],Green,Point[{x0,f[x0]}]}];
frames0[[2]]=Show[frames0[[1]],xline0,pointoncurve0];
tangent0=f'[x0]*(x-x0)+f[x0];
tplot0=Plot[tangent0,{x,2,4},PlotRange->{{2,3.1},{-5,15}},PlotStyle->Red];
frames0[[3]]=Show[frames0[[2]],tplot0];
xintercept0=Graphics[{PointSize[Large],Blue,Point[{x0-f[x0]/f'[x0],0}]}];
frames0[[4]]=Show[frames0[[3]],xintercept0];
Manipulate[frames0[[n]],{n,1,4,1},FrameLabel->"Newton's Method: Step 1"]

The other key to Newton’s method: 
Repeat the process, to get closer and closer to a root.

Altogether, it goes like this:

Newton’s method
Start with a rough guess, say (Subscript[x, 0])=3.
Find the tangent line at (Subscript[x, 0]), and let (Subscript[x, 1]) be the x-intercept.
Find the tangent line at (Subscript[x, 1]), and let (Subscript[x, 2]) be the x-intercept.
Find the tangent line at (Subscript[x, 2]), and let (Subscript[x, 3]) be the x-intercept.
Find the tangent line at (Subscript[x, 3]), and let (Subscript[x, 4]) be the x-intercept.
...
Continue until you are “close enough” to the root.  (How close is “close enough”?)

Run the following, then drag the slider to the right to demonstrate:

f[x_]:=(x^3)-x^2-x -7;
xn=3;
numsteps=4;
frames=ConstantArray[0,numsteps];
thecurve=Plot[f[x],{x,0,4},PlotStyle->Green];
firstguess=Graphics[{PointSize[Medium],Blue,Point[{xn,0}]}];
frames[[1]]=Show[thecurve,firstguess];
For[n=2,n≤numsteps,n++,
xline=Graphics[{Gray,Line[{{xn,0},{xn,f[xn]}}]}];
xnpointoncurve=Graphics[{PointSize[Medium],Green,Point[{xn,f[xn]}]}];
tangent=f'[xn]*(x-xn)+f[xn];
tplot=Plot[tangent,{x,2,4},PlotRange->{{1.9,3.8},{-5,15}},PlotStyle->Red];
xnext = xn-f[xn]/f'[xn];
xintercept=Graphics[{PointSize[Medium],Blue,Point[{xnext,0}]}];
frames[[n]]=Show[frames[[n-1]],xnpointoncurve,tplot, xintercept,xline];
xn=xnext;
]
Manipulate[frames[[n]],{n,1,numsteps,1},FrameLabel->"Newton's Method: 3 steps"]

The same process, but focused so that we can see the last step more clearly:

f[x_]:=(x^3)-x^2-x -7;
xn=3;
numsteps=4;
frames2=ConstantArray[0,numsteps];
thecurve2=Plot[f[x],{x,2.4,2.7},PlotStyle->Green];
firstguess=Graphics[{PointSize[Medium],Blue,Point[{xn,0}]}];
frames2[[1]]=Show[thecurve2,firstguess];
For[n=2,n≤numsteps,n++,
xline=Graphics[{Gray,Line[{{xn,0},{xn,f[xn]}}]}];
xnpointoncurve=Graphics[{PointSize[Medium],Green,Point[{xn,f[xn]}]}];
tangent=f'[xn]*(x-xn)+f[xn];
tplot=Plot[tangent,{x,2.4,2.7},PlotRange->{{2,3.1},{-5,15}},PlotStyle->Red];
xnext = xn-f[xn]/f'[xn];
xintercept=Graphics[{PointSize[Medium],Blue,Point[{xnext,0}]}];
frames2[[n]]=Show[frames2[[n-1]],xnpointoncurve,tplot, xintercept,xline];
xn=xnext;
]
Manipulate[frames2[[n]],{n,1,numsteps,1},FrameLabel->"Newton's Method"]

Again, but this time, algebraically (without actually making any graphs):

The tangent line at (Subscript[x, n]) is y = f'((Subscript[x, n]))(x-(Subscript[x, n]))+f((Subscript[x, n])).
To get the x-intercept, set y=0 and solve for x.
	f'((Subscript[x, n]))(x-(Subscript[x, n]))+f((Subscript[x, n])) = 0
	f'((Subscript[x, n]))(x-(Subscript[x, n]))  = -f((Subscript[x, n]))
	x-(Subscript[x, n])  = - ((f((Subscript[x, n])))/(f'((Subscript[x, n]))))
	x = (Subscript[x, n]) -((f((Subscript[x, n])))/(f'((Subscript[x, n])))) 
So we set (Subscript[x, n+1]) = (Subscript[x, n]) -((f((Subscript[x, n])))/(f'((Subscript[x, n])))) .

Remembering that N[ ] gives decimal approximations, and % means “the previous value computed”,
Newton’s Method looks like this:

newton[x_]:=x-f[x]/f'[x]

3
N[newton[%]]
N[newton[%]]
N[newton[%]]

How close is “close enough” (to a root)?
1. It’s up to you.
2. Take Math 350 for a better answer.
3. Well, for now you might at least check that f((Subscript[x, n])) is close to 0...

x0 = 3
f[x0]

x1 = N[newton[x0]]
f[x1]

x2= N[newton[x1]]
f[x2]

x3 = N[newton[x2]]
f[x3]

Solving equations with Newton's method:
Say you want to solve an equation A(x)=B(x) .  
  Why not solve A(x)-B(x) = 0 instead?  
Let f(x)=A(x)-B(x) and then solve f(x)=0 using Newton's Method.

Exercises

Exercise 1: Find roots of a function

Estimate all roots of the third degree polynomial function p(x)=(x^3)-4x-1.

We’ll start you off with a graph of y=p(x) that shows all three roots.

p[x_]:=(x^3)-4*x-1
Plot[p[x],{x,-5,5},PlotStyle -> Blue]

Exercise 2: Finding solutions of an equation

Find all numbers x in the interval  [0,1]  for which   (([cos(((3 π x)/2))] )^2)=x.

To determine the number of solutions to this problem, we plot a graph of the functions
F(x)=(([cos(((3 π x)/2))] )^2) and G(x)=x for 0<x<1. 
Then the solutions to this problem are all the values of x at which F(x)=G(x) .

funcF[x_]:=(Cos[3*Pi*x/2])^2
funcG[x_]:=x
Plot[{funcF[x], funcG[x]},{x,0,1},PlotStyle->{Green,Blue}]

We can see that there are three points of intersection: one near 0.25, one near 0.5 and one near 0.75.

The solutions are also the zeroes (or roots) of the function
                                              h(x)=G(x)-F(x).

We plot a graph of the functions f, F, and G so we can see indeed that f has zeroes where F and G intersect (near 0.25, near 0.5 and near 0.75).

h[x_]:=funcG[x]-funcF[x]
Plot[{funcF[x], funcG[x], h[x]},{x,0,1},PlotStyle->{Green, Blue,Red}]

Exercise 3: Calculate  π

Since tan((π/4))=1, we can calculate π by using finding a root of tan((x/4))-1.
Do just that, using Newton’s Method.

Exercise 3: Calculate e

The natural logarithm ln (x)=1 when x=e (“Euler's number”).
(Mathematica writes ln(x) simply as “Log[x]”.)

Use Newton's method to approximate the value of  e.