Solving cubics by polynomial fitting

摘要

A top-performance algorithm for solving cubic equations is introduced. This algorithm uses polynomial fitting for a decomposition of the given cubic into a product of a quadratic and a linear factor. This factorization can be computed extremely accurately and efficiently using a fixed-point iteration of the linearized fitting error. The polynomial fitting concept performs orders of magnitude better in terms of numerical accuracy and precision than any of the currently known and available algorithms for solving cubic equations. A special exception handler is presented for a reliable operation in the event of double, triple and tightly clustered roots.