1. Introduction
Kepler’s equation (KE) is given by:
(1)
where e is the orbit eccentricity, E is the eccentric angle, and M is the anomaly angle, and both are in (radians). Despite its simple appearance, KE has caught the attention not only of astronomers but also of many great scientists and star mathematicians. When it comes to the solution of KE, there is a plethora of published solutions. Meeus [1] lists three methods, as well as references to literally hundreds of alternative solutions. Colwell [2] presented a comprehensive study of KE problem and classified the solutions of dozens of authors into categories; among them are analytic, numeric, geometric, and iterative methods. Esmaelzadeh et al. [3] made a numerical comparison of the initial values used for the methods given in [2]. Deakin [4] addressed those solutions that were based on series expansion, Newton-Raphson iterations, and the bisection iterative scheme. Mikkola [5] approximated the sine function to a cubic equation. Even though it led to a close initial condition, it requires computations of square and cubic roots. Danby [6] and [7] introduced what is called the fourth order Kepler solver. Its solution uses up to the fourth derivatives of the KE. Attempted empirical initial conditions are reported in [8]. Yet another attempt at an initial condition is given by Mather [9]. What sets the methods in the literature apart is the initial condition or avoiding it by using sorts of series expansion as in [10]. Initial condition indeed plays a central role in the speed of convergence. Common to all these methods are a convergence problem or a computational burden that occurs in the critical region (when eccentricity is close to one and anomaly is close to zero). It is worth noting that an unsuitable initial condition in this region can lead either to a huge number of iterations or to an outright absurd solution.
2. Solution Preparation
Since radians are rarely used in astronomy, we have adopted degrees as the unit for all angles. Hence, E and M will be in degrees, and Equation (1) becomes
(2)
where
,
, and the functions sinR and cosR are related to the familiar sine and cosine functions by
Thus, the range of E and M will be [−180 180]. However, the method is addressed for anomalies that only fall in the range [0 180], as the range [−180 0] is a mirror image of the former. (Incidentally, if E is further normalized by 360, then Chebyshev economization can be a competitive algorithm for computing sinR and cosR functions as given in [11].)
The Newton iterative method implies that if
is the
iterative step, then
is:
(3)
3. Algorithm Motivation
The initial condition to KE plays a central role in the stability of the solution and its rapid convergence. If it were not for the region in which the anomaly M is low and/or the eccentricity e is high, this problem would not have its glamour and mystery. Early on, investigators realized that an improper initial value, e.g.,
, can easily lead to a ridiculous outcome. The reason—as realized—is that the solution E of the equation is far away from M. We know that E > M, but by how much? Let us look at some data on what we call a critical zone: an area of low anomalies and high eccentricities, typically M < 0.2 and e > 0.98. So, we construct a 2-dim array of E = f(e, M) as in Table 1. The e's and M's are arbitrary and only for clarification. The top row displays e, and the left column displays M. The entries in the table are the E's for the given e and M. The last column displays (E-M)/M, for e = 1.
Table 1. E = f (M, e).
M\e |
0.91 |
0.92 |
0.93 |
0.94 |
0.95 |
0.96 |
0.97 |
0.98 |
0.99 |
1.00 |
(E-M)/M |
0.10 |
1.11 |
1.25 |
1.43 |
1.66 |
1.99 |
2.48 |
3.28 |
4.74 |
7.70 |
12.55 |
124.50 |
0.20 |
2.22 |
2.49 |
2.84 |
3.30 |
3.94 |
4.86 |
6.26 |
8.48 |
11.79 |
15.81 |
78.05 |
0.30 |
3.31 |
3.72 |
4.23 |
4.91 |
5.81 |
7.07 |
8.86 |
11.36 |
14.55 |
18.11 |
59.37 |
0.40 |
4.40 |
4.93 |
5.60 |
6.45 |
7.58 |
9.09 |
11.10 |
13.67 |
16.70 |
19.94 |
48.85 |
0.50 |
5.47 |
6.12 |
6.92 |
7.94 |
9.24 |
10.92 |
13.04 |
15.60 |
18.47 |
21.49 |
41.98 |
0.60 |
6.52 |
7.28 |
8.20 |
9.35 |
10.79 |
12.58 |
14.75 |
17.26 |
20.00 |
22.84 |
37.07 |
0.70 |
7.56 |
8.40 |
9.43 |
10.70 |
12.24 |
14.10 |
16.28 |
18.73 |
21.36 |
24.05 |
33.36 |
0.80 |
8.57 |
9.50 |
10.62 |
11.97 |
13.59 |
15.49 |
17.66 |
20.06 |
22.58 |
25.15 |
30.44 |
0.90 |
9.55 |
10.56 |
11.76 |
13.18 |
14.85 |
16.77 |
18.93 |
21.26 |
23.70 |
26.17 |
28.08 |
1.00 |
10.52 |
11.59 |
12.86 |
14.33 |
16.04 |
17.97 |
20.09 |
22.37 |
24.73 |
27.11 |
26.11 |
Let dE = E-M. The more we dive into the critical zone, we see that the quantities dE, dE/M, are larger than those in the rest of the table. (dE = O (100M) for M < 0.2˚.) This led investigators to either expand the sine function as in Mikolla [5] or adopt a series expansion as in Deakin [4]. Our objective is to avoid computational burden—such as solving a cubic equation or computing cubic roots—and construct a simple empirical solution that does the job. Now we encounter two options: either fit the E data with a high-degree 2-dimensional polynomial or reckon back to a series expansion. Both were unfavorable choices. But one thing was clear: the difference dE, for fixed M, was roughly linear in the eccentricity. That led to the idea of selecting dE = e.K(M) where K is a gain function of M. Surprisingly, this resulted in decreasing the number of iterations appreciably. It became evident that dissociating dE from M was truly helpful. How about selecting two points 'far' from M but relatively close to each other? Much better! We now have six iterations or less. How about selecting three points? Analyses and results for these two methods are given in detail below under algorithms L and Q, with comparison in the concluding section.
4. Algorithm L
Figure 1 below is the basis on which our algorithm is built. The intent is to describe all the variables that annotate the figure. The KE graph is usually drawn as ordinate M vs. abscissa E, with e as a parameter. Our interest will be with that of e = 1. Any point on the graph is determined by the pair (E, M). Point A on the graph will be associated with Ea, Ma, Likewise for point C. There will be a point on the graph whose ordinate is M, the given angle for which we desire to get the solution to KE, its abscissa is denoted by Etrue. Finally, E0 describes the location of the initial condition in the figure. The initial condition we propose here is an empirical one and is based on selecting two points
and
on the E-M graph in the vicinity of the perceived solution. The line that joins A & C and the given anomaly M can be used to interpolate the initial condition, as depicted in Figure 1.
Figure 1. Straight line that determines E0.
Now we proceed to the selection of A&C. As discussed earlier, dE, the correction estimate to M, naturally, is a product of the eccentricity e and some gain. Thus,
(4)
and,
(5)
Therefore, the points
and
become:
(6)
What remains is to decide what gains we should use, as we do not know what these gains are. However, we may get a cue from their upper and lower values. The KE implies
is a maximum at
and a minimum at
i.e.
. Now, we construct a 2-dimensional table similar to the one created above, albeit we fill the table with the number of iterations needed to perform these computations. With Ka = 0 and Kc = 90, we get Table 2. Next, we manually tune the values of Ka and Kc—one at a time—in a way that lowers the number of iterations, N, over the entire range. Admittedly, this is a laborious task, but it is done offline and only once. By lowering Kc to 45˚, one can see that the region in which N ≥ 4 has shrunk from (M ≤ 25˚), as seen in Table 2, to a region (M ≤ 4˚). For space considerations, no table is given.
Table 2. Number of iterations for
,
.
M\e |
0.89 |
0.9 |
0.91 |
0.92 |
0.93 |
0.94 |
0.95 |
0.96 |
0.97 |
0.98 |
0.99 |
1 |
0.5 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
5 |
6 |
7 |
15 |
1.0 |
3 |
4 |
4 |
4 |
4 |
4 |
5 |
5 |
6 |
7 |
8 |
10 |
1.5 |
4 |
4 |
4 |
4 |
5 |
5 |
5 |
6 |
6 |
7 |
8 |
17 |
2.0 |
4 |
4 |
4 |
5 |
5 |
5 |
5 |
6 |
6 |
7 |
8 |
11 |
2.5 |
4 |
4 |
5 |
5 |
5 |
5 |
6 |
6 |
6 |
7 |
8 |
8 |
3.0 |
4 |
5 |
5 |
5 |
5 |
5 |
6 |
6 |
7 |
7 |
8 |
8 |
3.5 |
4 |
5 |
5 |
5 |
5 |
6 |
6 |
6 |
7 |
7 |
7 |
8 |
4.0 |
5 |
5 |
5 |
5 |
5 |
6 |
6 |
6 |
6 |
7 |
7 |
8 |
4.5 |
5 |
5 |
5 |
5 |
5 |
6 |
6 |
6 |
6 |
7 |
7 |
7 |
5.0 |
5 |
5 |
5 |
5 |
5 |
6 |
6 |
6 |
6 |
7 |
7 |
7 |
5.0 |
5 |
5 |
5 |
5 |
5 |
6 |
6 |
6 |
6 |
7 |
7 |
7 |
15.0 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
25.0 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
5 |
5 |
5 |
5 |
5 |
35.0 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
45.0 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
55.0 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
65.0 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
75.0 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
85.0 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
95.0 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
105.0 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
115.0 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
125.0 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
135.0 |
3 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
145.0 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
155.0 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
165.0 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
175.0 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
Moreover, upping Ka to 15˚, N is lowered to 4 for M ≥ 0.2 and e < 0.98 as shown in Table 3. Manipulating the gains further will not lower N anymore.
Now, we repeat the above computations for the “critical zone” (M < 0.2 and e ≥ 0.98), and empirically tune the values of Ka and Kc, to obtain Ka = 5.76˚ and Kc = 15˚. Values of N in this zone are listed in Table 4.
Table 3. Number of iterations for
,
.
M\e |
0.89 |
0.9 |
0.91 |
0.92 |
0.93 |
0.94 |
0.95 |
0.96 |
0.97 |
0.98 |
0.99 |
1 |
0.01 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
5 |
6 |
0.02 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
5 |
6 |
0.03 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
5 |
5 |
5 |
0.04 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
5 |
5 |
5 |
0.05 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
5 |
5 |
5 |
0.06 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
5 |
5 |
5 |
0.07 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
5 |
5 |
4 |
0.08 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
5 |
5 |
4 |
0.09 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
5 |
5 |
4 |
0.10 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
5 |
5 |
4 |
0.11 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
5 |
5 |
4 |
0.12 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
5 |
5 |
4 |
0.13 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
0.14 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
3 |
0.15 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
3 |
0.16 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
3 |
0.17 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
3 |
0.18 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
2 |
0.19 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
3 |
0.20 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
3 |
Table 4. N (
&
)
,
.
M\e |
0.978 |
0.980 |
0.982 |
0.984 |
0.986 |
0.988 |
0.990 |
0.992 |
0.994 |
0.996 |
0.998 |
1.000 |
0.01 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
3 |
0.02 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
3 |
4 |
0.03 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
3 |
3 |
4 |
4 |
0.04 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
0.05 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
0.06 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
0.07 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
0.08 |
3 |
3 |
3 |
3 |
3 |
2 |
3 |
3 |
4 |
4 |
4 |
4 |
0.09 |
3 |
3 |
3 |
3 |
2 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
0.10 |
3 |
3 |
3 |
2 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
0.11 |
3 |
3 |
2 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
0.12 |
3 |
2 |
2 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
0.13 |
2 |
2 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
0.14 |
2 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
3 |
0.15 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
3 |
0.16 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
3 |
3 |
0.17 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
3 |
3 |
0.18 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
3 |
3 |
3 |
0.19 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
3 |
3 |
3 |
0.20 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
3 |
3 |
3 |
Now we refine the M's and e's into values to the thousandth. We encounter a very tiny sub zone
&
for which N = 5. Even though its values are impractical, we proceed to obtain its gains.
In summary, the values of Ka and Kc for all zones are:
(7)
Figure 2. Number of iterations ≤ 4—linear entire range.
From the straight line equation that joins A&C, the initial condition E0 is determined by:
(8)
This method is tested against a wide range of anomalies and eccentricities. The convergence criterion is given by. To visualize the performance of the algorithm, we created two figures to show the number of iterations. The first figure covers a wide range of eccentricities [0.05, 0.10:0.10:0.9, 0.91:0.01:1.] and the range of anomalies [0.01, 0.10:0.10:20, 21:1:180]. The second figure depicts the number of iterations in the critical zone: a refined range of eccentricities [0.900:0.001:1]. The range of anomalies is refined to [0.001˚:0.001˚:2˚]. The reason for this fine grid, 200,000 points, is to ensure that no point in this grid will fall in the crack.
Figure 3. Number of iterations ≤ 4—linear refined range.
Figure 2 shows the number of iterations vs. the entire anomalies and eccentricities using the linear method. Figure 3 shows the number of iterations vs. the critical values of anomalies and eccentricities.
5. Algorithm Q
Alternative to the two points in algorithm L, we select three points
,
, and
to fit a quadratic line. The points A&C are the same as in the linear algorithm. Point B, is selected midway between A&C:
(9)
As in Algorithm L,
(10)
(11)
Now, the points
,
, and
become:
(12)
The initial condition E0 is determined by the Lagrange formula:
(13)
where
Figure 4 shows the number of iterations vs. the entire anomalies and eccentricities with use of the quadratic method. Figure 5 shows the number of iterations vs. the critical values of anomalies and eccentricities in the refined range. The convergence criterion is the same as in the linear method. Also, the numbers of iterations are evaluated at the same values as in the linear method.
Figure 4. Number of iterations ≤ 4—quadratic entire range.
Figure 5. Number of iterations ≤ 4—quadratic refined range.
6. Three Iterations or Less
Can we find a way to reduce the number of iterations to three or less? Yes, surprisingly, with very little computational overload. All the above figures or the printed data show that a good part of the landscape already has three or fewer iterations. The rest have four iterations. We notice that they reside in the “critical zone”. So what about slicing this zone into eight sub zones, each having its own gains! The boundaries of these zones and the companion gains are listed below.
(14)
In the above equation, it should be noted that the first 'if' statement declares the most inner critical zone, which is followed by the next critical sub zone. As discussed previously, these gains are obtained by tuning the gains until we maximize the area in which N ≤ 3, then we continue with the next sub zone. Figures 6-9 illustrate the improved performance of modified the algorithm.
Figure 6. Number of iterations ≤ 3—linear entire range.
Figure 7. Number of iterations ≤ 3—linear refined range.
Figure 8. Number of iterations ≤ 3—quadratic entire range.
Figure 9. Number of iterations ≤ 3—quadratic refined range.
7. Numerical Analysis
Herein we address, briefly, issues that affect the numerical computations. A top concern is the convergence of the Newton iteration algorithm, which is discussed in Kreysig [12]. Herein, we follow this reference very closely its derivation and, for simplicity, we adopt its notations. We consider a continuous function
with a continuous first derivative
. The solution to
is found by Newton method iteratively by
(15)
where
is the initial iteration value and is close to the solution s, and
(16)
for which,
(17)
Differentiating the above equation, evaluating it at
, and substituting for
gives
(18)
Let the error at the nth iteration be,
(19)
Then, we arrive at:
“Second-Order Convergence of Newton’s Method” Theorem: If
is three times differentiable and
,
, s is solution of
and if
sufficiently close to s, then Newton’s method is of second order
(20)
That is the error convergence is quadratic. Addressing the above to KE gives:
(21)
which yields,
(22)
Example:
Consider the extreme point,
,
. Using the adopted procedure gives
. Solution of KE,
,
and
. Equation (20) shows that
This implies that in three iterations we can obtain the required accuracy10−10 rad.
This example shows no matter how closely e to unity, there will be quadratic convergence so long as the initial condition is close to the solution.
To evaluate the computer time for the adopted algorithm we run a C program on a computer with an old processor: Intel core 2 Duo CPU E8400@3GHz. We made 2 runs: First Run: eccentricity e ranges from 0.98 to 1.0 with steps of 0.0002; anomaly m ranges from 0.0001 to 0.2 with steps of 0.002. The number of KE solving is 10201. The execution time interval is 31 ms. Thus, the average execution time 3.04 us.
Second Run: eccentricity e ranges from 0.90 to 1.0 with steps of 0.001; anomaly m ranges from 0.001 to 2.0 with steps of 0.001. The number of KE solving is 202,000. The execution time interval is 594 ms. Thus, the average execution time 2.94 us.
8. Conclusion
We have introduced two main methods for computing KE. The first one resulted in a number of iterations that is below or equal to four. The computation included the critical zone of small anomalies and high eccentricities. The second one resulted in a number of iterations that is below or equal to three. Visual inspection of Figures 4 - 5 and Figures 8 - 9 shows that the quadratic method, on average, uses a smaller number of iterations. The computational burden for both methods is minimal, as they use simple algebra (no square or cubic root evaluation). Computing the initial condition requires evaluating two sine functions for the linear algorithm and three for the quadratic algorithm. Carrying out the Newton-Raphson conversion requires the usual evaluation of one sine and one cosine function.