algorytm.org

Ciąg Sturma



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Ciąg Sturma
Ocena użytkowników:***** / 8
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 08 sierpnia 2005 21:07

Ciąg p0(x), p1(x),..., pn(x) nazywamy ciągiem Sturma jeśli:
  • 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 -9
p2(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 -1444
p3(x) = -8865

x-201
p0(x)-+-
p1(x)-++
p2(x)--+
p3(x)---
Liczba zmian znaków W(x)012

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
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 2
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 27 września 2012 21:21
Dodaj komentarz