Metoda równego podziału

Metoda równego podziału, metoda połowienia, metoda bisekcji^[1], 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 ${\displaystyle 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 ${\displaystyle f(x)=0.}$

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

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

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

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

Rozwiązanie:

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

Prezentacja metody równego podziału w języku Python 3. Początkowe wartości ${\displaystyle a}$ i ${\displaystyle b}$ muszą być wybrane w taki sposób, aby ${\displaystyle f(a)}$ i ${\displaystyle 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

• 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