Wpisany przez Tomasz Lubiński,
08 sierpnia 2005 21:07
Ciąg p0(x), p1(x),..., pn(x) nazywamy ciągiem Sturma jeśli:
Liczba miejsc zerowych wielomianu p(x) w przedziale <a, b) jest równa |W(b) - W(a)|, gdzie W(x) oznacza liczbę zmian znaku w punkcie x w ciągu Sturma p0(x), p1(x),..., pn(x) zbudowanym w oparciu o p(x).
Sposób konstrukcji ciągu jest następujący:
p0(x) = p(x)
p1(x) = -p'(x)
Pozostałe to reszta z dzielenia przedostatniego przez ostatni pomnożona przez stałą mniejszą od zera.
Skonstruujemy ciąg Sturma wielomianu p(x) = x3 - 2x2 - 5x + 5
p0(x) = p(x) = x3 - 2x2 - 5x + 5
p1(x) = -p'(x) = -3x2 + 4x + 5
p2(x) = 38x - 35
p3(x) = -8865
Z tabelki możemy odczytać m.in, że p(x) ma w przedziale <-2; 0) jedno miejsce zerowe bo |W(0) - W(-2)| natomiast przedziale <-2; 1) ma dwa miejsca zerowe bo |W(1) - W(-2)|
- p0(x) ma tylko pojedyncze miejsca zerowe,
- sign p1(a) = -sign p0'(a) dla wszystkich rzeczywistych zer a wielomianu p0(x),
- dla i=1,2,...,n-1 pi+1(a)*pi-1(a) < 0, jeśli a oznacza zera rzeczywiste wielomianu pi(a).
Liczba miejsc zerowych wielomianu p(x) w przedziale <a, b) jest równa |W(b) - W(a)|, gdzie W(x) oznacza liczbę zmian znaku w punkcie x w ciągu Sturma p0(x), p1(x),..., pn(x) zbudowanym w oparciu o p(x).
Sposób konstrukcji ciągu jest następujący:
p0(x) = p(x)
p1(x) = -p'(x)
Pozostałe to reszta z dzielenia przedostatniego przez ostatni pomnożona przez stałą mniejszą od zera.
Przykład:
Skonstruujemy ciąg Sturma wielomianu p(x) = x3 - 2x2 - 5x + 5
p0(x) = p(x) = x3 - 2x2 - 5x + 5
p1(x) = -p'(x) = -3x2 + 4x + 5
\begin{array}{ccccc}
(x^3 & -2x^2 & -5x & +5&):(-3x^2 + 4x + 5) = -\frac{1}{3}x + \frac{2}{9} \\
-x^3 & +\frac{4}{3}x^2 & +\frac{5}{3}x & &
\end{array}\\
\line(1,0){260}\\
\begin{array}{cccc}
\text{ }\text{ }=\text{ }\text{ }\text{ }& -\frac{2}{3}x^2 & -\frac{10}{3}x & +5 \\
& \frac{2}{3}x^2 & -\frac{8}{9}x & - \frac{10}{9}
\end{array}\\
\line(1,0){260}\\
\begin{array}{cccc}
\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }&\text{ }\text{ }=\text{ }\text{ }& -\frac{38}{9}x & +\frac{35}{9}
\end{array}
Resztę należy pomnożyć przez liczbę mniejszą od zera - dla ułatwienia rachunków niech będzie to -9p2(x) = 38x - 35
\begin{array}{cccc}
(-3x^2 & +4x & +5 &):(38x - 35) = -\frac{3}{38}x + \frac{47}{1444} \\
3x^2 & -\frac{105}{38}x & &
\end{array}\\
\line(1,0){260}\\
\begin{array}{ccc}
\text{ }\text{ }=\text{ }\text{ }\text{ }& \frac{47}{38}x & +5 \\
& -\frac{47}{38}x & +\frac{1645}{1444}
\end{array}\\
\line(1,0){260}\\
\begin{array}{ccc}
\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }&\text{ }\text{ }=\text{ }\text{ }\text{ }& \frac{8865}{1444}
\end{array}
Resztę należy pomnożyć przez liczbę mniejszą od zera - dla ułatwienia rachunków niech będzie to -1444p3(x) = -8865
| x | -2 | 0 | 1 |
| p0(x) | - | + | - |
| p1(x) | - | + | + |
| p2(x) | - | - | + |
| p3(x) | - | - | - |
| Liczba zmian znaków W(x) | 0 | 1 | 2 |
Z tabelki możemy odczytać m.in, że p(x) ma w przedziale <-2; 0) jedno miejsce zerowe bo |W(0) - W(-2)| natomiast przedziale <-2; 1) ma dwa miejsca zerowe bo |W(1) - W(-2)|
Implementacje
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| Tomasz Lubiński | Delphi/Pascal | Borland Delphi 5 | .pas | .pas | ***** / 2 |
Poprawiony: 27 września 2012 21:21