1
$\begingroup$

I'm reading a chapter about LU factorization. The way i understand it is that you take a normal equation where A is some matrix:

$$Ax = b$$

and you use normal elimination to factor A into lower and upper triangular parts L and U, which you store. Then, using these parts you can solve x for different values of b, without having to go through the process of Gaussian elimination over and over again for A (say you need to solve for a few million different b's).

Couldn't you just as easily do elimination to obtain the inverse of A, store the inverse, and then just solve for different b's?

$$x = bA^{-1}$$

I understand that since L and U have triangular forms, you can use simple substitution. Is that what makes LU factorization faster than using the inverse? Or is there some other benefit of LU factorization that I'm not understanding?

$\endgroup$
3
$\begingroup$

The first rule of numerical linear algebra is: You do not find inverse matrices. The reason for this is that matrix inversion is very numerically unstable, i.e the floating point arithmetic of the computer can yield huge errors when computing $A^{-1}$. Naturally, if the computed $A^{-1}$ has large error, you may as well discard any results of type $x = A^{-1} b$.

For this reason, there are a lot of methods where you do not compute $A^{-1}$. As you noticed correctly, the LU decomposition mimics the use of $A^{-1}$ but it is more stable than taking inverse. Notice I am not saying it is stable, just that it is more stable. To ensure stability, you need to do Gaussian elimination with partial pivoting: look it up if you are interested.

$\endgroup$

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.