Bisekcja, schemat Hornera i przybliżony pierwiastek kwadratowy

Metoda bisekcji znajduje przybliżone miejsce zerowe funkcji ciągłej f(x) na przedziale [a, b], jeśli f(a) i f(b) mają przeciwne znaki (czyli funkcja na pewno przecina oś OX gdzieś w tym przedziale). W każdym kroku dzielimy przedział na pół i sprawdzamy, w której połowie znak się zmienia.

def bisekcja(f, a, b, epsilon=1e-6): while (b - a) > epsilon: srodek = (a + b) / 2 if f(a) * f(srodek) < 0: b = srodek else: a = srodek return (a + b) / 2 # przykład: miejsce zerowe f(x) = x² - 2 (czyli pierwiastek z 2) wynik = bisekcja(lambda x: x**2 - 2, 0, 2)

Złożoność

Każdy krok zmniejsza przedział o połowę, więc liczba kroków potrzebnych do osiągnięcia dokładności epsilon wynosi w przybliżeniu log₂((b-a)/epsilon) — stąd nazwa "połowienie" i związek z notacją O(log n).

2. Schemat Hornera

Naiwne obliczenie wartości wielomianu W(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ... + a₀ wymaga O(n²) mnożeń (bo trzeba osobno liczyć każdą potęgę x). Schemat Hornera zapisuje wielomian w postaci zagnieżdżonej: W(x) = ((...(aₙx + aₙ₋₁)x + aₙ₋₂)x + ... )x + a₀, co pozwala policzyć wynik w O(n) mnożeń.

def horner(wspolczynniki, x): wynik = 0 for a in wspolczynniki: # od najwyższej potęgi do stałej wynik = wynik * x + a return wynik # W(x) = 2x³ - 6x² + 2x - 1, dla x = 3 wynik = horner([2, -6, 2, -1], 3)

3. Przybliżona wartość pierwiastka kwadratowego

Bez używania funkcji bibliotecznej math.sqrt() można wyznaczyć pierwiastek z liczby a na dwa sposoby: metodą bisekcji (szukamy miejsca zerowego f(x) = x² - a) albo szybciej zbieżną metodą Newtona.

def pierwiastek_newton(a, epsilon=1e-9): x = a # przybliżenie początkowe while abs(x * x - a) > epsilon: x = (x + a / x) / 2 # wzór Newtona return x

4. Ćwiczenia praktyczne

Ćwiczenie 1 — znajdź pierwiastek równania

Używając metody bisekcji, znajdź przybliżone rozwiązanie równania x³ - x - 2 = 0 na przedziale [1, 2] z dokładnością 10⁻⁶.

wynik = bisekcja(lambda x: x**3 - x - 2, 1, 2)
print(wynik) # ~1.521

Ćwiczenie 2 — porównaj liczbę operacji

Zmodyfikuj funkcję obliczającą wielomian naiwnie (używając x ** i w pętli) i porównaj liczbę wykonanych mnożeń z wersją Hornera dla wielomianu stopnia 10.

Sprawdź wiedzę

1. Warunkiem koniecznym do zastosowania metody bisekcji jest:

f(a) i f(b) mają ten sam znak f(a) i f(b) mają przeciwne znaki f jest wielomianem

2. Jaką złożoność obliczeniową ma obliczenie wartości wielomianu schematem Hornera?

O(n²) O(n) O(log n)

3. Metoda Newtona do liczenia pierwiastka kwadratowego opiera się na wzorze:

x = (x + a/x) / 2 x = x² - a x = a / 2

1. Metoda bisekcji (połowienia)