December 25, 2008
Happy Newton's Day, 2008!
So here we are, celebrating our 5th Newton's Day at 3QD. Along with Richard Dawkins, we independently and simultaneously came upon the idea of celebrating Newton's Day on December 25th in 2004, and each year since then I have written a little something about Sir Isaac. Here are my posts from 2004, 2005, 2006, and 2007. Today, I'll explain a simple but very useful mathematical technique called Newton's Method, discovered by Newton in 1669, though he published it later.
Newton's Method is a way of iteratively finding closer and closer solutions to a certain kind of mathematical equation (a real-valued function f(x), to be technical). We do this in the following way (it may help to look at the concrete example from Wikipedia in the graphic following my description of the general method, to better understand what I mean):
- Take a guess at the solution (a value for x).
- Plug in this value for x and see what f(x) is.
- Draw a line tangent to the function at this point.
- The point where this line intersects the x-axis is your new and improved value for x.
- Take this new value for x and go back to step 2. (This repeating is called iteration.)
Have a look at the graph (from Wikipedia) on the right. The function f(x) is the curved line shown in blue. In other words, for any point x on the horizontal axis, the blue line shows the value of f(x) on the vertical axis. The root (or solution) of the function is where the function crosses the horizontal axis; in other words, where the value of f(x) is zero. In the graph here, this is the value marked X. So we take a guess, Xn, go up the dotted blue line to the function, and then calculate the tangent line to the function at that point. This is shown in red. We see where that line crosses the x-axis, and take that point, Xn+1, as our value for x in the next iteration. As you can see, Xn+1 is a better approximation of the actual root, X. When we repeat the process over and over, one can very quickly converge on the correct solution.
How exactly do we do this? Let me show you. We know from calculus (as did Newton, since he invented it) that the derivative of a function f(x) at given point, written f'(xn), is just the slope of the tangent line at that point. But we also know that the slope of a line is just the "rise", in this case, the value of f(xn) (on the vertical axis), divided by the "run," the amount we move from Xn+1 to Xn on the horizontal axis. Setting these two quantities as equal, we get this equation: the derivative of the function at Xn is equal to the value of the function at Xn divided by the distance between Xn and Xn+1. In proper algebraic notation:
f'(xn) = f(xn) / (Xn - Xn+1)
Mutiplying both sides by (Xn - Xn+1), we get:
(Xn - Xn+1) * f'(xn) = f(xn)
Dividing both sides by f'(xn), we get:
(Xn - Xn+1) = f(xn) / f'(xn)
Subtracting Xn from both sides, we get:
- Xn+1 = f(xn) / f'(xn) - Xn
And finally, multiplying both sides by -1, we get:
Xn+1 = Xn - f(xn) / f'(xn)
So that's how once we make an initial guess Xn, we get our next value Xn+1. And then repeat the process.
Look at this nice example from Wikipedia, where one wants to find the square root of 612:
In each successive result on the right hand side above, the correct digits are underlined. As you can see, one converges to a very accurate (to nine significant digits) approximation rather quickly. Well, there you go. That's Newton's Method. Interestingly, since computers are very fast at doing this sort of iteration, Newton's Method has become even much more useful now than when he invented it.
Oh, and if you don't understand "derivatives", just take my word for it: the derivative of the function "x2 - 612" is "2x" and don't worry about the details... :-)
I wish all of you a very happy holiday season, and also best wishes for a wonderful new year!
Posted by S. Abbas Raza at 12:00 AM | Permalink
Comments
Happy Newton's Day to you in Brixen too! It's lovely seeing one of your increasingly rare math posts. More in 2009, I say!
Posted by: Elatia Harris | Dec 25, 2008 12:10:01 AM
When I sat through early physics classes about 50 years ago we used books by professor Francis Weston Sears, a former MIT professor of physics. These books were used by generations of physicists and engineers world wide. In fact, when I was at Berkeley, my friend Sheng Ma had pirated copies of these books from China. In the chapter on gravitation, professor Sears made the statement that "we do not today (about 1950) understand the (microscopic) cause of the gravitational force of attraction between all masses" or words to that effect. That was roughly 3 centuries from Newton. Today, almost 2009, we are another half century or so from Newton, roughly 350 years, and we still do not understand the microscopic cause of gravity or why all masses attract with a force proportional to the product of their masses and inversely proportional to the square of the distance between them, multiplied times the universal gravitional constant.
It is this force, of course, which is responsible for our own solar system and the various motions of the planets and earth about the Sun, all predicted precisely by the genius Issac Newton and his fundamental discovery. Kepler's laws are also predicted and the fact that all planets move in elliptical orbits about the Sun.
Fortunately for us, it is not necessary to understand the microscopic cause of gravity in order to build giant sckyscrapers, fly airplanes, take a trip to the Moon or send man up in a space shuttle and land it precisely at Edwards Air Force Base as was recently so beautifully and elegantly done the other day. All this is a result of Newton's laws of mechanics and his law of gravitation discovered three and a half centuries ago and basically confirmed for all to see on television every time the shuttle takes off or lands and every time you fly in a plane or feel a building sway in the wind in Chicago or New York or Los Angeles.
But why is it so difficult to understand the "cause" of gravity as we understand the "cause" of electromagnetism a-la quantum-electrodynamics? We can understand part of the answer if we consider a paper by Richard Feynman (posted above) on the subject. Many years ago he wrote an unpublished paper formally expanding the gravitational field equations into the usual relativistically invariant Born Series in analogy with QED for which he and two others received the Nobel Prize. Here is the main difference between the two situations: In the case of QED, the basic field equations are Maxwell's equations which are relativistically invariant as they stand. However, the gravitational field equations a-la Einstein are "classical" field equations, a step removed from those of Maxwell. It is not clear how to extend them to a quantum mechanical setting. Furthermore they are non linear even in a vacuum setting so this complicates the task enormously from a mathematical point of view. One can establish, however, that if it is meaningful to discuss the gravitational force in terms of a field, that field is a spin-2 field (graviton?) in contrast to the electromagnetic field which is a spin-1 field (photon) and of course is both attractive and repulsive. The spin-2 field is only attractive. We may never understand the true "cause" of gravity. But we can still be amazed and marvel at the beauty of gravitation and be thankful for its attraction which keeps us firmly on the ground and keeps the atmosphere around the earth to provide us oxygen to give us the energy for our life every day. If all this was created by random evolution, I am thankful for that. If all this was created by a genius level God, I am equally thankful for that too. We likely will never understand the true cause of that either.
Posted by: Winfield J. Abbe | Dec 25, 2008 8:33:17 AM
of course
1. One must be careful to make a good enough "first guess" so that the derivative never goes to zero between your first guess and the actual root.
2. This method is guaranteed to work if the derivative has magnitude less than 1 (and stays non zero) in some interval that contains your first guess and the actual root.
Posted by: ollie | Dec 25, 2008 9:42:37 AM
Ollie is right, of course. I should probably not have skipped the caveats in the interest of simplicity. Thanks.
Posted by: S. Abbas Raza | Dec 25, 2008 11:54:49 AM
Oh no, I am not fussing. I was merely pointing out that there are nerds out here that know what you are talking about. :)
Posted by: ollie | Dec 25, 2008 3:39:57 PM
Post a comment