Články » SŠ Matematika » Rovnice

Iterační metoda řešení rovnic

Vydáno dne v kategorii Rovnice; Autor: ; Počet přečtení: 24 542

Jak hrubou silou řešit rovnice


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.


Tento clanek pro vas napsal Jakub Vojacek!

Test

Vypočítejte druhou derivaci funkce


Hlavolam

Akce! Tma, bouřka, silný déšť. Podminovaná lávka přes širokou rozvodněnou řeku. Dvoučlené komadno prozatím uspělo. Oba politici držení v zajetí teroristy byli osvobozeni. Ještě je třeba se dostat na druhou stranu lávky, která exploduje za 17 minut. Víc času není. Lávka je ale moc úzká a bambus víc jak dva lidi najednou neunese. A pak, je hrozná tma a oni mají jenom jednu baterku (asi nízkorozpočtový film). Bez baterky se lávka prostě přejít nedá. To by byla sebevražda. Oba komandos jsou celkem ve formě: první přeběhne lávku za 1 minutu, druhý za 2 minuty. Politici jsou na tom, ale hůř: jeden přejde lávku za 5 a druhý za 10 minut. Přes lávku mohou jít jen dva najednou a ten rychlejší samozřejmě musí čekat na toho pomalejšího. Jak to stihnou? Nebo to nebude americkej happyend?