WikiDer > Halbierungsmethode

Halveringsmethode

Das Halbierungsmethode oder Bisektionsmethode ist ein Algorithmus zum Lösen von Gleichungen. Das Prinzip ist sehr einfach und die Methode einfach am Computer zu implementieren. Die Methode ähnelt der binären Suche innerhalb einer geordneten Datenzeile.

Beschreibung der Methode

Zuerst wird ein Intervall bestimmt, in dem eine Lösung der Gleichung liegt, nenne es ${Anzeigestil [a,b],}$ das ist schritt 1.

Schritt 2 beinhaltet die Bestimmung, ob sich die Lösung links oder rechts von der Mitte des Intervalls befindet. In der Gleichung reduziert auf 0 ${Anzeigestil f(x)=0}$ kommt das auf die entscheidung an ${Anzeigestil f((a b)/2).}$

Suchen Sie dann weiter in dem Teilintervall, in dem die Lösung liegt. Mit jeder Iteration wird die Länge des Intervalls, in dem die Suche fortgesetzt wird, um die Hälfte reduziert. Die Konvergenz des Verfahrens ist daher garantiert. Ein wichtiger Nachteil besteht darin, dass diese Konvergenz ebenfalls langsam ist.

Beispiel

Rooten ist keine elementare Operation wie Addition oder Multiplikation. In der Praxis sollten Wurzeln immer mit a . angefahren werden iterativ Algorithmus oder a Serie. Ein Beispiel zeigt die Näherung von ${displaystyle {sqrt[{3}]{2}}}$ mit der Halbierungsmethode. Es gibt effizientere Methoden als die Bisektion, um sich Wurzeln zu nähern.

Berechnung der Kubikwurzel wird übersetzt in das Lösen der Gleichung

{Anzeigestil x^{3}-2=0}

.

Es ist klar, dass ${Anzeigestil 1$ , also ist eine erste Näherung

{displaystyle x_{1}=1{,}5}

.

Schon seit ${Displaystil 1{,}5^{3}=3{,}375}$ , Lügen ${Anzeigestil x}$ also in der linken hälfte: ${Anzeigestil 1$ . Der Vorgang wird nun wiederholt und in zweiter Näherung erhält man

{displaystyle x_{2}={ frac {1}{2}}(1 1{,}5)=1{,}25}

.

Jetzt ist ${Displaystil 1{,}25^{3}=1{,}953125}$ , also lügt ${Anzeigestil x}$ in der rechten Hälfte: ${Displaystil 1{,}25$ . So läuft es:

{displaystyle x_{3}={ frac {1}{2}}(1{,}25 1{,}5)=1{,}375}

.

Dann stellt sich heraus: ${Displaystil 1{,}25$ . So wird

{displaystyle x_{4}={ frac {1}{2}}(1{,}25 1{,}375)=1{,}3125}

.

Denn für den gesuchten Wert gilt das ${Displaystil xca. 1{,}25992105}$ , wird immer sein ${displaystyle x_{i}}$ in der linken Hälfte der kommenden Intervalle sind:

{displaystyle x_{5}={ frac {1}{2}}(1{,}25 1{,}3125)=1{,}28125}

{displaystyle x_{6}={ frac {1}{2}}(1{,}25 1{,}28125)=1{,}265625}

{displaystyle x_{7}={ frac {1}{2}}(1{,}25 1{,}265625)=1{,}2578125}

Jetzt gehen sie unter ${Anzeigestil x}$ , die durch Berechnung der dritten Potenz bestimmt werden kann, also

{displaystyle x_{8}={ frac {1}{2}}(1{,}2578125 1{,}265625)=1{,}26171875}

.

Nun ist der Ansatz wieder oben:

{displaystyle x_{9}={ frac {1}{2}}(1{,}2578125 1{,}26171875)=1{,}259765625}

.

Und so weiter, bis die gewünschte Genauigkeit erreicht ist.

Anwendbarkeit

Diese Methode macht wirklich nur Sinn, wenn die Newtons Methode oder regula falsch kann nicht verwendet werden, wenn zum Beispiel viele Lösungen nahe beieinander liegen, was diese Methoden stören kann, oder wenn die Startwerte zu weit von der Lösung entfernt sind. Wenn die gewünschte Genauigkeit nicht zu groß ist, kann die Bisektionsmethode auch schneller sein, da weniger Berechnungen pro Schritt erforderlich sind.

Aus dem obigen Beispiel lernen wir, dass wir die Methode zum Lösen einer Gleichung der Form . anwenden können ${Anzeigestil f(x)=0}$ , wenn wir ein Intervall haben ${Anzeigestil [a,b]}$ in der die/eine Lösung liegt und alle Funktionswerte links von der Lösung kleiner oder größer sind als alle Funktionswerte rechts von der Lösung. wenn ${displaystyle f}$ kontinuierlich Ist eingeschaltet ${Anzeigestil [a,b],}$ und ${Anzeigestil f(a)<0}$ und ${Anzeigestil f(b)>0}$ (oder umgekehrt) nach Zwischenwertsatz garantiert mindestens einen Nullpunkt.

Der Algorithmus im Pseudocode

Stellen Sie zuerst die zu erreichende Genauigkeit ein ${Anzeigestil-Delta}$ Fest.

Reduziere die zu lösende Gleichung auf ${Anzeigestil f(x)=0}$ , und finde ein Intervall ${Anzeigestil [a,b]}$ so dass ${Anzeigestil f(a)}$ und ${Anzeigestil f(b)}$ haben gegensätzliche Vorzeichen.

Wiederholen Sie dann die folgenden Schritte:

Berechnen Sie den Funktionswert ${Anzeigestil f(m)}$ mitten drin ${displaystyle m}$ des Intervalls
Vergleichen Sie diesen Wert mit den Funktionswerten in den Endpunkten des Intervalls
Ersetzen Sie den Endpunkt, an dem die Funktion das gleiche Vorzeichen hat wie ${Anzeigestil f(m)}$ durch ${displaystyle m}$

Fahren Sie damit fort, bis die gewünschte Genauigkeit erreicht ist, d. h. bis die Länge des resultierenden Intervalls kleiner ist als ${Anzeigestil-Delta}$ .

Eine mögliche Implementierung in Pseudocode sieht dann so aus:

    const d = .... var a, b, m; a, bA, B; SOLANGE (b - a) > d m ← (a b) / 2 WENN f(m)*f(a) < 0 DANN b ← m SONST a ← m REPEAT-Schätzung ← (a b) / 2

Siehe auch

Navigation