Főmenü megnyitása
Az iteráció lényege az XKCD szerint.

Az iteráció egy gyakori fogalom a matematikában és az informatikában. Az iteráció valójában egy függvény ismételt végrehajtását jelenti az előző függvényértéken. A szabályos fraktálok némelyikét is iterációs algoritmusokkal lehet létrehozni, ilyen pl. a Koch-görbe. Valójában az iteráció a rekurzió egy speciális esete, amikor egy sorozat következő tagja az előtte lévőtől függ. A leggyakoribb alkalmazási területük a numerikus matematika, ahol a keresett értéket iterációs sorozattal közelítjük.

Tartalomjegyzék

DefinícióSzerkesztés

Legyen   függvény, és  . Ekkor iterációs sorozatnak nevezzük az alábbi sorozatot:

 
 

vagy a sorozatokra használt jelölésekkel:

 
 

Az iterációs sorozat egyértelműen meghatározott, ennek belátására a rekurziós definíció tételét kell az   párra alkalmazni.

AlkalmazásokSzerkesztés

Az iterációs eljárásoknak számtalan alkalmazásuk van, elsősorban egyszerűségüknek köszönhetően. Ennek révén a matematikában sorozatok vizsgálatára alkalmazzák, a számítástechnikában pedig főleg tárhelyspórolási célokkal.

SorozatokSzerkesztés

Az iterációs sorozatok a rekurzív sorozatok speciális esetei, méghozzá ahol a rekurziós függvény egyváltozós. Ezen sorozatok felhasználása meglehetősen széleskörű, különösen a numerikus számítások során gyakori a használatuk. Jellemző az iterációs sorozatokra, hogy nem minden esetben ismert a rájuk vonatkozó zárt alak.

Főleg a numerikus számítások esetén jellemző probléma, hogy a sorozat konvergens-e. Ennek eldöntésére a Cauchy-konvergenciakritériumot és Banach fixponttételét szokták alkalmazni jellemzően. Általában elmondható, hogy ha konvergens egy iterációs sorozat, akkor igen gyorsan konvergál, ez a fő oka a használatuknak. Erre a legismertebb példa a Newton-féle iteráció

Iterációs sorozatokat lehet definíciós célokra is használni, ilyen például az összeadás analitikus meghatározása.

FraktálokSzerkesztés

 
A harmadik gyök meghatározásához tartozó Newton-iteráció a komplex síkon. Ez egy tipikus fraktál, az egyes színek a három gyököt, a színárnyalat a konvergencia sebességét jelenti.

A fraktálok speciális matematikai objektumok, méghozzá olyan ponthalmazok, amiknek a dimenziószáma nem egész szám. Ezeknek előállítása tipikusan iterációs függvényekkel történik. A fentebb említett Newton-iteráció is fraktális alakzatokat hoz létre a komplex síkon a konvergencia figyelembe vételével. A legelső fraktál, a Mandelbrot-halmaz is iterációs sorozattal lett létrehozva. Konkrétan ez utóbbi halmaz egy iterációs sorozatcsalád konvergencia-halmaza:

 

Az iterációs sorozatok eszerint rendkívül bonyolult alakzatokat is rendkívül kevés információ segítségével határoznak meg. Ennek szép megjelenése a természetben az élőlények megjelenésének szabályozása. Fraktális szerkezete van például a fáknak vagy a harasztoknak, ezek génjei között a bonyolultságukhoz képest meglehetősen kevés kapcsolódik a felépítésükhöz.

Iteráció az informatikábanSzerkesztés

Az informatikában iterációnak nevezzük valamely eljárás ismétlődő végrehajtását.[1] Az iteráció esetén a programozónak saját kezűleg kell gondoskodni a leállásról, különben az iteráció végtelen ciklussá válhat. Igaz, egyes esetekben ez kívánatos lehet, ilyen például egy játékprogram fő ciklusa.

Az önhívó rekurziókat is iterációnak nevezzük, ezeket a numerikus számítások gépesítése során alkalmazzuk. Ilyenkor a kilépési feltétel egy elvárt pontosság elérése vagy meghatározott lépésszám lehet. Példa ilyen iterációra:

double SquareRoot(double x, double n){
    if(x^2-n <= 0,00001) return x; // Ha kellően pontos a közelítés, akkor visszaadjuk az értékét
    else return(SquareRoot(x/2-n/(2*x),n)); // Ez a Newton-iteráció képlete a gyök kiszámítására, ezzel végezzük el a következő iterációs lépést.
}

Habár a fenti példa kétváltozósnak tűnik, azonban az egyik változó paraméter, az értéke állandó.

JegyzetekSzerkesztés

  1. Ez az iterációnak az a speciális eseten, amikor a sorozat értelmezési tartománya:  

ForrásokSzerkesztés

  1. Kristóf János: Az analízis elemei (ELTE, 1994, jegyzet)
  2. Bronstein, Szemengyajev, Musiol, Mühlig: Matematikai kézikönyv (TypoTeX, 2000) ISBN 963-9132-59-4
  3. Stoyan Gisbert, Takó Galina: Numerikus módszerek (TypoTeX, 1993) ISBN 963-7546-31-6