Algoritme van de bisectiemethode met voorbeelden

Wat is de bisectiemethode?

De bisectiemethode is een van de meest fundamentele numerieke technieken voor het vinden van de wortel van een polynoom of transcendentale vergelijking. De methode werkt door het interval waarin de wortel zich bevindt te omsluiten en dit interval vervolgens in tweeën te delen bij elke iteratie, totdat de wortel binnen een acceptabele tolerantie is gevonden. Vanwege deze omsluitingsmethode wordt de bisectiemethode ook wel de bracketingmethode genoemd.

Omdat het werkingsmechanisme lijkt op binair zoeken, staat de bisectiemethode ook bekend als de binaire zoekmethode, halveringsmethode of dichotomiemethode. Ze berust op een sterke theoretische basis: de Tussenwaardestelling, die garandeert dat een continue functie die van teken verandert over een interval ergens binnen dat interval nul moet kruisen.

Nu de basisdefinitie vastligt, laten we eens kijken waarom het vinden van wortels van vergelijkingen belangrijk is en hoe de bisectiemethode in dat bredere plaatje past.

Wortels van vergelijkingen vinden

In deze bespreking concentreren we ons uitsluitend op vergelijkingen met één onafhankelijke variabele. Dergelijke vergelijkingen kunnen lineair of niet-lineair zijn. Lineaire vergelijkingen beschrijven de grafiek van een rechte lijn, terwijl niet-lineaire vergelijkingen krommen en complexere vormen beschrijven.

De wortel van een vergelijking is de waarde van de onafhankelijke variabele die aan de vergelijking voldoet. Bijvoorbeeld, de wortel van de vergelijking f(x) = 4 – x² = 0 is 2, omdat f(2) = 4 – 2² = 0.

Laten we f(x) beschouwen als een reële continue functie. Volgens de Tussenwaardestelling heeft de vergelijking f(x) = 0 minstens één wortel tussen a en b als f(a)f(b) < 0. Met andere woorden, de functie f(x) heeft een wortel, "c", ergens tussen a en b.

Deze eigenschap van tekenwisseling is precies wat de bisectiemethode benut. In de volgende sectie wordt uitgelegd hoe dit idee er grafisch uitziet.

Grafische weergave van de bisectiemethode

De volgende grafiek illustreert het werkingsmechanisme van de bisectiemethode. Uit de grafiek blijkt dat de werkelijke wortel van de vergelijking in het rood is gemarkeerd.

De procedure kan als volgt worden samengevat:

• We kiezen eerst twee initiële schattingen, een₁ en B₁, waarvoor f(a₁)f(geb₁) < 0. Volgens de Tussenwaardestelling moet de wortel in [a] liggen.₁, b₁].
• Vervolgens berekenen we het middelpunt van een₁ en B₁, wat b is₂Het initiële interval wordt nu gereduceerd tot [a₁, b₂] omdat f(a₁)f(geb₂) < 0.
• Op dezelfde manier wordt het interval steeds opnieuw gehalveerd totdat een benaderende oplossing binnen de gewenste tolerantie is gevonden.

Nu de geometrische intuïtie duidelijk is, kunnen we de procedure formaliseren als een stapsgewijs algoritme.

Algoritme voor bisectiemethode

De stappen voor het toepassen van het bisectiemethode-algoritme om de wortel van de vergelijking f(x) = 0 te vinden, zijn als volgt.

Stap 1) Kies initiële schattingen a, b en een tolerantiepercentage e.

Stap 2) Als f(a)f(b) >= 0, dan ligt de wortel niet in dit interval. In dat geval is er geen oplossing binnen [a, b].

Stap 3) Vind het middelpunt, c = (a + b)/2.

(i) Als de functiewaarde in het middenpunt f(c) = 0 is, dan is c de wortel. Ga naar stap 5.
(ii) Als f(a)f(c) < 0, ligt de wortel tussen a en c. Stel dan a = a, b = c.
(iii) Anderszins, stel a = c, b = b.

Stap 4) Als de absolute fout groter is dan de tolerantiegrens, oftewel (b – a) > e, ga dan terug naar stap 3.

Stap 5) Geef c weer als de geschatte wortel.

Laten we een voorbeeld bekijken van het bisectiemethode-algoritme in actie. We zullen de wortel van de volgende continue functie vinden met behulp van de formule van de bisectiemethode.

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

Bisectiemethode Voorbeeld

Stap 1) Laten we aannemen,

         een = -10,
         b = 10, en
         e = 1% of 0.01.

Stap 2) Nu gaan we na of f(a)f(b) >= 0 of niet.

         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

Daarom ligt de wortel van de bovenstaande functie in het interval [-10, 10].

Stap 3) Vervolgens wordt het middelpunt c berekend.

Nu moeten de volgende voorwaarden worden gecontroleerd:

(i) Of f(c) = 0:
         f(c) = f(0) = (0)³ - (0)² + 2 = 2, wat niet gelijk is aan 0.

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

De voorwaarde is voldaan. Voor de volgende iteratie zullen de waarden zijn:

         een = een = -10
         b = c = 0

Stap 4) Omdat (b – a) = (0 – (-10)) = 10 > 0.01, wordt het proces herhaald. De volgende iteraties worden weergegeven in de onderstaande tabel.

Stap 5) In de elfde iteratie wordt de voorwaarde in stap 4 onwaar. De benaderde wortel van deze vergelijking is dus -1.00586.

Na het afronden van een numeriek voorbeeld, presenteert het volgende gedeelte het logische diagram dat de volledige controlestroom weergeeft.

Bisectiemethode Logisch diagram

Het onderstaande stroomdiagram vat de beslissingslogica van de bisectiemethode samen, inclusief de controle van de haakjes, de update van het middelpunt en de tolerantietest.

Pseudo-Code

De onderstaande pseudocode weerspiegelt het algoritme en dient als blauwdruk voor het implementeren van de bisectiemethode in elke programmeertaal.

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

Bisectiemethode Voorbeeld in C/C++

De volgende C/C++ Het programma implementeert de bisectiemethode om de wortel van f(x) = x te vinden.³ - x² + 2 binnen het interval [-10, 10].

Input:

#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;
}

Output:

The root is :-1.00586

Bisectiemethode Voorbeeld in Python

De Python De onderstaande versie produceert met dezelfde logica ongeveer dezelfde wortel, waardoor deze ideaal is voor snelle experimenten en onderwijsdoeleinden.

Input:

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)

Output:

The root is :  -1.0059

Voordelen en beperkingen van de bisectiemethode

Zoals elke numerieke techniek heeft de bisectiemethode duidelijke sterke punten en een paar praktische nadelen. De onderstaande tabel vat de belangrijkste voor- en nadelen samen.

Toepassingen van de bisectiemethode

De bisectiemethode wordt gebruikt in veel praktische en moderne computerscenario's waar een robuuste stap voor het vinden van wortels vereist is.

• Technische simulaties: Het oplossen van niet-lineaire vergelijkingen die voorkomen in warmteoverdracht, vloeistofdynamica en constructieanalyse.
• Financiële modellering: Het berekenen van rendementen, interne rendementen en break-evenpunten in gevallen waar geen gesloten formules beschikbaar zijn.
• Machine learning en AI: Het bepalen van drempelwaarden, het kalibreren van modellen en het afstemmen van hyperparameters binnen AI-gestuurde numerieke oplossers.
• Computergrafiek: Het bepalen van snijpunten tussen stralen en oppervlakken en parameterwaarden langs krommen.
• Ingebedde systemen: Het benaderen van wortels in controllers met beperkte middelen, waar eenvoud en voorspelbaarheid belangrijker zijn dan snelheid.

Veelgestelde vragen