Iterační metoda řešení rovnic
Iterační metoda se dá využít v případě, že nám stačí výsledek zaokrouhlený na určitý počet desetinných míst (např. počítačové programy, odhady). V článku předpokládam elementární znalost pojmů konvergence a limita.
Založena je na konvergenci posloupnosti k žádané hodnotě: představme si třeba rovnici 1/x - x + 3 = 0. Převedeme si ji na tvar: xn = 1/xn-1 + 3, tedy tvar rekurentně zadané posloupnosti - zřejmě vidíme že naší původní rovnici bude vyhovovat situace kdy se xn = f(xn) (tedy x = 1/x + 3, původní zadání). Snažíme se tedy najít limitu této posloupnosti. Cvičně zvolíme počáteční hodnotu 1, a počítáme: x0 = f(1) = 1/1 + 3= 4. Získanou hodnotu x0 opět dosazujeme:
x1 = f(4) = 1/4 + 3 = 3,75 x2 = f(3,75) = 1/3,75 + 3 = 3,266 x3 = f(3,266) = 1/3,266 + 3 = 3,306 x4 = f(3,306) = 1/3,306 + 3 = 3,302 x5 = f(3,302) = 1/3,302 + 3 = 3,302
Vidíme, že po počítání s argumentem 3,302 se hodnota funkce nezměnila, tedy platí že xn = f(xn). Nutnou a dostačující podmínkou správnosti této metody je pouze zmíněná konvergentnost: je-li posloupnost konvergentní, pak existuje její limita, tedy taková hodnota pro kterou platí zmíněná rovnost, a po konečném počtu dosazení (při zvoleném počtu desetinných míst) se dostaneme k číslu, které je limitě dostatečně blízko aby naší podmínku splnilo.
Důkaz konvergence výše uvedené posloupnosti je snadný, stačí si ji analyticky vyjádřit jako xi = x0*1/2^i + (suma od 0 do i-1)3/2^j, kde oba sčítance viditelně konvergují.
Nejčastěji lze užít iterační metodu pro řešní soustavy rovnic: z každého řáku si vyjádříme jednu proměnnou, abychom získali ono rekurentní zadání posloupností. Zvolíme nějakou n-tici hodnot a opět dosazujeme. Tento postup lze optimalizovat, pokud při počítání i-té n-tice využíváme kromě hodnot z (i-1)-tého kroku také hodnoty spočítané v aktuálním kroku. Příklad:
I)x + y*1/2 = 0 II)y + x*1/2 = 8 převedeme: I) x = -y*1/2 II) y = 8 - x*1/2
zvolíme x0 = 0, y0 = 0. Pokud bychom počítali bez optimalizace, vypadalo by to takto:
x1 = 0*1/2 = 0 y1 = 8 - 0*1/2 = 8 x2 = 8*1/2 = 4 y2 = 8 - 0*1/2 = 8 x3 = 8*1/2 = 4 y3 = 8 - 4*1/2 = 6 x4 = 6*1/2 = 3 y4 = 8 - 4*1/2 = 6 x5 = 6*1/2 = 3 y5 = 8 - 3*1/2 = 6,5 ... xi = -5,33 yi = 10,66
Zjevně je vidět, že pro x i y se hodnoty měnily vždy po dvou krocích. Pokud bychom použili optimalizaci, výpočet by pro yi probíhal již s hodnotou xi, ne xi-1, takže by změny probíhaly rychleji:
x1 = 0*1/2 = 0 y1 = 8 - 0*1/2 = 8 x2 = 8*1/2 = 4 y2 = 8 - 4*1/2 = 6 x3 = 6*1/2 = 3 y3 = 8 - 3*1/2 = 6,5
po 3 iteracích jsme se dostali do stejného stavu jako po 5 iteracích bez optimalizace... Tato optimalizace nám náš důkaz správnosti nijak nemění, stále stačí zachovávat podmínku konvergence.
.