Iteráció

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

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: x_n+1=f(x_n) minden n > 0 egész számra.

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ó

Legyen $f:X\to X$ függvény, és $\iota \in X$. Ekkor iterációs sorozatnak nevezzük az alábbi sorozatot:

$i:\mathbb {N} \to X;\,{\begin{cases}i(0)&=\iota \\i(n+1)&=f(i(n))\\\end{cases}},$

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

${\begin{aligned}i_{0}&=\iota \\i_{n+1}&=f(i_{n})\end{aligned}}$

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 $(\iota ,f)$ párra alkalmazni.

Alkalmazások

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.

Sorozatok

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

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:

$M:=\{k|(i(0)=k,f(z)=z^{2}-c),\lim i\in \mathbf {C} \}$

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

Az informatikában iterációnak nevezzük valamely eljárás ismétlődő végrehajtását. 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ó.

Források

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