N–Body Problem

views updated

N-Body Problem

Newtonian gravitation

Solving the problem

Computers to the rescue?


The N-body problem is a specific way to find, when given initial characteristics (such as velocity and mass) of an n number of bodies, their motions as determined by classical mechanics. One way to learn more about the N-body problem is to consider the law of gravity and the motions of celestial bodies.

Newtonian gravitation

Everywhere astronomers look in the universe, they see clusters of objects. Most stars are not single, like the sun; they consist of two or more stars orbiting one another. Groups of stars are found in the open and globular star clusters, the latter containing up to a million stars. The Milky Way galaxy is a huge swarm of a few hundred billion stars, and galaxies themselves are grouped into clusters.

These clusters of objects, whether they be individual stars, star clusters, clouds of gas, or groups of galaxies, are impelled to move relative to one another in accordance with the law of gravitation. In most circumstances, the law of gravity as developed by English physicist and mathematician Sir Isaac Newton (16421727) describes the motion of these objects adequately. (In some extreme conditions, such as around very dense objects with intense gravitational fields, and even in very high-precision analyses of the orbits of more mundane objects like the planet Mercury, GermanAmerican physicist Albert Einsteins (18791955) treatment of gravitation in his theory of general relativity is required.) Newton discovered that the motions of orbiting objects could be explained (and predicted) if the gravitational attraction between two bodies depended on the product of their masses and the inverse square of their distance. The complete, analytical solution of the so-called two-body problem is one of the great triumphs of classical mechanics.

Difficulties arise, however, when one considers more than two bodies. The motions in a system of three interacting bodies, defining (sensibly enough) the three-body problem, cannot fully be treated analytically, meaning that one cannot derive on paper a single equation to predict the positions and velocities of the three bodies in the system at some arbitrary time in the future. An analytic solution is likewise impossible for a larger system of some number N of objects, and this seemingly intractable situation is called the N-body problem.

The N-body problem has many very important applications in astronomy. Wherever the long-term motions of a large group of gravitationally interacting bodies are concerned, the N-body problem looms large. This covers such diverse areas as the evolution of the solar system, the formation and gradual dissipation of clusters of stars, the evolution of galaxies, and even the overall evolution of the clusters of galaxies that comprise the large-scale structure of the universe. Some approach to solving the N-body problem is clearly desirable.

Solving the problem

As described above, there is no analytic solution for the N-body problem. However, it is possibleat least in principleto solve the N-body problem numerically. A qualitative description of this is as follows. Suppose one has four bodies stars for instanceall moving around one another under the influence of each others gravity. At a given time, scientists can calculate the gravitational force felt by star 1 using Newtons law of universal gravitation; this force is simply the sum of the forces exerted by the three other stars. One could do the same calculation for the other three stars. Knowing the force acting on the star, scientists can predict its motion, but only for a short period of time, since all the stars are moving and the gravitational force they exert on one another is constantly changing. Once the stars have

Key Terms

Law of universal gravitation The law developed by Isaac Newton that describes the motion of objects moving under the influence of their mutual gravitational force, which is proportional to the product of their masses and the inverse square of the distance between them.

N-body problem The problem of computing the motions over time of a system of some number of objects moving under the influence of their mutual gravitational attraction; this problem does not have an analytic solution and must be tackled by numerical or statistical methods.

Singularity In general, a situation in which a mathematical computation fails due to its value approaching infinity; in N-body computations, a singularity occurs where the distance between two particles approaches zero and the gravitational force imparted by one to the other approaches infinity.

Star cluster The targets of extensive N-body computations, these are collections of several hundred (open clusters) or several hundred thousand (globular clusters) stars held together by their mutual gravity. Much has been learned about their long-term evolution from N-body computations.

Two-body problem A fundamental problem of classical mechanics, the description of the motion of two objects moving under the influence of their mutual gravity; this problem has an explicit analytic solution.

moved a short distance, one needs to recalculate the force, re-derive the direction and velocity of each star, and allow them to move some moreagain, only for a short distance, at which point yet another calculation of the various forces will be required.

If the description above sounds tedious, it is! This is what scientists call an iterative process, a process in which the same steps are repeated many times. To predict the evolution of a cluster of stars, one might have to repeat the process described above thousands, even hundreds of thousands of times. Obviously, it would be sheer madness to attempt this on paper, and indeed, significant N-body calculations were nonexistent prior to the invention of computers.

Computers to the rescue?

The N-body problem is one ideally suited to a computera machine that can repeat a prescribed string of commands with blazing speed. So, the task now seems simple: plug Newtons law of gravitation into a large computer, specify the initial positions and velocities of the objects under study, hit return, and sit back with a cool drink to watch the fun. Of course, nothing is ever that easy.

Even the fastest computer in the world cannot overcome the fact that direct numerical computation of the evolution of a large system of objects is not feasible. Consider a star cluster. Because every star acts gravitationally on every other star, the number of calculations required to determine all the gravitational force components in a system of N objects goes roughly as N squared. For a modest-sized globular cluster of 500,000 stars, the computer would need to do 25 billion calculationsand that is just for the first force computation. Remember that after a certain time interval, usually called the time step, the forces must all be re-calculated. Globular clusters are long-lived objects; the ones orbiting the Milky Way Galaxy are probably 10 billion years old. Millions of time steps would be required to trace the entire history of the cluster, and the total number of calculations runs into the quintillions.

Even worse, early N-body calculations showed that a very common occurrence in star clusters was the formation of close binary starstwo stars orbiting one another so closely that in some cases they share a common atmosphere. The time step for the force calculation for these stars has to be very short, because the stars change their positions relative to one another quite rapidly. Additionally, the very small distance between these stars leads to singularities places where the computations produce values going to infinity. (This happens because when stars are nearly touching, the distance between them is almost zero relative to the size of the entire cluster or galaxy, and this value appears in the denominator of the force equation.)

The manifold difficulties with performing explicit N-body calculations have led researchers since 1960 to construct increasingly complex computer codes to deal with them. Codes have been developed that can apply different time steps to different objects, prevent the formation of close binaries, and effectively reduce the number of particles in a calculation by determining the average force imparted by groups of particles, rather than calculating them all explicitly. Many codes get rid of singularities by applying what is usually called softening to the system; this effectively means changing the force equation so that the troublesome zero never appears. Still other methods leave the realm of direct N-body calculations altogether and apply statistical methods to estimate the behavior of the entire system. Although these approximate methods have represented the best compromise available in the face of limited computing power, they are clearly not fully satisfactory, since different methods applied to the same N-body system do not always yield the same results. Since reproducibility of results is a cornerstone of science, the various methods summarized above have sometimes been sharply criticized, and there is widespread agreement that so far, no method yet devised is fully capable of correctly addressing the evolution of stellar and galactic systems.

This ongoing difficulty is the source of the question mark in the title of this part of this essay. It is possible to write a complex computer program that runs without crashing and generates page after page of resultsand yet have those results bear no resemblance at all to reality. Computers are very fast, but very literal-minded: they will do exactly what one tells them to, even if what one tells them is riddled with errors. Most (but not all) researchers realize that, and qualify their work with appropriate statements about the limitations of their code and their machines. Any aspiring scientist would do well to follow this lead, which is almost nowhere more important than in the arena of N-body calculations.



Bruus, Henrik. Many-body Quantum Theory in Condensed Matter Physics: An Introduction. Oxford, UK, and New York: Oxford University Press, 2004.

Valtonen, Mauri J. The Three-body Problem. Cambridge, UK, and New York: Cambridge University Press, 2006.


McDowell, Charlie, Department of Computer Science, University of California at Santa Cruz. This is an applet for displaying animations of n body orbits. <http://www.cse.ucsc.edu/~charlie/3body/> (accessed accessed October 18, 2006).

Jeffrey Hall