L'algoritmo di Sturm è un algoritmo usato per calcolare il numero di radici reali di un polinomio a coefficienti reali che cadono in un determinato intervallo
(
a
,
b
)
{\displaystyle (a,b)}
Sia
f
(
x
)
{\displaystyle f(x)}
n
{\displaystyle n}
{
f
1
(
x
)
=
f
(
x
)
f
2
(
x
)
=
f
′
(
x
)
f
i
(
x
)
=
−
{
f
i
−
2
(
x
)
mod
f
i
−
1
(
x
)
}
∀
i
=
3
,
2
,
.
.
.
,
m
{\displaystyle \left\{{\begin{matrix}f_{1}(x)=f(x)\\f_{2}(x)=f'(x)\\f_{i}(x)=-\left\{f_{i-2}(x)\mod f_{i-1}(x)\right\}&\forall i=3,2,...,m\end{matrix}}\right.}
dove con
A
(
x
)
mod
B
(
x
)
{\displaystyle A(x)\mod B(x)}
A
(
x
)
{\displaystyle A(x)}
B
(
x
)
{\displaystyle B(x)}
Il numero di distinti zeri reali di
f
(
x
)
{\displaystyle f(x)}
[
a
,
b
]
{\displaystyle [a,b]}
f
(
a
)
≠
0
{\displaystyle f(a)\neq 0}
f
(
b
)
≠
0
{\displaystyle f(b)\neq 0}
V
(
a
)
−
V
(
b
)
{\displaystyle V(a)-V(b)}
V
(
x
)
{\displaystyle V(x)}
f
1
(
x
)
,
f
2
(
x
)
.
.
.
f
m
(
x
)
{\displaystyle f_{1}(x),f_{2}(x)...f_{m}(x)}
La successione
{
f
i
(
x
)
}
i
=
1
,
2
,
.
.
.
,
m
{\displaystyle \left\{f_{i}(x)\right\}_{i=1,2,...,m}}
sequenza di Sturm , abbiamo che
f
(
x
)
=
(
x
−
z
1
)
μ
1
(
x
−
z
2
)
μ
2
.
.
.
(
x
−
z
r
)
μ
r
g
(
x
)
{\displaystyle f(x)=(x-z_{1})^{\mu _{1}}(x-z_{2})^{\mu _{2}}...(x-z_{r})^{\mu _{r}}g(x)}
dove
z
i
{\displaystyle z_{i}}
f
(
x
)
{\displaystyle f(x)}
μ
i
{\displaystyle \mu _{i}}
g
(
x
)
{\displaystyle g(x)}
f
′
(
x
)
f
(
x
)
=
f
2
(
x
)
f
1
(
x
)
=
∑
k
=
1
r
μ
k
x
−
z
k
+
g
(
x
)
{\displaystyle {\frac {f'(x)}{f(x)}}={\frac {f_{2}(x)}{f_{1}(x)}}=\sum _{k=1}^{r}{\frac {\mu _{k}}{x-z_{k}}}+g(x)}
considerando che le molteplicità sono tutte positive si ottiene
I
a
b
f
2
(
x
)
f
1
(
x
)
=
r
{\displaystyle I_{a}^{b}{\frac {f_{2}(x)}{f_{1}(x)}}=r}
dove si è usato l'indice di Cauchy , il teorema sulle sequenze di Sturm afferma
I
a
b
f
2
(
x
)
f
1
(
x
)
=
V
(
a
)
−
V
(
b
)
{\displaystyle I_{a}^{b}{\frac {f_{2}(x)}{f_{1}(x)}}=V(a)-V(b)}
da cui la tesi.
![{\displaystyle [a,b]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c4b788fc5c637e26ee98b45f89a5c08c85f7935)
