Algoritmo di sturm
Buongiorno,
non riesco a capire come calcolare P2(x), cioè il terzo elemento della successione di sturm, inoltre non so quali valori scegliere (cioè quali intervalli) quando vado a calcolare il numero di variazioni.
Ad esempio per il polinomio $ x^3 - 2x^2 - 2x + 4 = 0 $
Grazie mille
non riesco a capire come calcolare P2(x), cioè il terzo elemento della successione di sturm, inoltre non so quali valori scegliere (cioè quali intervalli) quando vado a calcolare il numero di variazioni.
Ad esempio per il polinomio $ x^3 - 2x^2 - 2x + 4 = 0 $
Grazie mille
Risposte
Ciao armi96,
Bella domanda, breve ma intensa: la risposta non potrà essere altrettanto breve...
Il Teorema di Jacques Charles François Sturm (Ginevra, 29 settembre 1803 – Parigi, 15 dicembre 1855), collaboratore di Joseph Liouville (Teoria di Sturm-Liouville) permette di determinare il numero di zeri reali di un polinomio a coefficienti reali compresi fra due numeri dati. Dato un polinomio a coefficienti reali $P(x)$, la successione o sequenza di Sturm
$P(x), P'(x), P_1(x), P_2(x), P_3(x),..., P_k(x) $
si ottiene nel modo seguente.
i) si divide $P(x)$ per $P'(x)$, ottenendo come quoziente $Q_1(x)$ e come resto $R_1(x)$:
$P(x) = Q_1(x)P'(x) + R_1(x) $;
ii) si pone $P_1(x) := - R_1(x) $ e si divide per $P_1(x)$, ottenendo come quoziente $Q_2(x)$ e come resto $R_2(x)$:
$P'(x) = Q_2(x)P_1(x) + R_2(x) $;
iii) si pone $P_2(x) := - R_2(x) $ e si divide per $P_2(x)$, ottenendo come quoziente $Q_3(x)$ e come resto $R_3(x)$:
$P_1(x) = Q_3(x)P_2(x) + R_3(x) $;
... E così via, fino ad ottenere l'ultimo polinomio $P_k(x)$ non nullo. In generale, $P_j(x) = - R_j(x)$, $j = 1, 2,..., k$. Quindi per trovare i termini della successione di Sturm basta fare delle divisioni fra polinomi. Nel caso del tuo esempio, $P(x) = x^3 - 2x^2 - 2x + 4 \implies P'(x) = 3x^2 - 4x - 2 $ per cui si ha:
$ x^3 - 2x^2 - 2x + 4 = frac{1}{9}(3x -2) \cdot(3x^2 - 4x - 2) + frac{1}{9}(-20x + 32) $
$P_1(x) := - R_1(x) = frac{1}{9}(20x - 32)$
$ 3x^2 - 4x - 2 = (frac{27}{20}x +9/25)(frac{20}{9}x - 32/9) - 18/25 $
$P_2(x) := - R_2(x) = 18/25$
Per quanto concerne gli intervalli, ci sono diversi teoremi in proposito: non so quali hai fatto, per cui vado un po' a naso...
1) Stima grossolana:
sia $P(x) = x^n + a_{n - 1}x^{n - 1} + a_{n - 2}x^{n - 2} + ... + a_0$ un polinomio a coefficienti reali con $a_n = 1$ (non è una limitazione, l'equazione $a_n x^n + a_{n - 1}x^{n - 1} + a_{n - 2}x^{n - 2} + ... + a_0 = 0$ si può sempre dividere per $a_n$). Se $c$ è uno zero di $P(x)$, allora $-(M + 1) < c < (M + 1) $, ove $M := max{|a_{n - 1}|, |a_{n - 2}|,..., |a_0|}$;
2) Stima migliore, Teorema di Maclaurin:
$c < (M + 1) $, ma con $M := max{|a_j|, a_j < 0}$
Ad esempio, nel tuo caso $P(x) = x^3 - 2x^2 - 2x + 4$ con la stima grossolana l'intervallo è $[-5, 5]$, con la stima migliore data dal Teorema di Maclaurin una radice di $P(x)$ non supera $3$; inoltre poiché $P(-x) = -x^3 - 2x^2 + 2x + 4$, una radice di $P(-x)$ non può superare $3$, cioè le radici di $P(x)$ sono maggiori o uguali a $-3$, per cui ci si può limitare al più vantaggioso intervallo $[-3, 3]$ (infatti non è difficile trovare che le radici dell'equazione $P(x) = 0$ che hai proposto sono $x_1 = 2$, $x_2 = sqrt{2}$ e $x_3 = - sqrt{2}$).
3) Stima ancora migliore, Teorema di Laguerre:
sia $P(x) = x^n + a_{n - 1}x^{n - 1} + a_{n - 2}x^{n - 2} + ... + a_0$ un polinomio a coefficienti reali con $a_n = 1$ e sia $s > 0$; si divida $P(x)$ per $(x - s)$, ottenendo un quoziente $Q(x)$ ed un resto $R(x)$. Se tutti i coefficienti di $Q(x)$ e di $R(x)$ risultano non negativi, allora $s$ è una limitazione superiore per gli zeri di $P(x)$.
Qui però mi fermo perché la risposta sta diventando un po' troppo lunga...
Bella domanda, breve ma intensa: la risposta non potrà essere altrettanto breve...
Il Teorema di Jacques Charles François Sturm (Ginevra, 29 settembre 1803 – Parigi, 15 dicembre 1855), collaboratore di Joseph Liouville (Teoria di Sturm-Liouville) permette di determinare il numero di zeri reali di un polinomio a coefficienti reali compresi fra due numeri dati. Dato un polinomio a coefficienti reali $P(x)$, la successione o sequenza di Sturm
$P(x), P'(x), P_1(x), P_2(x), P_3(x),..., P_k(x) $
si ottiene nel modo seguente.
i) si divide $P(x)$ per $P'(x)$, ottenendo come quoziente $Q_1(x)$ e come resto $R_1(x)$:
$P(x) = Q_1(x)P'(x) + R_1(x) $;
ii) si pone $P_1(x) := - R_1(x) $ e si divide per $P_1(x)$, ottenendo come quoziente $Q_2(x)$ e come resto $R_2(x)$:
$P'(x) = Q_2(x)P_1(x) + R_2(x) $;
iii) si pone $P_2(x) := - R_2(x) $ e si divide per $P_2(x)$, ottenendo come quoziente $Q_3(x)$ e come resto $R_3(x)$:
$P_1(x) = Q_3(x)P_2(x) + R_3(x) $;
... E così via, fino ad ottenere l'ultimo polinomio $P_k(x)$ non nullo. In generale, $P_j(x) = - R_j(x)$, $j = 1, 2,..., k$. Quindi per trovare i termini della successione di Sturm basta fare delle divisioni fra polinomi. Nel caso del tuo esempio, $P(x) = x^3 - 2x^2 - 2x + 4 \implies P'(x) = 3x^2 - 4x - 2 $ per cui si ha:
$ x^3 - 2x^2 - 2x + 4 = frac{1}{9}(3x -2) \cdot(3x^2 - 4x - 2) + frac{1}{9}(-20x + 32) $
$P_1(x) := - R_1(x) = frac{1}{9}(20x - 32)$
$ 3x^2 - 4x - 2 = (frac{27}{20}x +9/25)(frac{20}{9}x - 32/9) - 18/25 $
$P_2(x) := - R_2(x) = 18/25$
Per quanto concerne gli intervalli, ci sono diversi teoremi in proposito: non so quali hai fatto, per cui vado un po' a naso...
1) Stima grossolana:
sia $P(x) = x^n + a_{n - 1}x^{n - 1} + a_{n - 2}x^{n - 2} + ... + a_0$ un polinomio a coefficienti reali con $a_n = 1$ (non è una limitazione, l'equazione $a_n x^n + a_{n - 1}x^{n - 1} + a_{n - 2}x^{n - 2} + ... + a_0 = 0$ si può sempre dividere per $a_n$). Se $c$ è uno zero di $P(x)$, allora $-(M + 1) < c < (M + 1) $, ove $M := max{|a_{n - 1}|, |a_{n - 2}|,..., |a_0|}$;
2) Stima migliore, Teorema di Maclaurin:
$c < (M + 1) $, ma con $M := max{|a_j|, a_j < 0}$
Ad esempio, nel tuo caso $P(x) = x^3 - 2x^2 - 2x + 4$ con la stima grossolana l'intervallo è $[-5, 5]$, con la stima migliore data dal Teorema di Maclaurin una radice di $P(x)$ non supera $3$; inoltre poiché $P(-x) = -x^3 - 2x^2 + 2x + 4$, una radice di $P(-x)$ non può superare $3$, cioè le radici di $P(x)$ sono maggiori o uguali a $-3$, per cui ci si può limitare al più vantaggioso intervallo $[-3, 3]$ (infatti non è difficile trovare che le radici dell'equazione $P(x) = 0$ che hai proposto sono $x_1 = 2$, $x_2 = sqrt{2}$ e $x_3 = - sqrt{2}$).
3) Stima ancora migliore, Teorema di Laguerre:
sia $P(x) = x^n + a_{n - 1}x^{n - 1} + a_{n - 2}x^{n - 2} + ... + a_0$ un polinomio a coefficienti reali con $a_n = 1$ e sia $s > 0$; si divida $P(x)$ per $(x - s)$, ottenendo un quoziente $Q(x)$ ed un resto $R(x)$. Se tutti i coefficienti di $Q(x)$ e di $R(x)$ risultano non negativi, allora $s$ è una limitazione superiore per gli zeri di $P(x)$.
Qui però mi fermo perché la risposta sta diventando un po' troppo lunga...
Grazie mille per la risposta, avevo capito sin da subito l'algoritmo, solo che il mio professore, nelle soluzioni, semplifica i resti, ad esempio per lui $ P1(x) = 5x-8 $, quindi pensavo di aver applicato male la formula.
Non ho fatto nessuno di quei teoremi, l'unico che ho fatto è il Teorema di Sturm che permette di determinare quante soluzioni ha il polinomio, ed è qui che ho un altro problema, non riesco a capire come trovare gli intervalli.
Non ho fatto nessuno di quei teoremi, l'unico che ho fatto è il Teorema di Sturm che permette di determinare quante soluzioni ha il polinomio, ed è qui che ho un altro problema, non riesco a capire come trovare gli intervalli.
"armi96":
Grazie mille per la risposta
Prego!
"armi96":
ed è qui che ho un altro problema, non riesco a capire come trovare gli intervalli.
Ho modificato la mia risposta in modo che ora dovresti essere in grado di determinare gli intervalli: se però ancora non ti è chiaro, fammi sapere che cerco di spiegarmi ancora meglio...
Lo scopo dell'esercizio è sapere quante radici ci sono in un intervallo, e per il teorema di sturm basta contare quante volte varia il segno, in pratica devo fare questa tabellina, ma non so che metodo adottare per trovare gli intervalli
Click sull'immagine per visualizzare l'originale
"armi96":
Lo scopo dell'esercizio è sapere quante radici ci sono in un intervallo, e per il teorema di sturm basta contare quante volte varia il segno
Fin qui siamo d'accordo, a parte il fatto che Sturm lo scriverei con la lettera iniziale maiuscola...
"armi96":
in pratica devo fare questa tabellina
... che però è sbagliata: la successione corretta è $-\infty$, $-2$, $0$, $1$, $2$.
$S(-\infty) = 3 = S(-2) \implies $ Nessuna soluzione nell'intervallo $(-\infty, - 2)$;
$S(-2) = 3$ e $S(0) = 2 \implies $ Una soluzione nell'intervallo $[- 2, 0]$ (vero: è $x_3 = -sqrt{2}$);
$S(0) = 2$ e $S(1) = 2 \implies $ Nessuna soluzione nell'intervallo $[0, 1]$;
$S(1) = 2$ e $S(2) = 0 \implies $ Due soluzioni nell'intervallo $[1, 2]$ (vero: sono $x_1 = 2$ e $x_2 = sqrt{2}$).
"armi96":
ma non so che metodo adottare per trovare gli intervalli
Te l'ho spiegato nel mio primo post in risposta al tuo, che ti invito a rileggere con maggiore attenzione: nel caso dell'esempio proposto bastava limitarsi all'intervallo $[-3, 3]$. Che cosa non ti è chiaro?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo