Piotr Kowerzanow

Bartosz Kowalczyk

FTiMS IV semestr

Sprawozdanie z metody hybrydowej

Spis treści:

1. Ogólne omówienie metody hybrydowej pod kątem matematycznym

1.1 Ogólnie

1.2 Metoda Hybrydowa

1.2.1 Metoda bisekcji

1.2.2 Metoda Newtona-Robsona

1.2.3 Metoda hybrydowa

2. Omówienie algorytmu

1.Ogólne omówienie metody hybrydowej pod kątem matematycznym.

1.1 Ogólnie

Metoda hybrydowa jest jedną z wielu propozycji przybliżonego obliczania pierwiastków rzeczywistych równania

f(x)=0; (1)

gdy funkcja jest ciągła na pewnym przedziale (skończonym lub nieskończonym). Warto pamiętać o tym, że metody te zwykle podają tylko coraz to lepsze przybliżenie pierwiastków. Ponadto większość metod można stosować tylko wtedy, gdy znamy przedział, w którym znajduje się pojedynczy pierwiastek rozwiązywanego równania (mowa o przedziale izolacji pierwiastka). Metody te jak już stwierdziłem powyżej posiadają pewien błąd. Źródłami tych błędów są:

-błąd przybliżenia wynikający że stosowania danej metody,

-wpływ błędów współczynników równania f(x)=0,

-dokładność obliczeń przybliżonych.

Wyróżniamy takie metody jak: metoda bisekcji, metoda falsi, metoda Newtona-Raphsona oraz główny bohater tego sprawozdania - metoda hybrydowa. Pamiętajmy też o tym że istnieją odrębne metody dla szukania pierwiastka dla wielomianów. Istnieją też metody wyznaczania zer zespolonych dla wielomianów. Nie będę tego omawiał w tym dokumencie. Jeśli ktoś jest zainteresowany to polecam książkę „Analiza numeryczna” -Kincaid'a czy „metody numeryczne” autorstwa Fortuny, Macukowa i Wąsowskiego.

Metoda Hybrydowa jest metodą zbudowaną z metody Newtona-Rapsona oraz metody bisekcji w celu zminimalizowania wad obu tych metod.

1.2 Metoda Hybrydowa

1.2.1 Metoda bisekcji

Na początku chciałem przypomnieć ważne twierdzenie które jest kluczowe dla metody bisekcji oraz wszystkich metod numerycznych zajmujących się szukaniem pierwiastków równania. Mowa oczywiście o twierdzeniu Darbaux o miejscach zerowych funkcji:

Jeżeli funkcja f jest ciągła na przedziale [a.b] oraz spełnia warunek f(a)*f(b)<0, to istnieje punkt c є (a,b) taki, że f(c)=0.

Uwaga: Jeżeli funkcja jest dodatkowo malejąca albo rosnąca, to pkt c jest określony jednoznacznie.

Metoda bisekcji działa następująco: mamy funkcję ciągłą na przedziale [a,b]. Sprawdzamy czy f(a)*f(b)<0. Jeśli tak to szukamy pkt c:

c=(a+b)/2

Następnie sprawdzamy czy f(a)*f(c)<0, jeśli nie to sprawdzamy f(c)*f(b)<0. Jeśli jest prawdziwe wówczas szukamy kolejnego pkt takiego d, że d=(c+b)/2. Potem ponownie sprawdzamy. Pętlę tę wykonujemy tak długo, aż otrzymamy żądaną dokładność wyniku. Warto pamiętać że powyższe twierdzenie będące podstawą metody bisekcji umożliwia nam wyznaczać miejsca zerowe z dowolną dokładnością. Zaletami tej metody są:

-duża prostota,

-pewność że za każdą iteracją szukany pierwiastek leży pomiędzy dwiema wartościami zmiennych x, w których funkcja zmienia znak. A więc nie ma niebezpieczeństwa wypadnięcia poza przedział.

-metoda ta jest bezsensu dla pierwiastków r-krotnych gdzie r jest parzysta. Dla nieparzystych metoda ta zachowuje sens,

-duża odporność na błędy.

Wadą tej metody jest jego stosunkowo mała efektywność czyli powolne zbliżanie się do poszukiwanego pierwiastka.

1.2.2 Metoda Newtona-Robsona

Wyliczenie pierwiastka w metodzie Newtona dla funkcji w przedziale [a,b] i posiadającą pierwszą i drugą pochodną ze stałym znakiem. W metodzie tej z tego końca przedziały [a,b], w który funkcja f(x) ma ten sam znak co f”(x) prowadzimy styczną do wykresu funkcji y=f(x) i punkt x₁ w którym ta styczna przecina oś OX przyjmujemy za pierwsze przybliżenie szukanego pierwiastka. Przeprowadzamy tę operację tak długo dla nowych przedziałów (_x1 , f(x₁ )) tak długo aż znajdziemy pożądaną dokładność lub najbliższe przybliżenie do tejże dokładności. Poszczególne przybliżenia winny być monotonicznie zbieżne do szukanego pierwiastka.

Wzór dla metody jest taki:

x_1+i=x_i-(f(x_i)/f'(x_i))

Metoda ta umożliwia znalezienie wielokrotnych pierwiastków w liczbie parzystej i nieparzystej, jeżeli istnieje tylko odpowiednie sąsiedztwo szukanego pierwiastka o stałym znaku pierwszej i drugiej pochodnej, lecz obniża się tutaj rząd metody. Jednak istnieje odmiana tej metody taka, żeby zachować rząd, a więc zwiększająca zbieżność. To znaczy wzór wygląda następująca:

x_1+i=x_i-(u(x)/u'(x)), gdzie u(x)= f(x_i)/f'(x_i) , u'(x)=1-((f(x)*f”(x))/(f'²(x)). I f'(x)≠0.

Zaletą tej metody jest:

-duża szybkość w stosunku do metody bisekcji,

-możliwość znalezienia wielokrotnych pierwiastków (parzysta i nieparzysta liczba pierwiastków), do tego bez obniżania rzędu funkcji,

Wady tej metody to:

-możliwość, że metoda zacznie generować pierwiastki coraz dalsze od szukanego pierwiastka, więc nie możemy jej całkowicie ufać.

1.2.3 Metoda hybrydowa

Metoda hybrydowa korzysta z metody Newtona-Robsona oraz z metody bisekcji: mianowicie: najpierw szukamy metodą N-R. Za każdym użyciem tej metody sprawdzamy czy dokładność rośnie. Jeśli wynik zacznie się oddalać od pierwiastka. To przerywamy szukanie metodą N-R i zaczynamy szukać wyniku metodą bisekcji która jest wolniejsza ale nie ma ryzyka oddalania się od wyniku.

Tak więc metoda hybrydowa korzysta z metody N-R jako metody głównej, a w razie awarii w metodzie N-R, metoda bisekcji służy do korygowania błędów metody N-R.

2.Omówienie algorytmu

2.1 Ogólne omówienie zastosowania algorytmu

Przeznaczeniem tego algorytmu jest szybkie wyszukiwanie miejsc zerowych funkcji na zadanym przedziale. Używa on metody Newtona-Robsona, a w razie problemów związanych z ułomnościami tejże metody, zaczyna używać metody bisekcji. Dzięki temu możemy zminimalizować wady obu metod a zarazem wykorzystać ich zalety. Tak więc korzystamy z szybkości metody N-R oraz z niezawodności metody bisekcji przy zmniejszeniu czasu działania bisekcji oraz zmniejszeniu ryzyka wywalenia się na metodzie N-R związane z miejscowym brakiem zbieżności metody dla pewnych danych.

2.2 Omówienie poszczególnych etapów działania programu

Program wpierw pobiera przedziały od użytkownika. Program korzysta tylko z jednej funkcji z góry wybranej przez wykonawców programu. Następnie użytkownik proszony jest o podanie pkt startowego dla rozpoczęcia działania metody N-R.

W kolejnym etapie program sprawdza poprawność przedziałów i pkt startowego. Następnie program sprawdza czy pkt startowy nie jest aby pierwiastkiem. Potem program zaczyna przybliżać pierwiastek metodą N-R. Po każdym przybliżeniu sprawdzamy czy nie mamy do czynienia z oddalaniem się od pierwiastka. Jeśli zaczynamy się oddalać od pierwiastka to natychmiast przerywamy tę operację i przechodzimy do metody bisekcji. Zarówno metoda bisekcji jak i metoda N-R wykonywana jest 100000razy (sto tysięcy razy) lub do znalezienia takiego pkt x że f(x)=0.

2.3 Kompilacja programu

Program napisany został w C++ tak więc wymaga kompilatora GCC. Kompilujemy poleceniem g++ nazwa -lm.

---