Algorytm bisekcji

Metoda bisekcji (lub metoda równego podziału) jest metodą szacunkową, która pozwala znaleźć miejsce zerowe funkcji w danym przedziale $⟨a,b⟩$ gdzie $a<b$. Aby tak się stało, muszą zostać spełnione pewne warunki:

• obszar poszukiwania należy ograniczyć do przedziału $⟨a,b⟩$ tak, aby funkcja na krańcach przedziałów przyjmowała wartości różnych znaków,

• funkcja w tym przedziale musi być ciągłafunkcja ciągłaciągła.

Proces szukania miejsca zerowego polega na podzieleniu wybranego przedziału na dwie równe części, a następnie wybraniu jednej z nich (tej, która będzie dalszym obszarem poszukiwania). Wybór zależy od tego, który podprzedział dalej będzie spełniał warunek różności funkcji na swoich krańcach. Proces ten kontynuujemy do momentu, gdy osiągniemy określony warunek stopu.

Przykładowym warunkiem stopu mogą być następujące warunki:

1. Wartość funkcji w znalezionym punkcie, będącym potencjalnym miejscem zerowym funkcji, czyli wartość funkcji w tym punkcie wynosi, co do wartości bezwzględnej, <= $\epsilon$, gdzie $\epsilon$ jest określone na początku algorytmu.

2. Różnica pomiędzy punktami będącymi potencjalnymi miejscami zerowymi w kolejnych iteracjach wynosi $\pm \epsilon$, gdzie $\epsilon$ jest określone na początku algorytmu.

3. Osiągnięta została określona liczba iteracji algorytmu.

Bisekcja w języku Java – podejście rekurencyjne

Problem bisekcji może być zrealizowany w postaci rekurencji, od której zaczniemy implementację. Funkcja, której miejsca zerowego będziemy szukać, to $\sin \left(x\right)$ w przedziale $⟨1,5⟩$. Rekurencja opiera się na założeniu istnienia stanu końcowego, do którego będziemy próbowali dotrzeć. W omawianym przypadku stan ten będzie określony przez wybrany warunek stopu.

Zrealizujmy zatem pierwszy z określonych warunków. Do funkcji rekurencyjnej przekazywać będziemy parametry a oraz b, które określają kraniec przedziału, a także epsilon, czyli dokładność. Wówczas program może wyglądać następująco:

public class Main {
	public static double f(double x) {
		return Math.sin(x);
	}

	public static double bisekcja(double a, double b, double epsilon) {
		double x = (a + b) / 2;
		if (Math.abs(f(x)) < epsilon) {
			return x;
		}
		else if (f(a) * f(x) < 0) {
			return bisekcja(a, x, epsilon);
		}
		return bisekcja(x, b, epsilon);
	}

	public static void main(String[] args) {
		System.out.println(bisekcja(1, 5, 0.00001));
	}
}

W wyniku uruchomienia programu na ekran wypisany zostaje wynik 3.1416015625. Jest to zgodne z prawdą, gdyż jedynym miejscem zerowym funkcji sinus w podanym przedziale jest liczba $\pi \approx 3.1415926535$.

Bisekcja w języku Java – podejście iteracyjne

Podejście iteracyjne do bisekcji również wymaga określenia warunku stopu. Tym razem zaimplementujemy drugi z wymienionych na wstępie przykładowych warunków. Sprawdzenie warunku musi się wykonać co najmniej raz, aby uzyskać różnicę pomiędzy kolejnymi przybliżeniami miejsca zerowego. Odpowiednią konstrukcją informatyczną będzie zatem pętla do ... while (oczywiście jest to możliwe do zrealizowania również za pomocą pętli while).

public class Main {
	public static double f(double x) {
		return Math.sin(x);
	}
	
	public static double bisekcja(double a, double b, double epsilon) {
		double x0, x1 = (a + b) / 2;

		do {
			x0 = x1;

			if (f(a) * f(x0) < 0) {
				b = x0;
			}
			else {
				a = x0;
			}

			x1 = (a + b) / 2;
		}
		while (Math.abs(x1 - x0) > epsilon);

		return x1;
	}

	public static void main(String[] args) {
		System.out.println(bisekcja(1, 5, 0.00001));
	}
}

W wyniku uruchomienia programu na ekran wypisany zostaje wynik 3.1415939331054688. Jest to rozwiązanie dużo dokładniejsze, jednak należy pamiętać, że wymagało wykonania większej liczby operacji.

Słownik