Algoritmus metody půlení s příklady

Co je to bisekční metoda?

Metoda půlení je jednou z nejzákladnějších numerických technik pro nalezení kořene polynomu nebo transcendentální rovnice. Funguje tak, že se interval obsahující kořen zahradkuje a v každé iteraci se tento interval rozdělí na poloviny, dokud se kořen nenachází v rámci přijatelné tolerance. Kvůli tomuto chování při zahradkování se metoda půlení označuje také jako metoda zahradkování.

Protože její pracovní mechanismus se podobá binárnímu vyhledávání, je metoda půlení známá také jako metoda binárního vyhledávání, metoda půlení nebo metoda dichotomie. Spočívá na silném teoretickém základu: větě o mezilehlé hodnotě, která zaručuje, že spojitá funkce měnící znaménko v intervalu musí někde uvnitř tohoto intervalu procházet nulou.

Po stanovení základní definice se pojďme podívat, proč je hledání kořenů rovnic důležité a jak do tohoto širšího obrazu zapadá metoda bisekce.

Hledání kořenů rovnic

V této diskusi se zaměříme pouze na rovnice s jednou nezávislou proměnnou. Takové rovnice mohou být lineární nebo nelineární. Lineární rovnice popisují graf přímky, zatímco nelineární rovnice popisují křivky a složitější tvary.

Kořen rovnice je hodnota nezávislé proměnné, která splňuje danou rovnici. Například kořen rovnice f(x) = 4 – x² = 0 je 2, protože f(2) = 4 – 2² = 0.

Uvažujme f(x) jako reálnou spojitou funkci. Podle věty o mezilehlé hodnotě má rovnice f(x) = 0 alespoň jeden kořen mezi a a b, kdykoli f(a)f(b) < 0. Jinými slovy, funkce f(x) má kořen „c“ někde mezi a a b.

Tato vlastnost změny znaménka je přesně to, co využívá metoda půlení. Následující část ukazuje, jak tato myšlenka vypadá graficky.

Grafické znázornění metody půlení

Následující graf znázorňuje pracovní mechanismus metody bisekce. Z grafu vidíme, že skutečný kořen rovnice je označen červeně.

Postup lze shrnout následovně:

• Nejprve si vybereme dva počáteční odhady, a₁ a b₁, pro které f(a)₁)f(b₁) < 0. Podle věty o mezilehlé hodnotě musí kořen ležet v [a₁, b₁].
• Pak vypočítáme střed₁ a b₁, což je b₂Počáteční interval je nyní zkrácen na [a₁, b₂] protože f(a₁)f(b₂) < 0.
• Stejným způsobem se interval opakovaně snižuje na polovinu, dokud se nenalezne přibližné řešení v rámci požadované tolerance.

S jasnou geometrickou intuicí můžeme nyní formalizovat postup jako krok za krokem algoritmus.

Algoritmus bisekční metody

Kroky pro aplikaci algoritmu bisekční metody k nalezení kořene rovnice f(x) = 0 jsou následující.

Krok 1) Vyberte počáteční odhady a, b a míru tolerance e.

Krok 2) Pokud f(a)f(b) >= 0, pak kořen neleží v tomto intervalu. V takovém případě neexistuje řešení v intervalu [a, b].

Krok 3) Najděte střed, c = (a + b)/2.

(i) Pokud je hodnota funkce ve středu f(c) = 0, pak je c kořenem. Přejděte ke kroku 5.
(ii) Pokud f(a)f(c) < 0, kořen leží mezi a a c. Pak nechť a = a, b = c.
(iii) Jinak položme a = c, b = b.

Krok 4) Pokud je absolutní chyba vyšší než toleranční poměr, tj. (b – a) > e, vraťte se ke kroku 3.

Krok 5) Zobrazte c jako přibližný kořen.

Podívejme se na příklad algoritmu bisekční metody v akci. Pomocí vzorce bisekční metody najdeme kořen následující spojité funkce.

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

Příklad metody půlení

Krok 1) Předpokládejme,

         a = -10,
         b = 10 a
         e = 1 % nebo 0.01.

Krok 2) Nyní zkontrolujeme, zda f(a)f(b) >= 0 nebo ne.

         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

Kořen výše uvedené funkce tedy leží v intervalu [-10, 10].

Krok 3) Dále se vypočítá středový bod c.

Nyní je třeba zkontrolovat následující podmínky:

(i) Zda f(c) = 0:
         f(c) = f(0) = (0)³ - (0)² + 2 = 2, což se nerovná 0.

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

Podmínka je splněna. Pro další iteraci budou hodnoty:

         a = a = -10
         b = c = 0

Krok 4) Protože (b – a) = (0 – (-10)) = 10 > 0.01, proces se opakuje. Další iterace jsou uvedeny v tabulce níže.

Krok 5) V 11. iteraci se podmínka z kroku 4 stává nepravdivou. Přibližný kořen této rovnice je tedy -1.00586.

Po dokončení numerického příkladu představuje další část logický diagram, který zachycuje celý tok řízení.

Logický diagram metody půlení

Níže uvedený vývojový diagram shrnuje rozhodovací logiku metody bisekce, včetně kontroly závorek, aktualizace středu a testu tolerance.

PseudoCode

Níže uvedený pseudokód zrcadlí algoritmus a slouží jako plán pro implementaci metody bisekce v jakémkoli programovacím jazyce.

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

Příklad metody půlení v C/C++

Následující C/C++ Program implementuje metodu půlení pro nalezení kořene funkce f(x) = x³ - X² + 2 v intervalu [-10, 10].

Vstup:

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

Výstup:

The root is :-1.00586

Příklad metody půlení v Python

Jedno Python Níže uvedená verze vytváří stejný přibližný kořen s použitím identické logiky, což ji činí ideální pro rychlé experimentování a výuku.

Vstup:

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)

Výstup:

The root is :  -1.0059

Výhody a omezení metody bisekce

Stejně jako každá numerická technika má i metoda bisekce jasné silné stránky a několik praktických nevýhod. Níže uvedená tabulka shrnuje nejdůležitější výhody a nevýhody.

Aplikace metody půlení

Metoda půlení se používá v mnoha praktických a moderních výpočetních scénářích, kde je vyžadován robustní krok hledání kořenů.

• Inženýrské simulace: Řešení nelineárních rovnic, které se objevují v oblasti přenosu tepla, dynamiky tekutin a strukturální analýzy.
• Finanční modelování: Výpočet výnosů, vnitřních mír návratnosti a bodů zvratu tam, kde neexistují uzavřená řešení.
• Strojové učení a umělá inteligence: Lokalizace prahových hodnot, kalibrace modelů a ladění hyperparametrů v numerických řešičích řízených umělou inteligencí.
• Počítačová grafika: Určení průsečíků paprsků s plochou a hodnot parametrů podél křivek.
• Vestavěné systémy: Aproximace kořenů v nízkopříkonových řídicích jednotkách, kde je jednoduchost a předvídatelnost cennější než rychlost.

Nejčastější dotazy