I_R_W14_M28_C++ 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 funkcja (przedział poszukiwań miejsca zerowego) ma 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:
Słownik
metoda rozwiązywania problemów matematycznych za pomocą operacji na liczbach
bezwzględna różnica pomiędzy dokładną wartością a uzyskanym (np. w wyniku obliczeń lub pomiarów) jej przybliżeniem
funkcja wyrażana przez wielomian, czyli sumę co najmniej dwóch jednomianów
iloczyn litery oznaczającej zmienną oraz liczby (nazywanej stałą)
inaczej miejsce zerowe funkcji, czyli argument, dla którego wartość funkcji wynosi zero
miara szybkości, z jaką zmieniają się wartości funkcji; w ujęciu geometrycznym pochodną stanowi styczna do rozpatrywanej funkcji w ustalonym punkcie
linia prosta mająca jeden punkt wspólny z linią krzywą, np. wartością funkcji w punkcie, nieprzecinająca linii krzywej
zmierzanie do pewnej docelowej wartości granicznej wraz ze zwiększaniem się liczby iteracji