Matrix inversion using decomposition

Question

Why do I need $LU$, $QR$ and other matrix decomposition tech to find the inverse of a matrix?

Please if possible provide a ref for the answer.

Thanks in advance

Answer 1

If you have the $A=LU$ decomposition, then you could get the the $A^{-1}$ inverse matrix of course with $A^{-1}=U^{-1}L^{-1}$. Computer algebra systems often use the method to calculate the inverse matrix. You can read about it at LU decomposotion wikipedia article. This paper also write about it. You can find details about it also in the following book.

Gene H. Golub – Charles F. Van Loan: Matrix Computations. Third Edition. The Johns Hopkins University Press, Baltimore and London, 1996. at page 121.

If you have the $A=QR$ decomposition, you get analogous $A^{-1}=R^{-1}Q^{-1}$. Because $Q$ is orthogonal, you get $A^{-1}=R^{-1}Q^{-1}=R^{-1}Q^{T}$. You can read more about it in the answer.

Answer 2

There are two reasons:

1) computational efficiency - number of elementary operations required,

2) numerical stability - exact digits in the results.

The Cramer method, as taught in high school, requires an awfully high number of operations (more than N!, which is huge, O(N^N)). Never use it for N>3.

Other approaches, such a the Jacobi or Gauss methods are much better in this respect, taking "only" O(N³) operations. This is close to optimal, even though the theoretical complexity of matrix inversion is known to be lower (the best estimate is O(N^2.373...)).

The theoretical algorithms are reserved to really big arrays (or are just impractical), but it would be foolish not to use an efficient O(N³) method.

Also, depending on the properties of the algorithms and the condition of the matrices, accuracy can range from poor to excellent. For instance, Gaussian elimination is way better with partial or total pivoting than without. This is an advanced topic which is hard to summarize here.

You can find more information in the books Numerical Recipes (Teukolsy & al.), or Matrix Computations (G. Golub & al.).

It can also be worth to take a look at the manuals of the linear algebra packages available (such as LAPACK, LINPACK... http://en.wikipedia.org/wiki/Comparison_of_linear_algebra_libraries) and check the recommendations on the algorithms to use in different situations.