Metody numeryczne 1 (MEN331) - Ćwiczenia 9

Kalendarium, Zasady, Ćw1, Ćw2, Ćw3, Ćw4, Ćw5, Ćw6, Ćw7, Ćw8, Ćw9, Ćw10, Ćw11, Ćw12, Ćw13
Prowadzący: Rafał Witkowski
Temat: Wyznaczanie zer wielomianów
Problemem dzisiaj rozważanym będzie znajdowanie miejsc zerowych dowolnych wielomianów. Chodzi oczywiście o takie wielomiany, w których nie da się tego zrobić dobrze dokładnie. Wyniki nasze będą również oczywiście przybliżone i uzyskane z pewną dokładnością.
Omówione poniżej metody pozwalają na przybliżenie przedziałów, w których znajduję się owe szukane 0 wielomianów, oraz pozwalają określić ile (co najwyżej) znajduje się miejsc zerowych między dowolnymi dwoma punktami na osi rzeczywistej (w każdej z metod, jeśli weźmiemy wartości -nieskończonści i nieskończoności, otrzymamy liczbę wszystkich miejsc zerowych wielomianu).

Metoda Fouriera

Dla danego wielomianu postaci, tworzymy ciąg pochodnych f(x), f'(x),  ...,  f'''''''''(x) tak długi, aż ostatnia pochodna się wyzeruje w każdym punkcie. Ponadto przez M(x0) oznaczymy liczbę zmian znaku w ciągu tych pochodnych.

Twierdzenie Fouriera

Jeżeli f(x) jest wielomianem stopnia n określonym na przedziale (a,b) i f(a)f(b)<>0 to liczba ze wielomianu f(x) w tym przedizale jest równa M(a) - M(b) lub jest od tej liczby mniejsza o liczbę parzystą.

Przykład 1

Wyznaczyć ilość pierwiastków równania:
Rozwiązanie:


Zadanie 1
Oblicz za pomocą metody Fouriera'a ilość pierwistków wielomianów:


Metoda Laguerre'a

Dla wielomianu f(x) tworzymy ciąg wielomianów:


Następnie oznaczamy przez L(x0) liczbę zmian znaku w ciągu

Twierdzenie Laguerre'a

Jeżeli f(x)jest wielomianem stopnia n olreślonym na przedziale (a,b) i f(a)f(b)<>0 to liczba zer wielomianu f(x) w tym przedziale jest równa L(a) - L(b) lub jest od tej liczby mniejsza o liczbę parzystą

Przykład 2

Wyznaczyć ilość pierwiastków równania:

Rozwiązanie:



Reguła Kartezjusza

Przypadkiem szczególnym metody Laguerre'a jest tzw. reguła Kartezjusza mówiąca, że liczba dodatnich zer wielomianu z uwzględnieniem ich krotności jest równa liczbie zmian znaków ciągu współczynników a0, a1, ..., an lub jest od tej liczby mniejsza o liczbę parzystą.
Chcąc znaleźć liczbę ujemnych zer wielomianu konstruujemy wielomian f(-x) i badamy liczbę zer dodatnich tego wielomianu.

Przykład 3



czyli ciąg współczynników wygląda następująco: 1, -2, -5, 5 (+, -, -, +)
2 zmiany więc wielomian ma 2 lub 0 pierwiastków dodatnich.

Następnie konstruujemy wielomian f(-x) i rozpatrujemy jego współczynniki: -1, -2, 5, 5 (-, -, +, +)
czyli wielomian ma 1 pierwiastek ujemny. Zgadza się to z naszymi wcześniejszymi obliczeniami.
Zadanie 2
Oblicz za pomocą metody Laguerre'a i reguły Kartezjusza liczbę pierwiastków w wielomianie oraz określ (na ile to możliwe) gdzie się one znajdują.


Algorytm Sturma

Najpierw należy zdefiniować ciąg Sturma dla danego wielomianu:

w ciągu tym oznaczenie r(X, Z)  oznacza resztę z dzielenia wielomianu X przez wielomian Z

Twierdzenie Sturma

Niech w(c) będzie liczbą zmian znaku (nie licząc zer) w ciągu Sturma: W(c), W1(c), ... Wk+1(c). Wtedy dla dowolnych dwóch liczb a, b które nie są pierwiastkami wielomianu X liczba pierwiastków wielomianu w przedziale [a,b] wynosi dokładnie w(a) - w(b)
Zadanie 3
Oblicz za pomocą algorytmu Sturma liczbę pierwiastków w wielomianów: