Newton's Method for Approximating Zeros

Newton's Method allows us to approximate the zeroes of any function, by using derivatives.

The process is relatively simple: Suppose we want to estimate a zero of $f(x)$. First, choose any guess for the zero, and call it $x_0$. Then, calculate $x_1,x_2,x_3$, and so on using the recursion $$x_n=x_{n-1}-\frac{f(x_{n-1})}{f'(x_{n-1})}.$$ Each $x_i$ gives a better estimate for the zero than the previous value $x_{i-1}$, and so by repeating this process enough times we can arrive at a reasonably close approximation.

Let's take a look at an example: suppose $f(x)=x^3+x+1$.

Since $f(0)=1$, which is somewhat close to $0$, we can start by letting $x_0=0$. (The value that we choose does not actually matter as much in the long-run, so in theory we can start with $x_0=171,717,171$ if we really want. However, choosing a reasonable guess from the start will let us reach an approximation much more quickly.) Before we use the formula provided above, we should find out what the derivative of $f(x)$ is: $$f'(x)=(x^3+x+1)'=3x^2+1.$$ So, we have $$x_1=x_0-\frac{f(x_0)}{f'(x_0)}=0-\frac{f(0)}{f'(0)}=-\frac{1}{1}=-1.$$ This is closer to the actual solution than $0$, but let's continue: $$x_2=x_1-\frac{f(x_1)}{f'(x_1)}=-1-\frac{f(-1)}{f'(-1)}=-1+\frac{1}{4}=-\frac{3}{4}.$$ Now, we're much closer! By doing the same steps, we can find that $$x_3=-\frac{59}{86}\approx -0.686,$$ which is a pretty good estimate for the actual value of $x=-0.68233$. (If you go one step further, you'll get $$x_4=-\frac{523407}{767077}\approx -0.68234,$$ which is even more accurate but a lot more painful to calculate by hand.

To show why this process works, let's play around with the general function $f(x)$. Suppose we start with an initial guess for the zero- say $x=x_0$. Our goal is to determine a closer approximation for the zero, in terms of $x_0$.

To do so, imagine the graph of $y=f(x)$, and let $P=(x_0,f(x_0))$ be one point on the curve. If we draw the tangent line to the curve at $P$, we can see that the tangent line intersects the $x$-axis at $Q$, where $Q$ closer to the actual solution to $f(x)=0$ than $x_0$. So, let's let the $x$-coordinate of $Q$ be $x_1$. If we repeat the same process, we can similarly get $x_2, x_3, x_4$, and so on. Each $x_i$ gives a more accurate approximation of the zero of $f(x)$.

Great, so we now have a graphical method of approximating the zeroes of $f(x)$. But can we now find a formula algebraically? Of course, we can!

Recall that the main step of the process is to find the tangent line of the graph at $(x_i,f(x_i))$ and find its $x$-intercept. Let's start with the tangent line: If we let the line be $g(x)=mx+b$, we simply need to solve for $m$ and $b$. Here $m$ represents the slope of the tangent line at $x=x_i$, which by definition is $m=f'(x_i)$. Then our equation becomes $$g(x)=f'(x_i)x+b.$$ Since we know $g$ passes through the point $(x_i,f(x_i))$, we can plug this value in to get $$g(x_i)=f(x_i)=f'(x_i)\cdot x_i+b.$$ Solving for $b$, we get $b=f(x_i)-f'(x_i)\cdot x_i$. Therefore, our final equation of the tangent line becomes $$g(x)=f'(x_i)x+(f(x_i)-f'(x_i)\cdot x_i).$$ Since we want to find this line's $x$-intercept, we set $g(x)=0$ to find that $$0=f'(x_i)x+(f(x_i)-f'(x_i)\cdot x_i)$$ $$\Longrightarrow x=\frac{f'(x_i)\cdot x_i-f(x_i)}{f'(x_i)}=x_i-\frac{f(x_i)}{f'(x_i)}.$$ By setting this new value as $x_{i+1}$, we get the exact formula described above. So, we are done with the proof!

(Video) Newton's Method

by PatrickJMT

Here's a video by patrickJMT where he explains how Newton's Method works and how you use it to find the zeros of functions.

Newton's Method is a way to find $x$-intercepts of functions. You'll either be given a point to start with or you choose a point to start at. Let's call this starting point $x_1$.

We want to draw the tangent line at this point and note where it crosses the $x$-intercept.

Then we take the point where the tangent line crosses the $x$ axis and locate it on our original function. This point becomes our $x_2$.

We find the tangent line at our new point now and continue this same process. With each new $x_n$, or iteration, we should start to get closer to where our original function crosses the $x$-axis.

The general equation for Newton's Method is: $$\boxed{\begin{align} x_1&\\ x_2&=x_1-\frac{f(x_1)}{f'(x_1)}\\ x_3&=x_2-\frac{f(x_2)}{f'(x_2)}\\ \cdots\\ x_{n+1}&=x_n-\frac{f(x_n)}{f'(x_n)} \end{align}}$$

You have to be careful when using Newton's Method because it doesn't always work! If we took our starting point a little more to the left, the tangent line becomes horizontal.

Let's look at an example of Newton's Method. Patrick looks at a problem that says:

Find where $f(x)=x^7-1000$ intersects the $x$-axis; find a solution that's correct to eight decimal places.

Here's the graph of this function. If we look at $x=2$ we see it's a negative value. Then, at $x=3$, it's a positive value. Because our function is a polynomial and because of the Intermediate Value Theorem, we know there's at least one $x$-intercept between two and three.

Newton's Method tells us: $$\begin{align} x_{n+1}&=x_n-\frac{f(x_n)}{f'(x_n)}\\ x_{n+1}&=x_n-\frac{x_n ^7-1000}{7x_n^6} \end{align}$$

Suppose we make our first point, $x_1=3$. $$\begin{align} x_{2}&=x_1-\frac{x_1 ^7-1000}{7x_1^6}\\ x_{2}&=\color{red}{3}-\frac{\color{red}{3}^7-1000}{7\color{red}{(3)}^6}\\ x_{2}&=2.76739173 \end{align}$$

Now we repeat this to find $x_3$. $$\begin{align} x_{3}&=x_2-\frac{x_2 ^7-1000}{7x_2^6}\\ x_{3}&=\color{red}{2.76739173}-\frac{\color{red}{2.76739173}^7-1000}{7\color{red}{(2.76739173)}^6}\\ x_{3}&=2.69008741 \end{align}$$

Again for $x_4$. $$\begin{align} x_{4}&=x_3-\frac{x_3 ^7-1000}{7x_3^6}\\ x_{4}&=\color{red}{2.6900874}-\frac{\color{red}{2.6900874}^7-1000}{7\color{red}{(2.6900874)}^6}\\ x_{4}&=2.68275645 \end{align}$$

Again for $x_5$. $$\begin{align} x_{5}&=x_4-\frac{x_4 ^7-1000}{7x_4^6}\\ x_{5}&=\color{red}{2.68275645}-\frac{\color{red}{2.68275645}^7-1000}{7\color{red}{(2.68275645)}^6}\\ x_{5}&=2.6826958 \end{align}$$

Again for $x_6$. Don't worry it's almost over. $$\begin{align} x_{6}&=x_5-\frac{x_5 ^7-1000}{7x_5^6}\\ x_{6}&=\color{red}{2.6826958}-\frac{\color{red}{2.6826958}^7-1000}{7\color{red}{(2.6826958)}^6}\\ x_{6}&=2.68269578 \end{align}$$

Notice that the first eight digits after the decimal didn't change from the previous answer. This is because we're getting so insanely close that it's differing in very very very minute ways. So we actually have the answer accurate to eight decimal places. This tells us that our function, $f(x)=x^7-1000$, intercepts the $x$-axis at $x\approx2.6826958$.

(Videos) Newton's Method Example

by PatrickJMT

Here's a video by patrickJMT where he goes over some more examples using Newton's Method.

The problem he looks at is:

Compute two iterations of Newton's method for the given function and indicated initial guess: $$f(x)=x^2-8,\ x_1=3$$

Let's do the first iteration. $$\begin{align} x_{2}&=x_1-\frac{f(x_1)}{f'(x_1)}\\ x_{2}&=\color{red}{3}-\frac{\color{red}{3}^2-8}{2\color{red}{(3)}}\\ x_{2}&=\frac{17}{6} \end{align}$$

Now the second iteration. $$\begin{align} x_{3}&=x_2-\frac{f(x_2)}{f'(x_2)}\\ x_{3}&=\color{red}{\frac{17}{6}}-\frac{\color{red}{(\frac{17}{6})}^2-8}{2\color{red}{(\frac{17}{6})}}\\ x_{3}&\approx2.82843 \end{align}$$

Here's another video with another example.

Apply two iterations of Newton's Method to approximate the $x$-value of a point of intersection of these two functions using the given initial guess: $$f(x)=x^2-4,\ g(x)=2x-3,\ x_1=0$$ What is the value of $x_3$?

If we wanted to find the intersection of these two functions we would set them equal to each other. $$x^2-4=2x-3$$ What Newton's Method does is look for where the function equals zero. So we can rewrite this as: $$x^2-2x-1=0$$

Now we just apply Newton's Method do our new function which we'll call $h(x)$. $$\begin{align} x_{n+1}&=x_n-\frac{h(x_n)}{h'(x_n)}\\ x_{n+1}&=x_n-\frac{x_n^2-2x_n-1}{2x_n-2} \end{align}$$

The first iteration gives us: $$\begin{align} x_{2}&=x_1-\frac{h(x_1)}{h'(x_1)}\\ x_{2}&=\color{red}{0}-\frac{\color{red}{0}^2-2\color{red}{(0)}-1}{2\color{red}{(0)}-2}\\ x_2&=-\frac12 \end{align}$$

The second iteration give us: $$\begin{align} x_{3}&=x_2-\frac{h(x_2)}{h'(x_2)}\\ x_{3}&=\color{red}{-0.5}-\frac{\color{red}{(-0.5)}^2-2\color{red}{(-0.5)}-1}{2\color{red}{(-0.5)}-2}\\ x_3&=-\frac{5}{12} \end{align}$$

Here's one more video on Newton's Method. This one is to show you how this method can fail.

Given the following equation and initial guess, why would Newton's Method fail to approximate a solution? $$f(x)=(x-2)^2-1;\ x_1=2$$

We want to start at an $x$ that gives us something close to zero. If we plug in $x=2$ we get out $f(2)=-1$ which is close. So why will this not work? Let's look at the graph.

Newton's Method looks at the tangent line at the point we choose. We then want to see where this tangent line hits the $x$-axis because that place becomes our new $x$ value. But this point gives us a horizontal tangent line which doesn't hit the $x$-axis.

Let's see what would happen if we didn't notice this and instead jumped right in to using the method.

So our first iteration yields: $$\begin{align} x_{2}&=x_1-\frac{f(x_1)}{f'(x_1)}\\ x_{2}&=\color{red}{2}-\frac{(\color{red}{2}-2)^2-1}{2(\color{red}{2}-2)}\\ x_2&=2-\frac{-1}{0} \end{align}$$

And we all know we can't divide by zero.