Przeczytaj

Metoda bisekcji – implementacja algorytmu w języku C++

Przykład 1

Napisz program obliczający przybliżenie miejsca zerowego funkcji ciągłej $f(x)$ w danym przedziale $[a, b]$ .

Program przetestuj dla funkcji $f (x) = x^{4} - 8 x^{2} + 3 x + 1$ , przedziału $[2, 4]$ , o współczynniku $epsilon$ równym $0.01$ i współczynniku $delta$ równym $0.01$ .

Specyfikacja problemu:

Dane:

f(x) – funkcja rzeczywista ciągła, której miejsce zerowe mamy obliczyć
a – liczba rzeczywista; początek przedziału
b – liczba rzeczywista; koniec przedziału
epsilon – liczba rzeczywista; dokładność rozwiązania
delta – liczba rzeczywista; minimalna długość odcinka, po osiągnięciu której przestajemy go dalej dzielić; przybliżenie

Wynik:

Program, na standardowe wyjście, wypisuje liczbę rzeczywistą będącą przybliżoną wartością miejsca zerowego funkcji $f(x)$ , znajdującym się w zadanym przedziale $[a, b]$ .

Zacznijmy od dołączenia do programu niezbędnych bibliotek i deklaracji przestrzeni nazw. Dołączenie do programu biblioteki cmathcmathcmath pozwoli na użycie funkcji obliczającej wartość bezwzględną liczby zmiennoprzecinkowej fabs(). Następnie zdefiniujmy funkcję o nazwie f(), zwracającą wartość rozważanej funkcji dla danego punktu x.

#include <iostream>
#include <cmath>
using namespace std;

double f(double x) {
	return x * x * x * x - 8 * x * x + 3 * x + 1;
}

Kolejnym krokiem jest utworzenie definicji funkcji bisekcja, przyjmującej dwa parametry, będące liczbami zmiennoprzecinkowymi. Stanowią one krańce rozważanego przedziału. W funkcji stworzymy dwie zmienne lokalne, które będą zawierały wartości funkcji w tych punktach.

#include <iostream>
#include <cmath>
using namespace std;

double f(double x) {
	return x * x * x * x - 8 * x * x + 3 * x + 1;
}

double bisekcja(double a, double b) {
	double fA = f(a);
	double fB = f(b);
}

Konieczna będzie weryfikacja, czy analizowana funkcja spełnia warunki bisekcji. Trzeba w tym celu sprawdzić, czy funkcja przyjmuje w krańcach podanego przedziału wartości o różnych znakach. Można to zrobić np. poprzez sprawdzenie znaku wyniku mnożenia wartości funkcji w tych punktach. Niespełnienie tego założenia uniemożliwi znalezienie miejsca zerowego. W takim przypadku program zakończy działanie z kodem -1.

#include <iostream>
#include <cmath>
using namespace std;

double f(double x) {
	return x * x * x * x - 8 * x * x + 3 * x + 1;
}

double bisekcja(double a, double b) {
	double fA = f(a);
	double fB = f(b);

	if (fA * fB > 0) {
		cout << "Niespelnione zalozenia bisekcji." << endl;
		exit(-1);
	}
}

W przypadku spełnienia założenia bisekcji, obliczamy długość przedziału i zapisujemy go do zmiennej.

Kolejnym krokiem jest stworzenie pętli nieskończonej, w której będzie następować nieskończone połowienie przedziału. Znajdźmy punkt środkowy przedziału $[a, b]$ . Jego wartość zapiszemy w zmiennej x0, a wartość funkcji w tym punkcie w zmiennej fx0.

#include <iostream>
#include <cmath>
using namespace std;

double f(double x) {
	return x * x * x * x - 8 * x * x + 3 * x + 1;
}

double bisekcja(double a, double b) {
	double fA = f(a);
	double fB = f(b);

	if (fA * fB > 0) {
		cout << "Niespelnione zalozenia bisekcji." << endl;
		exit(-1);
	}
	else {
		double dlugoscPrzedzialu = b - a;

		while (true) {
			dlugoscPrzedzialu = dlugoscPrzedzialu / 2.0;
			double x0 = a + dlugoscPrzedzialu;
			double fx0 = f(x0);
		}
	}
}

Następnie, aby pętla nie wykonywała się w nieskończoność, musimy zaimplementować wybrany warunek końcowy. Dodajmy do definicji funkcji dwa parametry. Niech wartość parametru epsilon będzie pożądaną dokładnością wartości funkcji w punkcie. Będziemy szukać nie punktu o wartości funkcji 0, ale punktu, dla którego funkcja przyjmuje wartość z zakresu $[-\text{epsilon},\text{epsilon}]$ .

Ponadto nie chcemy dzielić odcinka w nieskończoność. Ustalimy pewne przybliżenie – parametr delta. Gdy wartość bezwzględna parametru przedziału dlugoscPrzedzialu będzie mniejsza niż wartość parametru delta, uznajemy odcinek za punkt – dalszy podział jest niemożliwy. Jeżeli co najmniej jeden z warunków zostanie spełniony, zwracamy punkt środkowy obecnie rozważanego przedziału i uznajemy go za miejsce zerowe funkcji.

#include <iostream>
#include <cmath>
using namespace std;

double f(double x) {
	return x * x * x * x - 8 * x * x + 3 * x + 1;
}

double bisekcja(double a, double b, double delta, double epsilon) {
	double fA = f(a);
	double fB = f(b);
    
	if (fA * fB > 0) {
		cout << "Niespelnione zalozenia bisekcji." << endl;
		exit(-1);
	}
	else {
		double dlugoscPrzedzialu = b - a;

		while (true) {
			dlugoscPrzedzialu = dlugoscPrzedzialu / 2.0;
			double x0 = a + dlugoscPrzedzialu;
			double fx0 = f(x0);
            
			if (fabs(dlugoscPrzedzialu) < delta || fabs(fx0) < epsilon) {
				return x0;
			}
		}
	}
}

Jeżeli wartość nie zostanie zwrócona, żaden z zaimplementowanych warunków końcowych nie jest spełniony.

Oznacza to, że musimy ustawić wartość środkową jako początek lub koniec nowego przedziału. Należy to zrobić tak, by po zmianie jednego z końców przedziału funkcja f dalej miała na jego końcach wartości różnych znaków.

Następnie przechodzimy na początek pętli i instrukcje są ponawiane – przedział jest ponownie dzielony, aż do spełnienia warunku końcowego.

Ważne!

W algorytmie bisekcji należy pamiętać, aby uwzględniać przypadki, w których miejsce zerowe znajduje się dokładnie w połowie przedziału $[a, b]$ . Nieuwzględnienie tego przypadku może powodować, że lewa lub prawa granica przedziału zostanie ustawiona na 0, przez co w kolejnej iteracji nie będzie spełnione założenie bisekcji, dotyczące różnych znaków na krańcach przedziału.

W przypadku programu tworzonego w ramach tego e‑materiału jest to zapewnione przez wykorzystanie warunku końcowego, który zostanie spełniony między innymi w sytuacji, gdy wartość funkcji w punkcie środkowym wynosi dokładnie 0.

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny cmath zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. double f otwórz nawias okrągły double x zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. return x asterysk x asterysk x asterysk x minus 8 asterysk x asterysk x plus 3 asterysk x plus 1 średnik. Linia 7. zamknij nawias klamrowy. Linia 9. double bisekcja otwórz nawias okrągły double a przecinek double b przecinek double delta przecinek double epsilon zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. double fA znak równości f otwórz nawias okrągły a zamknij nawias okrągły średnik. Linia 11. double fB znak równości f otwórz nawias okrągły b zamknij nawias okrągły średnik. Linia 13. if otwórz nawias okrągły fA asterysk fB zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Niespelnione zalozenia bisekcji kropka cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 15. exit otwórz nawias okrągły minus 1 zamknij nawias okrągły średnik. Linia 16. zamknij nawias klamrowy. Linia 17. else otwórz nawias klamrowy. Linia 18. double dlugoscPrzedzialu znak równości b minus a średnik. Linia 20. while otwórz nawias okrągły true zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. dlugoscPrzedzialu znak równości dlugoscPrzedzialu prawy ukośnik 2 kropka 0 średnik. Linia 22. double x0 znak równości a plus dlugoscPrzedzialu średnik. Linia 23. double fx0 znak równości f otwórz nawias okrągły x0 zamknij nawias okrągły średnik. Linia 25. if otwórz nawias okrągły fabs otwórz nawias okrągły dlugoscPrzedzialu zamknij nawias okrągły otwórz nawias ostrokątny delta kreska pionowa kreska pionowa fabs otwórz nawias okrągły fx0 zamknij nawias okrągły otwórz nawias ostrokątny epsilon zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. return x0 średnik. Linia 27. zamknij nawias klamrowy. Linia 29. if otwórz nawias okrągły fx0 asterysk fA otwórz nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 30. b znak równości x0 średnik. Linia 31. fB znak równości fx0 średnik. Linia 32. zamknij nawias klamrowy. Linia 33. else otwórz nawias klamrowy. Linia 34. a znak równości x0 średnik. Linia 35. fA znak równości fx0 średnik. Linia 36. zamknij nawias klamrowy. Linia 37. zamknij nawias klamrowy. Linia 38. zamknij nawias klamrowy. Linia 39. zamknij nawias klamrowy.

#include <iostream>
#include <cmath>
using namespace std;

double f(double x) {
	return x * x * x * x - 8 * x * x + 3 * x + 1;
}

double bisekcja(double a, double b, double delta, double epsilon) {
	double fA = f(a);
	double fB = f(b);

	if (fA * fB > 0) {
		cout << "Niespelnione zalozenia bisekcji." << endl;
		exit(-1);
	}
	else {
		double dlugoscPrzedzialu = b - a;

		while (true) {
			dlugoscPrzedzialu = dlugoscPrzedzialu / 2.0;
			double x0 = a + dlugoscPrzedzialu;
			double fx0 = f(x0);
            
			if (fabs(dlugoscPrzedzialu) < delta || fabs(fx0) < epsilon) {
				return x0;
			}
            
			if (fx0 * fA < 0) {
				b = x0;
				fB = fx0;
			}
			else {
				a = x0;
				fA = fx0;
			}
		}
	}
}

Teraz możemy wywołać funkcję bisekcja(), zgodnie z treścią zadania, tzn. dla przedziału $[2, 4]$ (a = 2, b = 4), z dokładnością epsilon = 0.01 i przybliżeniem delta = 0.01.

#include <iostream>
#include <cmath>
using namespace std;

double f(double x) {
	return x * x * x * x - 8 * x * x + 3 * x + 1;
}

double bisekcja(double a, double b, double delta, double epsilon) {
	double fA = f(a);
	double fB = f(b);

	if (fA * fB > 0) {
		cout << "Niespelnione zalozenia bisekcji." << endl;
		exit(-1);
	}
	else {
		double dlugoscPrzedzialu = b - a;

		while (true) {
			dlugoscPrzedzialu = dlugoscPrzedzialu / 2.0;
			double x0 = a + dlugoscPrzedzialu;
			double fx0 = f(x0);

			if (fabs(dlugoscPrzedzialu) < delta || fabs(fx0) < epsilon) {
				return x0;
			}

			if (fx0 * fA < 0) {
				b = x0;
				fB = fx0;
			}
			else {
				a = x0;
				fA = fx0;
			}
		}
	}
}

int main() {
	int a = 2;
	int b = 4;
	double delta = 0.01;
	double epsilon = 0.01;

	cout << bisekcja(a, b, delta, epsilon) << endl;

	return 0;
}

Słownik

algorytmy przybliżone (aproksymacyjne)

algorytmy służące do znajdowania przybliżonych rozwiązań problemów

bisekcja

pojęcie z dziedziny geometrii, oznaczające podział odcinka na dwie równe części lub podział figury na dwie przystające części

cmath

biblioteka zawierająca deklaracje funkcji matematycznych, takich jak potęgowanie, pierwiastek czy wartość bezwzględna

twierdzenie Darboux

każda funkcja ciągła, określona na pewnym przedziale rzeczywistym, przyjmuje wszystkie wartości pośrednie pomiędzy wartościami przyjmowanymi dla krańców przedziału.

pierwiastek funkcji

inaczej miejsce zerowe; punkt w którym wartość funkcji wynosi 0

Film samouczek

Sprawdź się

Metoda bisekcji – implementacja algorytmu w języku C++

Słownik