Puolitusmenetelmän algoritmi esimerkkeineen

Mikä on puolitusmenetelmä?

Puolitusmenetelmä on yksi perustavanlaatuisimmista numeerisista tekniikoista polynomi- tai transsendentaaliyhtälön juuren löytämiseksi. Se toimii sulkemalla välin, joka sisältää juuren, ja jakamalla sitten kyseisen välin puoliksi jokaisella iteraatiolla, kunnes juuri sijaitsee hyväksyttävän toleranssin sisällä. Tämän sulkemiskäyttäytymisen vuoksi puolitusmenetelmää kutsutaan myös sulkemismenetelmäksi.

Koska sen toimintamekanismi muistuttaa binäärihakua, puolitusmenetelmä tunnetaan myös binäärihakumenetelmänä, puolitusmenetelmänä tai dikotomiamenetelmänä. Se perustuu vahvaan teoreettiseen perustaan: väliarvolauseeseen, joka takaa, että jatkuvan, merkkiä muuttavan funktion on ylitettävä nolla jossain kyseisen aikavälin sisällä.

Kun perusmääritelmä on olemassa, tutkitaanpa, miksi yhtälöiden juurien löytäminen on tärkeää ja miten puolitusmenetelmä sopii tähän laajempaan kuvaan.

Yhtälöiden juurten löytäminen

Tässä keskustelussa keskitymme vain yhtälöihin, joissa on yksi riippumaton muuttuja. Tällaiset yhtälöt voivat olla lineaarisia tai epälineaarisia. Lineaariset yhtälöt kuvaavat suoran viivan kuvaajaa, kun taas epälineaariset yhtälöt kuvaavat käyriä ja monimutkaisempia muotoja.

Yhtälön juuri on yhtälön toteuttavan riippumattoman muuttujan arvo. Esimerkiksi yhtälön juuri f(x) = 4 – x² = 0 on 2, koska f(2) = 4 – 2² = 0.

Tarkastellaan funktiota f(x) reaalilukuna jatkuvana funktiona. Väliarvolauseen mukaan yhtälöllä f(x) = 0 on ainakin yksi juuri a:n ja b:n välillä aina, kun f(a)f(b) < 0. Toisin sanoen funktiolla f(x) on juuri, ”c”, jossain a:n ja b:n välillä.

Tätä merkkimuutosominaisuutta hyödyntää juuri puolitusmenetelmä. Seuraavassa osiossa näytetään, miltä tämä idea näyttää graafisesti.

Puolitusmenetelmän graafinen esitys

Seuraava kaavio esittää puolitusmenetelmän toimintamekanismia. Kaaviosta näemme, että yhtälön varsinainen juuri on merkitty punaisella.

Menettely voidaan tiivistää seuraavasti:

• Valitsemme ensin kaksi alustavaa arvausta, a.₁ ja b₁, jolle f(a₁)f(b₁) < 0. Väliarvolauseen mukaan juuren täytyy sijaita [a₁, b₁].
• Laskemme sitten a:n keskipisteen₁ ja b₁, joka on b₂Alkuperäinen aikaväli on nyt lyhennetty arvoon [a₁, b₂] koska f(a₁)f(b₂) <0.
• Samalla tavalla aikaväli puolitetaan yhä uudelleen, kunnes löydetään likimääräinen ratkaisu halutun toleranssin sisällä.

Kun geometrinen intuitio on selvä, voimme nyt formalisoida proseduurin askel askeleelta etenevänä algoritmina.

Bisection Method Algorithm

Puolitusmenetelmäalgoritmin soveltamisen vaiheet yhtälön f(x) = 0 juuren löytämiseksi ovat seuraavat.

Vaihe 1) Valitse alkuarviot a, b ja toleranssiaste e.

Vaihe 2) Jos f(a)f(b) >= 0, niin juuri ei ole tällä välillä. Tässä tapauksessa ei ole ratkaisua välillä [a, b].

Vaihe 3) Etsi keskipiste, c = (a + b)/2.

(i) Jos funktion arvo keskipisteessä f(c) = 0, niin c on juuri. Siirry vaiheeseen 5.
(ii) Jos f(a)f(c) < 0, niin juuri on a:n ja c:n välissä. Aseta silloin a = a, b = c.
(iii) Muussa tapauksessa asetetaan a = c ja b = b.

Vaihe 4) Jos absoluuttinen virhe on suurempi kuin toleranssiarvo, eli (b – a) > e, palaa vaiheeseen 3.

Vaihe 5) Näytä c likimääräisenä juurena.

Katsotaanpa esimerkkiä puolitusmenetelmän algoritmista toiminnassa. Löydämme seuraavan jatkuvan funktion juuren käyttämällä puolitusmenetelmän kaavaa.

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

Esimerkki puolittamisesta

Vaihe 1) Oletetaan,

         a = -10,
         b = 10 ja
         e = 1 % tai 0.01.

Vaihe 2) Nyt tarkistetaan onko f(a)f(b) >= 0 vai ei.

         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

Näin ollen yllä olevan funktion juuri on välillä [-10, 10].

Vaihe 3) Seuraavaksi lasketaan keskipiste c.

Seuraavat ehdot on nyt tarkistettava:

(i) Onko f(c) = 0:
         f(c) = f(0) = (0)³ - (0)² + 2 = 2, joka ei ole yhtä suuri kuin 0.

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

Ehto täyttyy. Seuraavalla iteraatiolla arvot ovat:

         a = a = -10
         b = c = 0

Vaihe 4) Koska (b – a) = (0 – (-10)) = 10 > 0.01, prosessi toistetaan. Seuraavat iteraatiot on esitetty alla olevassa taulukossa.

Vaihe 5) Yhdennessätoista iteraatiossa vaiheen 4 ehto muuttuu epätosiksi. Näin ollen yhtälön likimääräinen juuri on -1.00586.

Numeerisen esimerkin jälkeen seuraavassa osiossa esitetään looginen kaavio, joka kuvaa koko ohjausvirran.

Puolittamismenetelmän looginen kaavio

Alla oleva vuokaavio tiivistää puolitusmenetelmän päätöksentekologiikan, mukaan lukien sulkujen tarkistuksen, keskipisteen päivityksen ja toleranssitestin.

Pseudo-Code

Alla oleva pseudokoodi peilaa algoritmia ja toimii pohjana puolitusmenetelmän toteuttamiselle millä tahansa ohjelmointikielellä.

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

Esimerkki puolittamisesta C/C++

Seuraavat C/C++ ohjelma toteuttaa puolitusmenetelmän löytääkseen f(x) = x -funktion juuren³ - x² + 2 välillä [-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;
}

lähtö:

The root is :-1.00586

Esimerkki puolittamisesta menetelmässä Python

Python Alla oleva versio tuottaa saman likimääräisen juuren käyttämällä identtistä logiikkaa, mikä tekee siitä ihanteellisen nopeaan kokeiluun ja opetukseen.

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)

lähtö:

The root is :  -1.0059

Puolitusmenetelmän edut ja rajoitukset

Kuten kaikilla numeerisilla tekniikoilla, puolitusmenetelmällä on selkeitä vahvuuksia ja muutamia käytännön haittoja. Alla oleva taulukko kokoaa yhteen tärkeimmät hyvät ja huonot puolet.

Puolitusmenetelmän sovellukset

Puolitusmenetelmää käytetään monissa käytännön ja nykyaikaisissa laskentatilanteissa, joissa vaaditaan vankkaa juurenlöytövaihetta.

• Tekniset simulaatiot: Lämmönsiirrossa, virtausdynamiikassa ja rakenneanalyysissä esiintyvien epälineaaristen yhtälöiden ratkaiseminen.
• Talousmallinnus: Tuottojen, sisäisten tuottoprosenttien ja kannattavuusrajojemme laskeminen silloin, kun suljetun muodon ratkaisuja ei ole.
• Koneoppiminen ja tekoäly: Kynnysarvojen paikantaminen, mallien kalibrointi ja hyperparametrien virittäminen tekoälypohjaisissa numeerisissa ratkaisimissa.
• Tietokonegrafiikka: Säteen ja pinnan leikkauspisteiden ja parametriarvojen määrittäminen käyriä pitkin.
• Sulautetut järjestelmät: Juurten approksimointi vähän resursseja kuluttavissa ohjaimissa, joissa yksinkertaisuus ja ennustettavuus ovat arvokkaampia kuin nopeus.

UKK