Metoda połowienia przedziałów i przybliżanie pierwiastka

Ten materiał dotyczy algorytmów numerycznych, które podstawa programowa informatyki w zakresie rozszerzonym wymienia wprost: wyznaczania miejsc zerowych funkcji metodą połowienia oraz obliczania przybliżonej wartości pierwiastka kwadratowego. Uczysz się też odróżniać dwa źródła niedokładności obliczeń komputerowych — błąd przybliżenia i błąd zaokrąglenia — o których mówi ta sama podstawa.

Metoda połowienia przedziałów (bisekcja) zaczyna od przedziału $[a;b]$, na którego końcach funkcja ciągła ma różne znaki, czyli $f(a)\cdot f(b)<0$. W każdym kroku liczysz środek, sprawdzasz znak funkcji i zostawiasz tę połowę, na której znak się zmienia. Wykonujesz kolejne kroki ręcznie dla konkretnych funkcji, śledzisz program w Pythonie, który robi to samo w pętli, i obliczasz, ile kroków potrzeba do zadanej dokładności: po $n$ krokach przedział jest $2^n$ razy krótszy, więc dla dokładności 0,001 wystarczy 10 kroków. Poznajesz też ograniczenie metody: gdy funkcja ma na końcach przedziału ten sam znak, bisekcja nie wystartuje, nawet jeśli w środku są dwa miejsca zerowe.

Metoda Herona przybliża $\sqrt{a}$ wzorem $x_{k+1}=\frac{1}{2}(x_k+\frac{a}{x_k})$: nowe przybliżenie to średnia z poprzedniego i z ilorazu $a\mathrm{/}{x}_k$. Liczysz kolejne przybliżenia i widzisz, że liczba poprawnych cyfr mniej więcej podwaja się w każdym kroku — dlatego ta metoda jest dużo szybsza od połowienia.

Ostatni wątek to błędy: błąd przybliżenia wynika z przerwania obliczeń po skończonej liczbie kroków, a błąd zaokrąglenia — ze skończonej precyzji zapisu liczb zmiennoprzecinkowych w komputerze.

Materiał oferuje cztery formy pracy. Quiz zawiera kroki obliczeń, analizę programu i pytania o własności metod, z wyjaśnieniem każdego wyniku. Fiszki utrwalają warunek startu bisekcji, wzór Herona, kryteria zakończenia i rodzaje błędów. Egzamin ustny w formie rozmowy z egzaminatorem sprawdza, czy umiesz objaśnić metody i ocenić ich dokładność. Praca pisemna do wydruku zawiera zadania otwarte: obliczenia krok po kroku i zapis algorytmów w pseudokodzie lub w wybranym języku programowania (C++, Python lub Java).

Wszystkie zadania są oryginalnymi ćwiczeniami do samodzielnej nauki; wyniki programów i obliczeń zostały sprawdzone.

• Sprawdzasz warunek startu metody połowienia i wykonujesz jej kolejne kroki.
• Obliczasz liczbę kroków bisekcji potrzebną do zadanej dokładności.
• Obliczasz kolejne przybliżenia pierwiastka kwadratowego metodą Herona.
• Śledzisz program realizujący bisekcję i przewidujesz jego wynik.
• Odróżniasz błąd przybliżenia od błędu zaokrąglenia.

Materiał ćwiczeniowy przygotowany przez Zestly.