Twierdzenie Sturma

W matematyce sekwencja Sturma jednowymiarowego wielomianu p $jest$ sekwencją wielomianów powiązanych z $p$ i jego pochodną przez wariant algorytmu Euklidesa dla wielomianów . Twierdzenie Sturma wyraża liczbę różnych pierwiastków rzeczywistych p znajdujących $się$ w przedziale pod względem liczby zmian znaków wartości ciągu Sturma na granicach przedziału. Zastosowany do przedziału wszystkich liczb rzeczywistych daje całkowitą liczbę pierwiastków rzeczywistych $p$ .

Podczas gdy fundamentalne twierdzenie algebry z łatwością daje całkowitą liczbę pierwiastków zespolonych liczonych z krotnością , nie zapewnia procedury ich obliczania. Twierdzenie Sturma zlicza liczbę różnych pierwiastków rzeczywistych i umieszcza je w przedziałach. Dzieląc przedziały zawierające pewne pierwiastki, może izolować pierwiastki na dowolnie małe przedziały, z których każdy zawiera dokładnie jeden pierwiastek. Daje to najstarszy izolacji pierwiastków rzeczywistych i algorytm znajdowania pierwiastków o dowolnej precyzji dla wielomianów jednowymiarowych.

W przypadku obliczeń na liczbach rzeczywistych twierdzenie Sturma jest mniej wydajne niż inne metody oparte na zasadzie znaków Kartezjusza . Działa jednak na każdym rzeczywistym ciele zamkniętym i dlatego pozostaje fundamentalny dla teoretycznego badania złożoności obliczeniowej rozstrzygalności i eliminacji kwantyfikatorów w teorii liczb rzeczywistych pierwszego rzędu .

Sekwencja Sturma i twierdzenie Sturma zostały nazwane na cześć Jacquesa Charlesa François Sturma , który odkrył to twierdzenie w 1829 roku.

Twierdzenie

Łańcuch Sturma lub sekwencja Sturma jednowymiarowego wielomianu $P (x)$ z rzeczywistymi współczynnikami to sekwencja wielomianów taka, że P $\ Displaystyle P_ {0}, P_ {1}, \ ldots}$

{\ Displaystyle {\ rozpocząć {wyrównane} P_ {0} i = P, \\ P_ {1 }&=P',\\P_{i+1}&=-\nazwa_operatora {rem} (P_{i-1},P_{i}),\end{wyrównane}}}

dla $ja \geq 1$ , gdzie $P '$ jest pochodną P. i ${\ Displaystyle \ operatorname {rem} (P_ {i-1}, P_ {i})$ $}$ to reszta z podziału euklidesowego przez ${\ Displaystyle P_ {i-$ ${\ displaystyle P_ {i}.}$ Długość sekwencji Sturma jest co najwyżej stopniem $P$ .

Liczba zmian znaku w $ξ$ sekwencji Sturma $P$ to liczba zmian znaku - pomijając zera - w sekwencji liczb rzeczywistych

{\ Displaystyle P_ {0} (\ xi), P_ {1} (\ xi), P_ {2} (\ xi), \ ldots.}

Ta liczba odmian znaku jest tutaj oznaczona jako $V (ξ)$ .

Twierdzenie Sturma stwierdza, że jeśli $P$ jest wielomianem bez kwadratów , liczba różnych pierwiastków rzeczywistych $P$ w przedziale półotwartym $(a, b]$ wynosi $V (a) - V (b)$ (tutaj $a$ i $b$ to liczby rzeczywiste takie, że $a < b$ ).

Twierdzenie rozciąga się na nieograniczone przedziały, definiując znak w $+ \infty$ wielomianu jako znak jego wiodącego współczynnika (to znaczy współczynnika wyrazu najwyższego stopnia). W $-\infty$ znak wielomianu jest znakiem jego wiodącego współczynnika dla wielomianu parzystego stopnia, a przeciwieństwem wielomianu stopnia nieparzystego.

W przypadku wielomianu bez kwadratów, jeśli ani $a$ , ani $b nie$ jest pierwiastkiem wielokrotnym $p$ , to $V (a) - V (b)$ jest liczbą różnych pierwiastków rzeczywistych $P$ .

Dowód twierdzenia jest następujący: gdy wartość $a$ $od$ do $b$ , $może$ przechodzić przez zero jakiegoś ( $ja > 0$ ); $_$ liczba _ zmiana. Kiedy $x$ przechodzi przez pierwiastek z ${\ Displaystyle P_ {0} = P,}$ liczba odmian znaku ${\ Displaystyle (P_ {0}, P_ {1})}$ zmniejsza się od 1 do 0. Są to jedyne wartości $x$ , przy których może się zmienić jakiś znak.

Przykład

Załóżmy, że chcemy znaleźć liczbę pierwiastków w pewnym zakresie dla wielomianu ${\ Displaystyle p (x) = x ^ {4} + x ^ {3} -x -1}$ . Więc

{\ Displaystyle {\ rozpocząć {wyrównane} p_ {0}(x)&=p(x)=x^{4}+x^{3}-x-1\\p_{1}(x)&=p'(x)=4x^{3} +3x^{2}-1\end{wyrównane}}}

Reszta z ${\ Displaystyle - {\ tfrac {3}{16}} x ^ {2} - {\ tfrac {3} {4}} x - {\ tfrac {15} {16}};}$ euklidesowego p przez $p 1$ to $40$ mnożąc to przez $-1$ my uzyskać

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

.

Następnie dzieląc $p 1$ przez $p 2$ i mnożąc resztę przez $-1$ , otrzymujemy

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

.

Teraz dzieląc $p 2$ przez $p 3$ i mnożąc resztę przez $-1$ , otrzymujemy

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

.

Ponieważ jest to stała, kończy to obliczanie sekwencji Sturma.

Aby znaleźć liczbę pierwiastków rzeczywistych, $ocenić$ sekwencje znaków tych wielomianów w $-\infty$ i $\infty$ , którymi są odpowiednio $(+, -, +, +, -)$ i p {\ displaystyle p_ {0}} $(+, +, +, -, -)$ . Zatem

{\ Displaystyle V (- \ infty) -V (+ \ infty) = 3-1 = 2,}

gdzie $V$ oznacza liczbę zmian znaku w sekwencji, co pokazuje, że $p$ ma dwa pierwiastki rzeczywiste.

Można to zweryfikować, zauważając, że $p (x)$ można rozłożyć na czynniki jako $(x 2 - 1) (x 2 + x + 1)$ , gdzie pierwszy czynnik ma pierwiastki $-1$ i $1$ , a drugi czynnik nie ma pierwiastków rzeczywistych. To ostatnie twierdzenie wynika ze wzoru kwadratowego , a także z twierdzenia Sturma, które daje ciągi znaków $(+, -, -)$ przy $-\infty$ i $(+, +, -)$ przy $+\infty$ .

Uogólnienie

Sekwencje Sturma zostały uogólnione w dwóch kierunkach. Aby zdefiniować każdy wielomian w sekwencji, Sturm użył ujemnej reszty z podziału euklidesowego dwóch poprzednich. Twierdzenie pozostaje prawdziwe, jeśli ujemną część reszty zastąpi się jej iloczynem lub ilorazem przez stałą dodatnią lub kwadrat wielomianu. Przydatne jest również (patrz poniżej) rozważenie ciągów, w których drugi wielomian nie jest pochodną pierwszego.

Uogólniony ciąg Sturma to skończony ciąg wielomianów o rzeczywistych współczynnikach

{\ Displaystyle P_ {0}, P_ {1}, \ kropki, P_ {m}}

takie że

$_$ pierwszym dla $2__$ _
${\ displaystyle P_ {m}}$ nie ma żadnego rzeczywistego korzenia ani nie ma zmian znaku w pobliżu swoich rzeczywistych korzeni.
jeśli $P ja (ξ) = 0$ dla $0 < ja < m$ i $ξ$ liczba rzeczywista, to $P ja -1 (ξ) P ja + 1 (ξ) < 0$ .

Z ostatniego warunku wynika, że dwa kolejne wielomiany nie mają wspólnego pierwiastka rzeczywistego. W szczególności oryginalny ciąg Sturma jest uogólnionym ciągiem Sturma, wtedy (i tylko wtedy, gdy) wielomian nie ma wielu rzeczywistych pierwiastków (w przeciwnym razie pierwsze dwa wielomiany jego ciągu Sturma mają wspólny pierwiastek).

Podczas obliczania oryginalnej sekwencji Sturma przez dzielenie euklidesowe może się zdarzyć, że napotkamy wielomian, którego czynnik nigdy nie jest ujemny, taki jak ${\ displaystyle x ^ {2}}$ lub ${\ displaystyle x ^ {2}+1}$ . W takim przypadku, jeśli kontynuujemy obliczenia z wielomianem zastąpionym jego ilorazem przez czynnik nieujemny, otrzymujemy uogólniony ciąg Sturma, którego można również użyć do obliczenia liczby pierwiastków rzeczywistych, ponieważ dowód twierdzenia Sturma nadal obowiązuje ( ze względu na trzeci warunek). Może to czasami uprościć obliczenia, chociaż ogólnie trudno jest znaleźć takie nieujemne czynniki, z wyjątkiem parzystych potęg $x$ .

Wykorzystanie sekwencji pseudoreszt

W algebrze komputerowej rozważane wielomiany mają współczynniki całkowite lub można je przekształcić tak, aby miały współczynniki całkowite. Sekwencja Sturma wielomianu ze współczynnikami całkowitymi na ogół zawiera wielomiany, których współczynniki nie są liczbami całkowitymi (patrz powyższy przykład).

Aby uniknąć obliczeń z liczbami wymiernymi , powszechną metodą jest zastąpienie dzielenia euklidesowego pseudopodziałem przy obliczaniu największych wspólnych dzielników wielomianu . Sprowadza się to do zastąpienia sekwencji reszt algorytmu euklidesowego przez sekwencję pseudoreszt , przy czym sekwencja pseudoreszt jest sekwencją wielomianów takich jak ${\ Displaystyle p_ {0}, \ ldots, p_ {k}}$ że istnieją stałe ${\ Displaystyle a_ {i}}$ i ${\ Displaystyle b_ {i}}$ takie, że ${\ Displaystyle b_ {i} p_ {i + 1}}$ jest resztą z dzielenia euklidesowego ${\ Displaystyle a_ {i} p_ {i-1}}$ przez ${\ Displaystyle p_ {i}.}$ ${\ displaystyle a_ {i}}$ Różne rodzaje sekwencji pseudo-reszty są definiowane przez wybór i $i};}$ ${$ zazwyczaj wybiera się, nie wprowadzać mianowników podczas dzielenia euklidesowego, $a$ współczynników wynikowa reszta; szczegóły patrz $.$ pseudo-reszt . sekwencją pseudo-reszt $ja$ , a sekwencja Sturma wielomianu jest sekwencją pseudoreszt z i ${\ Displaystyle a_ {i} = 1}$ każdego $i za$ i ${\ Displaystyle b_ {i} = -1}$ .

Zaprojektowano różne sekwencje pseudoreszt do obliczania największych wspólnych dzielników wielomianów o współczynnikach całkowitych bez wprowadzania mianowników (patrz Sekwencja pseudoreszt ). Wszystkie można uczynić $,$ wybierając znak przeciwny do znaku ${\ displaystyle a_ {i}.}$ Pozwala to na użycie twierdzenia Sturma z sekwencjami pseudoreszt.

Izolacja korzeni

W przypadku wielomianu o rzeczywistych współczynnikach izolacja pierwiastka polega na znalezieniu dla każdego pierwiastka rzeczywistego przedziału zawierającego ten pierwiastek i żadnych innych pierwiastków.

Jest to przydatne do znajdowania pierwiastków , umożliwiając znalezienie pierwiastka i zapewniając dobry punkt wyjścia dla szybkich algorytmów numerycznych, takich jak metoda Newtona ; jest to również przydatne do poświadczania wyniku, ponieważ jeśli metoda Newtona zbiega się poza przedziałem, można od razu wywnioskować, że zbiega się do niewłaściwego pierwiastka.

Izolacja pierwiastka jest również przydatna do obliczeń z liczbami algebraicznymi . W przypadku obliczeń z liczbami algebraicznymi powszechną metodą jest przedstawienie ich jako pary wielomianu, którego pierwiastkiem jest liczba algebraiczna, oraz przedziału izolacji. Na przykład $)$ ${\ Displaystyle (x ^ {2} -2, [0,2]).}$ przez

Twierdzenie Sturma zapewnia sposób izolowania pierwiastków rzeczywistych, który jest mniej wydajny (dla wielomianów o współczynnikach całkowitych) niż inne metody wykorzystujące regułę znaków Kartezjusza . Jednak pozostaje przydatny w pewnych okolicznościach, głównie do celów teoretycznych, na przykład dla algorytmów rzeczywistej geometrii algebraicznej , które obejmują nieskończenie małe .

Aby wyizolować rzeczywiste korzenie, zaczyna się od przedziału $($ wszystkie rzeczywiste pierwiastki lub korzenie będące przedmiotem zainteresowania (często, zazwyczaj w problemach fizycznych, interesujące są i oblicza się i ${\ Displaystyle$ $.}$ Do zdefiniowania tego przedziału początkowego można użyć granic wielkości pierwiastków (patrz Własności pierwiastków wielomianowych § Granice (zespolonych) pierwiastków wielomianowych ). Następnie dzieli się ten przedział na dwie części, wybierając $c$ w środku $}$ Obliczenie daje liczbę $)}$ prawdziwych korzeni w ${\ Displaystyle (a, c]}$ i ${\ Displaystyle (c, b],}$ i można powtórzyć tę samą operację na każdym podprzedziale. Kiedy podczas tego procesu napotka się interwał, który nie zawiera pierwiastka, może zostać usunięty z listy interwałów do rozważenia. Kiedy natrafimy na przedział zawierający dokładnie jeden pierwiastek, możemy przestać go dzielić, ponieważ jest to przedział izolacji. Proces ostatecznie zatrzymuje się, gdy pozostają tylko odstępy izolacyjne.

Ten proces izolowania można zastosować z dowolną metodą obliczania liczby pierwiastków rzeczywistych w przedziale. Teoretyczna analiza złożoności i praktyczne doświadczenia pokazują, że metody oparte na zasadzie znaków Kartezjusza są bardziej efektywne. Wynika z tego, że obecnie sekwencje Sturma są rzadko używane do izolacji korzeni.

Aplikacja

Uogólnione sekwencje Sturma umożliwiają zliczanie pierwiastków wielomianu, w którym inny wielomian jest dodatni (lub ujemny), bez jawnego obliczania tych pierwiastków. Jeśli zna się przedział izolujący dla pierwiastka pierwszego wielomianu, pozwala to również na znalezienie znaku drugiego wielomianu na tym konkretnym pierwiastku pierwszego wielomianu, bez obliczania lepszego przybliżenia pierwiastka.

Niech $P (x)$ i $Q (x)$ będą dwoma wielomianami o rzeczywistych współczynnikach takich, że $P$ i $Q$ nie mają wspólnego pierwiastka, a $P$ nie ma wielu pierwiastków. Innymi słowy, $P$ i $P' Q$ są względnie pierwszymi wielomianami . To ograniczenie tak naprawdę nie wpływa na ogólność tego, co następuje jako GCD obliczenia pozwalają zredukować ogólny przypadek do tego przypadku, a koszt obliczenia sekwencji Sturma jest taki sam jak koszt GCD.

Niech $W (a)$ oznacza liczbę zmian znaku w $a$ uogólnionego ciągu Sturma począwszy od $P$ i $P' Q$ . Jeśli $a < b$ to dwie liczby rzeczywiste, to $W (za) - W (b)$ jest liczbą pierwiastków $P$ w przedziale ${\ Displaystyle (a, b]}$ tak, że $Q (a) > 0$ minus liczba pierwiastków w tym samym przedziale tak , że $Q (a) < 0$ . W połączeniu z całkowitą liczbą pierwiastków $P$ w tym samym przedziale określonym przez twierdzenie Sturma daje to liczbę pierwiastków $P$ taką, że $Q (a) > 0$ i liczbę pierwiastków $P$ taką, że $Q (a) < 0$ .

Zobacz też

Basu, Saugata; Pollack, Ryszard ; Roy, Marie-Françoise (2006). „Sekcja 2.2.2”. Algorytmy w rzeczywistej geometrii algebraicznej (wyd. 2). Springera . s. 52–57. ISBN 978-3-540-33098-1 . ^{[ martwy link ]}
Sturm, Jacques Charles François (1829). „Mémoire sur la résolution des équations numériques”. Bulletin des Sciences de Férussac . 11 : 419–425.
Sylwester, JJ (1853). „O teorii relacji syzygetycznych dwóch wymiernych funkcji całkowych, obejmującej zastosowanie do teorii funkcji Sturma i teorii największej wspólnej miary algebraicznej” . Phil. Trans. R. Soc. Londyn . 143 : 407–548. doi : 10.1098/rstl.1853.0018 . JSTOR 108572 .
Tomasz, Józef Miller (1941). „Twierdzenie Sturma dla wielu pierwiastków”. Narodowy Magazyn Matematyczny . 15 (8): 391–394. doi : 10.2307/3028551 . JSTOR 3028551 . MR 0005945 .
Heindel Lee E. (1971). Algorytmy arytmetyczne liczb całkowitych do wyznaczania wielomianu rzeczywistego zera . proc. SYMSAC '71 . P. 415. doi : 10.1145/800204.806312 . MR 0300434 . S2CID 9971778 .
de Moura, Leonardo; Passmore, Grant Olney (2013). „Obliczenia w rzeczywistych zamkniętych nieskończenie małych i transcendentalnych rozszerzeniach wymiernych” . proc. CADE 2013 . Notatki z wykładów z informatyki. 7898 : 178-192. doi : 10.1007/978-3-642-38574-2_12 . ISBN 978-3-642-38573-5 .
Panton, Don B.; Verdini, William A. (1981). „Program fortran do stosowania twierdzenia Sturma do obliczania wewnętrznych stóp zwrotu”. J. Finanse. ilościowe. Analny . 16 (3): 381–388. doi : 10.2307/2330245 . JSTOR 2330245 . S2CID 154334522 .
Akritas, Alkiviadis G. (1982). „Refleksje nad parą twierdzeń Budana i Fouriera”. Matematyka Mag . 55 (5): 292–298. doi : 10.2307/2690097 . JSTOR 2690097 . MR 0678195 .
Pedersen, Paweł (1991). „Wielowymiarowa teoria Sturma”. W Mattson, Harold F.; Mora, Teo; Rao, TRN (red.). Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 9. Międzynarodowe Sympozjum, AAECC-9, Nowy Orlean, LA, USA, 7–11 października 1991, Proceedings . Notatki z wykładów z informatyki. Tom. 539. Berlin: Springer. s. 318–332. doi : 10.1007/3-540-54522-0_120 . ISBN 978-3-540-54522-4 . MR 1229329 .
Yap, Chee (2000). Podstawowe problemy algebry algorytmicznej . Oxford University Press . ISBN 0-19-512516-9 .
Rahman, QI; Schmeisser, G. (2002). Analityczna teoria wielomianów . Monografie Londyńskiego Towarzystwa Matematycznego. Nowa seria. Tom. 26. Oxford: Oxford University Press . ISBN 0-19-853493-0 . Zbl 1072.30006 .
Baumol, William. Dynamika gospodarcza , rozdział 12, sekcja 3, „Jakościowe informacje o rzeczywistych korzeniach”
DG Hook i PR McAree, „Using Sturm Sequences To Bracket Real Roots of Polynomial Equations” w Graphic Gems I (red. A. Glassner), Academic Press, s. 416–422, 1990.