Nahraďme původní rovnici ekvivalentní a sestavme iterace podle pravidla 
. Jednoduchá iterační metoda je tedy jednokrokový iterační proces. Abyste mohli tento proces zahájit, musíte znát počáteční přiblížení. Zjistíme podmínky pro konvergenci metody a volbu počáteční aproximace.
Vstupenka č. 29
Seidelova metoda
Seidelova metoda (někdy nazývaná Gauss-Seidelova metoda) je modifikací jednoduché iterační metody, která spočívá v tom, že při výpočtu další aproximace x (k+1) (viz vzorce (1.13), (1.14)) je její již získané složky x 1 ( k+1) , ...,x i - 1 (k+1) se ihned použijí k výpočtu x i (k+1) .
Ve formě souřadnicového zápisu má metoda Seidel tvar:
X 1 (k+1) = c 11 x 1 (k) + c 12 x 2 (k) + ... + c 1n-1 x n-1 (k) + c 1n x n (k) + d 1
x 2 (k+1) = c 21 x 1 (k+1) + c 22 x 2 (k) + ... + c 2n-1 x n-1 (k) + c 2n x n (k) + d 2
...
x n (k+1) = c n1 x 1 (k+1) + c n2 x 2 (k+1) + ... + c nn-1 x n-1 (k+1) + c nn x n (k ) + dn
kde x (0) je nějaká počáteční aproximace k řešení.
I-tá složka (k+1)-té aproximace se tedy vypočítá podle vzorce
| x i (k+1) = ∑ j=1 i-1 c ij x j (k+1) + ∑ n j=i c ij x j (k) + d i, i = 1, ..., n | (1.20) |
Podmínka pro ukončení Seidelova iteračního procesu při dosažení přesnosti ε ve zjednodušené podobě má tvar:
|| x (k+1) - x (k) || ≤ ε.
Vstupenka č. 30
Způsob předávání
Pro řešení soustav A x = b s tridiagonální maticí se nejčastěji používá metoda rozmítání, která je adaptací Gaussovy metody na tento případ.
Napíšeme soustavu rovnic
d 1 x 1 + e 1 x 2 = b 1
c 2 x 1 + d 2 x 2 + e 2 x 3 = b 2
c 3 x 2 + d 3 x 3 + e 3 x 4 = b 3
... ... ...
c n-1 x n-2 + d n-1 x n-1 + e n-1 x n = b n-1
c n x n-1 + d n x n = b n
v maticovém tvaru: A x = b kde
A= 
Zapišme si vzorce metody rozmítání v pořadí jejich použití.
1. Přímý zdvih metody rozmítání (výpočet pomocných veličin):
| a 2 = -e 1 / d 1 b 2 = b 1 / d 1 a i+1 = -e i / , i=2, ..., n-1 b i+1 = [-c i b i + b i ] / , i=2, ..., n-1 | (1.9) |
2. Reverzní zdvih metoda zametání (nalezení řešení):
| x n = [-c n b n + b n ] / x i = a i+1 x i+1 + b i+1, i = n-1, ..., 1 |
Vstupenka č. 31
Jednoduchá iterační metoda
Podstata metody jednoduché iterace spočívá v pohybu z rovnice
f(x)= 0 (*)
na ekvivalentní rovnici
X=φ(x). (**)
Tento přechod lze provést různé způsoby, v závislosti na typu f(x). Například můžete dát
φ(x) = X+bf(x),(***)
Kde b= konst a kořeny původní rovnice se nezmění.
Pokud je známa počáteční aproximace ke kořenu x 0, pak nová aproximace
x 1=φx(0),
těch. obecné schéma iteračního procesu:
x k+1=φ(x k).(****)
Nejjednodušší kritérium pro ukončení procesu
|x k +1 -x k |<ε.
Kritérium konvergence jednoduchá iterační metoda:
pokud blízko kořene | φ/(x)| < 1, то итерации сходятся. Если указанное условие справедливо для любого X, pak iterace konvergují pro jakoukoli počáteční aproximaci.
Pojďme prozkoumat volbu konstanty b z hlediska zajištění maximální rychlosti konvergence. V souladu s kritériem konvergence je nejvyšší rychlost konvergence poskytnuta, když |φ / (x)| = 0. Zároveň na základě (***) b = –1/f / (x), a iterační vzorec (****) přejde do x i =x i-1 -f(x i-1)/f/ (x i-1).- těch. do vzorce Newtonovy metody. Newtonova metoda je tedy speciálním případem jednoduché iterační metody, poskytující nejvyšší rychlost konvergence ze všech možných možností výběru funkce φ(x).
Vstupenka č. 32
Newtonova metoda
Hlavní myšlenka metody je následující: počáteční aproximace je specifikována v blízkosti hypotetického kořene, načež je v aproximačním bodě vytvořena tečna ke studované funkci, pro kterou je nalezen průsečík s osou úsečky. Tento bod je brán jako další aproximace. A tak dále, dokud není dosaženo požadované přesnosti.
Nechť je funkce s reálnou hodnotou definovaná na intervalu a na něm diferencovatelná. Potom vzorec pro iterativní aproximační počet lze odvodit takto:
kde α je úhel sklonu tečny v bodě.
Požadovaný výraz pro má tedy tvar:
Vstupenka č. 33
Metoda zlatého poměru
Metoda zlatého řezu umožňuje eliminovat intervaly výpočtem pouze jedné funkční hodnoty v každé iteraci. V důsledku dvou uvažovaných hodnot funkce je určen interval, který by měl být použit v budoucnu. Tento interval bude obsahovat jeden z předchozích bodů a další bod umístěný symetricky k němu. Bod rozděluje interval na dvě části tak, že poměr celku k větší části je roven poměru větší části k menší, tedy rovný tzv. „zlatému řezu“.
Rozdělení intervalu na nestejné části vám umožní najít ještě efektivnější metodu. Vypočítejme funkci na koncích segmentu [ A,b] a položte A=X 1 , b=X 2. Vypočítejme také funkci ve dvou vnitřních bodech X 3 , X 4. Porovnejme všechny čtyři hodnoty funkce a vybereme z nich nejmenší. Nechť dopadne například nejmenší F(x 3). Je zřejmé, že minimum musí být v jednom ze segmentů, které k němu přiléhají. Proto segment [ X 4 ,b] lze zahodit a opustit segment . 
První krok byl učiněn. Na segmentu musíte opět vybrat dva vnitřní body, vypočítat funkční hodnoty na nich a na koncích a provést další krok. Ale v předchozím kroku výpočtů jsme již našli funkci na koncích nového segmentu a v jednom z jeho vnitřních bodů X 4. Uvnitř tedy stačí vybrat ještě jeden bod x 5 určit hodnotu funkce v něm a provést potřebná srovnání. Tím se zčtyřnásobí množství výpočtů požadovaných na krok procesu. Jaký je nejlepší způsob umístění bodů? Pokaždé se zbývající segment rozdělí na tři části a poté se jeden z vnějších segmentů zahodí.
Označme počáteční interval nejistoty D.
Protože v obecném případě může být kterýkoli ze segmentů vyřazen X 1, X 3 nebo X 4, X 2 pak vyberte body X 3 A X 4 takže délky těchto segmentů jsou stejné:
x 3 - x 1 = x 4 - x 2.
Po vyřazení dostaneme nový interval nejistoty délky D′.
Označme vztah D/D′ písmeno φ:
to znamená, nastavme , kde je další interval nejistoty. Ale
stejnou délkou jako segment vyřazený v předchozí fázi, tzn
Proto dostáváme:
.
To vede k rovnici nebo ekvivalentně 
.
Kladný kořen této rovnice dává
.
Vstupenka č. 34
interpolace funkcí, tzn. Pomocí dané funkce sestrojení další (obvykle jednodušší) funkce, jejíž hodnoty se shodují s hodnotami dané funkce v určitém počtu bodů. Kromě toho má interpolace praktický i teoretický význam.
Jednoduchá iterační metoda, nazývaná také metoda postupné aproximace, je matematický algoritmus pro zjištění hodnoty neznámé veličiny jejím postupným zpřesňováním. Podstatou této metody je, jak název napovídá, postupným vyjadřováním následných z počáteční aproximace se získávají stále jemnější výsledky. Tato metoda se používá k nalezení hodnoty proměnné v dané funkci a také při řešení soustav rovnic, lineárních i nelineárních.
Podívejme se, jak je tato metoda implementována při řešení SLAE. Jednoduchá iterační metoda má následující algoritmus:
1. Kontrola splnění podmínky konvergence v původní matici. Věta o konvergenci: má-li původní matice systému diagonální dominanci (tj. v každém řádku musí být prvky hlavní úhlopříčky větší v absolutní hodnotě než součet prvků vedlejších úhlopříček v absolutní hodnotě), pak jednoduchá iterační metoda je konvergentní.
2. Matice původního systému nemá vždy diagonální převahu. V takových případech lze systém převést. Rovnice, které splňují podmínku konvergence, jsou ponechány nedotčené a lineární kombinace jsou vytvořeny s těmi, které ji nesplňují, tzn. násobit, odčítat, sčítat rovnice k sobě, dokud nedosáhnete požadovaného výsledku.
Pokud jsou ve výsledném systému na hlavní diagonále nepohodlné koeficienty, pak se na obě strany takové rovnice přidají členy tvaru s i * x i, jejichž znaménka se musí shodovat se znaménky diagonálních prvků.
3. Transformace výsledného systému do normální formy:
x - =β - +α*x -
To lze provést mnoha způsoby, například takto: z první rovnice vyjádřete x 1 pomocí dalších neznámých, z druhé - x 2, ze třetí - x 3 atd. V tomto případě použijeme vzorce:
α ij = -(a ij / a ii)
i = b i /a ii
Opět byste se měli ujistit, že výsledný systém normálního tvaru splňuje podmínku konvergence:
∑ (j=1) |α ij |≤ 1, zatímco i= 1,2,...n
4. Začneme uplatňovat v podstatě samotnou metodu postupných aproximací.
x (0) je počáteční aproximace, vyjádříme jím x (1), poté vyjádříme x (2) až x (1). Obecný vzorec ve formě matice vypadá takto:
x (n) = β - +α*x (n-1)
Počítáme, dokud nedosáhneme požadované přesnosti:
max |xi (k)-xi (k+1) ≤ ε
Uveďme tedy jednoduchou iterační metodu do praxe. Příklad:
Vyřešit SLAE:
4,5x1-1,7x2+3,5x3=2
3,1x1+2,3x2-1,1x3=1
1,8x1+2,5x2+4,7x3=4 s přesností ε=10 -3
Podívejme se, zda v modulu převažují diagonální prvky.
Vidíme, že pouze třetí rovnice splňuje podmínku konvergence. Transformujme první a druhou rovnici a přidejte druhou k první rovnici:
7,6x1+0,6x2+2,4x3=3
Od třetího odečteme první:
2,7x1+4,2x2+1,2x3=2
Původní systém jsme převedli na ekvivalentní:
7,6x1+0,6x2+2,4x3=3
-2,7x1+4,2x2+1,2x3=2
1,8x1+2,5x2+4,7x3=4
Nyní uvedeme systém do jeho normální podoby:
x1=0,3947-0,0789x2-0,3158x3
x2=0,4762+0,6429x1-0,2857x3
x3= 0,8511-0,383x1-0,5319x2
Zkontrolujeme konvergenci iteračního procesu:
0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0,383+ 0,5319= 0,9149 ≤ 1, tzn. podmínka splněna.
0,3947
Počáteční odhad x(0) = 0,4762
0,8511
Dosazením těchto hodnot do rovnice normálního tvaru získáme následující hodnoty:
0,08835
x(1) = 0,486793
0,446639
Nahrazením nových hodnot získáme:
0,215243
x(2) = 0,405396
0,558336
Pokračujeme ve výpočtech, dokud se nepřiblížíme k hodnotám, které splňují danou podmínku.
x (7) = 0,441091
Zkontrolujeme správnost získaných výsledků:
4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3,1*0,1880+2,3*0,441-1,1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977
Výsledky získané dosazením nalezených hodnot do původních rovnic plně splňují podmínky rovnice.
Jak vidíme, jednoduchá iterační metoda poskytuje poměrně přesné výsledky, ale k vyřešení této rovnice jsme museli strávit spoustu času a dělat těžkopádné výpočty.
Nechť je dán systém n algebraických rovnic s n neznámými:
Algoritmus pro jednoduchou iterační metodu:
Všimněte si, že zde a dále spodní index označuje odpovídající složku vektoru neznámých a horní index iterační (aproximační) číslo.
Poté se vytvoří cyklický matematický proces, jehož každý cyklus představuje jednu iteraci. V důsledku každé iterace se získá nová hodnota vektoru neznámých. Pro organizaci iteračního procesu napíšeme systém (1) ve zmenšené podobě. V tomto případě jsou členy na hlavní diagonále normalizovány a zůstávají vlevo od rovnítka a zbytek se přenese na pravou stranu. Redukovaný systém rovnic má tvar:
všimněte si, že nebude nikdy dosaženo, ale s každou další iterací se vektor neznámých přibližuje k přesnému řešení.
12. Základní iterační vzorec používaný v jednoduché iterační metodě k řešení nelineární rovnice:
13. Kritérium pro zastavení iteračního procesu v jednoduché iterační metodě pro řešení nelineární rovnice:
Iterační proces končí, pokud je pro každou i-tou složku vektoru neznámých splněna podmínka pro dosažení přesnosti.
všimněte si, že přesné řešení v jednoduché iterační metodě nikdy nedosáhneme, nicméně s každou další iterací se vektor neznámých přibližuje k přesnému řešení
14. Kritérium pro výběr pomocné funkce F(x) pro iterační segment intervalu:
Při matematickém testu na řešení jednoduché iterační metody je třeba nejprve zkontrolovat podmínku konvergence. Aby metoda konvergovala, je nutné a postačující, aby v matici A byly absolutní hodnoty všech diagonálních prvků větší než součet modulů všech ostatních prvků v odpovídajícím řádku:
Nevýhoda iteračních metod Toto je dosti přísná podmínka konvergence, která není splněna pro všechny soustavy rovnic.
Pokud je podmínka konvergence splněna, je v další fázi nutné zadat počáteční aproximaci vektoru neznámých, který se obvykle volí jako nulový vektor:
15. Gaussova metoda, používaná k řešení soustav lineárních rovnic, poskytuje:
Metoda je založena na převodu matice do trojúhelníkového tvaru. Toho je dosaženo postupným odstraňováním neznámých ze systémových rovnic.
Jednoduchá iterační metoda je založena na nahrazení původní rovnice ekvivalentní rovnicí:
Nechť je známa počáteční aproximace ke kořenu x = x 0. Dosazením do pravé strany rovnice (2.7) získáme novou aproximaci 
, pak podobným způsobem dostaneme 
atd.:
. (2.8)
 |
Ne za všech podmínek iterační proces konverguje ke kořeni rovnice X. Pojďme se na tento proces podívat blíže. Obrázek 2.6 ukazuje grafickou interpretaci jednosměrného konvergentního a divergentního procesu. Obrázek 2.7 ukazuje obousměrné konvergentní a divergentní procesy. Divergentní proces je charakterizován rychlým nárůstem hodnot argumentu a funkce a abnormálním ukončením odpovídajícího programu.
 |
U obousměrného procesu je možné cyklování, tedy nekonečné opakování stejné funkce a hodnot argumentů. Smyčka odděluje divergentní proces od konvergentního.
Z grafů je zřejmé, že pro jednostranné i oboustranné procesy je konvergence ke kořeni určena sklonem křivky v blízkosti kořene. Čím menší sklon, tím lepší konvergence. Jak je známo, tečna sklonu křivky je rovna derivaci křivky v daném bodě.
Proto čím menší je číslo blízko kořene, tím rychleji se proces sbíhá.
Aby byl proces iterace konvergentní, musí být v blízkosti kořene splněna následující nerovnost:
Přechod z rovnice (2.1) do rovnice (2.7) lze provést různými způsoby v závislosti na typu funkce f(x). Při takovém přechodu je nutné funkci sestrojit tak, aby byla splněna podmínka konvergence (2.9).
Uvažujme jeden z obecných algoritmů pro přechod z rovnice (2.1) na rovnici (2.7).
Vynásobme levou a pravou stranu rovnice (2.1) libovolnou konstantou b a k oběma dílům přidat neznámé X. V tomto případě se kořeny původní rovnice nezmění:
Představme si notaci 
a přejděme od vztahu (2.10) k rovnici (2.8).
 |
Libovolná volba konstanty b zajistí splnění podmínky konvergence (2.9). Kritériem pro ukončení iteračního procesu bude podmínka (2.2). Obrázek 2.8 ukazuje grafickou interpretaci metody jednoduchých iterací pomocí popsaného způsobu zobrazení (měřítka podél os X a Y jsou různá).
Pokud je funkce vybrána ve tvaru , pak derivace této funkce bude . Nejvyšší rychlost konvergence pak bude při 
a iterační vzorec (2.11) se změní na Newtonův vzorec. Newtonova metoda má tedy nejvyšší stupeň konvergence ze všech iteračních procesů.
Softwarová implementace jednoduché iterační metody je provedena formou podprogramové procedury Iteras(PROGRAM 2.1).
Celá procedura se prakticky skládá z jednoho cyklu Opakovat...Dokud implementující vzorec (2.11) zohledňující podmínku pro zastavení iteračního procesu (vzorec (2.2)).
Procedura má vestavěnou ochranu smyčky počítáním počtu smyček pomocí proměnné Niter. V praktických hodinách se musíte spuštěním programu ujistit, jaký vliv má volba koeficientu b a počáteční aproximace v procesu hledání kořene. Při změně koeficientu b povaha iteračního procesu pro studovanou funkci se mění. Nejprve se stává oboustranným a poté smyčkovým (obr. 2.9). Osové váhy X A Y jsou rozdílní. Ještě větší hodnota modulu b vede k divergentnímu procesu.
Porovnání metod pro přibližné řešení rovnic
Porovnání výše popsaných metod pro numerické řešení rovnic bylo provedeno pomocí programu, který umožňuje sledovat proces hledání kořene v grafické podobě na obrazovce PC. Postupy zahrnuté v tomto programu a implementace porovnávaných metod jsou uvedeny níže (PROGRAM 2.1).
Rýže. 2.3-2.5, 2.8, 2.9 jsou kopie obrazovky PC na konci procesu iterace.
Ve všech případech byla jako studovaná funkce vzata kvadratická rovnice x 2 -x-6 = 0 s analytickým řešením x 1 = -2 a x 2 = 3. Chyba a počáteční aproximace byly u všech metod považovány za stejné. Výsledky vyhledávání kořenů x= 3, znázorněné na obrázcích, jsou následující. Metoda dichotomie konverguje nejpomaleji - 22 iterací, nejrychlejší je metoda jednoduchá iterace s b = -0,2 - 5 iterací. Není zde žádný rozpor s tvrzením, že Newtonova metoda je nejrychlejší.
Derivace zkoumané funkce v bodě X= 3 se rovná -0,2, to znamená, že výpočet byl v tomto případě proveden prakticky Newtonovou metodou s hodnotou derivace v bodě kořene rovnice. Při změně koeficientu b rychlost konvergence klesá a postupně konvergenční proces probíhá nejprve v cyklech a poté se stává divergentním.
Analogicky k (2.1) může být systém (5.1) reprezentován v následující ekvivalentní formě:
kde g(x) je iterativní vektorová funkce argumentu vektoru. Soustavy nelineárních rovnic často vznikají přímo ve tvaru (5.2) (např. v numerických schématech pro diferenciální rovnice v tomto případě není potřeba žádné další úsilí k transformaci rovnic (5.1) do soustavy (5.2); Pokud budeme pokračovat v analogii s jednoduchou iterační metodou pro jednu rovnici, pak proces iterace založený na rovnici (5.2) lze organizovat následovně:
- 1) nějaký počáteční vektor x ((,) e 5 o (x 0, A)(předpokládá se, že x* e 5„(x 0, A));
- 2) následné aproximace se vypočítají pomocí vzorce
pak je proces iterace dokončen a
Stejně jako dříve musíme zjistit, za jakých podmínek
Pojďme diskutovat o tomto problému provedením jednoduché analýzy. Nejprve zavedeme chybu i-té aproximace jako e(^ = x(i) - x*. Poté můžeme napsat
Dosadíme tyto výrazy do (5.3) a rozvineme g(x* + e (/i)) v mocninách e(k> v okolí x* jako funkce argumentu vektoru (za předpokladu, že všechny parciální derivace funkce g(x) jsou spojité). Vezmeme-li také v úvahu, že x* = g(x*), dostaneme
nebo v matricové formě
B = (bnm)= I (x*)1 - iterační matice.
Pokud chybovost ||e®|| je dostatečně malý, pak lze druhý člen na pravé straně výrazu (5.4) zanedbat a pak se shoduje s výrazem (2.16). Podmínku konvergence iteračního procesu (5.3) blízko přesného řešení tedy popisuje věta 3.1.
Konvergence jednoduché iterační metody. Nutné a dostatečný stav pro konvergenci iteračního procesu (5.3): 
a dostatečná podmínka:
Tyto podmínky mají spíše teoretický než praktický význam, protože neznáme x'. Analogicky s (1.11) získáme podmínku, která může být užitečná. Nechť x* e 5 o (x 0, A) a jakobijská matice pro funkci g(x)
existuje pro všechny x e Sn (x 0, a) (všimněte si, že C(x*) = B). Pokud prvky matice C(x) splňují nerovnost
pro všechna x e 5„(x 0, A), pak je pro jakoukoli maticovou normu splněna i dostatečná podmínka (5.5).
Příklad 5.1 (metoda jednoduché iterace) Zvažte následující systém rovnice:
Jednou z možností, jak tento systém znázornit v ekvivalentní formě (5.2), je vyjádřit X z první rovnice a x 2 z druhé rovnice: 
Potom má iterační schéma tvar
Přesné řešení je x* e 5„((2, 2), 1). Zvolme počáteční vektor x (0) = (2,2) a ? p =ČT 5. Výsledky výpočtu jsou uvedeny v tabulce. 5.1.
Tabulka 5.1
|
||X - X (i_1 > | 2 / X (A) 2 |
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
Tyto výsledky ukazují, že konvergence je poměrně pomalá. Abychom získali kvantitativní charakteristiku konvergence, provedeme jednoduchou analýzu, přičemž x (1/) považujeme za přesné řešení. Jakobiánská matice C(x) pro naši iterační funkci má tvar
pak se matice B přibližně odhadne jako
Je snadné zkontrolovat, že ani podmínka (5.5) ani podmínka (5.6) nejsou splněny, ale dochází ke konvergenci, protože 5(B) ~ 0,8.
Často je možné urychlit konvergenci jednoduché iterační metody mírnou změnou procesu výpočtu. Myšlenka této úpravy je velmi jednoduchá: vypočítat P složky vektoru x (A+1) lze použít nejen (t = n,..., N), ale také již vypočítané složky dalšího aproximačního vektoru x k^ (/= 1,P - 1). Modifikovanou jednoduchou iterační metodu lze tedy reprezentovat jako následující iterační schéma:
Pokud aproximace generované iteračním procesem (5.3) konvergují, pak iterační proces (5.8) má tendenci konvergovat rychleji díky úplnějšímu využití informací.
Příklad 5.2 (metoda modifikované jednoduché iterace) Modifikovaná jednoduchá iterace pro systém (5.7) je znázorněna jako
Stejně jako dříve volíme počáteční vektor x (0) = (2, 2) a g r = = 10-5. Výsledky výpočtu jsou uvedeny v tabulce. 5.2.
Tabulka 5.2
|
|||
|
|||
|
|||
|
I Velká změna v pořadí výpočtů vedla ke snížení počtu iterací na polovinu, a tedy i ke snížení počtu operací na polovinu.
