Zobecněná metoda minimální rezidua - Generalized minimal residual method
V matematice je generalizovaná metoda minimálního rezidua (GMRES) je iterační metoda pro numerické řešení nesymetrie soustava lineárních rovnic. Metoda aproximuje řešení vektorem v a Krylovský podprostor s minimem reziduální. The Arnoldiho iterace se používá k vyhledání tohoto vektoru.
Metodu GMRES vyvinul Yousef Saad a Martin H. Schultz v roce 1986.[1]GMRES je zobecněním MINRY metoda[2] vyvinuli Chris Paige a Michael Saunders v roce 1975. GMRES je také zvláštním případem DIIS metoda vyvinutá Peterem Pulayem v roce 1980. DIIS je také použitelný pro nelineární systémy.
Metoda
Označte Euklidovská norma libovolného vektoru proti podle . Označte (čtvercový) systém lineárních rovnic, které mají být vyřešeny
Matice A se předpokládá, že je invertibilní velikosti m-podle-m. Dále se předpokládá, že b je normalizován, tj. že .
The n-th Krylovský podprostor pro tento problém je
kde je počáteční chyba při počátečním odhadu . Jasně -li .
GMRES přibližuje přesné řešení vektorem který minimalizuje euklidovskou normu reziduální .
Vektory může být blízko lineárně závislé, takže namísto tohoto základu Arnoldiho iterace se používá k vyhledání ortonormálních vektorů které tvoří základ pro . Zejména, .
Proto vektor lze psát jako s , kde je m-podle-n matice tvořená .
Arnoldiho proces také produkuje ()-podle- horní Hessenbergova matice s
Protože sloupce jsme ortonormální, máme
kde
je první vektor v standardní základ z , a
jako první zkušební vektor (obvykle nula). Proto, lze nalézt minimalizací euklidovské normy rezidua
Tohle je lineární nejmenší čtverce problém velikosti n.
Tím se získá metoda GMRES. Na -tá iterace:
- vypočítat s Arnoldiho metodou;
- najít což minimalizuje ;
- vypočítat ;
- opakujte, pokud reziduum ještě není dostatečně malé.
Při každé iteraci je produkt maticový vektor musí být vypočítán. To stojí asi operace s plovoucí desetinnou čárkou pro obecné husté matice velikosti , ale náklady se mohou snížit na pro řídké matice. Kromě produktu matice-vektor, operace s plovoucí desetinnou čárkou musí být vypočítány na n -tá iterace.
Konvergence
The niterace minimalizuje reziduum v krylovském podprostoru K.n. Jelikož každý podprostor je obsažen v dalším podprostoru, zbytkový se nezvyšuje. Po m iterace, kde m je velikost matice A, Krylovský prostor K.m je celá Rm a proto metoda GMRES dospívá k přesnému řešení. Myšlenka však je, že po malém počtu iterací (relativně k m), vektor Xn je již dobrá aproximace přesného řešení.
To se obecně neděje. Věta o Greenbaumovi, Ptákovi a Strakošovi tvrdí, že pro každou nezvyšující se posloupnost A1, …, Am−1, Am = 0, lze najít matici A takové, že ||rn|| = An pro všechny n, kde rn je zbytek definovaný výše. Zejména je možné najít matici, pro kterou reziduum zůstává konstantní m - 1 iterace a při poslední iteraci klesne pouze na nulu.
V praxi však GMRES často funguje dobře. To lze prokázat v konkrétních situacích. Pokud je symetrická část A, to je , je pozitivní určitý, pak
kde a označují nejmenší a největší vlastní číslo matice , resp.[3]
Li A je symetrický a pozitivní definitivní, pak dokonce máme
kde označuje číslo podmínky z A v euklidovské normě.
V obecném případě, kde A není kladně definitivní, máme
kde Pn označuje sadu polynomů stupně nejvýše n s p(0) = 1, PROTI je matice objevující se v spektrální rozklad z A, a σ(A) je spektrum z A. Zhruba řečeno to říká, že k rychlé konvergenci dochází, když vlastní čísla A jsou seskupeny od původu a A není příliš daleko od normálnost.[4]
Všechny tyto nerovnosti vázaly pouze zbytky místo skutečné chyby, tj. Vzdálenost mezi aktuální iterací Xn a přesné řešení.
Rozšíření metody
Stejně jako ostatní iterační metody je GMRES obvykle kombinován s a předběžná úprava metoda za účelem urychlení konvergence.
Cena iterací roste s O (n2), kde n je číslo iterace. Proto je metoda někdy restartována po čísle, řekněme k, iterací, s Xk jako počáteční odhad. Výsledná metoda se nazývá GMRES (k) nebo restartován GMRES. U pozitivních definitních matic může tato metoda trpět stagnací konvergence, protože restartovaný podprostor je často blízký dřívějšímu podprostoru.
Nedostatky GMRES a restartovaných GMRES řeší recyklace krylovského podprostoru v metodách typu GCRO, jako jsou GCROT a GCRODR.[5]Recyklace krylovských podprostorů v GMRES může také urychlit konvergenci, když je třeba řešit sekvence lineárních systémů.[6]
Srovnání s ostatními řešiteli
Arnoldiho iterace se snižuje na Lanczosova iterace pro symetrické matice. Korespondence Krylovský podprostor metoda je minimální reziduální metoda (MinRes) Paige a Saunders. Na rozdíl od nesymetrického případu je metoda MinRes dána tříčlenným termínem relace opakování. Je možné ukázat, že pro obecné matice neexistuje žádná krylovská podprostorová metoda, která je dána krátkou relací opakování a přesto minimalizuje normy reziduí, jak to dělá GMRES.
Další třída metod navazuje na nesymetrická iterace Lanczos, zejména Metoda BiCG. Tito používají relaci třídobého rekurence, ale nedosahují minimální rezidua, a proto reziduum pro tyto metody monotónně neklesá. Konvergence není ani zaručena.
Třetí třída je tvořena metodami jako CGS a BiCGSTAB. Pracují také s relací třídobého opakování (tedy bez optimality) a mohou dokonce předčasně ukončit bez dosažení konvergence. Myšlenkou těchto metod je vhodně zvolit generující polynomy iterační sekvence.
Žádná z těchto tří tříd není nejlepší pro všechny matice; vždy existují příklady, kdy jedna třída překonává druhou. V praxi se proto zkouší více řešitelů, aby zjistili, který z nich je pro daný problém nejlepší.
Řešení problému nejmenších čtverců
Jednou částí metody GMRES je nalezení vektoru což minimalizuje
Všimněte si, že je (n + 1) -by-n matice, proto poskytuje příliš omezený lineární systém n+1 rovnice pro n neznámé.
Minimum lze vypočítat pomocí a QR rozklad: najít (n + 1) -by- (n + 1) ortogonální matice Ωn a (n + 1) -by-n horní trojúhelníková matice takhle
Trojúhelníková matice má o jeden řádek více, než má sloupce, takže její spodní řádek se skládá z nuly. Proto může být rozložen jako