Metoda równego podziału

Bisection method.png

Metoda równego podziału (metoda połowienia, metoda bisekcji, metoda połowienia przedziału) – jedna z metod rozwiązywania równań nieliniowych. Opiera się ona na twierdzeniu Bolzana-Cauchy’ego:

Jeżeli funkcja ciągła ma na końcach przedziału domkniętego wartości różnych znaków, to wewnątrz tego przedziału, istnieje co najmniej jeden pierwiastek równania

Aby można było zastosować metodę równego podziału, muszą być spełnione założenia:

  1. funkcja jest ciągła w przedziale domkniętym
  2. funkcja przyjmuje różne znaki na końcach przedziału:

Przebieg algorytmuEdytuj

  1. Sprawdzenie, czy pierwiastkiem równania jest punkt   czyli czy  
    Jeżeli tak jest algorytm kończy działanie, a punkt   jest szukanym miejscem zerowym.
  2. W przeciwnym razie, dopóki nie osiągniemy żądanej dokładności, czyli dopóki  
    1. Zgodnie ze wzorem z punktu pierwszego ponownie wyznaczane jest   dzieląc przedział   na dwa mniejsze przedziały:   i  
    2. Wybierany jest przedział o znaku przeciwnym niż   i odpowiednio górny albo dolny kraniec przedziału (  albo  ) przyjmuje wartość   tj.
      1. Jeżeli   to  
      2. Jeżeli   to  
  3. Po osiągnięciu żądanej dokładności algorytm kończy działanie, a szukany pierwiastek równania wynosi  

PrzykładEdytuj

Wyznaczyć pierwiastek równania   w przedziale  

Rozwiązanie:

  • Obliczamy wartości funkcji na końcach przedziału:   a  
  • Dzielimy przedział na połowy:   i obliczamy wartość  
  • Ponieważ wartość funkcji dla   jest różna od zera, algorytm jest kontynuowany. Mamy teraz dwa przedziały   i   Wybieramy ten, na którego końcach znaki funkcji są różne –   lub   Zatem pierwiastek leży w przedziale  
  • Dzielimy przedział na połowy:   i obliczamy wartość funkcji   – liczba   nie jest zatem pierwiastkiem.
  • Znowu dzielimy przedział na dwa podprzedziały, wybieramy jeden z nich itd.

Uwaga: rozwiązanie można wyznaczyć z dowolną dokładnością (czyli dla każdego   można znaleźć takie   że   gdzie   jest pierwiastkiem równania), w rzadkich przypadkach można uzyskać dokładną wartość pierwiastka (gdy algorytm zostanie zakończony w 1. punkcie). Algorytm metody równego podziału jest blisko spokrewniony z wyszukiwaniem binarnym.

PseudokodEdytuj

Prezentacja metody równego podziału w języku Python 3. Początkowe wartości a i b muszą być wybrane w taki sposób, aby f(a) i f(b) były przeciwnego znaku oraz „otaczały” poszukiwane miejsce zerowe. Zmienna epsilon określa dokładność wyniku, np. 0,0001.

while abs(a - b) > epsilon: # dopóki nie uzyskamy zadanej dokładności
    x1 = (a + b) / 2

    if abs(f(x1)) <= epsilon: # jeżeli znaleźliśmy miejsce zerowe mniejsze bądź równe przybliżeniu zera
        break
    elif f(x1) * f(a) < 0:
        b = x1 # nadpisywanie prawego krańca przedziału
    else:
        a = x1 # nadpisywanie lewego krańca przedziału

print((a + b) / 2) # zwracanie znalezionego miejsca zerowego

Zobacz teżEdytuj

Inne numeryczne metody wyznaczania pierwiastków równań: