aberth 0.0.1

Aberth's method for finding the zeros of a polynomial
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

aberth
======

An implementation of the
[Aberth-Ehrlich method](https://en.wikipedia.org/wiki/Aberth_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]` & tries to have minimal dependencies. It uses
[arrayvec](https://crates.io/crates/arrayvec) to avoid allocations and
[num-traits](https://crates.io/crates/num-traits) to be generic over floating
point types.


Usage
-----

Add it to your project:
```sh
cargo add aberth
```

Specify the coefficients of your polynomial in an array
```rust
// 0 = -1 + 2x + 4x^4 + 11x^9
let polynomial = [-1.0, 2.0, 0.0, 0.0, 4.0, 0.0, 0.0, 0.0, 0.0, 11.0];
```

Call the `aberth` method on your polynomial & provide an epsilon value.
```rust
use aberth::aberth;

let roots = aberth(&polynomial, EPSILON).unwrap();
// [
//   Complex { real:  0.4293261, imaginary:  1.084202e-19 },
//   Complex { real:  0.7263235, imaginary:  0.4555030 },
//   Complex { real:  0.2067199, imaginary:  0.6750696 },
//   Complex { real: -0.3448952, imaginary:  0.8425941 },
//   Complex { real: -0.8028113, imaginary:  0.2296336 },
//   Complex { real: -0.8028113, imaginary: -0.2296334 },
//   Complex { real: -0.3448952, imaginary: -0.8425941 },
//   Complex { real:  0.2067200, imaginary: -0.6750695 },
//   Complex { real:  0.7263235, imaginary: -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).


License
-------

This crate is dual-licensed under either of
[Apache license, Version 2.0](http://www.apache.org/licenses/LICENSE-2.0)
or the
[MIT license](http://opensource.org/licenses/MIT)
at your option.