6.28.13  Sturm sequences and number of sign changes of P on (a, b]: sturm sturmseq sturmab

Given a polynomial or rational expression P(x), the Sturm sequence is the sequence P₁(x),P₂(x), … given by the recurrence relation:

• P₁(x) is the opposite of the euclidean division remainder of P(x) by P′(x).
• P₂(x) is the opposite of the euclidean division remainder of P′(x) by P₁(x).
• …

If P(x) is a polynomial of degree n, then this sequence has at most n terms.

If P(x) is square-free, then Sturm’s Theorem gives a way to use the sequence to determine the number of zeros of P(x) on an interval.

The sturm command can find either the Sturm sequence (in which case it can also be called as sturmseq) or the number of zeros in an interval (in which case it can also be called as sturmab).

To find the Sturm sequence:

• sturm (or sturmseq) takes one mandatory argument and one optional argument:
  • P, a polynomial or rational expression.
  • Optionally, x, a variable name (by default x).
• sturm(P  ⟨ ,x⟩) (or sturmseq(P  ⟨,x⟩)) returns the list of the Sturm sequences and multiplicities of the square-free factors of P.

Examples.

• Input:
  sturm(2*x^3+2)
  or:
  sturm(2*y^3+2,y)
  Output:

  ⎡ ⎣

  2,

  ⎡ ⎣

  ⎡ ⎣

  1,0,0,1

  ⎤ ⎦

  ,

  ⎡ ⎣

  3,0,0

  ⎤ ⎦

  ,−9

  ⎤ ⎦

  ,1

  ⎤ ⎦

  The first term gives the content of the numerator (here 2), then the Sturm sequence (in list representation) [x³+1,3x²,−9].
  
• Input:
  sturm((2*x^3+2)/(3*x^2+2),x)
  or:
  sturmseq((2*x^3+2)/(3*x^2+2),x)
  Output:

  ⎡ ⎣

  2,

  ⎡ ⎣

  ⎡ ⎣

  1,0,0,1

  ⎤ ⎦

  ,

  ⎡ ⎣

  3,0,0

  ⎤ ⎦

  ,−9

  ⎤ ⎦

  ,1,

  ⎡ ⎣

  ⎡ ⎣

  3,0,2

  ⎤ ⎦

  ,

  ⎡ ⎣

  6,0

  ⎤ ⎦

  ,−72

  ⎤ ⎦

  ⎤ ⎦

  The first term gives the content of the numerator (here 2), then the Sturm sequence of the numerator ([[1,0,0,1],[3,0,0],-9]), then the content of the denominator (here 1) and the Sturm sequence of the denominator ([[3,0,2],[6,0],-72]). As expressions, [x³+1,3x², −9] is the Sturm sequence of the numerator and [3x²+2,6x,−72] is the Sturm sequence of the denominator.
• Input:
  sturm((x^3+1)^2,x)
  or:
  sturmseq((x^3+1)^2,x)
  Output:

  ⎡ ⎣

  1,1

  ⎤ ⎦

• Input:
  sturm(3*(3*x^3+1)/(2*x+2),x)
  Output:

  ⎡ ⎣

  3,

  ⎡ ⎣

  ⎡ ⎣

  3,0,0,1

  ⎤ ⎦

  ,

  ⎡ ⎣

  9,0,0

  ⎤ ⎦

  ,−81

  ⎤ ⎦

  ,2,

  ⎡ ⎣

  ⎡ ⎣

  1,1

  ⎤ ⎦

  ,1

  ⎤ ⎦

  ⎤ ⎦

  The first term gives the content of the numerator (here 3),
  the second term gives the Sturm sequence of the numerator (here 3x^3+1, 9x^2, -81),
  the third term gives the content of the denominator (here 2),
  the fourth term gives the Sturm sequence of the denominator (x+1,1).
• Input:
  sturm(2*x^3+2,x)
  or:
  sturmseq(2*x^3+2,x)
  Output:

  ⎡ ⎣

  2,

  ⎡ ⎣

  ⎡ ⎣

  1,0,0,1

  ⎤ ⎦

  ,

  ⎡ ⎣

  3,0,0

  ⎤ ⎦

  ,−9

  ⎤ ⎦

  ,1

  ⎤ ⎦

• Input:
  sturm((2*x^3+2)/(x+2),x)
  or:
  sturmseq((2*x^3+2)/(x+2),x)
  Output:

  ⎡ ⎣

  2,

  ⎡ ⎣

  ⎡ ⎣

  1,0,0,1

  ⎤ ⎦

  ,

  ⎡ ⎣

  3,0,0

  ⎤ ⎦

  ,−9

  ⎤ ⎦

  ,1,

  ⎡ ⎣

  ⎡ ⎣

  1,2

  ⎤ ⎦

  ,1

  ⎤ ⎦

  ⎤ ⎦

To compute the number of zeros in an interval:

• sturm (or sturmab) takes four arguments:
  • P, a polynomial expression.
  • x, a variable name.
  • a and b, two real or complex numbers.
• If a and b are reals, sturm(P,x,a,b) (or sturmab(P,x,a,b)) returns the number of sign changes of P on (a,b]; In other words, it returns the number of zeros in [a,b) of the polynomial P/G where G=gcd(P,P′).
• if a or b is complex, sturm(P,x,a,b) (or sturmab(P,x,a,b)) returns the number of complex roots of P in the rectangle having a and b as opposite vertices.

Examples.

• Input:
  sturm(x^2*(x^3+2),x,-2,0)
  or:
  sturmab(x^2*(x^3+2),x,-2,0)
  Output:

  1

• Input:
  sturm(x^2*(x^3+2),x,-2,0)
  or:
  sturmab(x^2*(x^3+2),x,-2,0)
  Output:

  1

• Input:
  sturm(x^3-1,x,-2-i,5+3i)
  or:
  sturmab(x^3-1,x,-2-i,5+3i)
  Output:

  3

• Input:
  sturm(x^3-1,x,-i,5+3i)
  Input:
  sturmab(x^3-1,x,-i,5+3i)
  Output:

  1

Warning!!!!
The polynomial is defined by its symbolic expression.
Input:

or:

Output: