Metoda równego podziału

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 Darboux:

Bisection method.png

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ń: