Uzawa iteration
In numerical mathematics, the Uzawa iteration is an algorithm for solving saddle point problems.
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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. where 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 solve S x_2 = B^* A^{-1} b_1 - b_2 in order to compute x_2 . The vector x_1 can be reconstructed by solving A x_1 = b_1 - B x_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. r_2 := B^* A^{-1} b_1 - b_2 - S x_2 = B^* A^{-1} (b_1 - B x_2) - b_2 = B^* x_1 - b_2, of the Schur complement system, where x_1 := A^{-1} (b_1 - B x_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 p_2 := r_2.\, In each step, we compute a_2 := S p_2 = B^* A^{-1} B p_2 = B^* p_1 and keep the intermediate result p_1 := A^{-1} B p_2 for later. The scaling factor is given by \alpha := p_2^* a_2 /p_2^* r_2 and leads to the updates 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 x_1 := x_1 - \alpha p_1.\, Now we only have to construct the new search direction by the Gram–Schmidt process, i.e., \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.
If solving the linear system A x=b exactly is not feasible, inexact solvers can be applied. If the Schur complement system is ill-conditioned, preconditioners can be employed to improve the speed of convergence of the underlying gradient method. Inequality constraints can be incorporated, e.g., in order to handle obstacle problems.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1244855918 under CC BY-SA 4.0; modifications have been made.