I_R_W14_M28_Java Miejsca zerowe funkcji
Metoda stycznych – założenia, cechy, działanie
Podczas rozwiązywania niektórych problemów matematycznych możemy stosować algorytmy numeryczne, czyli wykorzystujące operacje na liczbach. Jednym z nich jest metoda stycznych – algorytm wyszukiwania miejsc zerowych funkcji z pewną dokładnością.
W algorytmie przyjmujemy następujące założenia:
W przedziale funkcji (przedział poszukiwań miejsca zerowego) znajduje się jeden pierwiastek. Dodatkowo funkcja w tym przedziale jest określona i ciągła.
Pochodna funkcji w ustalonym przedziale musi być różna od zera.
Funkcja na końcach przedziału przyjmuje różne znaki.
Pierwsza i druga pochodna w przedziale mają takie same znaki.
Specyfikacja problemu:
Dane:
Ex– graniczna wartość błędu bezwzględnego wyznaczanego miejsca zerowego, po której osiągnięciu uznajemy uzyskane rozwiązanie za końcowe; liczba rzeczywista dodatniaEy– dokładność porównywana z otrzymywanymi przybliżeniami miejsca zerowego – jej osiągnięcie (spełnienie warunku, że wyznaczony punkt jest od niej mniejszy lub jej równy) oznacza uznanie uzyskanego rozwiązania za końcowe; liczba rzeczywista dodatniax1– wartość, od której rozpoczniemy poszukiwanie miejsca zerowego w zadanym przedziale; liczba rzeczywista z przedziału
Wynik:
x2– liczba rzeczywista z przedziału ; przybliżona wartość miejsca zerowego funkcji
Działanie metody
Rozpoczynamy od wyboru punktu startowego xIndeks dolny 11 (często oznaczanego również jako xIndeks dolny 00), z którego wyznaczamy styczną do wykresu funkcji f(x). Styczna do wykresu funkcji f(x) w punkcie x to pochodna tej funkcji – oznaczamy ją jako df(x).
Następnie wyznaczamy kolejny punkt: xIndeks dolny 22, będący miejscem przecięcia stycznej z osią OX.
W kolejnym kroku sprawdzamy, czy wartość funkcji w punkcie xIndeks dolny 22 spełnia przynajmniej jeden z podanych warunków:
wartość funkcji w punkcie
xIndeks dolny 22osiągnie założoną dokładnośćEy,różnica między kolejnymi przybliżeniami będzie dostatecznie mała – osiągnie założoną wartość błędu bezwzględnego
Ex.
Jeżeli tak, to xIndeks dolny 22 jest rozwiązaniem, czyli przybliżonym miejscem zerowym funkcji. W przeciwnym razie xIndeks dolny 22 staje się punktem startowym xIndeks dolny 11 i przedstawione czynności są powtarzane, aż do spełnienia wyróżnionych warunków.
Kolejne przybliżenia (pierwiastki) wyznaczane są na podstawie następującego wzoru:
Należy pamiętać, że istotną cechą opisanej metody jest brak gwarancji zwrócenia rozwiązania problemu, np. gdy punkt startowy znajduje się zbyt daleko od szukanego pierwiastka.
W takiej sytuacji pomocne może być ustalenie dodatkowego warunku zakończenia wykonywania algorytmu, np. poprzez ograniczenie maksymalnej liczby dozwolonych iteracji.
Metodę stycznych przetestujemy na następującej funkcji:
Operować będziemy na przedziale , a za punkt startowy przyjmiemy . Miejsca zerowego będziemy poszukiwać do momentu osiągnięcia dokładności (na potrzeby przykładu ograniczymy się jedynie do tego warunku).
Wyznaczamy styczną do funkcji w podanym punkcie oraz wyliczamy .
Analizując graficzną interpretację uzyskanych rezultatów, możemy zauważyć, że otrzymany punkt () znajduje się stosunkowo blisko poszukiwanego rozwiązania – wartość funkcji . Będziemy jednak kontynuować wykonywanie kolejnych kroków algorytmu (). Za punkt przyjmujemy uzyskany punkt i powtarzamy cały proces.
Po przeprowadzonych operacjach wartość funkcji w obliczonym punkcie wynosi około 0,04. Oznacza to, że osiągnięta została założona dokładność i odnalezione rozwiązanie przyjmujemy za końcowe.
W podanym przykładzie stosunkowo szybko uzyskaliśmy zadowalający rezultat (spełniający ustalone założenia), ponieważ przyjęty punkt startowy położony był blisko rzeczywistego miejsca zerowego analizowanej funkcji. W wielu przypadkach może być jednak konieczne wykonanie znacznie większej liczby iteracji algorytmu przed wyznaczeniem satysfakcjonującego rozwiązania.
Zbieżność
Wraz z liczbą iteracji błąd maleje kwadratowo, czego widocznym efektem jest zbliżanie się do szukanego miejsca zerowego – algorytm wyznaczania przybliżonej wartości miejsca zerowego funkcji charakteryzuje się więc zbieżnością kwadratową. Jest to bardzo szybka zbieżność, jednak nie zawsze musi ona zachodzić – w przypadku, gdy ustalony punkt startowy jest daleko od poszukiwanego rozwiązania, opisywana metoda może charakteryzować się rozbieżnością. Oznacza to, że z każdą iteracją algorytmu będziemy oddalać się od miejsca zerowego. Ponadto, obliczenie pochodnych z niektórych funkcji może być problematyczne. W związku z tym metodę stycznych najczęściej stosuje się przy funkcjach wielomianowych.
Pseudokod
Wprowadzamy wartość błędu bezwzględnego (
Ex) oraz dokładność (Ey), których osiągnięcie zakończy dalsze poszukiwania miejsca zerowego (a zarazem uzna ostatni uzyskany wynik za końcowy i satysfakcjonujący).
Ustalamy, od jakiej wartości rozpoczniemy przeszukiwanie (
x1) – może to być dowolna wartość zawierająca się w przedziale[a, b].
Definiujemy funkcję
metodaStycznych, która zwróci przybliżoną wartość miejsca zerowego funkcji.
Do kolejnej wartości
x(x1) przypisujemy poprzednią (x2).
Obliczamy następne możliwe miejsce zerowe – w tym celu zapisujemy kolejne przybliżenie z poprzedniej iteracji pętli (
x1)do zmiennejx2przechowującej poprzednią sprawdzaną wartość.
Ustalamy wartość argumentu funkcji dla punktu przecięcia stycznej do funkcji i osi OX.
Sprawdzamy warunek, czy uzyskane przybliżenie osiągnęło założoną dokładność (
Ey) lub czy bezwzględna różnica pomiędzy punktamix2ix1jest mniejsza bądź równa błędowiEx. Jeżeli choć jeden z tych warunków zostanie spełniony, przerywamy działanie pętli.
Na koniec działania funkcji
metodaStycznych()zwracamy przybliżoną wartość znalezionego miejsca zerowego
Definiujemy funkcję zwracającą wartość bezwzględną z wybranej wartości.
Wartość bezwzględna zmienia ujemne wartości w dodatnie, natomiast dla nieujemnych wartość pozostaje niezmienna.
Na końcu definiujemy funkcje
funkcja(x)ipochodna(x), które zwrócą wartość funkcji oraz pochodnej w wybranym punkciex. Przyjmiemy operowanie na następującej, przykładowej funkcji: