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: xn+1=f(xn) 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 → X {\displaystyle f:X\to X} függvény, és ι ∈ X {\displaystyle \iota \in X} . Ekkor iterációs sorozatnak nevezzük az alábbi sorozatot:

i : N → X ; { i ( 0 ) = ι i ( n + 1 ) = f ( i ( n ) ) , {\displaystyle 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:

i 0 = ι i n + 1 = f ( i n ) {\displaystyle {\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 ( ι , f ) {\displaystyle (\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 ∈ C } {\displaystyle 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.[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ó.

Jegyzetek

  1. ↑ Ez az iterációnak az a speciális eseten, amikor a sorozat értelmezési tartománya: n ∈ N {\displaystyle n\in \mathbf {N} }

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