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 436

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

Je dána funkce a funkce . Najděte definiční obor funkce


Hlavolam

Jak to tak bývá, zlý čaroděj uvěznil mudrce. A kdo by to čekal, dal mu šanci se zachránit, pokud splní úkol. Na stole je kulatý tác, kterým lze volně otáčet, a na něm čtyři mince do čtverce. Mudrc má zavázané oči, nic nevidí. Jeho úkolem je otočit mince tak, že bude na všech panna. Nemá to však jednoduché. Otočí jistý počet mincí, pak černokněžník tácem zatočí. Opět otočí nějaké mince a znovu se tácem náhodně otočí. Toto se opakuje, dokud nejsou všechny mince správně. V tu chvíli je hra zlotřilým čarodějem ukončena. Mudrc nepozná podle hmatu pannu od orla. Musí vždy mince nechat na svém místě, ve čtverci. A hlavně - kvůli zlé magii - má strašnou smůlu a pokud bude spoléhat jen na náhodu, tak úkol nikdy nesplní.