Solving equations is one of the most important things we do in mathematics, yet we are surprisingly limited in what we can solve analytically. For instance, equations as simple as \(x^5+x+1=0\) or \(\cos(x) =x\) cannot be solved by algebraic methods in terms of familiar functions. Fortunately, there are methods that can give us approximate solutions to equations like these. These methods can usually give an approximation correct to as many decimal places as we like. In Section 1.5 we learned about the Bisection Method. This section focuses on another technique (which generally works faster), called Newton's Method.

Newton's Method is built around tangent lines. The main idea is that if \(x\) is sufficiently close to a root of \(f(x)\text{,}\) then the tangent line to the graph at \((x,f(x))\) will cross the \(x\)-axis at a point closer to the root than \(x\text{.}\)

We start Newton's Method with an initial guess about roughly where the root is. Call this \(x_0\text{.}\) (See Figure 4.1.1.(a).) Draw the tangent line to the graph at \((x_0,f(x_0))\) and see where it meets the \(x\)-axis. Call this point \(x_1\text{.}\) Then repeat the process — draw the tangent line to the graph at \((x_1, f(x_1))\) and see where it meets the \(x\)-axis. (See Figure 4.1.1.(b).) Call this point \(x_2\text{.}\) Repeat the process again to get \(x_3\text{,}\) \(x_4\text{,}\) etc. This sequence of points will often converge rather quickly to a root of \(f\text{.}\)

We can use this geometric process to create an algebraic process. Let's look at how we found \(x_1\text{.}\) We started with the tangent line to the graph at \((x_0,f(x_0))\text{.}\) The slope of this tangent line is \(\fp(x_0)\) and the equation of the line is \begin{equation*} y=\fp(x_0)(x-x_0)+f(x_0) \text{.} \end{equation*}

This line crosses the \(x\)-axis when \(y=0\text{,}\) and the \(x\)-value where it crosses is what we called \(x_1\text{.}\) So let \(y=0\) and replace \(x\) with \(x_1\text{,}\) giving the equation: \begin{equation*} 0 = \fp(x_0)(x_1-x_0)+f(x_0) \text{.} \end{equation*}

Now solve for \(x_1\text{:}\) \begin{equation*} x_1=x_0-\frac{f(x_0)}{\fp(x_0)} \text{.} \end{equation*}

Since we repeat the same geometric process to find \(x_2\) from \(x_1\text{,}\) we have \begin{equation*} x_2=x_1-\frac{f(x_1)}{\fp(x_1)} \text{.} \end{equation*}

In general, given an approximation \(x_n\text{,}\) we can find the next approximation, \(x_{n+1}\) as follows: \begin{equation*} x_{n+1} = x_{n} - \frac{f(x_{n})}{\fp(x_{n})} \text{.} \end{equation*}

We summarize this process as follows.

Let's practice Newton's Method with a concrete example.

We can automate this process on a calculator that has an ANS key that returns the result of the previous calculation. Start by pressing 1 and then Enter. (We have just entered our initial guess, \(x_0=1\text{.}\)) Now compute \begin{equation*} \texttt{ ANS } - \frac{f(\texttt{ ANS } )}{\fp(\texttt{ ANS } )} \end{equation*} by entering the following and repeatedly press the Enter key.

ANS-(ANS^3-ANS^2-1)/(3*ANS^2-2*ANS)

Each time we press the Enter key, we are finding the successive approximations, \(x_1, x_2, \ldots\text{,}\) and each one is getting closer to the root. In fact, once we get past around \(x_7\) or so, the approximations don't appear to be changing. They actually are changing, but the change is far enough to the right of the decimal point that it doesn't show up on the calculator's display. When this happens, we can be pretty confident that we have found an accurate approximation.

Using a calculator in this manner makes the calculations simple; many iterations can be computed very quickly.

ANS - (cos(ANS)-ANS)/(-sin(ANS)-1)

If you know how to program, you can translate the following pseudocode into your favorite language to perform the computation in this problem.

x = .75
while true
    oldx = x
    x = x - (cos(x)-x)/(-sin(x)-1)
    print x
    if abs(x-oldx) < .0000000001
        break

This code calculates \(x_1\text{,}\) \(x_2\text{,}\) etc., storing each result in the variable x. The previous approximation is stored in the variable oldx. We continue looping until the difference between two successive approximations, abs(x-oldx), is less than some small tolerance, in this case, .0000000001.