Uzawská iterace - Uzawa iteration
v numerická matematika, Uzawská iterace je algoritmus pro řešení sedlový bod problémy. Je pojmenován po Hirofumi Uzawa a byl původně představen v kontextu konkávního programování.[1]
Základní myšlenka
Uvažujeme problém sedlového bodu formy
kde je symetrický pozitivně definitivní matice. Vynásobení prvního řádku o a odečtením od druhé řady se získá horní trojúhelníkový systém
kde označuje Schurův doplněk.Od té doby je symetrický kladně definitivní, můžeme použít standardní iterační metody jako klesání metoda nebo metoda konjugovaného gradientu na
za účelem výpočtu . Vektor lze rekonstruovat řešením
Je možné aktualizovat vedle během iterace pro systém doplňku Schur a získat tak efektivní algoritmus.
Implementace
Začneme iteraci gradientu konjugátu výpočtem zbytku
systému doplňků Schur, kde
označuje horní polovinu vektoru řešení, který odpovídá počátečnímu odhadu pro jeho spodní polovinu. Inicializaci dokončíme výběrem prvního směru vyhledávání
V každém kroku počítáme
a zachovat průběžný výsledek
na později. Faktor měřítka je dán vztahem
a vede k aktualizacím
Pomocí průběžného výsledku dříve uložené, můžeme také aktualizovat horní část vektoru řešení
Nyní musíme pouze zkonstruovat nový směr hledání pomocí Gram – Schmidtův proces, tj.,
Pokud je zbytková, iterace končí se stala dostatečně malou nebo pokud je normou je podstatně menší než což naznačuje, že Krylovský podprostor byl téměř vyčerpán.
Úpravy a rozšíření
Pokud řeší lineární systém přesně to není možné, lze použít nepřesná řešení.[2][3][4]
Pokud je Schurův komplementový systém špatně kondicionovaný, mohou být použity preconditionery ke zlepšení rychlosti konvergence podkladové gradientové metody.[2][5]
Mohou být začleněna omezení nerovnosti, například za účelem řešení problémů s překážkami.[5]
Reference
- ^ Uzawa, H. (1958). "Iterativní metody pro konkávní programování". In Arrow, K. J .; Hurwicz, L .; Uzawa, H. (eds.). Studium lineárního a nelineárního programování. Press Stanford University.
- ^ A b Elman, H. C .; Golub, G. H. (1994). "Nepřesné a předem upravené algoritmy Uzawa pro problémy se sedlovým bodem". SIAM J. Numer. Anální. 31 (6): 1645–1661. CiteSeerX 10.1.1.307.8178. doi:10.1137/0731085.
- ^ Bramble, J. H.; Pasciak, J. E .; Vassilev, A. T. (1997). "Analýza nepřesného algoritmu Uzawa pro problémy se sedlovým bodem". SIAM J. Numer. Anální. 34 (3): 1072–1982. CiteSeerX 10.1.1.52.9559. doi:10.1137 / S0036142994273343.
- ^ Zulehner, W. (1998). „Analýza iteračních metod pro problémy sedlového bodu. Jednotný přístup“. Matematika. Comp. 71 (238): 479–505. doi:10.1090 / S0025-5718-01-01324-2.
- ^ A b Gräser, C .; Kornhuber, R. (2007). „O předem připravených iteracích typu Uzawa pro problém sedlového bodu s omezeními nerovnosti“. Metody doménového rozkladu ve vědě a inženýrství XVI. Lec. Ne. Comp. Sci. Eng. 55. str. 91–102. CiteSeerX 10.1.1.72.9238. doi:10.1007/978-3-540-34469-8_8. ISBN 978-3-540-34468-1.
Další čtení
- Chen, Zhangxin (2006). „Techniky řešení lineárního systému“. Metody konečných prvků a jejich aplikace. Berlín: Springer. str. 145–154. ISBN 978-3-540-28078-1.