Az iteráció egy függvény ismételt végrehajtását jelenti az előző függvényértéken. Ez a rekurzió egy speciális esete, amikor egy sorozat mindegyik tagja az előtte álló tag ugyanazon függvénybe helyettesítésével adódik: xn+1=f(xn) minden n > 0 egész számra.

Az iteráció lényege az XKCD szerint.

A szabályos fraktálok némelyikét (pl. a Koch-görbét) is iterációs algoritmusokkal lehet létrehozni.

Gyakori fogalom a matematikában és a számítástudományban, az eljárás leggyakoribb alkalmazási területe a numerikus matematika, ahol egy probléma keresett megoldási értékét iterációs sorozattal közelítjük.

Definíció

szerkesztés

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

 

vagy, a hagyományos jelölések alkalmazásával:

 

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ások

szerkeszté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.

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álok

szerkeszté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ában

szerkeszté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, értéke állandó.

  1. Ez az iterációnak az a speciális eseten, amikor a sorozat értelmezési tartománya:  
  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