Metoda bisekcji

Metoda bisekcjimetoda bisekcjiMetoda bisekcji jest sposobem na wyznaczanie miejsca zerowego funkcji. Aby można było jej użyć do wskazania miejsca zerowego funkcji w przedziale , muszą zostać spełnione następujące warunki:

1. funkcja w zadanym przedziale jest ciągłaciągłość funkcji w przedzialeciągła,

2. wartości funkcji na końcach przedziału mają różne znaki.

Specyfikacja problemu:

Dane:

• f(x) – funkcja ciągła w zadanym przedziale

• a, b – liczby rzeczywiste, końce przedziału poszukiwań pierwiastka

• delta – liczba rzeczywista, przybliżenie określające maksymalną długość przedziału

• epsilon – liczba rzeczywista, przybliżenie wartości funkcji w punkcie x0

Wynik:

• x0 – liczba rzeczywista, przybliżenie miejsca zerowego

Algorytm znajdowania miejsca zerowego metodą połowienia przedziału możemy zapisać za pomocą listy kroków:

1. Wyznacz $x_0$ jako środek przedziału .

2. Sprawdź, czy dla argumentu $x_0$ wartość funkcji $f\left(x_0\right)$ zbliży się do zera z przybliżeniem epsilon lub długość przedziału będzie mniejsza od dokładności delta. Jeżeli tak, udało się znaleźć przybliżenie pierwiastka funkcji $x_0$. Zakończ algorytm.

3. W przeciwnym wypadku wybierz jedną z połówek przedziału. Lewy lub prawy koniec przedziału przyjmie wartość $x_0$:

   1. Jeżeli $f\left(x_0\right)·f\left(a\right)<0$, to $b=x_0$

   2. Jeżeli $f\left(x_0\right)·f\left(b\right)<0$, to $a=x_0$

4. Przejdź do punktu 1.

Przeanalizujmy wykres funkcji:

R146GNw8Cj4Sb

Ilustracja przedstawia wykres o funkcji: f(x) równe x do potęgi trzeciej minus 5 do potęgi drugiej plus 2x plus 5.

Jest to wykres funkcji opisanej wzorem:

Naszym zadaniem jest wyznaczenia pierwiastka funkcji w przedziale .

Nie jesteśmy w stanie wskazać miejsca zerowego funkcji, posługując się metodami poznanymi na lekcjach matematyki. Możemy jednak określić jego przybliżoną wartość, korzystając z metody bisekcji. Musimy jednak sprawdzić, czy spełnione są dwa warunki niezbędne, aby zastosować tę metodę.

Założenia metody połowienia podziału

Przyjrzyjmy się jeszcze raz wykresowi funkcji. Sprawdźmy, jakie wartości przyjmuje ona na końcach przedziału, w którym chcemy szukać pierwiastka.

RoRDCN9RyzLdv

Ilustracja przedstawia wykres o funkcji: f(x) równe x do potęgi trzeciej minus 5 do potęgi drugiej plus 2x plus 5.
Wartości jakie przyjmuje na końcach przedziału to: (0, 5) oraz (4, -3).

Oto wartości funkcji dla argumentów wyznaczających końce przedziału ($x=0$ oraz dla $x=4$):

Funkcja na końcach przedziału przyjmuje wartości różniące się znakami. Dla argumentu $x=0$ wartość funkcji jest dodatnia, natomiast dla $x=4$ ujemna. Wiedząc też, że funkcja jest ciągła w zadanym przedziale, możemy skorzystać z twierdzenia Darboux.

Mówi ono, że jeśli funkcja jest ciągła w zadanym przedziale i wartości funkcji dla krańców przedziałów są różnych znaków, to istnieje punkt pośredni $c\in (a,b)$ taki, że $f\left(c\right)=0$.

Algorytm bisekcji – pseudokod

Przeanalizujmy zapisany za pomocą pseudokodu algorytm bisekcji dla funkcji f w przedziale . Dokładność wyznaczenia pierwiastka opisują parametry delta oraz epsilon – określają one, z jakim przybliżeniem wyznaczymy miejsce zerowe. Parametr epsilon jest przybliżeniem wartości funkcji w punkcie x0 – nie będziemy szukać punktu, w którym wartość funkcji wynosi zero, lecz takiego, dla którego różni się ona od zera o wartości z zakresu $⟨-epsilon,epsilon⟩$. Przybliżenie delta określa minimalną długość przedziału, przy której możemy kontynuować dzielenie go na połowy.

Zwróconą wartością jest obliczone przybliżenie miejsca zerowego x0.

długośćPrzedziału = b - a
dopóki prawda wykonuj:
	długośćPrzedziału = długośćPrzedziału / 2
    x0 = a + długośćPrzedziału
    
    jeżeli wartośćBezwzględna(długośćPrzedziału) < delta LUB wartośćBezwzględna(f(x0)) < epsilon wykonaj:
    	zwróć x0 i zakończ algorytm
    
    jeżeli f(x0) * f(a) < 0 wykonaj:
    	b = x0
	w przeciwnym razie wykonaj:
    	a = x0

W pierwszej linii zapisane zostało polecenie obliczenia długości przedziału, w którym jest poszukiwane miejsce zerowe funkcji.

Następnie wewnątrz pętli przedział jest dzielony na dwie równe części; x0 oznacza punkt środkowy przedziału .

Jeżeli przedział będzie krótszy od wartości delta lub wartość bezwzględna z wartości funkcji w punkcie x0 będzie mniejsza od epsilon, przerywamy pętlę i zwracamy wartość punktu środkowego x0.

W przypadku, gdy punkt środkowy nie spełni żadnego z warunków, nie będzie on przybliżeniem miejsca zerowego, lecz stanie się nowym prawym lub lewym końcem przedziału. Wartości funkcji na końcach przedziału muszą mieć zawsze różne znaki. Jeżeli zatem iloczyn wartości funkcji w punkcie środkowym i na lewym końcu przedziału ma wartość ujemną, punkt środkowy staje się nowym prawym końcem przedziału. W przeciwnym wypadku będzie on końcem lewym.

Wyznaczenie pierwiastka funkcji trzeciego stopnia

Znajdźmy miejsce zerowe funkcji opisanej wzorem:

w przedziale . Wartości epsilon i delta niech wynoszą $0,15$.

Sprawdźmy, czy funkcja spełnia założenia.

1. Własnością funkcji wielomianowej jest ciągłość. Rozpatrywana funkcja jest opisana za pomocą wielomianu, a zatem zachowuje ciągłość dla dowolnych liczb rzeczywistych – także w przedziale .

2. Wartości funkcji na końcach przedziału mają różne znaki, ponieważ:

Funkcja spełnia wymagane założenia, a zatem możemy przejść do realizowania algorytmu bisekcji.

Przedział ma długość $2$; dzielimy go na pół, a więc punkt środkowy to $x_0=1$.

Sprawdzamy, czy:

• wartość bezwzględna z długości przedziału jest mniejsza od $0,15$ lub

• wartość funkcji w punkcie środkowym jest mniejsza od $0,15$.

Wartość funkcji w punkcie $x_0$ to:

Żaden z warunków nie jest spełniony, więc punkt środkowy staje się lewym lub prawym końcem przedziału. Sprawdzamy, czy iloczyn wartości funkcji w punkcie środkowym i lewym końcu przedziału daje wartość ujemną:

Iloczyn nie daje wartości ujemnej, więc punkt środkowy staje się lewym końcem przedziału.

Teraz poszukujemy miejsca zerowego w przedziale . Ponownie dzielimy długość przedziału na dwie równe części; środek przedziału to $x_0=1,5$.

Sprawdzamy warunki, czy:

• wartość bezwzględna z długości przedziału jest mniejsza od $0,15$ lub

• wartość funkcji w punkcie środkowym jest mniejsza od $0,15$.

Pierwszy warunek nie jest spełniony, ponieważ długość przedziału wynosi $0,5$. Natomiast wartość funkcji w punkcie środkowym to:

Wartość bezwzględna z wartości funkcji w punkcie środkowym jest mniejsza od $0,15$, więc zwrócona zostaje wartość $x_0$ równa $1,5$. Przybliżeniem miejsca zerowego funkcji

w przedziale jest $1,5$.

Słownik