Izzo algorithm for Lambert's problem - poliastro/poliastro GitHub Wiki

Resources

• Original paper http://arxiv.org/pdf/1403.2705v2.pdf

Performance

In section 5 there are some interesting performance explanations.

For the purose [sic] of this test we reimplement both our and Gooding algorithm in pure Python language (i.e. no C++ bindings) and we record the execution time to solve the same 100,000 randomly generated problems (using the same bounds as above). In the case M = 0, the proposed algorithm resulted to be faster by a factor 1.25, while in the multi revolution cases by a factor 1.5.

In short, Izzo algorithm results faster than Gooding. It uses a quartic (instead of cubic) iteration scheme and a better initial guess.

Iteration schemes

There are some subtle naming convention details that I need to clarify.

Gooding algorithm employs Halley iterations, while we make use of Householder iterative scheme. While Halley’s method has a slighlty lower complexity and does not need to compute also the third derivative from Eq.(22), our iterative scheme reaches, in the case M = 0, a comparable accuracy in only 2 iterations on average compared to the 3 iterations needed for the Gooding case.

• Halley's method https://en.wikipedia.org/wiki/Halley%27s_method
• Higher order http://numbers.computation.free.fr/Constants/Algorithms/newton.html
• Source paper http://www.sztaki.hu/~bozoki/oktatas/nemlinearis/SebahGourdon-Newton.pdf
• A more mathematical approach http://math.sfsu.edu/fpsac/pdfpapers/dmAN0162.pdf

Coding

SciPy has had Halley's method since 0.11 (not documented on the release notes, by the way), whereas Householder (quartic?) scheme is not implemented anywhere (after a quick Google search).

On the other hand, it's not clear if scipy.optimize.newton is numbifiable or not. For instance, it is used in poliastro.twobody.angles but without acceleration. This is a problem worth exploring on its own.