Iterační metoda řešení rovnic

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 x₀ 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 x_n = f(x_n). 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 x_i = x₀*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 x₀ = 0, y₀ = 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 y_i probíhal již s hodnotou x_i, ne x_i-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.