# How do computers “solve” the three-body-problem?

I've done a bit of research, and have learned that computers "solve" the three-body-problem by using "Numerical methods for ordinary differential equations", but I can't really find anything about it other then Wikipedia. Does anyone have any good sources about this topic that isn't any kind of Wikipedia?

My thoughts:
Currently I'm using simulations of three bodies flying around each other, using Newton's gravitational law, and at a random time in the simulation, everything goes chaotic. I though that this was the only way to kind of "solve" it, but how does this "Numerical methods for ordinary differential equations" method work? And what does the computer actually do?

• Related post by OP: physics.stackexchange.com/q/456720/2451 – Qmechanic Jan 26 at 10:38
• Do you want to learn how to write your own gravity sim software? Do you know much calculus? – PM 2Ring Jan 26 at 10:53
• it is unclear how your simulator "solved it". Did you make it? – Wolphram jonny Jan 26 at 10:59
• What are these "simulations" fat you're currently using? – Emilio Pisanty Jan 26 at 19:43
• In addition to the answers that mention Verlet, the computational approach for high-precision integration of the n-body problem is described in the article High precision Symplectic Integrators for the Solar System. – homocomputeris Jan 27 at 21:24

Numerical analysis is used to calculate approximations to things: the value of a function at a certain point, where a root of an equation is, or the solutions to a set of differential equations. It is a huge and important topic since in practice most real problems in mathematics, science and technology will not have an explicit closed-form solution (and even if they have, it might not be possible to compute with infinite precision - computers after all represent numbers with finite precision). In general there are trade-offs between accuracy and computational speed.

For the three-body problem we have three point masses in starting locations $$\mathbf{x}_i(0)$$ with velocities $$\mathbf{v}_i(0)$$ that we want to calculate for later times $$t$$. Mathematically we want to find the solution to the system $$\mathbf{x}'_i(t)=\mathbf{v}_i(t),$$ $$\mathbf{v}'_i(t)=\mathbf{f}_i(t)/m_i,$$ $$\mathbf{f}_i(t)=Gm_i \sum_{j\neq i} \frac{m_j(\mathbf{x}_j-\mathbf{x}_i)}{||\mathbf{x}_i-\mathbf{x}_j||^3}.$$

The obvious method is to think "if we move forward a tiny step $$h$$ in time, we can approximate everything to be linear", so we make a formula where we calculate the state at time $$t+h$$ from the state at time $$t$$ (and so on for $$t+2h$$ and onwards): $$\mathbf{x}_i(t+h)=\mathbf{x}_i(t)+h\mathbf{v}_i(t),$$ $$\mathbf{v}_i(t+h)=\mathbf{v}_i(t)+h\mathbf{f}_i(t).$$ This is called Euler's method. It is simple but tends to be inaccurate; the error per step is $$\approx O(h^2)$$ and they tend to build up. If you try it for a two body problem it will make the orbiting masses perform a precessing rosette orbit because of the error build-up, especially when they get close to each other.

There is a menagerie of methods for solving ODEs numerically. One can use higher order methods that sample the functions in more points and hence approximate them better. There are implicit methods that instead of trying to find a state at a later time only based on the current state look for a self-consistent late and intermediate state. Most serious methods for solving ODEs will also reduce the step-size $$h$$ when the forces grow big during close encounters to ensure that accuracy remains acceptable. As I said, this is a big topic.

However, for mechanical simulations you may in particular want to look at methods designed to preserve energy and other conserved quantities (symplectic methods - these are the ones used by professionals for long-run orbit calculations). Perhaps the simplest is the semi-implicit Euler method. There is also the Verlet method and leapfrog integration. I like the semi-implicit Euler method because it is super-simple (but being a first order-method it is still not terribly accurate): $$\mathbf{v}_i(t+h)=\mathbf{v}_i(t)+h\mathbf{f}_i(t),$$ $$\mathbf{x}_i(t+h)=\mathbf{x}_i(t)+h\mathbf{v}_i(t+h).$$ Do you see the difference? You calculate the updated velocity first, and then use it to update the positions - a tiny trick, but suddenly 2-body orbits are well behaved.

The three body problem is chaotic in a true mathematical sense. We know there are situations where tiny differences in initial conditions get scaled up to arbitrarily large differences in later positions (even if we rule out super-close passes between masses). So even with an arbitrarily fine numerical precision there will be a point in time where our calculated orbits will be totally wrong. The overall "style" of trajectory may still be correct, which is why it is OK to play around with semi-implicit Euler as long as one is not planning any space mission based on the results.

• For better accuracy, in addition to using a numerical solution like RK4 (Runge Kutta 4), the fact that the total energy of the system (potential and kinetic) is constant is taken into account, but I don't recall the mathematical process used to constrain the total energy to a constant value. There are some difficult cases, such as when one of the bodies has a relatively huge orbit, such as a sun, a planet, and an asteroid. – rcgldr Jan 26 at 15:45
• It is also worth pointing out that computers cannot operate on arbitrary real numbers or even solutions to polynomials without ever increasing data for the values used. Therefore, even if a perfect symbolic solution were found to a differential equation we'd be unable to compute any value of that function if it were anything past a simple linear equation. – The Great Duck Jan 26 at 16:54
• @JBentley no because of floating point precision, see the famed What every computer scientist needs to know about floating point arithmetic. – Kyle Kanos Jan 30 at 12:52
• @rcgldr I believe what you're looking for is called a symplectic integrator. See en.wikipedia.org/wiki/Symplectic_integrator – probably_someone Jan 30 at 12:57
• @JBentley the question is about the numerical implementation, so your remark lends to the confusion here. The physics of it is that it's an unsolved problem (see the answer to the linked question physics.stackexchange.com/a/456722/25301 ), so I think discrete time is irrelevant. – Kyle Kanos Jan 30 at 14:17

The "solution" of the three-body problem can be written as the pair of differential equations, \begin{align} \vec{v}&=\frac{\mathrm d\vec{x}}{\mathrm dt}\\ \vec{a}&=\frac{\mathrm d\vec{v}}{\mathrm dt} \end{align} where the latter is usually written in terms of the force, $$m\vec{a}=\vec{F}$$. Then using the definition of the derivative, $$\frac{\mathrm df}{\mathrm dx}=\lim_{h\to0}\frac{f(x+h)-f(x)}{h},$$ the differential equations we started with can be written as the finite difference equations, \begin{align} \vec x(t+\mathrm dt)&\simeq \vec x(t)+\vec v\,\mathrm dt \\ \vec v(t+\mathrm dt)&\simeq \vec v(t)+\vec a\,\mathrm dt \end{align} which is done assuming that $$\mathrm dt$$ is "just small" rather than infinitesimal.

It is these equations that a computer uses to "solve" the three body problem: given an initial condition for each of the bodies, the computer iteratively steps forward in time using the above finite difference equations with the force being the $$n$$-body force.

As mentioned in the comments, the simplistic model above is called Euler integration which is not at all well-suited for this problem because it does not conserve energy. A better option is called velocity Verlet, which is disucssed in other posts on physics.SE (I would recommend this post of mine as it gives some decent, but brief, details of the implementation).

A reasonably accessible paper on the three body problem, including a discussion on the numerical algorithms, is Musielak & Quarles (2014). For a larger discussion of more-useful higher-order techniques, as suggested by homocomputeris, see Farrés et al (2012)

• Velocity verlet is "good" only in comparison to Euler. For solving the solar system, it's rather worthless. Accuracy degrades rapidly. People use verlet because (a) it shows some short-term dynamics, (b) it kinda-sorta conserves quantities that should be conserved, and (c) the higher order techniques used to "solve" the solar system don't extend well to several thousand objects, let alone millions and millions of objects. – David Hammen Jan 26 at 14:17
• @DavidHammen all very good points. Note that I only said Verlet is a better option vs Euler, not that it's the best or any similar such comparison. – Kyle Kanos Jan 26 at 14:21
• @David Fair point. However, it's easy to increase the order of Leapfrog (a close sibling of Verlet) via Yoshida coefficients. IIRC, you could even make it adaptive, so it only uses as a high an order as is currently required, since you can do the Yoshida transform recursively, but I haven't tested that yet. – PM 2Ring Jan 31 at 16:30

A few years ago I put together a model of the inner solar system, the sun, Earth's moon, and the planets from Mercury to Mars.

I used a Leapfrog variation of Rk4 and got decent results, orbital periods consistent with initial configurations that stayed stable over time. Even some of the bad things I got I think suggested good numerical practices.

I'd initialize my planets with initial momentum, with the sun having zero initial momentum. The momentum of the planets didn't cancel out, so there was this weird net drift in roughly a straight line direction it took a while to figure out.

In addition to sorting that out, one feature I found important was the order of applying changes to position and speed.

You don't want to iterate through your bodies, calculate the net force in one pass body by body, and then apply your dynamic changes body by body. Otherwise it will, say, update the position of Venus, while keeping the position of Mars unchanged while you are updating the position of Earth. Your time steps get out of sync.

Store somewhere in memory the new displacements and velocities as you iterate through the bodies, and only after finding your dynamics at the present tick, run through and apply your changes. Apologies and congrats if you caught that on your first try. It tripped me up for a bit.

One way to simulate three bodies is using time step increments, in which you pretend that each body accelerates at a constant rate for a brief period of time. You start with the initial position vectors, velocity vectors, and the masses of the bodies, and then use them to calculate the acceleration vector of each body. In Newtonian Physics the gravitational acceleration vector of Body A from Body B is given by the equation $$\vec{a_{GA}}=-\frac{G\left(\vec{A}-\vec{B}\right)M_B}{||\vec{A}-\vec{B}||^3}$$ with $$G$$ being the Gravitational Constant, $$\vec{A}$$ being the position vector of Body A, $$\vec{B}$$ being the position vector of Body B, $$M_B$$ being the Mass of Body B, and $$\vec{a_{GA}}$$ being the Gravitational Acceleration Vector of Body A. In order to find the total gravitational acceleration vector of Body A you add up each of the gravitational acceleration vectors of body A from each of the other bodies.

You can find the position vectors and velocity vectors at the end of time step $$n$$ using the general formulas $$\vec{x_n}=\frac{1}{2}\vec{a_{n-1}}s^2+\vec{v_{n-1}}s+\vec{x_{n-1}}$$ $$\vec{v_n}=\vec{a_{n-1}}s+\vec{v_{n-1}}$$ with $$\vec{a_{n-1}}$$ being the acceleration vector for time step $$n-1$$, $$\vec{v_{n-1}}$$ being the velocity vector for time step $$n-1$$, $$\vec{x_{n-1}}$$ being the position vector $$n-1$$, $$s$$ being the length of the time step increments, $$\vec{x_n}$$ being the position vector for time step $$n$$, and $$\vec{v_n}$$ being the velocity vector for time step $$n$$. At each time step you also recalculate the acceleration vectors as they are not constant.

This method of simulating $$n$$ bodies works for any force law, meaning that you can use it for simulating $$n$$ bodies for a force law $$F=f(r)$$, with $$f(r)$$ being some function of distance, although in the case of the force law $$F=f(r)$$ the equation I specified previously for calculating the acceleration of Body A from body B becomes $$\vec{a_{GA}}=-\frac{\vec{A}-\vec{B}}{||\vec{A}-\vec{B}||}GM_Bf\left(||\vec{A}-\vec{B}||\right)$$ but the other formulas I mentioned, including the part about adding the acceleration vectors remain the same.

It turns out that knowing the pairwise trajectories one can determine the equation of motion of bodies. The equations of motion are written as $$\frac{d^2 \vec r^k}{ds^2}=-G\sum_{n=1,n\ne k}^N \frac{m_n(\vec r^k-\vec r^n)}{|\vec r^k-\vec r^n|^3}\tag{1}$$ We solve the auxiliary problem of pair interaction of bodies with reduced inertial mass $$\frac{m_n m_k}{\sum_{k=1}^N m_k} \frac{d^2 \vec R^{kn}}{ds^2}=-G \frac{m_n m_k\vec R^{kn}}{|\vec R^{kn}|^3 }\tag{2}$$ These equations differ in different initial conditions. Subtract from equation (2) equation (1), we get $$\frac{d^2 R_0^k}{ds^2}-\frac{d^2 r^k}{ds^2}= G\sum_{n=1,n\ne k}^N \frac{m_n(\vec r^k-\vec r^n)}{|\vec r^k-\vec r^n|^3}- G\sum_{n=1,n\ne k}^N \frac{m_n\vec R^{kn}}{|\vec R^{kn}|^3}=0,\vec R^{kn}=\vec r^k-\vec r^n$$ Where $$\vec R_0^k=\sum_{n=1 n \ne k}^N \frac{m_n \vec R^{kn}}{\sum_{p=1}^N m_p}$$ Get the formula $$\frac{d^2 \vec R_0^k}{ds^2}=\frac{d^2 \vec r^k}{ds^2}$$ Integrating this equality, we obtain the equation of motion for each of the N bodies. $$\vec r_0^k=\frac{d\vec r^k(0)}{ds}s+\vec r^k(0)+\vec R_0^k(s)- \frac{d\vec R^k(0)}{ds}s-\vec R^k(0)= \vec R_0^k(s)$$ The movement of each body is determined by the movement of the center of inertia of the pair body system. Initial conditions are determined from the condition $$\frac{d\vec r^k(0)}{ds}s+\vec r^k(0)= \frac{d\vec R^k(0)}{ds}s+\vec R^k(0)\tag{3}$$ We select the coordinate system $$\sum_{n=1}^N m_n \vec r^n(0)=0,\sum_{n=1}^N m_n \frac{d \vec r^n(0)}{ds}=0$$ and then condition (3) is satisfied identically. Will get $$\vec R^{kn}(0)=\vec r^k(0)- \vec r^n(0), \frac{d \vec R^{kn}}{ds}(0)=\frac{d \vec r^k}{ds}(0)-\frac{d \vec r^n}{ds}(0)$$ The energy of the pair trajectory of the system are calculated by the formula $$E_{kn}=\frac{m_k m_n}{\sum_{q=1}^N m_q} (\frac{d \vec R^{kn}}{ds}(0))^2/2-\frac{G m_k m_n}{|\vec R^{kn}(0)|}+\frac{M_{kn}^2\sum_{q=1}^N m_q}{2 m_k m_n |R^{kn}|^2}=\frac{m_k m_n}{\sum_{q=1}^N m_q} (\frac{d \vec R^{kn}}{ds}(0))^2/2-\frac{G m_k m_n}{|\vec R^{kn}(0)|}+\frac{m_k m_n}{2 \sum_{q=1}^N m_q |R^{kn}(0)|^2}(\frac{d \vec R^{kn}}{ds}(0)\times \vec R^{kn}(0))^2$$ The moment of the pulse is determined by the formula vector product $$M_{kn}=\frac{m_k m_n}{\sum_{q=1}^N m_q} \frac{d \vec R^{kn}}{ds}(0)\times \vec R^{kn}(0)$$ In this case, the constructed solution is substituted into the calculated trajectories $$\vec r_0^k-\vec r_0^p$$ of the planets and used $$\vec R^{kp}=r^k-r^p$$, then we get $$\vec R^{kp}=\vec r_0^k-\vec r_0^p$$. Indeed $$r_0^k-r_0^p =\sum_{n=1}^N \frac{m_n \vec R^{kn}}{\sum_{q=1}^N m_q}-\sum_{n=1}^N \frac{m_n \vec R^{pn}}{\sum_{q=1}^N m_q}=\sum_{n=1}^N \frac{m_n (\vec r^k-\vec r^n)}{\sum_{q=1}^N m_q}-\sum_{n=1}^N \frac{m_n (\vec r^p-\vec r^n)}{\sum_{q=1}^N m_q}=\vec r^k-\vec r^p=R_{kp}$$ Simplified Formula $$\vec r_0^u=\sum_{n=1}^N \frac{m_n \vec R^{un}(s)}{\sum_{q=1}^N m_q |R^{un}(s)|} \frac{p_{un}}{1+e_{un}cos(\varphi_{un}-\varphi_{un0})}$$ The angle is calculated by the formula $$\varphi_{un}-\varphi_{un0}=\int_0^s \frac{M_{un}}{|\vec R^{pn}(u)|^2}du$$ The magnitude $$\frac{R^{un}(\varphi)}{|R^{un}(\varphi)|}=\frac{\vec R^{un}(0)}{|\vec R^{un}(0)|}cos\varphi+\frac{\vec R^{un}(0)\times \vec M_{un}}{|\vec R^{un}(0)\times \vec M_{un}|}sin\varphi$$ of the angle $$\varphi$$ common to all pair trajectories corresponds to the direction $$\frac{R^{un}(\varphi)}{|R^{un}(\varphi)|}$$ with single orths $$\frac{\vec R^{un}(0)}{|\vec R^{un}(0)|},\frac{\vec R^{un}(0)\times \vec M_{un}}{|\vec R^{un}(0)\times \vec M_{un}|}$$. We have the final formula for the trajectory of bodies $$\vec r_0^u(\varphi)=\sum_{n=1}^N \frac{m_n}{\sum_{q=1}^N m_q}[\frac{\vec R^{un}(0)}{|\vec R^{un}(0)|}cos\varphi+\frac{\vec R^{un}(0)\times \vec M_{un}}{|\vec R^{un}(0)\times \vec M_{un}|}sin\varphi]\frac{p_{un}}{1+e_{un}cos\varphi}$$ But for the lack of an infinite solution even for a short time, it is necessary to assume $$|\vec R^{un}(\varphi)|=\frac{p_{un}}{1+e_{un}cos\varphi}>0,e_{un}<1$$ This imposes a restriction on the value of the parameters; the energy of pair interaction must be negative. Thus, bodies of small mass are excluded, whose contribution to the energy of the system is not significant. According to the formula of pair interaction, the radius varies according to the law see Landau Lifshits volume 1 $$r=a(ecosh\xi-1);t=\sqrt{\frac{a^3}{G\sum_{q=1}^N m_q}}(esinh\xi-\xi),r\approx c\sqrt{\frac{r_g}{a}}t$$ After simple transformations, this formula is reduced to $$r=\sqrt{V^2(0)+\frac{(\vec V(0)\times \vec R(0))^2}{R(0)^2}-\frac{2G\sum_{q=1}^N m_q}{R(0)}}t$$ This linear increase in radius shifts the center of gravity of the system. A particle moving to infinity leads to the whole system being carried along and the center of gravity shifts. The second cosmic velocity corresponds to a positive value of the radicand, or positive energy of the system.

• The formula $\vec r_0^k(s)=\sum_{n=1}^N \frac{m_n \vec R^{kn}(s)}{\sum_{q=1}^N m_q}$ defines the trajectories on paired paths $\vec R^{kn}(s)$. – Evgeniy Yakubovskiy Jan 30 at 15:56