Analysis of iterative methods for saddle point problems: A unified approach (Q2781206)

Systems of linear equations of the form NEWLINE\[NEWLINEK\begin{pmatrix} u\\ p\end{pmatrix}= \begin{pmatrix} f\\ g\end{pmatrix},\quad K= \begin{pmatrix} A & B^T\\B & 0\end{pmatrix},NEWLINE\]NEWLINE where \(A\) is a symmetric, positive definite \(n\times n\) matrix and \(B\) is an \(m\times n\) matrix with full rank \(m\leq n\), arise in linearly constrained quadratic programming problems or saddle point problems. The coefficient matrix \(K\) is nonsingular and the negative Schur complement \(C= BA^{-1} B^T\) is symmetric and positive definite. Mathematically the system is equivalent to NEWLINE\[NEWLINEAu= f- B^T p,\qquad Cp= BA^{-1} f-g.NEWLINE\]NEWLINE Theoretically one can first compute \(p\) from the second equation and then \(u\) from the first equation. However, for large scale problems only approximate solvers for \(C\) and \(A\) are available. Two classes of methods are considered in this paper: inexact Uzawa algorithms and a class of methods with symmetric preconditioners. The author estimates the convergence rate of both classes by a common approach that involves a transformation of the iteration matrix. The obtained bounds are partially sharper than the estimates in the literature and their sharpness is confirmed by fairly extensive computations.