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.