Zadanie 2 (17.11.2012)

Metoda bisekcji

A) Rozwiąż równanie x³ = 100 x log₂ x, wykorzystując metodę bisekcji (dla x należącego do zbioru liczb rzeczywistych).
Opisz trzy kolejne kroki odpowiedniego algorytmu, podając przedziały, w których algorytm szuka rozwiązania oraz trzy kolejne rozwiązania przybliżone (przedział początkowy wybierz samodzielnie). Podaj ostateczne rozwiązanie, wyznaczone z dokładnością trzech miejsc po przecinku. Określ liczbę iteracji, jaka była potrzebna do uzyskania tego rozwiązania.

B) Załóżmy, że dane są dwa algorytmy: A₁ o złożoności czasowej n³, oraz A₂ o złożoności czasowej 100 n log₂ n. Na podstawie rozwiązania z punktu A) sformułuj wnioski dotyczące porównania szybkości tych dwóch algorytmów zależnie od n.

Uwaga: Jeśli punkt A) zostanie rozwiązany za pomocą samodzielnie napisanego programu komputerowego, należy dołączyć do rozwiązania jego zapis (z komentarzami objaśniającymi główne kroki) lub precyzyjny opis zastosowanego algorytmu.

Ponieważ napłynęło kilka rozwiązań częściowo poprawnych (które można jeszcze poprawić), chcielibyśmy wyjaśnić dokładniej, co powinno zawierać poprawne rozwiązanie. Są to następujące elementy:

1) określenie, ile rozwiązań ma podane równanie;
2) znalezienie (metodą bisekcji) obydwu rozwiązań przybliżonych lub tego tylko, które ma sens ze względu na punkt B zadania (kolejne kroki metody należy "rozpisać");
3) określenie, ile dokładnie iteracji (krokow bisekcji) potrzeba było (przy wybranym samodzielnie przedziale początkowym), aby uzyskać rozwiązanie przybliżające rozwiązanie dokładne z dokładnością trzech miejsc po przecinku (chodzi o dokładność przybliżenia);
4) precyzyjne sformułowanie wniosków co do szybkości algorytmów A1 i A2 dla różnych n (tzn. dla jakich n, który algorytm jest szybszy od którego).

Autorzy niepełnych rozwiazań mogą je jeszcze uzupełnić.