Bisektionsmetodens algoritme med eksempler

Hvad er bisektionsmetoden?

Bisektionsmetoden er en af ​​de mest grundlæggende numeriske teknikker til at finde roden af ​​et polynomium eller en transcendental ligning. Den fungerer ved at indsætte det interval, der indeholder roden, i parentes og derefter opdele dette interval i halvdele ved hver iteration, indtil roden er placeret inden for en acceptabel tolerance. På grund af denne parentesadfærd kaldes bisektionsmetoden også for bracketingmetoden.

Da dens funktionsmekanisme minder om binær søgning, er bisektionsmetoden også kendt som den binære søgemetode, halveringsmetoden eller dikotomimetoden. Den hviler på et stærkt teoretisk fundament: mellemværdisætningen, som garanterer, at en kontinuerlig funktion, der ændrer fortegn over et interval, skal krydse nul et sted inden for dette interval.

Med den grundlæggende definition på plads, lad os undersøge, hvorfor det er vigtigt at finde rødderne i ligninger, og hvordan bisektionsmetoden passer ind i det bredere billede.

Finde ligningers rødder

I denne diskussion fokuserer vi kun på ligninger med én uafhængig variabel. Sådanne ligninger kan være lineære eller ikke-lineære. Lineære ligninger beskriver grafen for en ret linje, mens ikke-lineære ligninger beskriver kurver og mere komplekse former.

Roden af ​​en ligning er værdien af ​​den uafhængige variabel, der opfylder ligningen. For eksempel er roden af ​​ligningen f(x) = 4 – x² = 0 er 2, fordi f(2) = 4 – 2² = 0.

Lad os betragte f(x) som en reel kontinuert funktion. Ifølge mellemværdisætningen har ligningen f(x) = 0 mindst én rod mellem a og b, når f(a)f(b) < 0. Med andre ord har funktionen f(x) en rod, "c", et sted mellem a og b.

Denne fortegnsændringsegenskab er præcis, hvad Bisection-metoden udnytter. Det næste afsnit viser, hvordan denne idé ser grafisk ud.

Grafisk repræsentation af bisektionsmetoden

Følgende graf repræsenterer bisektionsmetodens virkemåde. Ud fra grafen kan vi se, at den faktiske rod af ligningen er markeret med rødt.

Proceduren kan opsummeres som følger:

• Vi vælger først to indledende gæt, en₁ og b₁, for hvilken f(a₁)f(b₁) < 0. Ifølge mellemværdisætningen skal roden ligge i [a₁, b₁].
• Vi beregner derefter midtpunktet af en₁ og b₁, hvilket er b₂Det indledende interval er nu reduceret til [a₁, b₂] fordi f(a₁)f(b₂) < 0.
• På samme måde halveres intervallet igen og igen, indtil en omtrentlig løsning findes inden for den ønskede tolerance.

Med den geometriske intuition klar, kan vi nu formalisere proceduren som en trin-for-trin algoritme.

Bisektionsmetodealgoritme

Trinene til at anvende bisektionsmetoden til at finde roden af ​​ligningen f(x) = 0 er som følger.

Trin 1) Vælg de indledende gæt a, b og en tolerancerate e.

Trin 2) Hvis f(a)f(b) >= 0, så ligger roden ikke i dette interval. I så fald er der ingen løsning inden for [a, b].

Trin 3) Find midtpunktet, c = (a + b)/2.

(i) Hvis funktionsværdien ved midtpunktet f(c) = 0, så er c roden. Gå til trin 5.
(ii) Hvis f(a)f(c) < 0, ligger roden mellem a og c. Sæt da a = a, b = c.
(iii) Ellers sættes a = c, b = b.

Trin 4) Hvis den absolutte fejl er højere end toleranceraten, dvs. (b – a) > e, skal du gå tilbage til trin 3.

Trin 5) Vis c som den omtrentlige rod.

Lad os se et eksempel på bisektionsmetodens algoritme i aktion. Vi finder roden af ​​følgende kontinuerte funktion ved hjælp af bisektionsmetodens formel.

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

Eksempel på halvsektionsmetode

Trin 1) Lad os antage,

         a = -10,
         b = 10, og
         e = 1% eller 0.01.

Trin 2) Nu vil vi kontrollere, om f(a)f(b) >= 0 eller ej.

         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

Derfor ligger roden af ​​ovenstående funktion i intervallet [-10, 10].

Trin 3) Dernæst beregnes midtpunktet c.

Nu skal følgende forhold kontrolleres:

(i) Om f(c) = 0:
         f(c) = f(0) = (0)³ - (0)² + 2 = 2, hvilket ikke er lig med 0.

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

Betingelsen er opfyldt. For den næste iteration vil værdierne være:

         a = a = -10
         b = c = 0

Trin 4) Når (b – a) = (0 – (-10)) = 10 > 0.01, gentages processen. De næste iterationer er vist i tabellen nedenfor.

Trin 5) I den 11. iteration bliver betingelsen i trin 4 falsk. Den omtrentlige rod af denne ligning er således -1.00586.

Med et færdigt numerisk eksempel præsenterer næste afsnit det logiske diagram, der indfanger det fulde kontrolflow.

Bisektionsmetode logisk diagram

Flowchartet nedenfor opsummerer beslutningslogikken bag bisektionsmetoden, herunder bracketkontrol, midtpunktsopdatering og tolerancetest.

pseudoCode

Pseudokoden nedenfor afspejler algoritmen og fungerer som en skabelon til implementering af bisektionsmetoden i ethvert programmeringssprog.

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

Eksempel på halveringsmetode i C/C++

Følgende C/C++ Programmet implementerer bisektionsmetoden til at finde roden af ​​f(x) = x³ - x² + 2 inden for intervallet [-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

Eksempel på halveringsmetode i Python

Python Versionen nedenfor producerer den samme omtrentlige rod ved hjælp af identisk logik, hvilket gør den ideel til hurtig eksperimentering og undervisning.

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

Fordele og begrænsninger ved bisektionsmetoden

Som enhver numerisk teknik har bisektionsmetoden klare styrker og et par praktiske ulemper. Tabellen nedenfor opsummerer de vigtigste fordele og ulemper.

Anvendelser af bisektionsmetoden

Bisektionsmetoden bruges i mange praktiske og moderne databehandlingsscenarier, hvor et robust rodfindingstrin er påkrævet.

• Ingeniørsimuleringer: Løsning af ikke-lineære ligninger, der optræder i varmeoverføring, fluiddynamik og strukturanalyse.
• Finansiel modellering: Beregning af udbytter, interne afkastsatser og break-even-punkter, hvor lukkede løsninger ikke findes.
• Maskinlæring og AI: Lokalisering af tærskler, kalibrering af modeller og finjustering af hyperparametre i AI-drevne numeriske løsere.
• Computergrafik: Bestemmelse af stråle-overfladeskæringer og parameterværdier langs kurver.
• Indlejrede systemer: Tilnærmelse af rødder i controllere med lavt ressourceforbrug, hvor enkelhed og forudsigelighed er mere værdifuldt end hastighed.

Ofte Stillede Spørgsmål