Bisektionsverfahren mit Beispielen

Was ist die Bisektionsmethode?

Die Bisektionsmethode ist eines der grundlegendsten numerischen Verfahren zur Bestimmung der Nullstelle eines Polynoms oder einer transzendenten Gleichung. Sie funktioniert, indem das Intervall, das die Nullstelle enthält, eingegrenzt und in jedem Iterationsschritt halbiert wird, bis die Nullstelle innerhalb einer akzeptablen Toleranz gefunden ist. Aufgrund dieses Eingrenzungsverhaltens wird die Bisektionsmethode auch als Klammerverfahren bezeichnet.

Da ihr Funktionsprinzip der binären Suche ähnelt, ist die Bisektionsmethode auch als binäre Suchmethode, Halbierungsmethode oder Dichotomiemethode bekannt. Sie basiert auf einer soliden theoretischen Grundlage: dem Zwischenwertsatz, der garantiert, dass eine stetige Funktion, die innerhalb eines Intervalls ihr Vorzeichen ändert, die Nullstelle irgendwo in diesem Intervall schneiden muss.

Nachdem wir die grundlegende Definition geklärt haben, wollen wir untersuchen, warum das Finden von Nullstellen in Gleichungen wichtig ist und wie die Bisektionsmethode in dieses Gesamtbild passt.

Finden von Gleichungswurzeln

In dieser Betrachtung konzentrieren wir uns ausschließlich auf Gleichungen mit einer unabhängigen Variablen. Solche Gleichungen können linear oder nichtlinear sein. Lineare Gleichungen beschreiben den Graphen einer Geraden, während nichtlineare Gleichungen Kurven und komplexere Formen beschreiben.

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

Betrachten wir f(x) als reelle, stetige Funktion. Nach dem Zwischenwertsatz besitzt die Gleichung f(x) = 0 genau dann mindestens eine Nullstelle zwischen a und b, wenn f(a)f(b) < 0 gilt. Anders ausgedrückt: Die Funktion f(x) hat eine Nullstelle „c“ irgendwo zwischen a und b.

Diese Vorzeichenwechsel-Eigenschaft nutzt die Bisektionsmethode aus. Im nächsten Abschnitt wird dies grafisch veranschaulicht.

Grafische Darstellung der Bisektionsmethode

Die folgende Grafik veranschaulicht die Funktionsweise der Bisektionsmethode. Aus der Grafik ist ersichtlich, dass die tatsächliche Wurzel der Gleichung rot markiert ist.

Das Verfahren lässt sich wie folgt zusammenfassen:

• Wir wählen zunächst zwei Anfangsschätzungen, a₁ und B₁, für welche f(a₁)f(b₁) < 0. Nach dem Zwischenwertsatz muss die Wurzel in [a liegen.₁, B₁].
• Anschließend berechnen wir den Mittelpunkt eines₁ und B₁, was b ist₂Das anfängliche Intervall wird nun auf [a reduziert.₁, B₂] weil f(a₁)f(b₂) < 0.
• Auf die gleiche Weise wird das Intervall immer wieder halbiert, bis eine Näherungslösung innerhalb der gewünschten Toleranz gefunden ist.

Nachdem die geometrische Intuition klar geworden ist, können wir das Verfahren nun als schrittweisen Algorithmus formalisieren.

Algorithmus der Bisektionsmethode

Die Schritte zur Anwendung des Bisektionsverfahrens zur Bestimmung der Nullstelle der Gleichung f(x) = 0 sind wie folgt.

Schritt 1) Wähle Anfangswerte a, b und eine Toleranzrate e.

Schritt 2) Wenn f(a)f(b) >= 0, dann liegt die Nullstelle nicht in diesem Intervall. In diesem Fall gibt es keine Lösung innerhalb von [a, b].

Schritt 3) Bestimme den Mittelpunkt, c = (a + b)/2.

(i) Wenn der Funktionswert an der Mitte f(c) = 0 ist, dann ist c die Nullstelle. Fahre mit Schritt 5 fort.
(ii) Falls f(a)f(c) < 0, liegt die Nullstelle zwischen a und c. Dann setze a = a und b = c.
(iii) Andernfalls setze a = c, b = b.

Schritt 4) Ist der absolute Fehler größer als die Toleranzrate, also (b – a) > e, gehe zurück zu Schritt 3.

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

Betrachten wir ein Beispiel für die Anwendung des Bisektionsverfahrens. Wir werden die Nullstelle der folgenden stetigen Funktion mithilfe der Bisektionsformel bestimmen.

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

Beispiel einer Halbierungsmethode

Schritt 1) Nehmen wir an,

         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)³ – (-10)² + 2 = -1098
         f(b) = f(10) = (10)³ - (10)² + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

Daher liegt die Nullstelle der obigen Funktion im Intervall [-10, 10].

Schritt 3) Als Nächstes wird der Mittelpunkt c berechnet.

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

(i) Ob f(c) = 0:
         f(c) = f(0) = (0)³ - (0)² + 2 = 2, was nicht gleich 0 ist.

(ii) Ob 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 (b – a) = (0 – (-10)) = 10 > 0.01, wird der Prozess wiederholt. Die nächsten Iterationen sind in der folgenden Tabelle dargestellt.

Schritt 5) Im 11. Iterationsschritt ist die Bedingung aus Schritt 4 nicht mehr erfüllt. Daher ist die Näherungslösung dieser Gleichung -1.00586.

Nachdem ein numerisches Beispiel abgeschlossen ist, wird im nächsten Abschnitt das logische Diagramm vorgestellt, das den gesamten Kontrollfluss abbildet.

Logisches Diagramm der Halbierungsmethode

Das nachfolgende Flussdiagramm fasst die Entscheidungslogik der Bisektionsmethode zusammen, einschließlich der Klammerprüfung, der Mittelpunktaktualisierung und des Toleranztests.

Pseudo-Code

Der unten stehende Pseudocode bildet den Algorithmus nach und dient als Vorlage für die Implementierung der Bisektionsmethode in jeder Programmiersprache.

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++

Das folgende C/C++ Das Programm implementiert das Bisektionsverfahren, um die Nullstelle von f(x) = x zu finden.³ - x² + 2 innerhalb des Intervalls [-10, 10].

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

Das Python Die untenstehende Version liefert mit identischer Logik die gleiche Näherungswurzel und eignet sich daher ideal für schnelle Experimente und Lehrzwecke.

Eingang:

def value(x):
    return x*x*x - x*x + 2

def bisection_method(a, b):
    if (value(a) * value(b) >= 0):
        return
    c = a
    while ((b-a) >= 0.01):
        c = (a+b)/2
        if (value(c) == 0.0):
            break
        if (value(c)*value(a) < 0):
            b = c
        else:
            a = c
    print("The root is : ", "%.4f" % c)

a = -10
b = 10
bisection_method(a, b)

Ausgang:

The root is :  -1.0059

Vorteile und Grenzen der Bisektionsmethode

Wie jedes numerische Verfahren hat auch die Bisektionsmethode klare Stärken und einige praktische Nachteile. Die folgende Tabelle fasst die wichtigsten Vor- und Nachteile zusammen.

Anwendungen der Bisektionsmethode

Die Bisektionsmethode wird in vielen praktischen und modernen Computerszenarien eingesetzt, in denen ein zuverlässiger Nullstellenfindungsschritt erforderlich ist.

• Ingenieursimulationen: Lösen nichtlinearer Gleichungen, die in der Wärmeübertragung, der Fluiddynamik und der Strukturanalyse auftreten.
• Finanzmodellierung: Berechnung von Renditen, internen Zinsfüßen und Gewinnschwellen, für die keine geschlossenen Lösungen existieren.
• Maschinelles Lernen und KI: Schwellenwerte ermitteln, Modelle kalibrieren und Hyperparameter in KI-gesteuerten numerischen Lösern optimieren.
• Computergrafik: Bestimmung von Strahl-Oberflächen-Schnittpunkten und Parameterwerten entlang von Kurven.
• Eingebettete Systeme: Annäherung an die Wurzeln in ressourcenarmen Reglern, bei denen Einfachheit und Vorhersagbarkeit wichtiger sind als Geschwindigkeit.

Häufig gestellte Fragen