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 $\ds \sqrt{3}$. Since $\ds \sqrt{3}$ is a solution to $\ds x^2=3$ or $\ds x^2-3=0$, we use $\ds 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 $\ds \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. 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 $\ds \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 $\ds x_i$. To find a better approximation we will always do the same thing: find the slope of the tangent line at $\ds x_i$, find the equation of the tangent line, find the $x$-intercept. The slope is $\ds 2x_i$. The tangent line is $\ds 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 $\ds 0 =(2x_i)(x-x_i)+(x_i^2-3)$. With a little algebra this turns into $\ds x=(x_i^2+3)/(2x_i)$; this is the next approximation, which we naturally call $\ds 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 $\ds x_0=2$, we get $\ds x_1=(x_0^2+3)/(2x_0)=(2^2+3)/4=7/4$ (the same approximation we got above, of course), $\ds x_2=(x_1^2+3)/(2x_1)= ((7/4)^2+3)/(7/2)=97/56\approx 1.73214$, $\ds 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. $\square$
|
You can drag the point $x_0$ to change the initial value. Drag it out
to the right side of the graph, then drag it to $1$ and $0.5$.
You can change the function here, for example to Math.sin(x) or Math.exp(x) or Math.pow(2,x) or 1-2/(x*x).
| ||
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 $\ds 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 $\ds x=x_0$? The slope is $\ds f'(x_0)$ and the line goes through $\ds(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 $\ds x_0$ we have computed $\ds 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 $\ds x_i$ we compute $\ds 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)}.$$
Example 6.3.2 Returning to the previous example, $\ds f(x)=x^2-3$, $f'(x)=2x$, and the formula becomes $\ds x_{i+1}=x_i - (x_i^2-3)/(2x_i)=(x_i^2+3)/(2x_i)$, as before. $\square$
In practice, which is to say, if you need to approximate a value in the course of designing a bridge or a building or an airframe, you will need to have some confidence that the approximation you settle on is accurate enough. As a rule of thumb, once a certain number of decimal places stop changing from one approximation to the next it is likely that those decimal places are correct. Still, this may not be enough assurance, in which case we can test the result for accuracy.
Example 6.3.3 Find the $x$ coordinate of the intersection of the curves $y=2x$ and $y=\tan x$, accurate to three decimal places. To put this in the context of Newton's method, we note that we want to know where $2x=\tan x$ or $f(x)=\tan x-2x=0$. We compute $\ds f'(x)=\sec^2 x - 2$ and set up the formula: $$x_{i+1} = x_i-{\tan x_i -2x_i\over \sec^2 x_i - 2}.$$ From the graph in figure 6.3.2 we guess $\ds x_0=1$ as a starting point, then using the formula we compute $\ds x_1=1.310478030$, $\ds x_2=1.223929096$, $\ds x_3=1.176050900$, $\ds x_4=1.165926508$, $\ds x_5=1.165561636$. So we guess that the first three places are correct, but that is not the same as saying $1.165$ is correct to three decimal places—$1.166$ might be the correct, rounded approximation. How can we tell? We can substitute $1.165$, $1.1655$ and $1.166$ into $\tan x - 2x$; this gives $-0.002483652$, $-0.000271247$, $0.001948654$. Since the first two are negative and the third is positive, $\tan x - 2x$ crosses the $x$ axis between $1.1655$ and $1.166$, so the correct value to three places is $1.166$. $\square$
Exercises 6.3
You may want to use this Sage worksheet.
Ex 6.3.1 Approximate the fifth root of 7, using $\ds x_0=1.5$ as a first guess. Use Newton's method to find $\ds x_3$ as your approximation. (answer)
Ex 6.3.2 Use Newton's Method to approximate the cube root of 10 to two decimal places. (answer)
Ex 6.3.3 The function $\ds f(x)=x^3-3x^2-3x+6$ has a root between 3 and 4, because $f(3)=-3$ and $f(4)=10$. Approximate the root to two decimal places. (answer)
Ex 6.3.4 A rectangular piece of cardboard of dimensions $8\times 17$ is used to make an open-top box by cutting out a small square of side $x$ from each corner and bending up the sides. (See exercise 20 in 6.1.) If $x=2$, then the volume of the box is $2\cdot 4\cdot 13=104$. Use Newton's method to find a value of $x$ for which the box has volume 100, accurate to 3 significant figures. (answer)