Metoda równego podziału

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
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 Darboux:

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 algorytmu[edytuj | edytuj kod]

  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ład[edytuj | edytuj kod]

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.

Pseudokod[edytuj | edytuj kod]

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 | edytuj kod]

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