Wyszukiwanie Trójkowe

O algorytmie

Wyszukiwanie Trójkowe to metoda, która znajduje maksimum (lub minimum) funkcji unimodalnej na pewnym przedziale [a, b]. Algorytm ten jest przykładem algorytmu "dziel i zwyciężaj". Jego zasada działania opiera się na pewnych prawdach matematycznych.

Wyszukiwanie maksimum

Szukając maksimum funkcji na przedziale [a, b] wiadomo, że istnieje taki x, że f(a) ≤ f(x) ≤ f(b). Przydatny jest też fakt, że maksimum na pewno nie leży w pierwsze trzeciej części podanego przedziału, ani w ostatniej trzeciej części. Weźmy dowolne dwa punkty p₁ oraz p₂, które będą leżały na przedziale [a, b] oraz p₁ < p₂. Istnieją wtedy dokładnie trzy możliwości:

• f(p1) < f(p2), wtedy pewne jest, że maksimum nie wystąpi w przedziale [a, p1], więc ograniczamy przedział do [p1, b]
• f(p1) > f(p2), wtedy analogicznie do poprzedniej sytuacji maksimum nie wystąpi w przedziale [p2, b], więc ograniczamy przedział do [a, p2]
• f(p1) = f(p2), wtedy ograniczamy przedział do [p1, p2]

Punkty p₁ oraz p₂ mogą być dowolne, ale optymalnie jest wybrać je tak, żeby równały się p₁ = a + (b - a)/3 oraz p₂ = b - (b - a)/3. Jest to związane z faktem, że przedział [a, b] dzielimy na trzy części, a wybrane punkty wskazują na punkty podziału przedziału.

Przykład

Wykres funkcji f(x) = -2x² - x + 2

Weźmy przykładowo funkcję f(x) = -2x² - x + 2. Będziemy szukać jej miejsca zerowego na przedziale [-3, 3]. Jak widać na zamieszczonym po prawej stronie obrazku maksimum powinno znajdować się w punkcie x_max = 0.25. Poniżej zostały przedstawione kolejne iteracje wyliczania wyniku. Przyjmujemy, że wykonujemy, aż przedział będzie mniejszy niż 0.1. Wartości zostały przedstawione z dokładnością do czterech miejsc po przecinku.

W celu popełnienia jak najmniejszego błędu przyjmujemy, że punkt x leży pośrodku przedziału [a, b], więc x = -0.252113. Dokładny punkt to x = -0.25. Punkt ten można uzyskać zmniejszając precyzję poszukiwań na np. 0.0001. Wtedy algorytm zwraca x = -0.25001. Tym razem jednak zostało wykonane ponad 2 razy więcej iteracji.

Implementacja

Podczas implementacji tego algorytmu należy pamiętać, że znalezione wartości w programie będą miały postać przybliżoną, więc warto dodać dodatkowy argument precyzja, który określi dokładność z jaką mają być prowadzone obliczenia. Jednym z pomysłów jest precyzja określająca minimalną długość przedziału. Po osiągnięciu ustalonej długości przedziału podajemy wartość pośrodku przedziału, aby popełnić jak najmniejszy błąd.

Założenia

Podczas implementowania zadania przyda się wczytać funkcję od użytkownika. Skorzystam tutaj z własnej biblioteki wielomian.h, która umożliwia wczytywanie wielomianu, jego wypisanie czy obliczenie wartości w konkretnym punkcie. Szerzej o bibliotece można znaleźć w artykule o Schemacie Hornera.

Wyszukiwanie maksimum

Na początek zastanówmy się nad przypadkiem, gdy chcemy wyszukać maksimum funkcji. Funkcja szukajMaksimum() przyjmuje cztery argumenty: wielomian w, który odpowiada funkcji, lewy i prawy jako przedział [a, b] oraz precyzja - do jakiej rozpiętości ma zostać zawężony maksymalnie przedział.

1. double szukajMaksimum(wielomian* w, double lewy, double prawy, double precyzja = 0.0001) {
2.   while (true) {
3.     if (abs(prawy - lewy) < precyzja)
4.       return (lewy + prawy) / 2;
5.     double znacznikLewy = lewy + (prawy - lewy) / 3;
6.     double znacznikPrawy = prawy - (prawy - lewy) / 3;
7.     if (wartosc_wielomianu(w, znacznikLewy) <
8.       wartosc_wielomianu(w, znacznikPrawy)) {
9.       lewy = znacznikLewy;
10.     } else {
11.       prawy = znacznikPrawy;
12.     }
13.   }
14. }

Wyszukiwanie maksimum

W analogiczny sposób implementuje się wyszukiwanie minimum z tą różnicą, że należy zamienić zawężanie przedziałów w instrukcji warunkowej. Wystarczy zmienić znak mniejszości na większości.

Testowanie funkcji

W celu sprawdzenia napisanej funkcji można skorzystać z poniższego fragmentu kodu:

1. int main() {
2.   cout << "Podaj wzor funkcji (tylko wielomian):\n";
3.   wielomian* w = wczytajWieloman();
4.   cout << "f(x) = ";
5.   wypiszWieloman(w);
6.   double a, b;
7.   cout << "Podaj przedzial [a, b]\na = ";
8.   cin >> a;
9.   cout << "b = ";
10.   cin >> b;
11.   cout << "Szukany x to " << szukajMaksimum(w, a, b) << endl;
12.   system("pause");
13.   return 0;
14. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz rekurencyjną wersję kodu, która będzie wyszukiwać minimum funkcji modalnej używają Wyszukiwania Trójkowego. Przetestuj działanie napisanej funkcji.

Przykładowo dla funkcji f(x) = 7x² - 4x - 3, przedziału [-3, 3] i precyzji Δ = 0.0001 program powinien znaleźć x_min = 0.285725.

• Kod źródłowy Zadanie 1