1
$\begingroup$

I have a system with below coefficient matrix

$$ C = \begin{pmatrix} A & B^T \\ B & D \end{pmatrix},$$

where, $A$ and $D$ are square and positive definite. Furthermore, if $B$ be square, then $B$ will be positive definite (it is optional). It is possible that the condition number of $C$ will be large. How can solve this system to avoid numerical problem as much as possible.

$\endgroup$
  • $\begingroup$ I have added more information about QR factorizations in response to the OP's question. $\endgroup$ – Carl Christian Jun 1 '16 at 19:07
3
$\begingroup$

Please notice that you assumptions do not preclude singular matrices. A specific example is \begin{equation} C = \begin{bmatrix} I & I \\ I & I \end{bmatrix} \end{equation} where $I$ denotes the identity matrix of dimension $I$. This example also shows that the condition that $B$ is positive definite is not necessarily useful.

I appreciate the fact that you have simplified your question by removing the context and presenting the bare mathematical facts. However, I fear that you may have gone too far and that important information has been lost, i.e. you matrix appears worse than it really is.

Assuming that the matrix is not to ill conditioned, then you can solve \begin{equation} Cx = \begin{bmatrix} A & B^T \\ B & D \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} f_1 \\ f_2 \end{bmatrix} \end{equation} by passing to the Schur complement system \begin{equation} S x_2 = (D - B A^{-1} B^T) x_2 = f_2 - B A^{-1} f_1 \end{equation} which you solve for $x_2$. This is attractive, if $D$ is small, and it is easy to solve systems with coefficient matrix $A$. It is less attractive, if $D$ is large as $S$ is likely a dense matrix.

If the system is ill-conditioned, then the best course of action is to do a QR factorization with column pivoting $AP = QR$. By inspecting $R$ you will at least get information about, say, the numerical rank of $A$ and you might find that $f$ is in the range of your matrix anyway.

EDIT: The rank revealing QR factorization with column pivoting $AP = QR$ is a closely related to the Gram-Schmidt algorithm for computing an orthogonal basis for the column space of $A$. Here $P$ is simply a permutation matrix which is often picked to ensure that the diagonal entries of the upper triangular matrix $R$ are monotone decreasing. The strength of having a factorization of the form

$$ AP = Q R = Q \begin{bmatrix} R_{11} & R_{12} \\ 0 & R_{22} \end{bmatrix} $$

is that you can start to make estimates of the singular values of $A$ in terms of the matrices $R_{11}$ and $R_{22}$. A good book which is freely available from MIT's website is "Matrix Computations" by Golub and van Loan.

http://web.mit.edu/ehliu/Public/sclark/Golub%20G.H.,%20Van%20Loan%20C.F.-%20Matrix%20Computations.pdf

Among the many topics discussed you will find QR factorizations. I am not familiar with the following report on rank revealing QR factorizations, but the authors are of a caliber where I am confident that this report is also good

ftp://ftp.mcs.anl.gov/pub/tech_reports/reports/P559.pdf

QR factorization with column pivoting is implemented in LAPACK. This is a link to the relevant node

http://www.netlib.org/lapack/lug/node42.html

$\endgroup$
  • $\begingroup$ Very Tanks. Your idea is excellent. Can you explain your answer more than more in the ill-conditioned state? $\endgroup$ – Hamed Maz Jun 1 '16 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.