Metoda půlení – co je, algoritmus a příklad

Co je metoda bisekce?

Metoda bisekce je jedním ze základních numerických řešení pro nalezení kořene polynomiální rovnice. Uzavře interval, ve kterém leží kořen rovnice, a v každé iteraci je rozdělí na poloviny, dokud nenajde kořen. Metoda půlení se tedy také nazývá metoda bracketingu.

Protože je však pracovní mechanismus podobný binárnímu vyhledávacímu algoritmu, je metoda bisekce známá také jako metoda binárního vyhledávání, metoda půlení nebo metoda dichotomie. Primárně je založen na teorému střední hodnoty.

Hledání kořenů rovnic

V tomto příkladu uvažujeme pouze rovnice s jednou nezávislou proměnnou. Může být lineární nebo nelineární. Lineární rovnice se používají k zobrazení grafu přímky, zatímco nelineární rovnice se používají k zobrazení křivek.

Kořen rovnice znamená hodnotu nezávisle proměnné, která rovnici vyhovuje. Například: kořen rovnice f(x)= 4-x² = 0 je 2, protože f(2) = 4-2² = 0.

Uvažujme f(x) jako skutečnou spojitou funkci. Podle věty o střední hodnotě má rovnice f(x)=0 alespoň jeden kořen mezi a a b, pokud f(a)f(b) < 0. Funkce f(x) má kořen „c,“ mezi a a b.

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

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

Začít s:

Nejprve jsme vzali dva počáteční odhady, a₁ a b_1, pro které f(a₁)f(b₁) < 0. Podle věty o střední hodnotě by kořen měl ležet v [a₁, b₁].
Můžeme najít střed a₁ a b_1,což je b₂. Počáteční interval je tedy nyní snížen na [a₁, b₂] protože f(a₁)f(b₂) < 0.
Stejným způsobem se interval zkracuje, dokud není nalezeno přibližné řešení.

Algoritmus bisekční metody

Kroky pro použití algoritmu metody půlení 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) Jestliže f(a)f(b) >=0, pak kořen v tomto intervalu neleží. Nebude tedy žádné řešení.

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

(i) Je-li funkční hodnota středu f(c) = 0, pak c je kořen. Přejděte ke kroku 5.
(ii) Jestliže f(a)f(c) < 0, kořen leží mezi a a c. Potom nastavte a = a, b = c.
(iii) Jinak nastavte a = c, b = b.

Krok 4) Pokud je absolutní chyba vyšší než míra tolerance nebo (ba) > e, přejděte ke kroku 3.

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

Podívejme se na příklad algoritmu metody bisekce.
Musíme najít kořen následující spojité funkce pomocí vzorce metody půlení.

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)3 – (-10)2 + 2 = -1098
         f(b) = f(10) = (10)3 – (10)2 + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

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

Krok 3) Potom se nejprve vypočítá střed c.

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

(i) zda f(c) = 0:
f(c) = f(0) = (0)3 – (0)2 + 2 = 2 ≠ 0

(ii) pokud 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 (ba) = (0-(-10)) = 10>0.05, proces se bude opakovat. Další iterace jsou uvedeny v tabulce.

Opakování	a	b	c	ba	f(c)
1	-10	0	0	10	2
2	-5	0	-5	5	-148
3	-2.5	0	-2.5	2.5	-19.875
4	-1.25	0	-1.25	1.25	-1.52562
5	-1.25	-0.625	-0.625	0.625	1.36523
6	-1.25	-0.9375	-0.9375	0.3125	0.297119
7	-1.09375	-0.9375	-1.09375	0.15625	-0.50473
8	-1.01562	-0.9375	-1.01562	0.078125	-0.0791054
9	-1.01562	-0.976562	-0.976562	0.0390625	0.115003
10	-1.01562	-0.996094	-0.996094	0.0195312	0.0194703
11	-1.00586	-0.996094	-1.00586	0.00976562	-0.0294344

Krok 5) V 11. iteraci bude podmínka kroku 4 nepravdivá. Kořen této rovnice je tedy -1.00586.

Logický diagram metody půlení

Pseudo kód

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++

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