Ć
wiczenie 6: Znajdowanie miejsc zerowych równań nieliniowych
1
Metody numeryczne - laboratorium
Ć
wiczenie 6: Znajdowanie miejsc zerowych równań nieliniowych
Wprowadzenie teoretyczne
Dane jest równanie nieliniowe o ogólnej postaci
0
)
(
=
x
f
. Należy znaleźć pewne miejsce zerowe
równania. Do tego służą następujące metody iteracyjne.
Metoda bisekcji (połowienia)
Dany jest początkowy przedział
[
]
0
0
, b
a
, na którym przypuszcza się, że występuje miejsce zerowe
równania. Przedział ten musi spełniać następujące warunki:
1) funkcja
)
(x
f
musi być ciągła na przedziale
2)
0
)
(
)
(
0
0
<
b
f
a
f
- funkcja musi przyjmować różne znaki na końcach przedziału
W k-tym kroku procedury, wyznacza się punkt środkowy przedziału:
2
k
k
k
b
a
x
+
=
Nowe granice przedziału wyznacza się w zależności od położenia punktu środkowego:
k
k
k
k
b
b
x
a
=
=
+
+
1
1
,
dla
0
)
(
)
(
>
k
k
x
f
a
f
k
k
k
k
x
b
a
a
=
=
+
+
1
1
,
dla
0
)
(
)
(
>
k
k
x
f
b
f
Jeżeli
0
)
(
=
k
x
f
, to koniec procedury. W przeciwnym wypadku wykonuje się ją tak długo, aż nie
zostanie wypełniony warunek stopu:
- wartość funkcji
ε
≤
)
(
k
x
f
, gdzie
ε
jest z góry zadaną dokładnością
lub
- określona maksymalna liczba iteracji
Reguła falsi
Założenia metody opartej na regule falsi są identyczne, jak w przypadku metody bisekcji.
Również działanie jej opiera się na podobnej zasadzie. Poprzednia metoda w każdym kroku
wykorzystuje jedynie informację o znaku funkcji w rozpatrywanym przedziale. Można dodatkowo
uwzględnić wartość funkcji wyznaczając nowy przedział na podstawie przecięcia siecznej z osią X.
Sieczna wyznaczone jest przez dwa punkty o współrzędnych
(
)
)
(
,
k
k
a
f
a
,
(
)
)
(
,
k
k
b
f
b
.
Równanie prostej przechodzące przez dwa punkty na płaszczyźnie:
k
k
k
k
k
k
a
b
a
f
b
f
a
x
a
f
y
−
−
=
−
−
)
(
)
(
)
(
Ć
wiczenie 6: Znajdowanie miejsc zerowych równań nieliniowych
2
Przyjmuje się, że poszukiwany punkt x
k
spełnia równanie siecznych, to znaczy wartość prostej y
k
wynosi 0. Stąd wyznacza się punkt x
k
:
(
)
)
(
)
(
)
(
k
k
k
k
k
k
k
a
f
a
f
a
b
a
f
a
x
−
−
−
=
Nowe granice przedziału wyznacza się w zależności od położenia wyznaczonego punktu x
k
. Robi się
to analogicznie jak w metodzie bisekcji. Również warunek stopu jest realizowany w ten sam sposób.
Metoda Newtona
Metoda ta, w przeciwieństwie do metod poprzednich, nie wymaga podania przedziału, na
którym poszukiwane jest miejsce zerowe. Wystarczające jest podanie pojedynczego punktu będącego
pierwszym przybliżeniem szukanego rozwiązania. Metoda uwzględnia nie tylko wartość funkcji, ale
również jej nachylenie (pochodną). Stąd wymagane jest, aby funkcja
)
(x
f
miała ciągła pochodną w
otoczeniu rozpatrywanego punktu x
k
. Idea metody polega na poszukiwaniu rozwiązania przez
poruszanie się wzdłuż prostej stycznej do funkcji w punkcie. Prosta ta jest opisana równaniem:
)
(
'
)
(
k
k
k
x
f
x
x
x
f
y
=
−
−
Poszukiwany jest punkt x
k+1
, w którym prosta styczna przecina oś X (y=0):
)
(
'
)
(
1
k
k
k
k
x
f
x
f
x
x
−
=
+
Procedura jest wykonywana, aż nie zostanie osiągnięty punkt o odpowiednio małej wartości,
lub zostanie osiągnięta maksymalna liczba iteracji.
Metoda wymaga wyznaczenia pochodnej funkcji. Jeżeli pochodna nie jest znana analitycznie,
należy zrobić to numerycznie. Prowadzi to do metody siecznych.
Metoda siecznych
Znalezienie miejsca zerowego funkcji w kroku k+1 metody Newtona można zastąpić
następującym wyrażeniem wynikającym z przybliżenia pochodnej różnicą skończoną:
)
(
)
(
)
(
1
1
1
−
−
+
−
−
−
=
k
k
k
k
k
k
k
x
f
x
f
x
x
x
f
x
x
Postępowanie jest identyczne jak w metodzie Newtona. Wymaga jednak podania dwóch
początkowych wartości do procedury iteracyjnej (przykładowo, aby wyznaczyć wartość x
3
należy znać
wartości x
2
oraz x
1
). W przeciwieństwie do metody bisekcji oraz reguły falsi, początkowe rozwiązania
metody siecznych nie muszą tworzyć przedziału, w którym zawarte jest poszukiwane rozwiązanie
równania.
Ć
wiczenie 6: Znajdowanie miejsc zerowych równań nieliniowych
3
Zadania laboratoryjne
Ć
wiczenie polegać będzie na zbadaniu 3 różnych metod rozwiązywania równań nieliniowych. W tym
celu należy napisać funkcje realizujące wybrane metody. Język programowania jest dowolny
(Matlab/Scilab oferują wygodne narzędzia i środowisko). Funkcje te należy wykorzystać do zbadania
następujących zagadnień.
Zadanie 1
Dla wybranej metody znaleźć oszacowania następujących wartości:
a)
3
b)
4
16
c)
3
15
Sprawdzić szybkość zbieżności oszacowania w zależności od przyjętego punktu/zakresu startowego.
Przy jakiej liczbie iteracji otrzymuje się rozsądną dokładność?
Wskazówka: Rozpatrzyć równanie nieliniowe
0
=
−
c
x
n
Zadanie 2
Porównaj skuteczność działania opracowanych metod dla następujących przypadków równań:
a) funkcji wielomianowej posiadającej zarówno miejsca zerowe wymierne, jak i niewymierne, np.
)
4
(
*
)
50
(
*
)
5
(
*
)
2
(
*
)
(
*
)
6
(
)
(
1
Π
−
−
−
−
Π
+
+
=
x
x
x
x
x
x
x
y
b) funkcji nieliniowej, posiadającej punkt nieciągłości, np.
1
1
)
log(
)
(
2
2
−
−
=
x
x
x
y
(Uwaga! W
implementacji należy uwzględnić przypadek nieciągłości, który może prowadzić do
rozbieżności procedury)
c) funkcji trygonometrycznej, np.
)
cos(
)
sin(
)
(
2
3
x
x
x
y
−
=
Proponuje się badać zbieżność procedury rozwiązywania w zależności od:
- wybranej metody,
- badanego miejsca zerowego (dla funkcji posiadających więcej miejsc zerowych),
- punktu/zakresu startowego,
- zadanej dokładności.
Narysować wykres błędu bezwzględnego/względnego (przyjąć takie postaci funkcji, aby miejsca
zerowe były znane) w zależności od liczby iteracji.
Na podstawie przeprowadzonych obserwacji, należy wyciągnąć wnioski dotyczące zakresów
przydatności poszczególnych zbadanych metod numerycznych.