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

${ displaystyle { begin {pmatrix} A&B B ^ {*} & end {pmatrix}} { begin {pmatrix} x_ {1} x_ {2} end {pmatrix}} = { begin {pmatrix} b_ {1} b_ {2} end {pmatrix}},}$

kde ${ displaystyle A}$ je symetrický pozitivně definitivní matice. Vynásobení prvního řádku o ${ displaystyle B ^ {*} A ^ {- 1}}$ a odečtením od druhé řady se získá horní trojúhelníkový systém

${ displaystyle { begin {pmatrix} A&B & - S end {pmatrix}} { begin {pmatrix} x_ {1} x_ {2} end {pmatrix}} = { begin {pmatrix} b_ {1} b_ {2} -B ^ {*} A ^ {- 1} b_ {1} end {pmatrix}},}$

kde ${ displaystyle S: = B ^ {*} A ^ {- 1} B}$ označuje Schurův doplněk.Od té doby ${ displaystyle S}$ je symetrický kladně definitivní, můžeme použít standardní iterační metody jako klesání metoda nebo metoda konjugovaného gradientu na

${ displaystyle Sx_ {2} = B ^ {*} A ^ {- 1} b_ {1} -b_ {2}}$

za účelem výpočtu ${ displaystyle x_ {2}}$. Vektor ${ displaystyle x_ {1}}$ lze rekonstruovat řešením

${ displaystyle Ax_ {1} = b_ {1} -Bx_ {2}. ,}$

Je možné aktualizovat ${ displaystyle x_ {1}}$ vedle ${ displaystyle x_ {2}}$ 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

${ displaystyle r_ {2}: = B ^ {*} A ^ {- 1} b_ {1} -b_ {2} -Sx_ {2} = B ^ {*} A ^ {- 1} (b_ {1 } -Bx_ {2}) - b_ {2} = B ^ {*} x_ {1} -b_ {2},}$

systému doplňků Schur, kde

${ displaystyle x_ {1}: = A ^ {- 1} (b_ {1} -Bx_ {2})}$

označuje horní polovinu vektoru řešení, který odpovídá počátečnímu odhadu ${ displaystyle x_ {2}}$ pro jeho spodní polovinu. Inicializaci dokončíme výběrem prvního směru vyhledávání

${ displaystyle p_ {2}: = r_ {2}. ,}$

V každém kroku počítáme

${ displaystyle a_ {2}: = Sp_ {2} = B ^ {*} A ^ {- 1} Bp_ {2} = B ^ {*} p_ {1}}$

a zachovat průběžný výsledek

${ displaystyle p_ {1}: = A ^ {- 1} Bp_ {2}}$

na později. Faktor měřítka je dán vztahem

${ displaystyle alpha: = p_ {2} ^ {*} a_ {2} / p_ {2} ^ {*} r_ {2}}$

a vede k aktualizacím

${ displaystyle x_ {2}: = x_ {2} + alpha p_ {2}, quad r_ {2}: = r_ {2} - alpha a_ {2}.}$

Pomocí průběžného výsledku ${ displaystyle p_ {1}}$ dříve uložené, můžeme také aktualizovat horní část vektoru řešení

${ displaystyle x_ {1}: = x_ {1} - alpha p_ {1}. ,}$

Nyní musíme pouze zkonstruovat nový směr hledání pomocí Gram – Schmidtův proces, tj.,

${ displaystyle beta: = r_ {2} ^ {*} a_ {2} / p_ {2} ^ {*} a_ {2}, quad p_ {2}: = r_ {2} - beta p_ { 2}.}$

Pokud je zbytková, iterace končí ${ displaystyle r_ {2}}$ se stala dostatečně malou nebo pokud je normou ${ displaystyle p_ {2}}$ je podstatně menší než ${ displaystyle r_ {2}}$ což naznačuje, že Krylovský podprostor byl téměř vyčerpán.

Úpravy a rozšíření

Pokud řeší lineární systém ${ displaystyle Ax = b}$ 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

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.