Teorema di Sturm

In matematica , e più precisamente in analisi , il teorema di Sturm , stabilito nel 1829 da Charles Sturm , permette di calcolare il numero di radici reali distinte di una funzione polinomiale compresa in un dato intervallo. Il corrispondente metodo di calcolo efficace è chiamato algoritmo di Sturm .

Suite Sturm

Diamo a noi stessi un polinomio $P = x n + a n - 1 x n - 1 + ... + a 1 x + a 0$ . La sequenza di Sturm o catena di Sturm dal polinomio $P$ è una sequenza finita di polinomi $P 0 , P 1 , ..., P m$ . È costruito per induzione:

$P 0 = P$ ;
$P 1 = P '$ , dove $P'$ è la derivata di $P$ , cioè il polinomio $P '= nx n - 1 + ... + a 1$ ;
Per $i \geq 2$ , $P i$ è l'opposto del resto della divisione di $P i - 2$ per $P i - 1$ .
La costruzione si ferma all'ultimo polinomio diverso da zero.

Per ottenere questa sequenza, calcoliamo i resti intermedi che otteniamo applicando l'algoritmo di Euclide a $P 0$ e alla sua derivata $P 1$ :

{\ displaystyle {\ begin {matrix} P_ {0} & = & P_ {1} Q_ {1} & - & P_ {2} \\ P_ {1} & = & P_ {2} Q_ {2} & - & P_ {3} \\\ vdots & \ vdots & \ vdots & \ vdots & \ vdots \\ P_ {m-2} & = & P_ {m-1} Q_ {m-1} & - & P_ {m } \\ P_ {m -1} & = & P_ {m} Q_ {m} & - & 0 \\\ end {matrix}}}

Se $P$ ha solo radici distinte, l'ultimo termine è una costante diversa da zero. Se questo termine è zero, $P$ ammette più radici, e in questo caso possiamo applicare il teorema di Sturm usando la sequenza $T 0 , T 1 , ..., T m - 1 , 1$ che otteniamo dividendo $P 1 , P 2 , ..., P m - 1$ di $P m$ .

Enunciato del teorema

Il numero di distinte radici reali in un intervallo $[ a , b ]$ di un polinomio con reali coefficienti , dei quali $un$ e $b$ non sono radici, è uguale al numero di cambi di segno della sequenza Sturm ai limiti di questo intervallo.

Più formalmente includi $σ ( ξ )$ il numero di cambi di segno (zero non viene conteggiato come segno di cambiamento) nel seguente

{\ displaystyle P (\ xi), P_ {1} (\ xi), P_ {2} (\ xi), \ ldots, P_ {m} (\ xi)}

Il teorema di Sturm dice che per due numeri reali $a$ , $b$ , $un < b$ , dove $un$ e $b$ non sono radici di $P$ , il numero di radici nell'intervallo $[ a , b ]$ è:

{\ displaystyle \ sigma (a) - \ sigma (b) ~}

. Dimostrazione

Viene fornita una dimostrazione come riferimento.

Esempio

Supponiamo di voler conoscere il numero di radici in un certo intervallo del polinomio $p ( x ) = x 4 + x 3 - x -1$ . Iniziamo calcolando i primi due termini.

{\ displaystyle {\ begin {align} p_ {0} (x) & = p (x) = x ^ {4} + x ^ {3} -x-1 \\ p_ {1} (x) & = p '(x) = 4x ^ {3} + 3x ^ {2} -1 \ end {allineato}}}

Dividendo $p 0$ per $p 1$ otteniamo il resto $- 3 / 16 x 2 - 3 / 4 x - 15 / 16$ e moltiplicandolo per $-1$ otteniamo $p 2 ( x ) = 3 / 16 x 2 + 3 / 4 x + 15 / 16$ . Successivamente, dividiamo $p 1$ per $p 2$ e moltiplichiamo il resto per $-1$ , otteniamo $p 3 ( x ) = -32 x -64$ . Quindi dividiamo $p 2$ per $p 3$ e moltiplicando il resto per $-1$ , otteniamo $p 4 ( x ) = - 3 / 16$ .

Infine, la sequenza di Sturm del polinomio $P$ è quindi:

{\ displaystyle p_ {0} (x) = x ^ {4} + x ^ {3} -x-1}

{\ displaystyle p_ {1} (x) = 4x ^ {3} + 3x ^ {2} -1}

{\ displaystyle p_ {2} (x) = {\ tfrac {3} {16}} x ^ {2} + {\ tfrac {3} {4}} x + {\ tfrac {15} {16}}}

{\ displaystyle p_ {3} (x) = - 32x-64}

{\ displaystyle p_ {4} (x) = - {\ tfrac {3} {16}}}

Per trovare il numero di radici totali, ad es. tra $-\infty$ e + $\infty$ , valutiamo $p 0 , p 1 , p 2 , p 3 ,$ e $p 4$ in $-\infty$ e indichiamo la sequenza corrispondente di segni: $+ - + + -$ . Contiene tre cambi di segno (da $+$ a $-$ , quindi da $-$ a $+$ , quindi da $+$ a $-$ ). Facciamo lo stesso in + $\infty$ e otteniamo la sequenza di segni $+ + + - -$ , che contiene solo un cambio di segno. Secondo il teorema di Sturm, il numero totale di radici del polinomio $P$ è $3 - 1 = 2.$ Possiamo verificare notando che $p ( x ) = x 4 + x 3 - x - 1$ è scomposto in $( x 2 - 1) ( x 2 + x + 1)$ , dove vediamo che $x 2 - 1$ ha due radici ( $-1$ e $1$ ) mentre $x 2 + x + 1$ non ha radici reali.

Applicazioni

Possiamo usare questo teorema per calcolare il totale numero di radici reali distinti, scegliendo i limiti $un$ e $b$ in modo che tutte le vere radici sono nell'intervallo $[ a , b ]$ : per esempio $[ a , b ] = [- M , M ] è$ adatto, con, come desiderato:

{\ displaystyle M = 1 + {\ max} _ {i = 0} ^ {n-1} | a_ {i} |}

o .

{\ displaystyle M = \ max \ left (1, \ sum _ {i = 0} ^ {n-1} | a_ {i} | \ right)}

Possiamo anche usare questo teorema per trovare le radici di qualsiasi polinomio per dicotomia, e quindi ottimizzare qualsiasi criterio polinomiale (trovando le radici della sua derivata).

Note e riferimenti

(fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato " Teorema di Sturm " ( vedi l'elenco degli autori ) .

C. Sturm, " Sulla risoluzione delle equazioni numeriche ", in Scienze matematiche e fisiche , volume VI, Parigi, 1835, p. 271-318
Edouard Callandreau, " Famosi problemi matematici ", Edizioni Albin Michel , Parigi, 1949, 1 volume, 478p

(a) Peter Bürgisser Michael Clausen e Amin Shokrollahi , Algebraic Complexity Theory , Springer Science & Business Media,14 marzo 2013, 618 p. ( ISBN 978-3-662-03338-8 , leggi online ) (Esercizio 3.10, p. 93).
[PDF] Sandrine Caruso, “Suite de Sturm. " .
Per altri esempi, vedere l'articolo Teoria delle equazioni (matematica) .
Vedi il teorema di Lagrange sui polinomi .
(in) Holly P. Hirst e Wade T. Macey , " Bounding the Roots of Polynomials " , The College Mathematics Journal , MAA , vol. 28, n o 4,Settembre 1997, p. 292-295 ( DOI 10.2307 / 2687152 ).