Iteración de Uzawa

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

Consideramos un problema de punto de 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 definida positiva simétrica . Al multiplicar la primera fila por y restar de la segunda fila se obtiene el sistema triangular superior. ${\estilo de visualización A}$$Estilo de visualización 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 y definido positivamente, podemos aplicar métodos iterativos estándar como el método de descenso de gradiente o el método de gradiente conjugado para resolver $Estilo de visualización S:=B^{*}A^{-1}B}$${\estilo de visualización S}$

$Estilo de visualización Sx_{2}=B^{*}A^{-1}b_{1}-b_{2}}$

para calcular . El vector se puede reconstruir resolviendo $estilo de visualización x_{2}$$estilo de visualización x_{1}}$

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

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

Comenzamos la iteración del gradiente conjugado calculando el residuo

${\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 solución que coincide con la estimación inicial para su mitad inferior. Completamos la inicialización eligiendo la primera dirección de búsqueda $estilo de visualización 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 más adelante. El factor de escala viene 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 solución. $estilo de visualización 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 residuo se ha vuelto suficientemente pequeño o si la norma de es significativamente menor que , lo que indica que el subespacio de Krylov se ha agotado casi por completo. $estilo de visualización r_{2}$$estilo de visualización p_{2}$$estilo de visualización r_{2}$

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

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

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

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