pub struct SturmChain<K> { /* private fields */ }
Expand description
calculate Sturm chain and find all real roots by Sturm method.
use find_real_roots_of_polynomial::SturmChain;
use polynomial_ring::{polynomial, Polynomial};
use num::{BigRational, BigInt};
let v = [-2, 0, 1].iter().map(|x| BigRational::from(BigInt::from(*x))).collect::<Vec<_>>();
let f = Polynomial::new(v); // f=x^2-2=(x-√2)(x+√2)
let limit = BigRational::new(BigInt::from(1), BigInt::from(16)); // 1/16
let sc = SturmChain::<BigRational>::new(f);
let roots = sc.find_all_real_roots(&limit);
assert_eq!(roots.len(), 2);
assert!(&roots[0].1 - &roots[0].0 < limit);
assert!(&roots[1].1 - &roots[1].0 < limit);
// -√2 ∈ [-93/64, -45/32] = [-1.453125, -1.40625]
// √2 ∈ [45/32, 93/64] = [1.40625, 1.453125]
assert_eq!(roots[0].0, BigRational::new(BigInt::from(-93), BigInt::from(64)));
assert_eq!(roots[0].1, BigRational::new(BigInt::from(-45), BigInt::from(32)));
assert_eq!(roots[1].0, BigRational::new(BigInt::from(45), BigInt::from(32)));
assert_eq!(roots[1].1, BigRational::new(BigInt::from(93), BigInt::from(64)));
Implementations§
source§impl<K: Sized> SturmChain<K>
impl<K: Sized> SturmChain<K>
sourcepub fn new(poly: Polynomial<K>) -> Self
pub fn new(poly: Polynomial<K>) -> Self
make Sturm chain
Input polynomial is converted to square-free polynomial. Then Sturm chain calcurated.
sourcepub fn strum_method(&self, left: &K, right: &K) -> Vec<(K, K)>
pub fn strum_method(&self, left: &K, right: &K) -> Vec<(K, K)>
This function returns half-open intervals. Each of them has exact one root.
Let polynomial has $n
$ real roots in (left, right]
. Let the roots be
$r_0, r_1, \dots, r_{n-1}
$. Where, $r_0 < r_1 < \dots < r_{n-1}
$. (Note. input
ploynomial was converted to square-free polynomial. So, all root are simple root.)
This function returns $n
$ half-open intervals. Let this intervals
$(l_0, u_0], (l_1, u_1], \dots, (l_{n-1}, u_{n-1}]
$. $\forall i, r_i \in (l_i, u_i]
$.
use find_real_roots_of_polynomial::SturmChain;
use polynomial_ring::{polynomial, Polynomial};
use num::{BigRational, BigInt, Zero, One};
let v = [0, -1, 0, 1].iter().map(|x| BigRational::from(BigInt::from(*x))).collect::<Vec<_>>();
let f = Polynomial::new(v); // f=x^3-1=(x-1)x(x+1)
let m_two = BigRational::from(BigInt::from(-2));
let p_two = BigRational::from(BigInt::from(2));
let sc = SturmChain::<BigRational>::new(f);
let intervals = sc.strum_method(&m_two, &p_two);
assert_eq!(intervals.len(), 3);
// -1 ∈ (-2, -1]
assert_eq!(intervals[0].0, m_two);
assert_eq!(intervals[0].1, -BigRational::one());
// 0 ∈ (-1, 0]
assert_eq!(intervals[1].0, -BigRational::one());
assert_eq!(intervals[1].1, BigRational::zero());
// 1 ∈ (0, 2]
assert_eq!(intervals[2].0, BigRational::zero());
assert_eq!(intervals[2].1, p_two);
sourcepub fn find_all_real_roots(&self, limit: &K) -> Vec<(K, K)>
pub fn find_all_real_roots(&self, limit: &K) -> Vec<(K, K)>
Find all real roots.
size of interval is less than limit
.
use find_real_roots_of_polynomial::SturmChain;
use polynomial_ring::{polynomial, Polynomial};
use num::{BigRational, BigInt};
let v = [-1, -1, 1].iter().map(|x| BigRational::from(BigInt::from(*x))).collect::<Vec<_>>();
let f = Polynomial::new(v); // f=x^2-x-1=(x-(1+√5)/2)(x-(1-√5)/2)
let limit = BigRational::new(BigInt::from(1), BigInt::from(8)); // 1/8
let sc = SturmChain::<BigRational>::new(f);
let roots = sc.find_all_real_roots(&limit);
assert_eq!(roots.len(), 2);
assert!(&roots[0].1 - &roots[0].0 < limit);
assert!(&roots[1].1 - &roots[1].0 < limit);
// (1-√5)/2(≒-0.61803) ∈ [-5/8, -9/16] = [-0.625, -0.5625]
// (1+√5)/2(≒ 1.61803) ∈ [45/32, 3/2] = [1.5625, 1.625]
assert_eq!(roots[0].0, BigRational::new(BigInt::from(-5), BigInt::from(8)));
assert_eq!(roots[0].1, BigRational::new(BigInt::from(-9), BigInt::from(16)));
assert_eq!(roots[1].0, BigRational::new(BigInt::from(25), BigInt::from(16)));
assert_eq!(roots[1].1, BigRational::new(BigInt::from(13), BigInt::from(8)));
sourcepub fn has_imaginary_root(&self) -> bool
pub fn has_imaginary_root(&self) -> bool
Determine if input polynomial has an imaginary root.
use find_real_roots_of_polynomial::SturmChain;
use polynomial_ring::{polynomial, Polynomial};
use num::{BigRational, BigInt};
let v0 = [-1, 0, 1].iter().map(|x| BigRational::from(BigInt::from(*x))).collect::<Vec<_>>();
let v1 = [1, 0, 1].iter().map(|x| BigRational::from(BigInt::from(*x))).collect::<Vec<_>>();
let f = Polynomial::new(v0); // f=x^2-1=(x+1)(x-1)
let g = Polynomial::new(v1); // g=x^2+1=(x+i)(x-i)
let f_sc = SturmChain::<BigRational>::new(f);
let g_sc = SturmChain::<BigRational>::new(g);
assert_eq!(f_sc.has_imaginary_root(), false);
assert_eq!(g_sc.has_imaginary_root(), true);
Auto Trait Implementations§
impl<K> Freeze for SturmChain<K>
impl<K> RefUnwindSafe for SturmChain<K>where
K: RefUnwindSafe,
impl<K> Send for SturmChain<K>where
K: Send,
impl<K> Sync for SturmChain<K>where
K: Sync,
impl<K> Unpin for SturmChain<K>where
K: Unpin,
impl<K> UnwindSafe for SturmChain<K>where
K: UnwindSafe,
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more