Felezési módszer – Mi az, algoritmus és példa

Mi az a felezési módszer?

A felezési módszer az egyik alapvető numerikus megoldás a polinomiális egyenlet gyökerének megtalálására. Zárójelbe teszi azt az intervallumot, amelyben az egyenlet gyöke található, és minden iterációban felére osztja őket, amíg meg nem találja a gyökeret. Így a felező módszert zárójeles módszernek is nevezik.

Mivel azonban a működési mechanizmus hasonló a bináris keresési algoritmushoz, a felezési módszert bináris keresési módszernek, felező módszernek vagy dichotómia módszernek is nevezik. Elsősorban a Köztes érték tételen alapul.

Egyenletek gyökereinek megtalálása

Ebben a példában csak egy független változóval rendelkező egyenleteket veszünk figyelembe. Lehet lineáris vagy nemlineáris. A lineáris egyenletek az egyenes grafikonját ábrázolják, míg a nemlineáris egyenletek a görbék ábrázolására szolgálnak.

Az egyenlet gyöke az egyenletet kielégítő független változó értékét jelenti. Például: egy f(x)= 4-x egyenlet gyöke² = 0 2, mert f(2) = 4-2² = 0.

Tekintsük f(x)-t valós folytonos függvénynek. A köztes érték tétele szerint az f(x)=0 egyenletnek legalább egy gyöke van a és b között, ha f(a)f(b) < 0. Az f(x) függvénynek van egy gyöke, „c” a és b között.

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áthatjuk, hogy az egyenlet gyöke pirossal van jelölve.

Mindenekelőtt:

• Először két kezdeti sejtést tettünk, a₁ és b_1, amelyre f(a₁)f(b₁) < 0. A köztes érték tétele szerint a gyöknek [a₁, b₁].
• Megtalálhatjuk a felezőpontját₁ és b_1, ami b₂. Így a kezdeti intervallum most [a₁, b₂] mert f(a₁)f(b₂) < 0.
• Ugyanígy csökkentjük az intervallumot, amíg a közelítő megoldást meg nem találjuk.

Felezési módszer algoritmus

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

Step 1) Válasszon kiindulási a, b tippeket és e tűréshatárt

Step 2) Ha f(a)f(b) >=0, akkor a gyök nem ebben az intervallumban található. Így nem lesz megoldás.

Step 3) Keresse meg a felezőpontot, c = (a+b)/2

(i) Ha az f(c) felezőpont függvényértéke = 0, akkor c a gyök. Folytassák az 5. lépéssel.
(ii) Ha f(a)f(c) < 0, akkor a gyök a és c között van. Ezután állítsa be a = a, b = c.
(iii) Egyéb esetben a = c, b = b.

Step 4) Ha az abszolút hiba nagyobb, mint a tűréshatár vagy (ba) > e, folytassa a 3. lépéssel.

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

Lássunk egy példát a felezési módszer algoritmusára.
Meg kell találnunk a következő folytonos függvény gyökerét a felező módszer képletével.

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

Ezért a fenti függvény gyökere ebben az intervallumban van [-10, 10].

Step 3) Ekkor először a c felezőpont kerül kiszámításra.

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

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

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

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

         a = a = -10
         b = c = 0

Step 4) Mivel (ba) = (0-(-10)) = 10>0.05, a folyamat megismétlődik. A következő iterációk a táblázatban láthatók.

Ismétlés	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

Step 5) A 11. iterációban a 4. lépés feltétele hamis lesz. Így ennek az egyenletnek a gyöke -1.00586.

Felezési módszer logikai diagramja

Ál-Code

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

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

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

Íme a felezési módszer előnyei és hátrányai:

Érvek	Hátrányok
Könnyen és egyszerűen megvalósítható gyökérkeresési módszer.	A konvergencia lassú, mert egyszerűen az intervallum felezésén alapul.
Mivel a gyökér zárójelben van, mindig konvergens.	Ha az egyik kezdeti találgatás közel van a gyökérhez, a gyökér elérése több iterációt igényel.
A hibaarány az iterációk számának növelésével vagy csökkentésével szabályozható.