Metoda równego podziału

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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 Bolzano-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 algorytmu[edytuj]

  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]

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]

Prezentacja metody równego podziału w języku pakietu MATLAB. 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 f(x1) == 0 % jeżeli znaleźliśmy miejsce zerowe
        break;
    else if f(x1) * f(a) < 0
        b = x1; % nadpisywanie prawego krańca przedziału
    else
        a = x1; % nadpisywanie lewego krańca przedziału
    end
end

display((a + b) / 2); % zwracanie znalezionego miejsca zerowego

Zobacz też[edytuj]

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