Iteración de Uzawa

En matemáticas numéricas , la iteración de Uzawa es un algoritmo para resolver problemas de puntos silla . Lleva el nombre de Hirofumi Uzawa y se introdujo originalmente en el contexto de la programación cóncava. ^[1]

Idea básica

Consideremos un problema de punto silla de la forma

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

donde es una matriz simétrica definida positiva . Multiplicar la primera fila por y restar de la segunda fila produce el sistema triangular superior ${\displaystyle A}$ ${\displaystyle B^{*}A^{-1}}$

${\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}},}$

donde denota el complemento de Schur . Dado que es simétrico positivo-definido, podemos aplicar métodos iterativos estándar como el método de descenso de gradiente o el método de gradiente conjugado para ${\displaystyle S:=B^{*}A^{-1}B}$ ${\displaystyle S}$

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

para poder calcular . El vector se puede reconstruir resolviendo ${\displaystyle x_{2}}$ ${\displaystyle x_{1}}$

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

Es posible actualizar durante la iteración del sistema de complemento de Schur y así obtener un algoritmo eficiente. ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$

Implementación

Comenzamos la iteración del gradiente conjugado calculando el residual

${\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},}$

del sistema del complemento de Schur, donde

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

denota la mitad superior del vector de solución que coincide con la suposición inicial para su mitad inferior. Completamos la inicialización eligiendo la primera dirección de búsqueda. ${\displaystyle x_{2}}$

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

En cada paso calculamos

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

y mantener el resultado intermedio

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

Para luego. El factor de escala está dado por

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

y conduce a las actualizaciones

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

Usando el resultado intermedio guardado anteriormente, también podemos actualizar la parte superior del vector de solución. ${\displaystyle p_{1}}$

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

Ahora sólo nos queda construir la nueva dirección de búsqueda mediante el proceso de Gram-Schmidt , es decir,

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

La iteración termina si el residual se ha vuelto lo suficientemente pequeño o si la norma de es significativamente menor que lo que indica que el subespacio de Krylov se ha agotado casi. ${\displaystyle r_{2}}$ ${\displaystyle p_{2}}$ ${\displaystyle r_{2}}$

Modificaciones y ampliaciones

Si no es factible resolver el sistema lineal exactamente, se pueden aplicar solucionadores inexactos. ^{[2] [3] [4]} ${\displaystyle Ax=b}$

Si el sistema del complemento de Schur está mal condicionado, se pueden emplear precondicionadores para mejorar la velocidad de convergencia del método del gradiente subyacente. ^{[2] [5]}

Se pueden incorporar restricciones de desigualdad, por ejemplo, para manejar problemas de obstáculos. ^[5]

Referencias

1. Uzawa, H. (1958). "Métodos iterativos para programación cóncava". En Arrow, KJ; Hurwicz, L.; Uzawa, H. (eds.). Estudios en programación lineal y no lineal . Prensa de la Universidad de Stanford.
2. Elman, HC; Golub, GH (1994). "Algoritmos de Uzawa inexactos y precondicionados para problemas de punto de silla". SIAM J. Número. Anal. 31 (6): 1645-1661. CiteSeerX 10.1.1.307.8178 . doi :10.1137/0731085.  
3. Zarza, JH ; Pasciak, JE; Vassilev, AT (1997). "Análisis del algoritmo inexacto de Uzawa para problemas de punto de silla". SIAM J. Número. Anal . 34 (3): 1072–1982. CiteSeerX 10.1.1.52.9559 . doi :10.1137/S0036142994273343. 
4. Zulehner, W. (1998). "Análisis de métodos iterativos para problemas de punto de silla. Un enfoque unificado". Matemáticas. comp . 71 (238): 479–505. doi : 10.1090/S0025-5718-01-01324-2 .
5. Gräser, C.; Kornhuber, R. (2007). "Sobre iteraciones precondicionadas de tipo Uzawa para un problema de punto de silla con restricciones de desigualdad". Métodos de descomposición de dominios en ciencias e ingeniería XVI . Lec. No. comp. Ciencia. Ing. vol. 55, págs. 91-102. CiteSeerX 10.1.1.72.9238 . doi :10.1007/978-3-540-34469-8_8. ISBN  978-3-540-34468-1.

Otras lecturas

• Chen, Zhangxin (2006). "Técnicas de solución de sistemas lineales". Métodos de elementos finitos y sus aplicaciones . Berlín: Springer. págs. 145-154. ISBN 978-3-540-28078-1.