Přejít na matematické fórum Připravili jsme pro Vás zbrusu nové fórum a jsme připravení odpovídat na Vaše otázky!


Články » SŠ Matematika » Rovnice

Iterační metoda řešení rovnic

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

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

Určete definiční obor funkce


Hlavolam

Tři cestovatelé a tři jejich sluhové byli na výpravě po Indii. Jedno dne večer se šel ještě jeden z cestovatelů projít ven, když zaslechl, jak se sluhové radí, že své pány přepadnou zabijí a okradou. Jen musí počkat, až se nějakou náhodou cestovatelé rozdělí, aby sluhů na ně bylo víc. Cestovatelé totiž byli dobře ozbrojeni. Když to vyslechl, vrátil se zpět a než aby tropil rozruch, nechal si to pro sebe a dával jen pozor, aby se nikdy nerozdělili. Jenže druhého dne došli k řece, kterou bylo nutné překonat. Do pramice, jenž byla přivázána u břehu se však vešli jen dvě osoby. Jak to jen zařídit, aby ani na chvíli nebyl počet sluhů na kterémkoliv z břehů větší než počet cestovatelů?