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

  1. ^ 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.
  2. ^ 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.
  3. ^ 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.
  4. ^ 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.
  5. ^ 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í