How do computers "solve" the three-body-problem?

Question

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?

Answer 1

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.

Answer 2

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)

Answer 3

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.

Answer 4

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.

Answer 5

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.