Ć

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.