When somebody asks you to find x in, for example,
x2 - 7x + 11 = 0 eq. 5.3-1you, undoubtably recall from algebra, that there is a formula for problems like these. The quadratic formula says, in this case, that
_________ _ 7 ± Ö72 - 4×11 7 ± Ö5 x =and in this way you can find the zeros of
= eq. 5.3-2 2 2
But what if somebody asked you to find the x that solves
x3 + 16x2 - 52x - 15 = 0 eq. 5.3-3Not as easy, eh? But for cubics (that is third degree polynomials), there is also a formula (and oddly enough it is called the cubic formula) that tells you what x values make them zero. If you bothered to click and see the cubic formula, you have, with near certainty, determined it to be nasty.
For fourth degree polynomials (that is quartics), there is also a formula to find the zeros. And that formula is a whole lot nastier than the cubic formula. If you want to see where that one comes from, click here, but remember that it is optional material and won't be on your exam.
When you get to fifth degree polynomials (that is quintics) and higher degree than that, you get to the ultimate in nastiness. And that is that there simply is no formula that gives you their zeros in terms of roots and powers. I don't mean just that no formula has been discovered. Mathematicians have proved that no such formulas exist, so it is pointless even to go looking for them.
But quadratics are not all peaches and cream either. When you are trying to find the solution to a quadratic using the quadratic formula, you still have to take the square root of something. Granted that if you have an electronic calculator with a square root key, taking a square root is no more difficult than multiplying or adding. Yet multiplying and adding are operations we learned to do in grammar school using pencil and paper. Finding a square root can be done with pencil and paper too, but only with much more trouble. So what is a good way to find a square root, and why is it good? We shall get back to that shortly. But first, a little story.
Long ago an order of wise monks founded the hamlet of Shangrila. At first, they were unable to attract settlers into their little paradise-on-earth. You see, Shangrila is isolated far from nearest village or farm. It is hidden in a valley that you cannot see until you are right upon it. The way to the valley is long and tortuous, with many opportunities to lose you way and perish in the wind-blown snows of the Himalayan peaks.
So the monks set upon a project of erecting stone signposts all through the wilderness to direct travelers unerringly to Shangrila. And their efforts were successful -- in fact too successful. Soon there was a steady stream of settlers arriving in Shangrila, and their numbers soon became a burden to the public parks, schools, and sewers. So the monks set off into the wilderness once again to tear down the signposts they had erected only a few decades earlier. Unfortunately, they had grown older and physically weaker in that time. Tearing down the stacks of stones was too much exertion. So instead they redirected the pointers. They started at the signposts that were farthest way from Shangrila, and those they nudged quite a bit, until they were pointing somewhere other than at Shangrila. Then gradually they worked toward the signposts that were nearer and nearer to Shangrila. But winter was fast approaching, and the closer they got to Shangrila, the faster they had to work. Consequently, the signposts closest to Shangrila were the ones they nudged the least.
So the intrepid traveler can still find his or her way to Shangrila, but it is never along a direct route. You have to wander around the wilderness until you find one of the ancient signposts. You follow the direction and distance it instructs, even though that information is not entirely accurate. Then once having gone that distance and direction, you must wander until you find another signpost. Its information will not be entirely accurate either, but because you are now closer to Shangrila than when you started, the information on this signpost is somewhat more accurate than what you found on the last one. So now, follow the new instructions, then wander until you find yet another signpost. If you keep this up long enough, it will bring you within sight of Shangrila.
If you have a first degree polynomial, that is
f(x) = ax + b eq. 5.3-4
and you want to find where
If I then walk from
So what did we do to find Shangrila (which, by metaphorical definition, is where
f(x0) = 3x0 + 1 eq. 5.3-5aand
f'(x0) = 3 eq. 5.3-5bThen we subtracted the quotient of these two values from x0, and that is what we took to be x1. It turned out that x1 landed us right at Shangrila's village temple.
In the case of f(x) being a 1st degree polynomial such as we have here, it doesn't matter what you choose for x0. If you use the procedure above on x0 to generate x1, then x1 will always place you right at Shangrila. That's because with a 1st degree polynomial, the monks haven't messed with the signposts yet. They all point directly to Shangrila. To follow a signpost at x0 (no matter where that happens to be), all you do is
f(x0) x1 = x0 -and you have the key to the temple.
eq. 5.3-6 f'(x0)
By using just a little algebra, we can readily see why it doesn't matter
what you choose for x0 (that is for 1st degree
ax0 + b ax0 b b x1 = x0 -So you can see that x0 cancels completely, and that
= x0 - - = x0 - x0 - eq. 5.3-7 a a a a
Earlier I promised I'd show you a way to find square roots. We do this by constructing a polynomial whose zero is the square root of one of its coefficients. The polynomial that does that is
f(x) = x2 - C eq. 5.3-8You will agree, won't you, that when you substitute
We are going to use the same method for finding Shangrila this time as we did in the case of the 1st degree polynomial. Let's say that we want to find the ever-popular square root of 2. Then
f(x) = x2 - 2 eq. 5.3-9aSince we are going to need the derivative of this thing in order to apply the procedure, here it is as well:
f'(x) = 2x eq. 5.3-9bSo we pick an arbitrary guess at where Shangrila might be. I'm going to pick
Now we find x1 by applying 5.3-6 to x0.
Taking the quotient of f(x0) over
f'(x0), we get 1.166666.... Subtracting that
Figure 5.3-2a shows us how the signpost in the wilderness points us.
You can see on the graph how our choice of x0 places
us in the wilderness. So we start hiking from the point,
We are still not at Shangrila yet. So what to do to get closer? Look for another signpost that will get us to an x2. And since eq. 5.3-6 worked so well last time, we do the same thing to x1 to get x2 as we did to x0 to get x1
f(x1) x2 = x1 -
eq. 5.3-10 f'(x1)
We already know that
The brown trace in figure 5.3-2b shows how this procedure is the same as
departing from x1 using the derivative as a signpost,
and arriving at x2. And how close are we to Shangrila
now? With a calculator you can see that
Once again, we know x2 and f(x2).
It is easy to find
We can continue iterating the same procedure and get:
x4 = 1.41421378004720... x5 = 1.41421356237311...It turns out that x5 differs from the known value of the square root of 2 in only the 15th significant digit. To fifteen figures, the square root of 2 is 1.41421356237310.... What's more,
You may have noticed that with each iteration of this method, the number of digits of accuracy that we had achieved actually doubled. That is a characteristic of this method that is known as quadratic convergence. The method itself is called Newton-Raphson iteration. And you can use it to find the real zeros of any polynomial, no matter how high its degree is.
You can find a brief biography of Isaac Newton by
To see for yourself how well this works for finding square roots, get
out your calculator. See if you can use the Newton-Raphson iteration
method to find the square root of 24 using 5 as a
first guess (that is
f(x) = x2 - 24 eq. 5.3-11a f'(x) = 2x eq. 5.3-11bApply the method for only three iterations, then compare the result (that is your x3) with what the square root key on your calculator gives you for the square root of 24. Not bad, eh?
You will notice that in every problem where we apply Newton-Raphson to taking
a square root,
Now let's apply Newton Raphson to finding a zero to eq. 5.3-3. You will recall that it is:
x3 + 16x2 - 52x - 15 = 0So we have
f(x) = x3 + 16x2 - 52x - 15 = 0 eq. 5.3-12aAnd taking the derivative we also have
f'(x) = 3x2 + 32x - 52 eq. 5.3-12bIt is useful to know that polynomials of odd degree always have at least one real zero. The same is not true of polynomials of even degree. And if you apply Newton-Raphson to a polynomial that has no real zeros, you will get nowhere. But this one is of odd degree, so let's find one of its zeros. For this demonstration, I will pick
The general equation for Newton-Raphson iteration is
f(xn) xn+1 = xn -
This means that whenever you have an approximation, xn, that you want to turn into the next better approximation, xn+1, you apply eq. 5.3-13. When you substitute our current f(x) and f'(x) into 5.3-13 you get
xn3 + 16xn2 - 52xn - 15 xn+1 = xn -Applying eq. 5.3-14, starting with
eq. 5.3-14 3xn2 + 32xn - 52
x0 = 1.00000000000000 x1 = -1.94117647058824 x2 = -0.590015065697130 x3 = -0.288662835874521 x4 = -0.267024962511487 x5 = -0.266907347175526 x6 = -0.266907343690306
When I put x6 into f(x) I get zero to 15 significant figures, so there's no need to carry this on any further.
Notice that the successive approximations do jump around a bit at first. That is because 1 might not have been the best choice as a first guess. But by x3, Newton-Raphson had gotten the sign and one significant figure correct. It was rapid convergence from there.
Figure 5.3-3a shows the region of this function near the origin. In the
graph, the function is divided by 20 so that it will fit
conveniently into the frame. But scaling a function does not change
where it's zeros are a bit. Observe that if we had chosen
x0 greater than about 1.43, the Newton-Raphson
iteration would have converged to something other than
-0.266907343690306. Here is the same iteration but starting
x0 = 1.60000000000000 x1 = 9.32441860465117 x2 = 5.96893068605278 x3 = 4.10904512385328 x4 = 3.25723966832183 x5 = 3.02008494387405 x6 = 3.00014028560274 x7 = 3.00000000692899 x8 = 3.00000000000000
If you use
polynomial long division,
you can divide
= x2 + 19x + 5 eq. 5.3-15 (x - 3.0)
from which you can get the other two zeros by applying the quadratic formula. Figure 5.3-3b gives you a bigger view of the cubic we have solved here by showing f(x)/100 on a larger scale.
1) Since the 17th century, western music has been based upon the so called well tempered scale. According to this plan, there are twelve notes in each octave (including all the sharps and flats). For example, if you start at C, you have C, #C, D, #D, E, F, #F, G, #G, A, #A, B. After that, it starts over with the C of the next octave (notice that we don't count the C twice, and hence there are twelve notes and not thirteen). Twenty centuries before the advent of the well tempered scale, Pythagoras of the island of Samos in Greece had already discovered that when two musical notes sound an octave apart, the higher one vibrates at twice the frequency of the lower one. He also discovered that what the ear perceives as the pitch interval between notes is actually the ratio of their frequencies, and that two notes that harmonize have a ratio equivalent to the ratio of two small integers.
So much for the background of this problem. The well tempered scale divides the octave (a ratio of 2:1) into twelve equal intervals (which musicians call half-steps). Therefore the ratio of the frequencies of any two adjacent notes (ie, a half step apart) should be that number which, when raised to the twelfth power, gives 2. So what you must do is use the Newton-Raphson method to determine that number. Use 1.0 as your first guess.
2) Mary is a frugal person and saves her money diligently. She began saving in 1992. In that year, on January 1, she opened a savings account and deposited $1000. On January 1 of 1993, she deposited another $1500. On January 1 of 1994, she deposited $1500 again. On January 1 of 1995, she deposited $2500, and on January 1 of 1996, she deposited $3500. On January 1 of 1997, she checked her account balance before making her next deposit. It was $11953.84. The annual interest rate that the bank had been paying (and to simplify the problem, assume that interest is compounded annually) never changed throughout the time Mary had the account. Use Newton-Raphson to determine what that interest rate is. And don't panic. This problem is not as hard as you think. Think about what is going on with compound interest. See if you can find a polynomial interpretation of this problem.
Return to Table of Contents
Move on to 5.4 Like a Steam Locomotive (Rolle's Theorem)
email me at firstname.lastname@example.org