Metody numeryczne

szukanie pierwiastka metodą bisekcji

Dawid Rasała

Pierwiastki równania f(x) = 0 na ogół nie wyrażają się zamkniętymi

wzorami, dlatego rozwiązując równania nieliniowe stosujemy na

ogół metody przybliżone, opierające się zazwyczaj na kolejnych

przybliżeniach pierwiastka. Są to metody iteracyjne, co oznacza, że

startując od jednego lub kilku przybliżeń początkowych

pierwiastka, metody te dają ciąg x

0

, x

1

, x

2

, … kolejnych przybliżeń

pierwiastka.

Rozwiązywanie równań

Metody numeryczne
Dawid Rasała

Metoda równego podziału (metoda połowienia, metoda

bisekcji, metoda połowienia przedziału) - jedna z metod

rozwiązywania równań nieliniowych. Opiera się ona na

następującym twierdzeniu:

Metoda bisekcji

Jeżeli funkcja ciągła f(x) ma na końcach przedziału domkniętego

wartości różnych znaków, to wewnątrz tego przedziału, istnieje co

najmniej jeden pierwiastek równania f(x) = 0.

Metody numeryczne
Dawid Rasała

Mamy daną funkcję f(x) oraz przedział <a,b>, w którym będziemy

poszukiwali miejsca zerowego. Aby można było zastosować

algorytm połowienia muszą być spełnione poniższe warunki:

1. Funkcja f(x) jest określona w każdym punkcie przedziału <a,b>.

Określoność funkcji oznacza, iż dla każdej wartości argumentu x z

przedziału <a,b> potrafimy policzyć wartość funkcji. Dla przykładu

rozważmy prostą funkcję:

W punkcie x = 1 tak podana funkcja ma nieokreśloną wartość.

Musimy dzielić przez 0, a jak wiadomo jest to zadanie

niewykonalne.

Metoda bisekcji

Metody numeryczne
Dawid Rasała

2. Funkcja f(x) jest ciągła. Ciągłość funkcji oznacza z kolei, iż jej

wartości nie "wykonują" nagłych skoków, nie istnieją przerwy w

kolejnych wartościach funkcji. Dla przykładu rozważmy taką oto

funkcję:

Nieciągłość występuje w punkcie x = 0, czyli w miejscu zmiany

przepisu funkcji.

Metoda bisekcji

Metody numeryczne
Dawid Rasała

3. Funkcja f(x) na krańcach przedziału <a,b> przyjmuje różne

znaki. Ponieważ funkcja, zgodnie z poprzednim wymogiem, jest

ciągła, to przyjmuje w przedziale <a,b> wszystkie wartości

pośrednie pomiędzy f(a) i f(b).  Wartości te mają różne znaki (czyli

leżą po różnych stronach osi OX), zatem musi być taki punkt x

o

w

przedziale <a,b>, dla którego funkcja przyjmuje wartość

pośrednią.

Metoda bisekcji

Metody numeryczne
Dawid Rasała

Gdy funkcja f(x) spełnia powyższe trzy warunki, to w przedziale

<a,b> zagwarantowane jest istnienie pierwiastka i możemy go

wyszukać algorytmem połowienia. Zasada jest następująca:

Kroki algorytmu

1. Wyznaczamy punkt x

o

jako środek przedziału <a,b>.

2. Obliczamy wartość funkcji w punkcie x

o

. Sprawdzamy, czy f(x

o

)

znajduje się dostatecznie blisko 0:

Metody numeryczne
Dawid Rasała

3. Jeśli nierówność jest spełniona, to x

o

jest poszukiwaną wartością

pierwiastka. Zwracamy wynik i kończymy algorytm. W przeciwnym

razie za nowy przedział poszukiwań pierwiastka przyjmujemy tą

połówkę <a,x

o

> lub <x

o

,b>, w której funkcja zmienia znak na

krańcach i przechodzimy ponownie do punktu 1.

Kroki algorytmu

Metody numeryczne
Dawid Rasała

Algorytm powtarzamy od początku dotąd, aż:

1.znajdziemy pierwiastek, czyli spełniona będzie nierówność

2.przedział <a,b> osiągnie założoną długość (może to być również

epsilon)

3.wykonamy określoną ilości iteracji.

Warunki zakończenia obliczeń

Metody numeryczne
Dawid Rasała

Wyznaczyć pierwiastek równania x

3

− x + 1 = 0 w przedziale [ −

2;0].

Przykład

Metody numeryczne
Dawid Rasała

1. Wszystkie poniższe równania maja pierwiastek w przedziale (0,

1.6). Wyznaczyć te pierwiastki metodą bisekcji z błędem

mniejszym od 0,02:

a) x * cos(x) = - ln(x);

b) 2 x - e

-x

= 0.

2. Napisać w dowolnym języku program, który realizuje meodę

bisekcji dla zadanej funkcji.

Zadania

Metody numeryczne
Dawid Rasała