Kiinteäpisteiterointi

Kiinteäpisteiterointi on numeerisen analyysin menetelmä, jolla ratkaistaan yhtälö x = φ(x) muuttamalla ongelman kiinteäksi pisteeksi. Menetelmä perustuu ajatukseen, että kiinteä piste x* täyttää x* = φ(x*). Tämän jälkeen aloitetaan arvaus x0 ja päivitetään peräkkäin x_{n+1} = φ(x_n). Iterointia jatketaan, kunnes muutos |x_{n+1} - x_n| on alle ennalta määritellyn kynnysarvon tai kun residuum f(x_n) on riittävän pieni.

Konvergenssi riippuu φ:n ominaisuuksista. Jos φ määrittää kontraktion tietyllä intervalilla I siten, että φ(I) ⊆ I ja on olemassa L < 1, jolla |φ'(x)| ≤ L kaikilla x ∈ I, niin kaikilla alkupisteillä x0 ∈ I konvergoidaan kiinteäpisteeseen x* ∈ I. Lokaali konvergenssi on taattu myös, jos φ on jatkuvasti derivoituva ja |φ'(x*)| < 1; konvergenssin nopeus on lineaarinen ja likimääräinen nopeuskerroin on |φ'(x*)|. Jos arvo on isompi kuin 1, menetelmä voi hajaantua.

Käytännössä voidaan parantaa konvergenssia rentoutuksella, jolloin päivitys tungetaan muualta x_{n+1} = (1 - λ) x_n + λ φ(x_n) 0 < λ ≤ 1. Pienemmät λ-arvot voivat parantaa vakaata konvergenssia epävarmemmissa tapauksissa.

Esimerkki: ratkaistaan x = cos x. Valitaan φ(x) = cos x ja aloitetaan vaikkapa x0 = 0.5. Prosessi konvergoi kohti kiinteää pistettä x* ≈ 0.7390851332.

Monissaulotteisissa tapauksissa x ∈ R^n ja x_{k+1} = φ(x_k) with φ: R^n → R^n. Siirtymässä konvergenssi vaatii Jacobian Dφ(x*) summan ominaisuuksia, kuten spectral radius < 1. Kiinteäpisteiterointi on laajasti käytössä ratkaisujen etsimisessä, joissa suora ratkaisu on ei-triviaalti tai kun ratkaisu voidaan helposti asettaa kiinteäpistemuotoon.