11.2.12 Sturm sequences and number of sign changes of P on (a,b]
Given a polynomial or rational expression P(x), the Sturm sequence is
the sequence P1(x),P2(x), … given by the recurrence
relation:
-
P1(x) is the opposite of the euclidean division remainder of P(x) by
P′(x).
- P2(x) is the opposite of the euclidean division remainder of P′(x) by
P1(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 finds 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.
- 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
or:
|
| ⎡
⎣ | 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) is [x3+1,3x2,−9].
sturm((2*x^3+2)/(3*x^2+2),x) |
or:
sturmseq((2*x^3+2)/(3*x^2+2),x) |
|
| ⎡
⎣ | 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,
[x3+1,3x2, −9] is the Sturm sequence of the numerator and
[3x2+2,6x,−72] is the Sturm sequence of the denominator.
or:
sturm(3*(3*x^3+1)/(2*x+2),x) |
|
| ⎡
⎣ | 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 3x3+1,9x2,−81),
the third term gives the content of the denominator (here
2),
and the fourth term gives the Sturm sequence of the denominator
(here x+1,1).
or:
|
| ⎡
⎣ | 2, | ⎡
⎣ | ⎡
⎣ | 1,0,0,1 | ⎤
⎦ | , | ⎡
⎣ | 3,0,0 | ⎤
⎦ | ,−9 | ⎤
⎦ | ,1 | ⎤
⎦ |
| | | | | | | | | | |
|
or:
sturmseq((2*x^3+2)/(x+2),x) |
|
| ⎡
⎣ | 2, | ⎡
⎣ | ⎡
⎣ | 1,0,0,1 | ⎤
⎦ | , | ⎡
⎣ | 3,0,0 | ⎤
⎦ | ,−9 | ⎤
⎦ | ,1, | ⎡
⎣ | ⎡
⎣ | 1,2 | ⎤
⎦ | ,1 | ⎤
⎦ | ⎤
⎦ |
| | | | | | | | | | |
|
Examples of computing the number of zeros in an interval:
sturm(x^2*(x^3+2),x,-2,0) |
or:
sturmab(x^2*(x^3+2),x,-2,0) |
sturm(x^2*(x^3+2),x,-2,0) |
or:
sturmab(x^2*(x^3+2),x,-2,0) |
or:
sturmab(x^3-1,x,-2-i,5+3i) |
or:
Note that the polynomial must defined by its symbolic expression.
For example, these commands produce an error:
or:
sturm([1,0,0,2,0,0],x,-2,0) |