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.

Quadratwurzel-Funktion als Umkehrfunktion der Quadratfunktion.

Quadratwurzel-Funktion als Umkehrfunktion der Quadratfunktion.

Quadratfunktion x²

Quadratfunktion x².

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.

Bisektion-Verfahren. Die orangenen Linien stellen die untere und die obere Grenze L und H dar.

Bisektion-Verfahren. Die orangenen Linien stellen die untere und die obere Grenze L und H dar. Der gesuchte Wert befindet sich irgendwo zwischen diesen beiden Grenzen.

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.

Bisektion-Verfahren. Die Intervallmitte m zwischen L und H ist der geschätzte Wurzelwert von x.

Bisektion-Verfahren. Die Intervallmitte m zwischen L und H ist der geschätzte Wurzelwert von x.

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.

Bisektion-Verfahren. Das gesuchte Ergebnis befindet sich irgendwo zwischen 0 und 5.

Bisektion-Verfahren. Das gesuchte Ergebnis befindet sich irgendwo zwischen 0 und 5.

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.

Bisektion-Verfahren. Das Intervall zwischen L und H in der Mitte teilen und testen ob der Wert m unter- oder überschätzt wurde. Intervallgrenzen anpassen.

Bisektion-Verfahren. Das Intervall zwischen L und H in der Mitte teilen und testen ob der Wert m unter- oder überschätzt wurde. Intervallgrenzen anpassen.

Bisektion-Verfahren. Das Intervall zwischen L und H in der Mitte teilen und testen ob der Wert m unter- oder überschätzt wurde. Intervallgrenzen anpassen.

Bisektion-Verfahren. Das Intervall zwischen L und H in der Mitte teilen und testen ob der Wert m unter- oder überschätzt wurde. Intervallgrenzen anpassen.

Bisektion-Verfahren. Das Intervall zwischen L und H in der Mitte teilen und testen ob der Wert m unter- oder überschätzt wurde. Intervallgrenzen anpassen.

Bisektion-Verfahren. Das Intervall zwischen L und H in der Mitte teilen und testen ob der Wert m unter- oder überschätzt wurde. Intervallgrenzen anpassen.

Bisektion-Verfahren. Das Intervall zwischen L und H in der Mitte teilen und testen ob der Wert m unter- oder überschätzt wurde. Intervallgrenzen anpassen.

Bisektion-Verfahren. Das Intervall zwischen L und H in der Mitte teilen und testen ob der Wert m unter- oder überschätzt wurde. Intervallgrenzen anpassen.

Bisektion-Verfahren. Das Intervall zwischen L und H in der Mitte teilen und testen ob der Wert m unter- oder überschätzt wurde. Intervallgrenzen anpassen.

Bisektion-Verfahren. Das Intervall zwischen L und H in der Mitte teilen und testen ob der Wert m unter- oder überschätzt wurde. Intervallgrenzen anpassen.

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 x5 oder Polynome in bestimmten Intervallen.

5 Kommentare zu “Quadratwurzel mit Bisektion berechnen”

  1. Niklas Rotheram 30. May 2012 um 12:19 Uhr

    Danke für die tolle Erklärung! Ich hab schon immer gefragt, wie Computer Wurzeln berechnen ;)

  2. Maximam 30. May 2012 um 19:43 Uhr

    Also intern berechnet die CPU die Wurzel sicherlich nicht durch Bisektion, weil es weit bessere Verfahren gibt. Werde ich mal später vlt. auch vorstellen.

  3. Niklas Rotheram 31. May 2012 um 13:06 Uhr

    Würde mich auf jeden Fall interessieren!

  4. Adelhardtam 10. July 2017 um 09:52 Uhr

    Eine Anmerkung habe ich zum Verfahren:
    * Bekanntlich gilt für die Zahlen zwischen 0 und 1, dass die Wurzel größer ist als die Zahl, z.B. 0.9^2 = 0.81.
    * Das heißt, oben müsste die Ungleichung 1 <= Wurzel(x) <= x lauten.

  5. Maximam 10. July 2017 um 22:25 Uhr

    @Adelhardt: Danke!

Trackback URI | Kommentare als RSS

Einen Kommentar schreiben

XHTML: Du kannst folgende Tags verwenden: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <sub> <sup>

Hinweis: Ich behalte mir das Recht vor solche Kommentare, die Beleidigungen oder rechtswidrige Inhalte beinhalten erst nach einer Editierung freizugeben oder kommentarlos zu löschen. Ähnliches gilt auch für Kommentare die offensichtlich nur der Suchmaschinenoptimierung dienen.