An implementation of the Aberth-Ehrlich method for finding the zeros of a polynomial.
Aberth's method uses an electrostatics analogy to model the approximations as negative charges and the true zeros as positive charges. This enables finding all complex roots simultaneously, converging cubically (worst-case it converges linearly for zeros of multiplicity).
This crate is #![no_std] and tries to have minimal dependencies:
- num-complex for Complex number types
- arrayvec to avoid allocations
- num-traits to be generic over floating
point types.
Add it to your project:
sh
cargo add aberth
Specify the coefficients of your polynomial in an array in ascending order
and then call the aberth method on your polynomial.
```rust
use aberth::aberth;
const EPSILON: f32 = 0.001;
// 0 = -1 + 2x + 4x^4 + 11x^9 let polynomial = [-1., 2., 0., 0., 4., 0., 0., 0., 0., 11.];
let roots = aberth(&polynomial, EPSILON).unwrap(); // [ // Complex { re: 0.4293261, im: 1.084202e-19 }, // Complex { re: 0.7263235, im: 0.4555030 }, // Complex { re: 0.2067199, im: 0.6750696 }, // Complex { re: -0.3448952, im: 0.8425941 }, // Complex { re: -0.8028113, im: 0.2296336 }, // Complex { re: -0.8028113, im: -0.2296334 }, // Complex { re: -0.3448952, im: -0.8425941 }, // Complex { re: 0.2067200, im: -0.6750695 }, // Complex { re: 0.7263235, im: -0.4555030 }, // ] ```
Note that the returned values are not sorted in any particular order.
The function returns an Err if it fails to converge after 100 cycles. This
is excessive. Even polynomials of degree 20 will converge after <20 iterations.
Using a larger epsilon can usually avoid these errors.
The coefficient of the highest degree term should not be zero or you will get nonsense extra roots (probably at 0 + 0j).
This crate is dual-licensed under either of Apache license, Version 2.0 or the MIT license at your option.