Felezési módszer algoritmusa példákkal

Mi a felezési módszer?

A felezési módszer az egyik legalapvetőbb numerikus technika polinom vagy transzcendentális egyenlet gyökének megtalálására. Úgy működik, hogy zárójelbe teszi a gyökeret tartalmazó intervallumot, majd minden iterációban ezt az intervallumot felére osztja, amíg a gyök elfogadható tűréshatáron belülre nem kerül. Ezen zárójelezési viselkedés miatt a felezési módszert zárójelezési módszernek is nevezik.

Mivel a működési mechanizmusa a bináris kereséshez hasonlít, a felezési módszert bináris keresési módszernek, felezési módszernek vagy dichotómiai módszernek is nevezik. Erős elméleti alapokon nyugszik: a közbenső érték tételén, amely garantálja, hogy egy folytonos, előjelet változtató függvénynek valahol az adott intervallumon belül át kell mennie a nullán.

Miután az alapvető definíciót tisztáztuk, vizsgáljuk meg, miért fontos az egyenletek gyökeinek megtalálása, és hogyan illeszkedik a felezési módszer ebbe a tágabb képbe.

Egyenletek gyökereinek megtalálása

Ebben a megbeszélésben csak az egy független változóval rendelkező egyenletekre összpontosítunk. Az ilyen egyenletek lehetnek lineárisak vagy nemlineárisak. A lineáris egyenletek az egyenes vonal grafikonját írják le, míg a nemlineáris egyenletek görbéket és összetettebb alakzatokat.

Egy egyenlet gyöke a független változó azon értéke, amely kielégíti az egyenletet. Például az f(x) = 4 – x egyenlet gyöke.² = 0 az 2, mert f(2) = 4 – 2² = 0.

Tekintsük az f(x) függvényt egy valós folytonos függvénynek. A közbenső értéktétel szerint az f(x) = 0 egyenletnek legalább egy gyöke van a és b között, ha f(a)f(b) < 0. Más szóval, az f(x) függvénynek van egy gyöke, „c”, valahol a és b között.

Pontosan ezt az előjelváltási tulajdonságot használja ki a felezési módszer. A következő szakasz bemutatja, hogyan néz ki ez az ötlet grafikusan.

A felezési módszer grafikus ábrázolása

A következő grafikon a felezési módszer működési mechanizmusát mutatja be. A grafikonon látható, hogy az egyenlet tényleges gyöke pirossal van jelölve.

Az eljárás a következőképpen foglalható össze:

• Először két kezdeti tippet választunk, a₁ és b₁, amelyre f(a₁)f(b₁) < 0. A közbenső értéktétel szerint a gyöknek az [a₁, b₁].
• Ezután kiszámítjuk a középpontját₁ és b₁, ami b₂A kezdeti intervallum most [a]-ra csökken.₁, b₂] mert f(a₁)f(b₂) < 0.
• Ugyanígy az intervallumot újra és újra felezzük, amíg egy közelítő megoldást nem találunk a kívánt tűréshatáron belül.

Miután a geometriai intuíció világos, most már formalizálhatjuk az eljárást lépésről lépésre haladó algoritmusként.

Felezési módszer algoritmus

Az f(x) = 0 egyenlet gyökének megtalálásához a felezési módszer algoritmusának alkalmazásának lépései a következők.

Step 1) Válasszon kezdeti becsléseket (a, b), és tolerancia rátát (e).

Step 2) Ha f(a)f(b) >= 0, akkor a gyök nem ebben az intervallumban található. Ebben az esetben nincs megoldás az [a, b] intervallumon belül.

Step 3) Határozza meg a felezőpontot, c = (a + b)/2.

(i) Ha a függvényérték a felezőpontban f(c) = 0, akkor c a gyök. Folytasd az 5. lépéssel.
(ii) Ha f(a)f(c) < 0, akkor a gyök a és c között van. Ekkor legyen a = a, b = c.
(iii) Egyébként állítsuk be, hogy a = c, b = b.

Step 4) Ha az abszolút hiba nagyobb, mint a tűréshatár, azaz (b – a) > e, akkor térjünk vissza a 3. lépéshez.

Step 5) Jelenítse meg c hozzávetőleges gyökérként.

Nézzünk egy példát a felezési módszer algoritmusára működés közben. A felezési módszer képletével megkeressük a következő folytonos függvény gyökét.

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

Felezési módszer példa

Step 1) Tegyük fel,

         a = -10,
         b = 10, és
         e = 1% vagy 0.01.

Step 2) Most megvizsgáljuk, hogy f(a)f(b) >= 0 vagy sem.

         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

Tehát a fenti függvény gyöke a [-10, 10] intervallumban található.

Step 3) Ezután kiszámítjuk a c középpontot.

Most a következő feltételeket kell ellenőrizni:

(i) F(c) = 0:
         f(c) = f(0) = (0)³ - (0)² + 2 = 2, ami nem egyenlő 0-val.

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

A feltétel teljesül. A következő iterációban az értékek a következők lesznek:

         a = a = -10
         b = c = 0

Step 4) Mivel (b – a) = (0 – (-10)) = 10 > 0.01, a folyamat megismétlődik. A következő iterációkat az alábbi táblázat mutatja.

Step 5) A 11. iterációban a 4. lépésben szereplő feltétel hamissá válik. Így az egyenlet közelítő gyöke -1.00586.

Egy numerikus példa bemutatása után a következő szakasz bemutatja a teljes vezérlési folyamatot bemutató logikai diagramot.

Felezési módszer logikai diagramja

Az alábbi folyamatábra összefoglalja a felezési módszer döntési logikáját, beleértve a zárójel-ellenőrzést, a középpont-frissítést és a tűrésvizsgálatot.

Ál-Code

Az alábbi pszeudokód tükrözi az algoritmust, és tervrajzként szolgál a felezőmódszer bármely programozási nyelven történő megvalósításához.

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

Felezési módszer példa C/C++

A következő C/C++ A program a felezési módszert valósítja meg az f(x) = x függvény gyökének meghatározásához.³ - x² + 2 a [-10, 10] intervallumon belül.

Bemenet:

#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

Felezési módszer példa in Python

Az Python Az alábbi verzió ugyanazt a közelítő gyököt állítja elő azonos logika felhasználásával, ami ideálissá teszi a gyors kísérletezéshez és tanításhoz.

Bemenet:

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

A felezési módszer előnyei és korlátai

Mint minden numerikus technikának, a felezési módszernek is vannak egyértelmű előnyei és néhány gyakorlati hátránya. Az alábbi táblázat összefoglalja a legfontosabb előnyöket és hátrányokat.

A felezési módszer alkalmazásai

A felezési módszert számos gyakorlati és modern számítástechnikai helyzetben használják, ahol robusztus gyökkeresési lépésre van szükség.

• Mérnöki szimulációk: A hőátadásban, a folyadékdinamikában és a szerkezetanalízisben megjelenő nemlineáris egyenletek megoldása.
• Pénzügyi modellezés: Hozamok, belső megtérülési ráták és fedezeti pontok kiszámítása olyan esetekben, amikor nem léteznek zárt alakú megoldások.
• Gépi tanulás és mesterséges intelligencia: Küszöbértékek meghatározása, modellek kalibrálása és hiperparaméterek finomhangolása mesterséges intelligencia által vezérelt numerikus megoldókban.
• Számítógépes grafika: Sugár-felület metszéspontok és paraméterértékek meghatározása görbék mentén.
• Beágyazott rendszerek: Gyökök közelítése alacsony erőforrás-igényű vezérlőkben, ahol az egyszerűség és a kiszámíthatóság értékesebb a sebességnél.

GYIK