Czegóż dawniej uczono

Twierdzenie Sturma

Rozważamy wielomian $w$ o współczynnikach rzeczywistych stopnia $n:$ Wiadomo, że wielomian taki ma $n$ pierwiastków zespolonych; niektóre z nich (czasami wszystkie) są, być może, rzeczywiste. Twierdzenie Sturma pozwala obliczyć liczbę pierwiastków rzeczywistych wielomianu $w$ należących do wybranego przedziału $⟨a;b⟩:$ Oczywiście, odpowiedź na to pytanie możemy uzyskać, stosując metodę badania funkcji wielomianowej $w ;$ znaną z analizy matematycznej. Metoda Sturma jest czysto algebraiczna, nie stosuje metod analizy matematycznej.

Sprecyzujmy założenia. Wielomian $|w$ o współczynnikach rzeczywistych nie ma pierwiastków wielokrotnych (gdyby miał, to możemy je usunąć opisaną w Delcie 12/2015 metodą) oraz dla ustalonych liczb $a,b(a < b)$ wartości $|w(a)$ i $|w(b)$ są różne od zera.

Ciągiem Sturma dla wielomianu $w$ nazywamy ciąg wielomianów $|w,w,w,...,w 01 2 s$ określony przez algorytm Euklidesa dla wielomianu $w$ i jego pochodnej $′ w,$ zmodyfikowany w ten sposób, że rozważamy kolejne reszty z dzielenia zaopatrzone w znak minus:

w0 = w, w1 = w′ , w2 w0 = q1w1− w2, w3 w1 = q2w2− w3, ........................ ws ws−2 = qs−1ws−1− ws

dotąd aż wielomian $|ws$ nie będzie miał pierwiastków w przedziale $|⟨a, b⟩.$ Ten warunek na pewno możemy spełnić, gdyż zmodyfikowany algorytm Euklidesa, który tu stosujemy, prowadzi do największego wspólnego dzielnika wielomianu $w$ i jego pochodnej, a gdyby ten miał pierwiastek, to byłby to wspólny pierwiastek $|w$ i $w′ ,$ czyli pierwiastek wielokrotny wielomianu $w,$ wbrew założeniu, że nie ma pierwiastków wielokrotnych.

Dla $x$ należącego do $⟨a,b⟩$ przez $z(x)$ oznaczamy liczbę zmian znaku w ciągu $|w0(x), w1(x),w2(x),...,ws(x),$ tj. liczbę takich sytuacji, gdy kolejne wyrazy są liczbami przeciwnych znaków, a jeśli któryś wyraz jest zerowy, to pomijamy go i porównujemy znaki pozostałych wyrazów sąsiednich.

Twierdzenie 1 (Sturma). Liczba pierwiastków rzeczywistych wielomianu $|w$ spełniającego sformułowane wyżej założenia w przedziale $⟨a,b⟩$ jest równa $z(a) − z(b).$

Dowód. Dwa kolejne wielomiany ciągu Sturma nie mogą mieć wspólnego miejsca zerowego w przedziale $|⟨a, b⟩,$ gdyby bowiem $|wk(x0) = wk+1(x0) = 0,$ to wobec równości

wk = qk+1wk+1− wk+2

mielibyśmy $|w (x ) = 0 k+2 0$ i kolejne wielomiany ciągu Sturma aż do $ws$ zerowałyby się w punkcie $|x0,$ co nie jest możliwe.

Wszystkie wielomiany ciągu Sturma mają skończoną liczbę miejsc zerowych, możemy więc dany przedział $|⟨a,b⟩$ podzielić na skończoną liczbę podprzedziałów, w których każdy z wielomianów ma stały znak. Funkcja $z$ jest stała w każdym z tych podprzedziałów i może zmieniać swą wartość tylko przy przejściu przez punkt, w którym zeruje się jeden z wielomianów ciągu Sturma.

Jeśli $x 0$ jest miejscem zerowym wielomianu $w k$ dla $0 < k < s,$ to ponieważ

wk− 1 = qk ⋅wk− wk+1,

więc liczby $|wk− 1(x0),wk+1(x0)$ mają przeciwne znaki. W pobliżu punktu $x0$ na lewo i na prawo możliwe są następujące układy znaków liczb $|wk− 1(x),wk(x),wk+1(x)$ :

− − +,−++, +− −,++ −

a w samym punkcie $x0$ :

−0+, +0 −.

w(x) = (x −x0) ⋅v(x), v(x0) ≠ 0, w′ (x) = w1(x) = v(x) + (x− x0) ⋅v′ (x).

Ponieważ $|v(x0)≠ 0,$ więc w pewnym otoczeniu $x0$ funkcja $v$ ma stały znak. Gdy $x < x0,$ funkcja $|w$ ma przeciwny znak niż $v,$ gdy zaś $|x > x0,$ funkcje $|w$ i $v$ mają ten sam znak. Zatem funkcja $z$ przy przejściu przez $|x0$ zmniejsza swą wartość o 1. Liczba pierwiastków rzeczywistych wielomianu $|w$ leżących w przedziale $|⟨a,b⟩$ jest istotnie równa $z(a) −z(b).$

Przykład 1. Wyznaczymy liczbę pierwiastków rzeczywistych wielomianu $|w(x) = x3 −3x − 1$ i wskażemy takie przedziały o końcach w liczbach całkowitych, z których każdy zawiera tylko jeden z tych pierwiastków.

Zamiast pochodnej $|w′(x) = 3x2 −3$ możemy przyjąć $w1(x) = x2 − 1,$ gdyż przy wyznaczaniu liczby zmian znaku ważne są tylko znaki wartości wielomianów ciągu Sturma. Obliczamy $|x3− 3x − 1 = x⋅(x2 − 1) − 2x− 1,$ więc przyjmujemy $w2(x) = 2x + 1,$ a ponieważ $x2− 1 = ( 12x− 14) (2x + 1)− 34,$ więc $|w(x) = 3. 3 4$ Budujemy tabelkę, w której pierwszym wierszu wypisujemy wybrane liczby całkowite - będą one końcami przedziałów, w których spodziewamy się pierwiastków wielomianu $w,$ a w pierwszej kolumnie wypisujemy wielomiany ciągu Sturma. Pod każdą liczbą z pierwszego wiersza wypisujemy znaki kolejnych wielomianów, a niżej liczbę zmian znaku.

$|-------------|----|---|--|--| |-------------|−-2-|−1-|0-|2-| | x3− 3x −1 | − |+ |− |+ | |-------------|----|---|--|--| |----x2−-1----|-+--|0--|−-|+-| | 2x + 1 | − |− |+ |+ | |-------------|----|---|--|--| | 34 | + |+ |+ |+ | |-------------|----|---|--|--| -Liczba-zmian---3---2---1--0--$

Z tabeli odczytujemy, że po jednym pierwiastku wielomianu $|w$ zawiera każdy z przedziałów $(− 2,−1),(−1,0),(0,2).$ Są to oczywiście wszystkie pierwiastki, gdyż wielomian stopnia trzeciego nie ma więcej niż trzy pierwiastki.

Przykład 2. Rozważmy teraz wielomian $|w(x) = x3 + 3x− 5.$ Jako $w1(x)$ możemy przyjąć $x2 + 1.$ Ponieważ $x3 + 3x− 5 = x ⋅(x2 +1) +2x − 5,$ więc przyjmujemy $| w2(x) = −2x + 5.$ Następnie obliczamy $| 2 1 5 29- x + 1 = (−2x − 4)⋅(− 2x + 5) + 4$ ; zatem $29 w3(x) = −-4 .$ Budujemy tabelkę podobną, jak w poprzednim przykładzie, ale zaczniemy od wyznaczenia znaków granic wielomianów ciągu Sturma w $− ∞$ i $|+∞ .$

$|-----------|----|---|----| |-----------|−∞--|---|+∞--| | 3 | | | | |x--+-3x−-5-|-−--|---|-+--| | x2 + 1 | + | | + | |-----------|----|---|----| |--−2x-+-5--|-+--|---|-−--| | −29 | − | | − | |-----4-----|----|---|----| --------------2--------1---$

Wynika stąd, że wielomian $w$ ma tylko jeden pierwiastek rzeczywisty. Obliczmy liczbę zmian znaku na końcach przedziału $| ⟨1,2⟩.$

$|-----------|1-|-2-|+∞--| |-----------|--|---|----| |x3 + 3x− 5 |− |+ | + | |-----------|--|---|----| |---x2 +-1--|+-|+--|-+--| | −2x + 5 |+ |+ | − | |-----29----|--|---|----| | −4- |− |− | − | |-----------|--|---|----| -------------2---1---1--|$

Jedyny pierwiastek wielomianu $w$ należy do przedziału $⟨1,2⟩.$