Quadratwurzel mit Bisektion berechnen

Im Folgenden werde ich zeigen, wie man relativ einfach die Umkehrfunktion einer monotonen Funktion berechnen kann. Als Beispiel nehme ich die Wurzelfunktion.

Nehmen wir an, wie möchten die Wurzel von 10 berechnen. Wie geht man dabei vor?

Wir kennen das Ergebnis nicht, aber wir können sagen in welchem Bereich es sich befindet. Der Betrag der Wurzel wird auf jeden Fall größer oder gleich der 0 sein (wir rechnen mit positiven Zahlen) und es wird auf jeden Fall kleiner oder gleich der Zahl sein, von der wir die Quadratwurzel berechnen möchten.
Wir können auch schreiben (ich beziehe mich nur auf positive Zahlen): 1 ≤ √x ≤ x .

Ich nenne im Folgenden die untere Grenze L (low) und die obere H (high). Am Anfang ist also

L = 0
H = x
L ≤ √x ≤ H .

Die beiden Grenzen sind als orangene Linien in dem Graphen der Wurzelfunktion dargestellt.

Wir wissen also, dass die gesuchte Zahl zwischen L und H liegt, aber wir wissen nicht wo genau. Um näher an das Ergebnis heranzukommen, bestimmen wir die Mitte zwischen L und H.
m = (L+H)/2
Die Zahl m ist unsere aktuelle Schätzung für die Wurzel. Wir prüfen, wie gut diese Schätzung ist. Dazu quadrieren wir m und schauen ob m² über oder unter x liegt.

Wenn m² größer als x ist, dann bedeutet das, dass das wahre Ergebnis auf jeden Fall kleiner als m sein muss, d.h. wir können sagen, dass das Ergebnis zwischen L und m liegt. Deswegen setzen wir die obere Grenze H gleich m.

Wenn m² kleiner als x ist, dann bedeutet das, dass das wahre Ergebnis auf jeden Fall größer als m sein muss, d.h. wir können sagen, dass das Ergebnis zwischen m und H liegt. Deswegen setzen wir die untere Grenze L gleich m.

Wenn m² gleich x ist, dann ist m die Wurzel von x. Diesen Fall werden wir aber im Hinblick auf Programmiersprachen nicht behandeln, weil ein Gleichheitsvergleich bei Fließkommazahlen nicht unproblematisch ist.

Nach diesem Schritt wissen wir zwar immer noch nicht das Ergebnis, aber wir haben das Intervall in dem es sich befindet halbiert. Am Beispiel von der Wurzel von 10, können wir also sagen, dass Sqrt(x) irgendwo zwischen L=0 und H=5 liegt.

Als Nächstes wird das Intervall zwischen L und H wieder halbiert und es wird ein Vergleich zwischen m² und x durchgeführt. Dadurch verschiebt sich einer der Grenzen und grenzt das gesuchte Ergebnis mehr ein. Hier wird auch der Name Bisektion klar, man unterteilt den Intervall (=Sektion) in zwei(=Bi) weitere Intervalle.

Dieser Ablauf wird so lange wiederholt bis man die gewünschte Genauigkeit erreicht hat.

Hier wird auch der Name Bisektion klar, man unterteilt den Intervall (=Sektion) in zwei(=Bi) weitere Intervalle.

Einige weitere Schritte für ein besseres Verständnis des Algorithmus.

Wie man sieht, werden die Intervallgrenzen immer enger und der gesuchte Wert immer genauer (√10 = 3,162277660…).

Umsetzung in C++

Der vorgestellte Algorithmus lässt sich in wenigen Zeilen in C++ realisieren.

// Berechnet die Quadratwurzel von value
// N = Anzahl der Schritte
double sqrtBisection(double value, size_t N)
{
	double L = 0.0;
	double H = value;
	double m = 0.0;

	for(size_t i = 0; i < N; ++i)
	{
		// Intervallmitte berechnen
		m = (L+H)*0.5;

		if(m*m > value)	// m überschätzt
			H = m;
		else            // m unterschätzt
			L = m;
	}

	return m;
}

Man könnte natürlich fragen wofür man es braucht, wenn es doch meistens sowieso eine sqrt(x)-Funktion zur Verfügung steht. Nun, zum Beispiel bei Handware-Programmierung auf einem FPGA. Genau dies musste ich im Rahmen eines Studiumprojekts machen.
Andererseits kann dieses Verfahren für jede monoton verlaufende Funktion verwenden. Also beispielsweise auch für x⁵ oder Polynome in bestimmten Intervallen.