On the iterative algorithm for large sparse saddle point problems (Q2507831): Difference between revisions

The authors consider nonsymmetric systems of linear algebraic equations of a block \(2 \times 2\) structure \[ \left( \begin{matrix} A & B^T \\ -B & 0 \end{matrix} \right) \left( \begin{matrix} x \\ y \end{matrix} \right) = \left( \begin{matrix} f \\ -g \end{matrix} \right), \enspace \underline A = \left( \begin{matrix} A & B^T \\ -B & 0 \end{matrix} \right), \] which are equivalent to the original saddle point problem \[ \left( \begin{matrix} A & B^T \\ B & 0 \end{matrix} \right) \left( \begin{matrix} x \\ y \end{matrix} \right) = \left( \begin{matrix} f \\ g \end{matrix} \right), \enspace \hat A = \left( \begin{matrix} A & B^T \\ B & 0 \end{matrix} \right), \] where \(A \in {\mathbb R}^{n \times n}\) is symmetric positive definite, \(B \in {\mathbb R}^{m \times n}\), \(m \leq n\), rank\((B) = m,\) \(x,f \in {\mathbb R}^n,\) \(y,g \in {\mathbb R}^m\). It is proved that the spectrum of \(\hat A\) consists of \(n\) positive and \(m\) negative eigenvalues, and that \(\underline A\) is positive stable, i.e., Re\((\lambda)>0\) for all \(\lambda \in \sigma (\underline A)\), \(\sigma\) the spectrum of \(\underline A\). That means, the eigenvalue distribution of \(\underline A\) is more favorable for the solution by simple methods. Based on the eigenvalue distribution and splitting the coefficient matrix including two preconditioning matrices a generalized relaxation method is developed, which contains the classical Uzawa's algorithm for the saddle point problem as a special case. By a proper choosing of the relaxation parameter the new method converges three times faster than the classical algorithm, which is also demonstrated by numerical examples.