$$\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}}$$

# 6.3: Newton's Method

Suppose you have a function $$f(x)$$, and you want to find as accurately as possible where it crosses the $$x$$-axis; in other words, you want to solve $$f(x)=0$$. Suppose you know of no way to find an exact solution by any algebraic procedure, but you are able to use an approximation, provided it can be made quite close to the true value. Newton's method is a way to find a solution to the equation to as many decimal places as you want. It is what is called an "iterative procedure,'' meaning that it can be repeated again and again to get an answer of greater and greater accuracy. Iterative procedures like Newton's method are well suited to programming for a computer. Newton's method uses the fact that the tangent line to a curve is a good approximation to the curve near the point of tangency.

Example 6.3.1

Approximate $$\sqrt{3}$$.

Solution

Since $$\sqrt{3}$$ is a solution to $$x^2=3$$ or $$x^2-3=0$$, we use $$f(x)=x^2-3$$. We start by guessing something reasonably close to the true value; this is usually easy to do; let's use $$\sqrt3\approx2$$. Now use the tangent line to the curve when $$x=2$$ as an approximation to the curve, as shown in figure 6.3.1.

Figure 6.3.1. Netwon's Method

Since $$f'(x)=2x$$, the slope of this tangent line is 4 and its equation is $$y=4x-7$$. The tangent line is quite close to $$f(x)$$, so it crosses the $$x$$-axis near the point at which $$f(x)$$ crosses, that is, near $$\sqrt3$$. It is easy to find where the tangent line crosses the $$x$$-axis: solve $$0=4x-7$$ to get $$x=7/4=1.75$$. This is certainly a better approximation than 2, but let us say not close enough. We can improve it by doing the same thing again: find the tangent line at $$x=1.75$$, find where this new tangent line crosses the $$x$$-axis, and use that value as a better approximation. We can continue this indefinitely, though it gets a bit tedious. Lets see if we can shortcut the process. Suppose the best approximation to the intercept we have so far is $$x_i$$. To find a better approximation we will always do the same thing: find the slope of the tangent line at $$x_i$$, find the equation of the tangent line, find the $$x$$-intercept. The slope is $$2x_i$$. The tangent line is $$y=(2x_i)(x-x_i)+(x_i^2-3)$$, using the point-slope formula for a line. Finally, the intercept is found by solving $$0 =(2x_i)(x-x_i)+(x_i^2-3)$$. With a little algebra this turns into $$x=(x_i^2+3)/(2x_i)$$; this is the next approximation, which we naturally call $$x_{i+1}$$. Instead of doing the whole tangent line computation every time we can simply use this formula to get as many approximations as we want. Starting with $$x_0=2$$, we get $$x_1=(x_0^2+3)/(2x_0)=(2^2+3)/4=7/4$$ (the same approximation we got above, of course), $$x_2=(x_1^2+3)/(2x_1)= ((7/4)^2+3)/(7/2)=97/56\approx 1.73214$$, $$x_3\approx 1.73205$$, and so on. This is still a bit tedious by hand, but with a calculator or, even better, a good computer program, it is quite easy to get many, many approximations. We might guess already that $$1.73205$$ is accurate to two decimal places, and in fact it turns out that it is accurate to 5 places.

Let's think about this process in more general terms. We want to approximate a solution to $$f(x)=0$$. We start with a rough guess, which we call $$x_0$$. We use the tangent line to $$f(x)$$ to get a new approximation that we hope will be closer to the true value. What is the equation of the tangent line when $$x=x_0$$? The slope is $$f'(x_0)$$ and the line goes through $$(x_0,f(x_0))$$, so the equation of the line is $$y=f'(x_0)(x-x_0)+f(x_0).$$ Now we find where this crosses the $$x$$-axis by substituting $$y=0$$ and solving for $$x$$: $$x={x_0f'(x_0)-f(x_0)\over f'(x_0)} = x_0 - {f(x_0)\over f'(x_0)}.$$ We will typically want to compute more than one of these improved approximations, so we number them consecutively; from $$x_0$$ we have computed $$x_1$$: $$x_1={x_0f'(x_0)-f(x_0)\over f'(x_0)} = x_0 - {f(x_0)\over f'(x_0)},$$ and in general from $$x_i$$ we compute $$x_{i+1}$$: $$x_{i+1}={x_if'(x_i)-f(x_i)\over f'(x_i)} = x_i - {f(x_i)\over f'(x_i)}.$$

### Contributors

• Integrated by Justin Marshall.