Iteráció
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ó
szerkesztésLegyen 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ésAz 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
szerkesztésAz 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ésA 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ésAz 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
szerkesztés- ↑ Ez az iterációnak az a speciális eseten, amikor a sorozat értelmezési tartománya:
Források
szerkesztés- Kristóf János: Az analízis elemei (ELTE, 1994, jegyzet)
- Bronstein, Szemengyajev, Musiol, Mühlig: Matematikai kézikönyv (TypoTeX, 2000) ISBN 963-9132-59-4
- Stoyan Gisbert, Takó Galina: Numerikus módszerek (TypoTeX, 1993) ISBN 963-7546-31-6