Halbierungsmethode – Was ist, Algorithmus und Beispiel

Was ist die Halbierungsmethode?

Die Bisektionsmethode ist eine der grundlegenden numerischen Lösungen zum Finden der Wurzel einer Polynomgleichung. Sie umklammert das Intervall, in dem die Wurzel der Gleichung liegt, und unterteilt es bei jeder Iteration in Hälften, bis die Wurzel gefunden ist. Daher wird die Bisektionsmethode auch als Klammermethode bezeichnet.

Da der Arbeitsmechanismus jedoch dem binären Suchalgorithmus ähnelt, ist die Bisektionsmethode auch als binäre Suchmethode, Halbierungsmethode oder Dichotomiemethode bekannt. Sie basiert hauptsächlich auf dem Zwischenwertsatz.

Finden von Gleichungswurzeln

In diesem Beispiel betrachten wir nur Gleichungen mit einer unabhängigen Variablen. Es kann entweder linear oder nichtlinear sein. Lineare Gleichungen werden verwendet, um den Graphen einer geraden Linie darzustellen, während nichtlineare Gleichungen zur Darstellung von Kurven verwendet werden.

Die Wurzel einer Gleichung bezeichnet den Wert der unabhängigen Variablen, die die Gleichung erfüllt. Zum Beispiel: die Wurzel einer Gleichung f(x)= 4-x² = 0 ist 2, weil f(2) = 4-2² = 0.

Betrachten wir f(x) als eine reelle stetige Funktion. Nach dem Zwischenwertsatz hat die Gleichung f(x)=0 mindestens eine Wurzel zwischen a und b, wenn f(a)f(b) < 0. Die Funktion f(x) hat eine Wurzel „c“. zwischen A und B.

Grafische Darstellung der Halbierungsmethode

Die folgende Grafik stellt den Arbeitsmechanismus der Bisektionsmethode dar. Aus der Grafik können wir erkennen, dass die Wurzel der Gleichung rot markiert ist.

Zunächst:

Wir haben zunächst zwei erste Vermutungen angenommen, a₁ und B_1, für welche f(a₁)f(b₁) < 0. Nach dem Zwischenwertsatz sollte die Wurzel in [a liegen₁, B₁].
Wir können den Mittelpunkt von a finden₁ und B_1,Das ist b₂. Somit wird das Anfangsintervall nun auf [a₁, B₂] weil f(a₁)f(b₂) < 0.
Auf die gleiche Weise wird das Intervall reduziert, bis die Näherungslösung gefunden ist.

Algorithmus der Bisektionsmethode

Die Schritte zum Anwenden des Bisektionsmethodenalgorithmus zum Finden der Wurzel der Gleichung f(x)=0 sind wie folgt

Schritt 1) Wählen Sie die anfänglichen Schätzungen a, b und die Toleranzrate e

Schritt 2) Wenn f(a)f(b) >=0, dann liegt die Wurzel nicht in diesem Intervall. Daher wird es keine Lösung geben.

Schritt 3) Finden Sie den Mittelpunkt, c = (a+b)/2

(i) Wenn der Funktionswert des Mittelpunkts f(c) = 0 ist, dann ist c die Wurzel. Gehen Sie zu Schritt 5.
(ii) Wenn f(a)f(c) < 0, liegt die Wurzel zwischen a und c. Dann setze a = a, b = c.
(iii) Sonst setze a = c, b = b.

Schritt 4) Wenn der absolute Fehler höher ist als die Toleranzrate oder (ba) > e, fahren Sie mit Schritt 3 fort.

Schritt 5) Zeigen Sie c als ungefähre Wurzel an.

Sehen wir uns ein Beispiel für den Algorithmus der Halbierungsmethode an.
Wir müssen die Wurzel der folgenden kontinuierlichen Funktion mithilfe der Formel der Bisektionsmethode finden.

f(x) = x³ - x² + 2

Beispiel einer Halbierungsmethode

Schritt 1) Angenommen,

         a = -10,
         b = 10, und
         e = 1 % oder 0.01

Schritt 2) Jetzt prüfen wir, ob f(a)f(b) >= 0 ist oder nicht.

         f(a) = f(-10) = (-10)3 – (-10)2 + 2 = -1098
         f(b) = f(10) = (10)3 – (10)2 + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

Daher liegt die Wurzel der obigen Funktion in diesem Intervall [-10, 10].

Schritt 3) Dann wird zuerst der Mittelpunkt c berechnet.

Nun müssen folgende Voraussetzungen überprüft werden:

(i) ob f(c) = 0:
f(c) = f(0) = (0)3 – (0)2 + 2 = 2 ≠ 0

(ii) wenn f(a)f(c) < 0:
f(c)f(a) = 2*(-1098) < 0

Die Bedingung ist erfüllt. Für die nächste Iteration lauten die Werte:

a = a = -10
b = c = 0

Schritt 4) Da (ba) = (0-(-10)) = 10>0.05, wird der Vorgang wiederholt. Die nächsten Iterationen sind in der Tabelle aufgeführt.

Iteration	a	b	c	ba	f(c)
1	-10	0	0	10	2
2	-5	0	-5	5	-148
3	-2.5	0	-2.5	2.5	-19.875
4	-1.25	0	-1.25	1.25	-1.52562
5	-1.25	-0.625	-0.625	0.625	1.36523
6	-1.25	-0.9375	-0.9375	0.3125	0.297119
7	-1.09375	-0.9375	-1.09375	0.15625	-0.50473
8	-1.01562	-0.9375	-1.01562	0.078125	-0.0791054
9	-1.01562	-0.976562	-0.976562	0.0390625	0.115003
10	-1.01562	-0.996094	-0.996094	0.0195312	0.0194703
11	-1.00586	-0.996094	-1.00586	0.00976562	-0.0294344

Schritt 5) In der 11. Iteration ist die Bedingung von Schritt 4 falsch. Somit ist die Wurzel dieser Gleichung -1.00586.

Logisches Diagramm der Halbierungsmethode

Pseudocode

Start
Set a, b, e
if f(a)*f(b) >=0 
	Output("Root does not exist in this interval")
	Stop
while (b-a)>e do   
	c ← (a + b)/2    
	if f(c) = 0
        	break    
	end if 
	if f(c)*f(a) < 0 then
      	b ← c    
	else        
		a ← c
end while
Output(c)
Stop

Beispiel für die Bisektionsmethode in C/C++

Eingang:

#include<bits/stdc++.h>
using namespace std;
#define Error 0.01
double value(double x)
{
	return x*x*x - x*x + 2;
}
void bisection_method(double a, double b)
{
	if (value(a) * value(b) >= 0)
	{
		cout << "The root does not lie in this interval\n";
		return;
	}
	double c = a;
	while ((b-a) >= Error)
	{
		c = (a+b)/2;
		if (value(c) == 0.0)
			break;
		else if (value(c)*value(a) < 0)
			b = c;
		else
			a = c;
	}
	cout << "The root is :" << c;
}
int main()
{
	double a =-10 , b = 10;
	bisection_method(a, b);
	return 0;
}

Ausgang:

The root is :-1.00586

Beispiel für die Bisektionsmethode in Python