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:

Jeżeli funkcja ciągła $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 $f(x)=0.$

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

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

Przebieg algorytmu

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

Przykład

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

Rozwiązanie:

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

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ż

• metoda numeryczna

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

• metoda iteracji
• metoda Newtona (zwana również metodą Newtona-Raphsona lub metodą stycznych)
• metoda siecznych
• odwrotna interpolacja kwadratowa
• regula falsi