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 Bolzano-Cauchy'ego:

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. Sprawdzić, czy pierwiastkiem równania jest punkt $x_1=\frac{a+b}{2}$, czyli czy $f(x_1)=0$.
2. Jeżeli tak jest, algorytm kończy się, a punkt jest miejscem zerowym. W przeciwnym razie $x_1$ dzieli przedział $[a,b]$ na dwa mniejsze przedziały $[a, x_1]$ i $[x_1, b]$.
3. Wybierany jest ten przedział, dla którego spełnione jest drugie założenie, tzn. albo $f(x_1)f(a) < 0$ albo $f(x_1)f(b) < 0$. Cały proces powtarzany jest dla wybranego przedziału.

Działanie algorytmu kończy się w punkcie 2 albo po osiągnięciu żądanej dokładności przybliżenia pierwiastka.

Przykład

Wyznaczyć pierwiastek równania $x^3-x+1=0$ 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 $\epsilon > 0$ można znaleźć takie $x_0$, że $\mid x - x_0 \mid < \epsilon$ gdzie $x$ jest pierwiastkiem równania), w rzadkich przypadkach można uzyskać dokładną wartość pierwiastka (gdy algorytm zostanie zakończony w punkcie 2). Algorytm metody równego podziału jest blisko spokrewniony z wyszukiwaniem binarnym.

Pseudokod

Prezentacja bisekcji w języku Visual Basic. Zmienne xL i xR odpowiadają punktom a i b powyżej. Początkowe wartości xL i xR muszą być wybrane w taki sposób, aby f(xL) i f(xR) były przeciwnego znaku, oraz otaczały poszukiwane miejsce zerowe. Zmienna epsilon określa dokładność wyniku.

'Zapętl aż uzyskamy zadaną dokładność
Do While (abs(xR - xL)) > epsilon
 
  xM = (xL + xR) / 2
 
  If ((f(xL) * f(xM)) < 0) Then
    'Nadpisz prawy przedział
    xR = xM
  ElseIf ((f(xR) * f(xM)) < 0)
    'Nadpisz lewy przedział
    xL = xM
  End If
Loop
 
'Zwróć znalezione miejsce zerowe
Return (xR + xL) / 2

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

• regula falsi
• metoda siecznych
• metoda stycznych
• metoda iteracji