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. Mai 2012 um 12:19 Uhr

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

  2. Maximam 30. Mai 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. Mai 2012 um 13:06 Uhr

    W├╝rde mich auf jeden Fall interessieren!

  4. Adelhardtam 10. Juli 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. Juli 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.