Gyökök szétválasztása

A matematika numerikus analízis nevű ágában a gyökök szétválasztása algoritmikus eljárás amely hozzásegít egy polinom adott véges, zárt I intervallumba eső valós gyökeinek közelítő meghatározására. Az eljárás eredményeképpen I-t kisebb I₁, I₂, I₃,..., I_n intervalumokra osztjuk, amelyek mind a polinomnak legfeljebb egy gyökét tartalmazzák, és arra is választ kapunk, hogy az I_k-k közül melyek tartalmaznak egy gyököt, és melyek egyet sem.

A gyökök szétválasztása a feladat természetétől függően önmagában is alkalmas a gyökök meghatározására, ha ugyanis a részintervallumok mérete kisebb, mint az a pontosság, amellyel meg kívánjuk határozni a polinom gyökeit, akkor azzal, hogy tudjuk, melyik intervallumok tartalmaznak gyököt, máris a kívánt pontossággal ismerjük a zérushelyeket. Ellenkező esetben az egyes gyököket tartalmazó részintervallumokra valamilyen más gyökkereső algoritmust alkalmazunk. Ilyenkor a gyökök szétválasztása azért hasznos, mert a legtöbb módszer kizárólag egyetlen gyök megkeresésére alkalmas, tehát alkalmazásukhoz szükség van a gyökök szétválasztására, mint előkészítő lépésre.

Az eljárás eredményes alkalmazásához tudnunk kell, hogy az adott intervallumban a polinomnak hány gyöke van. Ezt például a Descartes-féle előjelszabály vagy más függvénydiszkussziós eljárás segítségével deríthetjük ki.

Az eljárás elméleti hátterét a Bolzano-tétel adja. Nem csak polinomokra alkalmazható, hanem általánosítható tetszőleges valós függvényre is, amely az I intervallumon folytonos, és véges sok zérushellyel bír.

Elméleti háttér

Ha a karakterisztikus méretek alapján lerögzítettük, hogy mekkora pontosságot várunk el a közelítő megoldástól, azonosíthatjuk azokat a rövid szakaszokat, melyeken belül egyetlen gyök található. Ebben a következő tétel van segítségünkre:

Tétel:

• 1. ha az f(x) függvény folytonos az [a, b] intervallumon és az intervallum két végén ellentétes előjelű, akkor legalább egy vagy páratlan számú gyöke található az intervallum belsejében.
• 2. ha az f(x) függvény folytonos az [a, b] intervallumon és az intervallum két végén azonos előjelű, akkor vagy nincs gyöke vagy páros számú gyöke található az intervallum belsejében.

Az eljárás menete

Számunkra tehát az olyan szakaszok érdekesek, melyek végpontjaiban a függvény behelyettesítési értékei az abszcissza két oldalán helyezkednek el, azaz kielégítik az f(a)f(b) < 0 közrezárási feltételt. Ennek biztosításához ismét a függvény karakterisztikus méretére van szükségünk. Az "aprót" úgy határozzuk meg, mint a legkisebb x irányú karakterisztikus méretnél jóval, mondjuk két-három nagyságrenddel kisebb intervallumot. Az eljárás a következő: egy x_min, x_max intervallumon, adott kis h lépésekben "araszolunk" végig. Minden lépésben ellenőrizzük, hogy a végpontokban vett függvényértékek különböző előjelűek-e. Ha igen, akkor megjegyezzük a végpontok helyét. Az eljárás a végpontok egy-egy tömbjét téríti vissza. Pszeudokódban ugyanez:

1: function Gyökszétválasztás( in: f, xmin, xmax, h out: (ai), (bi))
2: *** f a tanulmányozott függvény, xmin, xmax az intervallum határai, h a lépésköz, (ai), (bi) a gyököket tartalmazó intervallumok végpontjai
3: pre xmax > xmin
4: x → xmin
5: i → 1
6: while x < xmax do
7: y → x + h
8: if f(x)f(y) < 0 then *** közrezárási feltétel
9: ai x
10: bi y
11: i → i + 1
12: end if
13: x → y
14: end while
15: return (ai); (bi)
16: end function

Végső következtetésként megállapíthatjuk, hogy a gyökök szétválasztására nem létezik általános érvényű numerikus módszer. Az f(x) függvény viselkedésének bizonyos mértékű ismerete minden esetben szükséges.

Források

• Lázár Zsolt, Lázár József, Járai-Szabó Ferenc: Numerikus módszerek