Solving Kepler's equation via Smale's α-theory

We obtain an approximate solution $\tilde{E}=\tilde{E}(e,M)$ of Kepler's equation $E-e\sin(E)=M$ for any $e\in[0,1)$ and $M\in[0,\pi]$. Our solution is guaranteed, via Smale's $\alpha$-theory, to converge to the actual solution $E$ through Newton's method at quadratic speed, i.e. the $n$-th iteration produces a value $E_n$ such that $|E_n-E|\leq (\frac12)^{2^n-1}|\tilde{E}-E|$. The formula provided for $\tilde{E}$ is a piecewise rational function with conditions defined by polynomial inequalities, except for a small region near $e=1$ and $M=0$, where a single cubic root is used. We also show that the root operation is unavoidable, by proving that no approximate solution can be computed in the entire region $[0,1)\times[0,\pi]$ if only rational functions are allowed in each branch.