Ćwiczenie 5 (6 godzin)

Numeryczne rozwiązywanie równań i układów równań nieliniowych

Cel ćwiczenia

Praktyczne sprawdzenie wiedzy n/t popularnych metod iteracyjnych rozwiązywania równań i ukła-

dów równań nieliniowych. Porównanie przydatności poszczególnych metod do wyznaczania zer funkcji

określonych typów. Prześledzenie związku między rzędem metody iteracyjnej a szybkością zbieżności

ciągu przybliżeń.

Instrukcja wykonawcza

1. Napisać M-funkcje realizujące metody bisekcji, siecznych i Newtona. Zastosować napisane proce-

dury do znalezienia pierwiastków dwóch równań podanych przez prowadzącego. Zaobserwować

różnice w szybkości zbieżności w/w metod. Dla metod siecznych i Newtona przyjąć kryterium za-

trzymania obliczeń



m

|

x

n+1

−x

n

|

1−m

< ε



∨(n > 25), gdzie x

n

– n–te przybliżenie, m =

|x

n+1

−x

n

|

|x

n

−x

n−1

|

,

ε – założona tolerancja (ewentualnie, zwłaszcza w fazie uruchamiania podprogramu prostsze:

(|x

n+1

− x

n

| < ε) ∨ (n > 25)); dla metody bisekcji obliczenia prowadzić do momentu, gdy

długość przedziału zawierającego pierwiastek zmaleje poniżej 2ε.

2. Dla drugiego z przykładów z punktu 1. (zero wielokrotne) powtórzyć obliczenia zastępując podaną

funkcję f (·) ilorazem f (·)/f

0

(·).

W punktach 1. i 2. zarejestrować w każdej iteracji następujące wartości x

n

, f (x

n

), f

0

(x

n

),

x

n+1

−x

n

, x

n

−x

∗

, gdzie x

∗

– podana przez prowadzącego lub wyznaczona analitycznie wartość

dokładna pierwiastka.

3. Zastosować standardową procedurę Matlab’a fzero do równań rozwiązywanych w punktach 1

i 2. Porównać wyniki z uzyskanymi poprzednio.

4. Posługując się M-plikiem laguerre.m realizującym metodę Laguerre’a, plikiem bairstow.m im-

plementującym metodę Bairstowa oraz wbudowaną funkcją Matlab’a roots wyznaczyć wszyst-
kie zera wskazanego przez prowadzącego wielomianu. W odniesieniu do zer rzeczywistych po-

sługiwać się także innymi dostępnymi metodami (M-plikami stworzonymi w punkcie 1.). Użyć

pierwiastków wyznaczonych z wykorzystaniem deflacji (a więc wszystkich z wyjątkiem pierwszego

lub pierwszych dwóch obliczanych przez funkcje laguerre i bairstow) jako punktu startowe-

go metody Newtona i zaobserwować ile iteracji zostanie wykonanych przy tej samej założonej

dokładności; porównać uzyskane wyniki z dokładną wartością pierwiastka. Porównać szybkość

zbieżności poszczególnych metod (obliczenia wykonać dla różnej założonej dokładności ε , np.

10

−3

, 10

−5

, 10

−9

).

5. Prześledzić działanie metody Lehmera-Schura (plik lehmer.m). Zapoznać się z opisem zastoso-

wanego algorytmu (w „pomocy” funkcji lehmer) i wyjaśnić obserwowane rozbieżności między

wynikami oczekiwanymi na podstawie rozważań teoretycznych a obliczanymi przez program.

6. Napisać M-plik realizujący metodę Newtona dla układów dwóch równań z dwiema niewiadomymi

i za jego pomocą rozwiązać wskazany przez prowadzącego układ dwóch równań nieliniowych.

Ocenić szybkość zbieżności otrzymanego ciągu przybliżeń.

Sprawozdanie powinno zawierać

•

tabelaryczne zestawienie wyników z punktów 1, 2 oraz 6 i 7; wykresy |x

n

− x

∗

| (w przypadku

układu równań kx

n

− x

∗

k) w funkcji n,

•

wyniki obliczeń wszystkich zer wielomianów i tabelaryczne porównanie szybkości zbieżności po-

szczególnych metod; zestawienie różnic między wynikami uzyskiwanymi z wykorzystaniem de-

flacji i „poprawianych” w oparciu o oryginalny wielomian,

•

zestawienie czasu obliczeń zer wielomianu metodą Lehmera-Schura w zależności od założonej do-

kładności, rzeczywiście osiągniętą dokładność i dyskusję możliwych przyczyn rozbieżności między

nimi,

•

uwagi i wnioski,

•

skomentowane listingi napisanych na zajęciach M-plików.

Wymagana wiedza teoretyczna

•

jedno– i dwupunktowe wzory iteracyjne: metoda bisekcji ([1, str. 215–216], [2, str. 116–118]),

metoda siecznych ([1, str. 222–224], [2, str. 125–126]), regula falsi ([1, str. 224–225], [2, str.

121–125]), wzory Newtona-Raphsona ze szczególnym uwzględnieniem metody stycznych ([1, str.

217–221], [2, str. 126–131])

•

ogólny warunek zbieżności jednopunktowej metody iteracyjnej [1, str. 228–229],

•

pojęcie rzędu zbieżności metody; rząd zbieżności popularnych metod iteracyjnych ([1, str. 230–

231], [2, str. 147–148], [3, str. 298–299])

•

ogólne oszacowanie błędu jednopunktowych metod iteracyjnych [1, str. 233] i wynikające z niego

wnioski n/t osiągalnej dokładności wyznaczenia zer jedno– i wielokrotnych metodą Newtona

(stycznych) [1, str. 232–236],

•

stosowane kryteria zatrzymania obliczeń [1, str. 235–236],

•

iteracyjne wyznaczanie zer wielomianów: specyfika metody Newtona, metoda Meahly’ego [4, str.

208], metoda Laguerre’a ([1, str. 238–239], [3, str. 339–341]), uwarunkowanie zer wielomianów

([1, str. 240–242], [4, str. 216–218]), korzyści i niebezpieczeństwa wynikające ze stosowania

deflacji ([1, str. 239–240], [2, str. 149–150])

•

istota i właściwości metody Lehmera-Schura ([3, str. 328–331])

•

istota i właściwości metody Bairstowa ([4, str. 214–215],[3, str. 346–348]).

•

metoda Newtona w zadaniach rozwiązywania układów równań nieliniowych – podstawowe wła-

ściwości ([1, str.244–245], [2, str. 152–153])

Wymagana wiedza n/t programu Matlab

•

Pętle i instrukcje warunkowe

•

Podstawowe operatory działające na tablicach „poelementowo” ( .*, ./, .\, .^ )

•

Funkcje definiowane przez użytkownika (M-funkcje)

•

reprezentacja wielomianu w programie Matlab

•

Standardowe procedury znajdowania miejsc zerowych funkcji ( fzero ) oraz wyznaczania wszyst-

kich pierwiastków wielomianu roots )

Literatura

[1] Germund Dahlquist, ˚

Ake Bj¨

orck. Metody numeryczne, strony 215–248. PWN Warszawa, 1983.

[2] Zenon Fortuna, Bohdan Macukow, Janusz Wąsowski. Metody numeryczne, strony 115–160. WNT War-

szawa, 1995.

[3] Anthony Ralston. Wstęp do analizy numerycznej, strony 297–351. PWN Warszawa, 1983.
[4] Josef Stoer. Wstęp do metod numerycznych, wolumen 1, strony 180–223. PWN Warszawa, 1979.
[5] Jerzy Krupka, Roman Z. Morawski, Leszek J. Opalski. Metody numeryczne dla studentów elektroniki

i technik informacyjnych, strony 77–85. Oficyna Wydawnicza Politechniki Warszawskiej, Warszawa, 1997.

[6] David Kincaid, Ward Cheney. Analiza numeryczna, strony 63–120. WNT Warszawa, 2006.