De la Wikipedia, enciclopedia liberă.
Algoritmul lui Sturm este un algoritm folosit pentru a calcula numărul rădăcinilor reale ale unui polinom cu coeficienți reali care se încadrează într-un interval dat {\ displaystyle (a, b)} .
Algoritm
Este {\ displaystyle f (x)} un polinom de grad {\ displaystyle n} , definim secvența polinoamelor
- {\ 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}} \ dreapta.}
unde cu{\ displaystyle A (x) \ mod B (x)} restul polinomului este indicat în diviziunea polinomului {\ displaystyle A (x)} pentru polinom {\ displaystyle B (x)} .
Numărul de zerouri reale distincte ale {\ displaystyle f (x)} în interval {\ displaystyle [a, b]} , cu {\ displaystyle f (a) \ neq 0} Și {\ displaystyle f (b) \ neq 0} , Este egal cu {\ displaystyle V (a) -V (b)} , unde este {\ displaystyle V (x)} indică de câte ori elementele succesiunii {\ displaystyle f_ {1} (x), f_ {2} (x) ... f_ {m} (x)} își schimbă semnul, ignorând zerourile.
Demonstrație
Succesiunea {\ displaystyle \ left \ {f_ {i} (x) \ right \} _ {i = 1,2, ..., m}} este o secvență Sturm , o avem
{\ displaystyle f (x) = (x-z_ {1}) ^ {\ mu _ {1}} (x-z_ {2}) ^ {\ mu _ {2}} ... (x-z_ { r}) ^ {\ mu _ {r}} g (x)}
unde este {\ displaystyle z_ {i}} este un zero real al {\ displaystyle f (x)} cu multiplicitate {\ displaystyle \ mu _ {i}} in timp ce {\ displaystyle g (x)} este un polinom fără rădăcini reale. Pentru care
{\ 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)}
având în vedere că multiplicitățile sunt toate pozitive, obținem
{\ displaystyle I_ {a} ^ {b} {\ frac {f_ {2} (x)} {f_ {1} (x)}} = r}
unde s-a folosit indicele Cauchy , afirmă teorema secvenței lui Sturm
{\ displaystyle I_ {a} ^ {b} {\ frac {f_ {2} (x)} {f_ {1} (x)}} = V (a) -V (b)}
de aici teza.
linkuri externe