Články » SŠ Matematika » Rovnice

Iterační metoda řešení rovnic

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

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

Nalezněte asymptotu se směrnicí funkce


Hlavolam

Byl jednou jeden mladý kouzelník a ten se šíleně zamiloval do jediné dcery krále, kterému sloužil. Ta ho taky hrozně milovala (dokázal jí kdykoliv vykouzlit květiny :-). Ale otec král tomu vůbec nepřál. Chtěl pro svou dceru nějakého urozeného a bohatého ženicha a ne takového nekňubu, jako byl kouzelník (jak si myslel). Intrikami, se mu ho podařilo křivě obvinit z krádeže a uvrhnout do žaláře. Ale kouzelník byl moc populární mezi lidem a tak ho nemohl dát jen tak jednoduše popravit, jak by rád. Vymyslel tedy na něj lest: u soudu mu dal možnost losování vlastní smrti. Řekl: "Zde v klobouku jsou dvě kuličky: černá a bílá. Vylosuješ-li si bílou, budeš žít. Ale vytáhneš-li z klobouku černou, zemřeš." Vypadalo to jako férová šance, ale král, který nechtěl nic riskovat, mu tam dal obě kuličky černé. Kouzelník naštěstí nebyl hloupý a dovtípil se to. Jak to jenom navléct, aby přežil ...