5
$\begingroup$

So lets say that I need to invert a matrix that is generally dense and is poorly conditioned. What are some ways I can get an accurate inverse?

Here are my candidates:

  1. SVD Inverse
  2. Inverse Via Cholesky Decomposition
  3. Inverse Via LU Decomposition
  4. Inverse Via QR Decomposition

Are there any other methods I am missing? Of all of them, which is the most robust to ill-conditioning? And why?

My thought is that it has to do with operation count. The smaller the number of operations needed, the less ability for error to propagate. So the most 'stable' methods are the ones with the lowest operation counts.

Edit: I only want to find the inverse of the matrix, not actually solve a linear system.

$\endgroup$
3
  • 1
    $\begingroup$ The QR methods are robust. $\endgroup$
    – copper.hat
    Mar 14, 2016 at 16:11
  • $\begingroup$ Copper -- Thanks for the suggestion! I will add that to the list. My understanding is that QR decomposition is something special -- It is computing the Gram-Schmidt orthogonalization of the column space. This orthogonality is what makes it more robust, am I correct? $\endgroup$
    – The Dude
    Mar 14, 2016 at 16:26
  • $\begingroup$ Multiplying by orthogonal matrices is about as stable as things get in the numerical analysis world, and this is how QR methods work, hence the robustness. The price paid is an increase in computational cost (very roughly this is about a 2x price, but this is just my rule of thumb). $\endgroup$
    – copper.hat
    Mar 14, 2016 at 16:32

1 Answer 1

Reset to default
2
$\begingroup$

Flop counts are presented in Comparing LU or QR decompositions for solving least squares.

From Matrix Computations, Golub and Van Loan, 3e $\S$ 5.7.1, p. 270

Comparing flop counts for operations on $n\times n$ matrices:

$\frac{2}{3}n^{3}\ $ $\qquad$ Gaussian elimination

$\frac{4}{3}n^{3}\ $ $\qquad$ Householder orthogonalization

$2n^{3}$ $\qquad \ \ $ Modified Gram-Schmidt

$12n^{3}$ $\qquad$ Singular Value Decomposition

The SVD is the gold standard in terms of handling ill-conditioned problems. The $\mathbf{Q}\mathbf{R}$ is also a good choice.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .