Numeryczne metody poszukiwania miejsc zerowych funkcji

Nie zawsze w prosty sposób da si znale

miejsce zerowe funkcji w danym

przedziale. Korzystamy wówczas z metod numerycznych, które przybli aj

rozwizanie z zadan dokładno ci. Ka da z trzech prezentowanych ni ej meto

wymaga, aby funkcja na kra cach przedziału miała ró ne warto ci oraz eby była

ci le monotoniczna (albo malejca, albo rosnca w całym przedziale).

a) metoda bisekcji (równego podziału)

Mamy dan funkcj f(x) oraz przedział <xp,xk> , w którym chcemy znale miejsce

zerowe tej funkcji z zadan dokładno ci .

Opisana w tym podpunkcie metoda jest najwolniej zbie n metod

znajdowania przybli onych pierwiastków funkcji w zadanym przedziale

argumentów <xp,xk> . Metod bisekcji mo na zastosowa, je li funkcja jest

ci gła i na kra cach przedziału posiada ró ne znaki. W takim przypadku

twierdzenie o warto ciach po rednich mówi nam, i :

je li f(xp) < 0 < f(xk) lub f(xp) > 0 > f(xk),

to istnieje taki punkt xo: xp < xo < xk,

e f(xo) = 0

Innymi słowy twierdzenie to gwarantuje nam istnienie przynajmniej jednego

pierwiastka w danym przedziale. Metoda bisekcji ( połowienia, krojenia na pół)

polega na dzieleniu zadanego przedziału argumentów na dwie równe połówki.

Dokonujemy tego znajduj c punkt rodkowy przedziału jako redni arytmetyczn

jego kra ców.

Je li warto funkcji w punkcie podziału jest równa zero ( lub dostatecznie bliska), to

punkt ten traktujemy jako pierwiastek funkcji i ko czymy dalsze wykonywanie

algorytmu. W przeciwnym razie warto funkcji w punkcie podziału nie jest równa

zero, wi c musi by od niego wi ksza lub mniejsza. Sprawdzamy, w której z

otrzymanych przez podział połówek funkcja zmienia znak na przeciwny na kra cach -

jest tylko jedna taka połówka. Wybran połówk traktujemy jako nowy przedział

zawieraj cy pierwiastek i znów dzielimy j na dwie cz ci sprawdzaj c warto

funkcji w rodku przedziału. Operacje te kontynuujemy, a do znalezienia pierwiastka.

Punkt xo w granicy niesko czonych podziałów jest zbie ny do punktu b d cego

poszukiwanym pierwiastkiem zadanej funkcji. Poniewa nie mo emy wykonywa

tych oblicze w niesko czono , to zadawalamy si przybli on warto ci

pierwiastka, któr otrzymamy po kilkunastu obiegach.

Podstawy Informatyki 2 rok akad. 2003/2004 mgr in . Paweł Myszkowski 1

b) metoda siecznych (regula falsi)

Metoda bisekcji zaprezentowana w poprzednim rozdziale zupełnie nie korzystała z

własno ci funkcji i jej przebiegu wewn trz badanego przedziału - wystarczała jej

informacja o znaku funkcji na jego kra cach. Punkt przewidywanego pierwiastka

wyznacza si zawsze w rodku przedziału. Tymczasem mo na przypuszcza, i

pierwiastek b dzie zwykle bli ej tego punktu ko cowego, w którym warto

bezwzgl dna funkcji jest mniejsza, szczególnie gdy przedział poszukiwa staje si

coraz mniejszy i wykres funkcji w tym przedziale coraz bardziej zbli ony jest do

odcinka linii prostej. Spostrze enie to umo liwia szybsze zbli enie si do punktu

b d cego pierwiastkiem funkcji i zostało wykorzystane w metodzie siecznych,

zwanej równie metod regula falsi ( fałszywej pozycji - poniewa wyznacza si

pierwiastek w punkcie na osi x, gdzie go nie ma)

Algorytm metody siecznych jest nast puj cy. Badana funkcja musi by ci gła i na

kracach zadanego przedziału poszukiwa pierwiastka <xp,xk> musi mie przeciwny

znak, czyli f(xp) x f(xk) < 0. Punkty wykresu odpowiadaj ce kracom przedziału

ł czymy sieczn , która przetnie o x w punkcie xo. Punkt ten jest kandydatem na

pierwiastek i obliczamy go wg wzoru:

Podstawy Informatyki 2 rok akad. 2003/2004 mgr in . Paweł Myszkowski 2

Obliczamy warto funkcji w punkcie xo i sprawdzamy, czy jej moduł wpada

w zało one otoczenie zera o promieniu ( epsilon):

Je li tak, to xo jest poszukiwanym przybli eniem pierwiastka funkcji i koczymy

obliczenia. W przeciwnym razie punkt xo dzieli przedział <xp,xk> na dwie cz ci:

<xp,xo> oraz <xo,xk> . Sprawdzamy, w której z tych cz ci znak warto ci funkcji na

kracach jest przeciwny i t cz

przyjmujemy za nowy przedział poszukiwa

pierwiastka. Obliczamy nast pny punkt przeci cia siecznej, sprawdzamy, czy jest

pierwiastkiem itd. Je li warunki pocz tkowe b d spełnione, to metoda siecznych

gwarantuje zbie no kolejno otrzymywanych punktów xo do warto ci pierwiastka

funkcji ( sprawd jednak 1 i 2).

Zwró cie uwag , i metoda regula falsi opiera si na identycznym schemacie

jak metoda bisekcji. Ró ni si one jedynie sposobem wyznaczania punktu xo.

Tutaj jest to przeci cie siecznej wykresu funkcji z osi x, tam rodek

przedziału poszukiwa pierwiastka.

c) metoda stycznych (Newtona)

Metoda stycznych ( zwana równie metod Newtona) ró ni si nieco od opisanych

dotychczas metod wyznaczania pierwiastka funkcji. W metodzie tej nie okre lamy

przedziału poszukiwa, lecz punkt na osi x dostatecznie blisko pierwiastka funkcji,

który oznaczymy xp. Nast pnie znajdujemy prost styczn do wykresu funkcji w tym

Podstawy Informatyki 2 rok akad. 2003/2004 mgr in . Paweł Myszkowski 3

punkcie. Prosta ta przecina o x i wyznacza nam kolejny punkt, który obliczamy wg

wzoru:

We wzorze mamy funkcj pochodn od f(x). Znaj c wzór algebraiczny funkcji f(x)

mo emy analitycznie znale wzór jej pochodnej, jednak na potrzeby oblicze

numerycznych, gdzie niezb dna jest warto pochodnej a nie jej wzór, korzysta si

najcz ciej z przybli onego wyznaczania pochodnej na podstawie definicji ilorazu

ró nicowego funkcji:

, gdzie jest otoczeniem zera.

Poniewa pochodna w punkcie jest granic ilorazu ró nicowego przy

d

cym do 0, to o ile otoczenie jest dostatecznie małe, otrzymana

przybli ona warto pochodnej funkcji f (xp) le y blisko warto ci dokładnej.

Oczywi cie otoczenie to nie mo e by mniejsze od dokładno ci wyznaczania

funkcji, gdy w takim przypadku nie otrzymamy poprawnej warto ci

pochodnej.

Wzór na przybli on warto pochodnej wstawiamy do wzoru na punkt xo,

upraszczamy odpowiednio i otrzymujemy:

Po znalezieniu punktu xo obliczamy warto funkcji f(xo) i sprawdzamy, czy

Je li tak, to xo jest poszukiwanym pierwiastkiem przybli onym funkcji f(x) i

koczymy wykonywanie algorytmu. W przeciwnym razie za nowy punkt xp

przyjmujemy obliczony punkt xo i powtarzamy obliczenia, a do uzyskania

pozytywnego wyniku.

Podstawy Informatyki 2 rok akad. 2003/2004 mgr in . Paweł Myszkowski 4