Iteraatio

Iteraatio, eli iteraatio, on prosessi, jossa tietyllä säännöllä tuotetaan toistuvasti uusia arvoja aiemman arvon perusteella. Usein määritelmä on x_{n+1} = f(x_n) tai yleisemmin x_{n+1} = F(x_n). Termi juontaa juurensa latinasta iteratio-, "toisto". Iteraatiota käytetään sekä matematiikassa ja laskennassa että erilaisten prosessien parantamisessa.

Matematiikassa ja numeerisessa laskennassa tavoittelee, että jono x_n konvergoituu kohti jokin pistettä. Yleinen käsite on kiinteä piste: x* on ratkaisu x* = f(x*). Jos x_{n+1} = f(x_n) konvergoi kohti x*, ja jos tarvittavat ehdot täyttyvät, kuten |f'(x*)| < 1, konvergenssi on paikallinen ja sen nopeus on tyypillisesti lineaarinen; joissakin menetelmissä konvergenssi voi olla nopeampaa, esimerkiksi Newtonin menetelmällä.

Esimerkki: kiinteän pisteen iteraatio. Ratkaistaan x = cos x. Aloita arviosta x_0 ja aseta x_{n+1} = cos(x_n). Jos kiinteä piste x* toteutuu, eli x* = cos(x*), saadaan kiinteä piste. Toinen tunnettu esimerkki on Newtonin menetelmä, jossa ratkaistavaa f(x)=0 lähestytään muuttamalla x_{n+1} = x_n - f(x_n)/f'(x_n).

Sovellukset: Iteraatiota käytetään laajalti numeerisessa laskennassa ja ohjelmoinnissa: lineaarialgebran ratkaisuun tarkoitetut Jacobi- ja Gauss-Seidel -menetelmät, optimoinnin päivitysaskeleet ja aikadifferentiaaliyhtälöiden ratkaisut time-stepping -menetelmät. Iteraatio mahdollistaa suurten ongelmien lähestymisen askel askeleelta ja on keskeinen osa monia algoritmeja ja simulointia.