In numerical mathematics, the Uzawa iteration is an algorithm for solving saddle point problems. It is named after Hirofumi Uzawa and was originally introduced in the context of concave programming.[1]
Basic idea
We consider a saddle point problem of the form
\( {\displaystyle {\begin{pmatrix}A&B\\B^{*}&\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}} ={\begin{pmatrix}b_{1}\\b_{2}\end{pmatrix}},} \)
where A is a symmetric positive-definite matrix. Multiplying the first row by \( {\displaystyle B^{*}A^{-1}} \) and subtracting from the second row yields the upper-triangular system
\( {\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}},} \)
where \( {\displaystyle S:=B^{*}A^{-1}B} \) denotes the Schur complement. Since S is symmetric positive-definite, we can apply standard iterative methods like the gradient descent method or the conjugate gradient method to
\( {\displaystyle Sx_{2}=B^{*}A^{-1}b_{1}-b_{2}} \)
in order to compute \( x_{2} \). The vector \( x_{1} \) can be reconstructed by solving
\( {\displaystyle Ax_{1}=b_{1}-Bx_{2}.\,}
It is possible to update \( x_{1} \)alongside \( x_{2} \) during the iteration for the Schur complement system and thus obtain an efficient algorithm.
Implementation
We start the conjugate gradient iteration by computing the 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},} \)
of the Schur complement system, where
\( {\displaystyle x_{1}:=A^{-1}(b_{1}-Bx_{2})} \)
denotes the upper half of the solution vector matching the initial guess \( x_{2} \) for its lower half. We complete the initialization by choosing the first search direction
\( {\displaystyle p_{2}:=r_{2}.\,} \)
In each step, we compute
\( {\displaystyle a_{2}:=Sp_{2}=B^{*}A^{-1}Bp_{2}=B^{*}p_{1}} \)
and keep the intermediate result
\( {\displaystyle p_{1}:=A^{-1}Bp_{2}} \)
for later. The scaling factor is given by
\( {\displaystyle \alpha :=p_{2}^{*}a_{2}/p_{2}^{*}r_{2}} \)
and leads to the updates
\( {\displaystyle x_{2}:=x_{2}+\alpha p_{2},\quad r_{2}:=r_{2}-\alpha a_{2}.} \)
Using the intermediate result \( p_{1} \) saved earlier, we can also update the upper part of the solution vector
\( {\displaystyle x_{1}:=x_{1}-\alpha p_{1}.\,} \)
Now we only have to construct the new search direction by the Gram–Schmidt process, i.e.,
\( {\displaystyle \beta :=r_{2}^{*}a_{2}/p_{2}^{*}a_{2},\quad p_{2}:=r_{2}-\beta p_{2}.} \)
The iteration terminates if the residual \( r_{2} \) has become sufficiently small or if the norm of \( p_{2} \) is significantly smaller than \( r_{2} \) indicating that the Krylov subspace has been almost exhausted.
Modifications and extensions
If solving the linear system \( {\displaystyle Ax=b} \) exactly is not feasible, inexact solvers can be applied.[2][3][4]
If the Schur complement system is ill-conditioned, preconditioners can be employed to improve the speed of convergence of the underlying gradient method.[2][5]
Inequality constraints can be incorporated, e.g., in order to handle obstacle problems.[5]
References
Uzawa, H. (1958). "Iterative methods for concave programming". In Arrow, K. J.; Hurwicz, L.; Uzawa, H. (eds.). Studies in linear and nonlinear programming. Stanford University Press.
Elman, H. C.; Golub, G. H. (1994). "Inexact and preconditioned Uzawa algorithms for saddle point problems". SIAM J. Numer. Anal. 31 (6): 1645–1661. CiteSeerX 10.1.1.307.8178. doi:10.1137/0731085.
Bramble, J. H.; Pasciak, J. E.; Vassilev, A. T. (1997). "Analysis of the inexact Uzawa algorithm for saddle point problems". SIAM J. Numer. Anal. 34 (3): 1072–1982. CiteSeerX 10.1.1.52.9559. doi:10.1137/S0036142994273343.
Zulehner, W. (1998). "Analysis of iterative methods for saddle point problems. A unified approach". Math. Comp. 71 (238): 479–505. doi:10.1090/S0025-5718-01-01324-2.
Gräser, C.; Kornhuber, R. (2007). "On Preconditioned Uzawa-type Iterations for a Saddle Point Problem with Inequality Constraints". Domain Decomposition Methods in Science and Engineering XVI. Lec. Not. Comp. Sci. Eng. 55. pp. 91–102. CiteSeerX 10.1.1.72.9238. doi:10.1007/978-3-540-34469-8_8. ISBN 978-3-540-34468-1.
Further reading
Chen, Zhangxin (2006). "Linear System Solution Techniques". Finite Element Methods and Their Applications. Berlin: Springer. pp. 145–154. ISBN 978-3-540-28078-1.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
