Metoda równego podziału

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Metoda bisekcji)
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 {\textstyle f(x)} 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 {\textstyle f(x)=0.}

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

  1. funkcja {\textstyle f(x)} jest ciągła w przedziale domkniętym {\textstyle [a;b]}
  2. funkcja przyjmuje różne znaki na końcach przedziału: {\textstyle f(a)f(b)<0}

Przebieg algorytmu[edytuj]

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

Przykład[edytuj]

Wyznaczyć pierwiastek równania {\textstyle f(x)=x^3-x+1} w przedziale {\textstyle [-2;2].}

Rozwiązanie:

  • Obliczamy wartości funkcji na końcach przedziału: {\textstyle f(-2)=-5,} a {\textstyle f(2)=7.}
  • Dzielimy przedział na połowy: {\textstyle x_1 = \frac{-2+2}{2} = 0} i obliczamy wartość {\textstyle f(x_1)=1.}
  • Ponieważ wartość funkcji dla {\textstyle x_1} jest różna od zera, algorytm jest kontynuowany. Mamy teraz dwa przedziały {\textstyle [-2,0]} i {\textstyle [0,2].} Wybieramy ten, na którego końcach znaki funkcji są różne – {\textstyle f(-2)f(0) = -5 \cdot 1 = -5 < 0} lub {\textstyle f(0)f(2) = 1 \cdot 7 = 7 > 0.} Zatem pierwiastek leży w przedziale {\textstyle [-2,0]}
  • Dzielimy przedział na połowy: {\textstyle x_2 = \frac{-2+0}{2} = -1} i obliczamy wartość funkcji {\textstyle f(-1)=1} – liczba {\textstyle x_2} 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 {\textstyle \epsilon > 0} można znaleźć takie {\textstyle x_0,} że {\textstyle \mid x - x_0 \mid < \epsilon} gdzie {\textstyle x} 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ń: