SYNAPS (SYmbolic Numeric ApplicationS) » Univariate Solvers

Sturm Subdivision Solver

Another criterion to detect the number of roots in an interval, can be used. It is based on Sturm's theorem. Here is the simplifed version, that we exploit:

Theorem: Let $f \in \mathbbm{R}[x]$ and $S (x) = [f (x), f' (x), S_2 (x), \ldots, S_N (x)]$ be the Sturm sequence of $f$ and $f'$ (x). Let $V (a)$ be the number of sign variation of $S (a)$ for $a \in \mathbbm{R}$ . Then, for any $a, b \in \mathbbm{R}$ , $V (a) - V (b)$ is the number of roots in ]a,b[.

This leads to the following schema of algorithms, (which applies event to polynomials with multiple roots):

Algorithm: Isolation of the roots of on the interval .
INPUT: A polynomial $f \in \mathbbm{R}[x]$ .

Compute the Sturm sequence $S (x)$ of $f$ and $f'$ .

Compute the number of sign changes $r = V (a) - V (b)$ .

If $r = 0$ remove the interval.

If $r > 1$ and compute $V ( \frac{a + b}{2})$ and apply recursively the algorithm to the two halves of the input interval.

OUTPUT: a list of subintervals of $[a, b]$ containing exactly one real root of $f$ .

Sturm Approximation Solver

Seq<O> solve(const UPOL& p, SlvSturm<O,C> mth);

This solver computes an approximation of the roots, within the precision $\varepsilon$ specified by the solver SlvSturm. The default value is $\varepsilon = 10^{- 3}$ . If we want a specific precision $\varepsilon =$ eps, we can use the following construction: solve(p, SlvSturm<O,C>(eps)).

The solver outputs a sequence of numbers of type O, corresponding to the first parameter O of this class.

The second parameter C is the type of coefficients used during the computation. The default type is the type QQ of rational numbers. \

The univariate polynomial p of type UPOL, is supposed to be given with exact coefficients. It is converted to a polynomial of type UPolDse<C>, if needed.

See synaps/usolve/sturm/SlvSturm.h.

Sturm Isolation Solver

Seq< Interval<O> > solve(const UPOL& p, IslSturm<O,C> mth);

This solver computes an isolation interval of the roots. It outputs a sequence of intervals of numbers of type O, containing one and only one root of p.

The second parameter C is the type of coefficients used during the computation. The default type is the type QQ of rational numbers. \

The univariate polynomial p of type UPOL, is supposed to be given with exact coefficients. It is converted to a polynomial of type UPolDse<C>, if needed.

See synaps/usolve/sturm/IslSturm.h.

Example

#include <synaps/upol.h>
#include <synaps/arithm/QQ.h>
#include <synaps/usolve/sturm/IslSturm.h>
int main()
{
  using std::cout;  using std::endl;

  UPolDse<QQ> P("2*x^7+3*x^6+2*x^5+x^4-x^3-2*x^2-3*x+1");
  cout <<"Testing: "<<P<<endl;
  //| Testing: 2*x^7+3*x^6+2*x^5+1*x^4-1*x^3-2*x^2-3*x+1

  cout <<solve(P,IslSturm<QQ>())<<endl;
  //| [ -5/2,0 ], [ 0,5/8 ], [ 5/8,5/4 ]

  cout <<solve(P,IslSturm<QQ>(),0,1)<<endl;
  //| [ 0,1/2 ], [ 1/2,1 ]

}

SYNAPS DOCUMENTATION