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

1

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



rozwi



zanie 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 malej



ca, albo rosn



ca w całym przedziale).

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

Mamy dan



funkcj

f(x) oraz przedział

<x

p

,x

k

>

, 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 <x

p

,x

k

>. 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(x

p

) < 0 < f(x

k

) lub f(x

p

) > 0 > f(x

k

),

to istnieje taki punkt x

o

: x

p

< x

o

< x

k

,

e f(x

o

) = 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 x

o

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

2

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

kra



cach zadanego przedziału poszukiwa



pierwiastka <x

p

,x

k

> musi mie



przeciwny

znak, czyli f(x

p

) x f(x

k

) < 0. Punkty wykresu odpowiadaj



ce kra



com przedziału

ł



czymy sieczn



, która przetnie o



x w punkcie x

o

. Punkt ten jest kandydatem na

pierwiastek i obliczamy go wg wzoru:

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

3

Obliczamy warto





funkcji w punkcie x

o

i sprawdzamy, czy jej moduł wpada

w zało one otoczenie zera o promieniu

(epsilon):

Je



li tak, to x

o

jest poszukiwanym przybli eniem pierwiastka funkcji i ko



czymy

obliczenia. W przeciwnym razie punkt x

o

dzieli przedział <x

p

,x

k

> na dwie cz





ci:

<x

p

,x

o

> oraz <x

o

,x

k

>. Sprawdzamy, w której z tych cz

 

ci znak warto



ci funkcji na

kra



cach 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 x

o

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 x

o

.

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 x

p

. Nast



pnie znajdujemy prost



styczn



do wykresu funkcji w tym

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

4

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

(x

p

) 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 x

o

,

upraszczamy odpowiednio i otrzymujemy:

Po znalezieniu punktu x

o

obliczamy warto





funkcji f(x

o

) i sprawdzamy, czy

Je



li tak, to x

o

jest poszukiwanym pierwiastkiem przybli onym funkcji f(x) i

ko



czymy wykonywanie algorytmu. W przeciwnym razie za nowy punkt x

p

przyjmujemy obliczony punkt x

o

i powtarzamy obliczenia, a do uzyskania

pozytywnego wyniku.