Laboratorium 4b: Funkcje. Metoda połowienia — usprawnienia

Praktycznie wszyscy poprawnie zaprogramowali algorytm metody połowienia polegający na wyznaczaniu przybliżonego miejsca zerowego funkcji dzieląc pierwotny przedział na połowy.

Uwaga: Przedział można dzielić w dowolnym stosunku — czasami przyśpieszy to znalezienie miejsca zerowego, czasami może opóźnić. Wydaje się że podział na dwie równe połowy jest sensownym kompromisem.

Niestety zaprogramowany w tej formie algorytm jest zupełnie nieprzydatny z kilku powodów:

Znajduje miejsca zerowe funkcji sinus, które i tak są znane¹.
W tej formie nie może być wykorzystany (bez przeprogramowania) do znajdowania miejsc zerowych innych funkcji.
Za każdym razem trzeba pisać i kompilować nowy program — trudno w większej aplikacji użyć algorytmu do znajdowania miejsc zerowych kilku różnych funkcji.

Kolejnym Państwa zadaniem będzie (przynajmniej częściowe) usuniecie tych wad. Wykorzystamy w tym celu funkcje.

1. „Zamknięcie” algorytmu połowienia w funkcji

Musimy tę funkcję zaprojektować:

nadać jej jakąś nazwę; na przykład pol()
zdefiniować jej parametry; parametrami mogą być:
- początek przedziału (w algorytmie byłą to zmienna A),
- koniec przedziału (była to zmienna B),
- wydaje się, że parametrem powinna być również dokładność obliczeń ($\varepsilon$)².
Wszystkie parametry to liczby zmiennoprzecinkowe typu double.
przyjmujemy, że funkcja będzie zwracała współrzędną znalezionego miejsca zerowego. Można umówić się, że ta współrzędna to dokładnie środek przedziału $[a,b]$.

Zatem deklaracja funkcji („prototyp”) będzie następująca:

double pol(double a, double b, double epsilon);

Algorytm jak poprzednio:

graph LR start([Start]) --> ala["c=(a+b)/2."] ala --> przedzial{"sin(a)*sin(c)<0"} przedzial --> |TAK| Be[b = c] przedzial --> |NIE| Aa[a = c] Be --> koniec{"fabs(a-b)> epsilon"} Aa --> koniec koniec --> |TAK| ala koniec --> |NIE| return["return (a+b)/2."] return --> stop([STOP])

Umawiamy się, że na potrzeby wszystkich tworzonych funkcji nie będzie w ich kodzie używana funkcja printf() do wyprowadzania wyników obliczeń lub informowania o wystąpieniu błędów lub innych sytuacjach wyjątkowych.

W miarę możliwości należy w tym celu wykorzystać polecenie return.

2. Funkcja, której miejsca zerowego szukamy

Funkcja, której miejsca zerowego szukamy jest na stałe „wbudowana” w algorytm metody połowienia:

if( sin(a) * sin(c) ) < 0

Możemy algorytm uczynić bardziej uniwersalnym zastępując funkcję sin() ogólną nazwą funkcji f(x)

if( f(a) * f(c) ) < 0

i dostarczając funkcję f(x), na przykład taką:

double f( double x)
{
    return sin( x / 180. * M_PI )
}

Tym razem f() wylicza wartość funkcji sinus dla argumentu podanego w stopniach, a nie w radianach. M_PI to stała (zdefiniowana w pliku nagłówkowym math.h) równa wartości $\pi$ z maksymalną dla zmiennych typu double precyzją.

Zadania do wykonania

Wyodrębnić algorytm połowienia jako funkcję zdefiniowaną w pierwszej części instrukcji.
Zdefiniować wybraną przez siebie (inną niż sinus) funkcję i znaleźć jej miejsce zerowe.
Zrealizować zadanie opisane w rozdziale Uwaga.
Oceniając Państwa zadania, w przypadku gdy wystawiam ocenę pozytywną nie pojawia się przy ocenie żaden komentarz. Czasami, jednak, oprócz komentarza pojawia się pytanie. Oczekuję odpowiedzi na te pytania. Przygotowałem odpowiednie miejsce na e-portalu.
(Nieobowiązkowe) Spróbować zaprogramować funkcję pol() jako funkcję rekurencyjną.
Osoby, które wykonały już punkty: 1 i 5 skupiają się na zadaniach 2 i 3 (ewentualnie 4) i po zapoznaniu się z instrukcją Laboratorium 6 próbują zrealizować metodę Newtona-Raphsona znajdowania miejsc zerowych.

Rekurencja

Zasadniczą częścią algorytmu jest powtarzanie operacji połowienia tak długo, jak przedział $[a,b]$ jest dłuższy niż $\varepsilon$. Zorganizowane jest to za pomocą pętli do (lub while).

Popatrzmy na kod rekurencyjnej funkcji silnia:

int silnia(int n)
{
    if (n == 0) 
        return 1;
    else
        return n * silnia(n - 1);
}

Pierwsza instrukcja return (return 1;) powoduje zakończenie obliczeń z wynikiem 1; druga instrukcja return (return n * silnia(n - 1);) powoduje ponowne wywołanie funkcji silnia() — w efekcie zapętlenie³ kodu.

Bardzo podobnie będzie w przypadku metody połowienia: po zmianie wartości parametrów a lub b ponownie wywołujemy funkcję z nowymi ich wartościami.

Uwaga

Załóżmy, że szukamy miejsca zerowego funkcji

$$y = x^2 - 4$$

w przedziale $[0,4]$; w pierwszym kroku algorytmu c przyjmuje wartość 2 (jest to wartość miejsca zerowego funkcji).

Sprawdzić jak zachowa się algorytm połowienia w tym przypadku. Zaproponować modyfikację algorytmu.

Jak wiadomo funkcja sinus ma miejsca zerowe w punktach o współrzędnych $n\pi, n=\ldots,-2,-1,0,1,2,\ldots$ ↩︎
Również parametru $\delta$ opisanego w rozdziale „dla bystrzaków” ↩︎
Pętle można zrealizować na kilka sposobów: while, do, for, goto, rekurencja. ↩︎