Last modified 2017-09-25 00:25:11 CDT

Ax=b and A=LU

To solve \( Ax=b \), first factorize:

\[A = LU\]

Then solve:

\[Lc = b\] \[c = L^{-1}b\]

Then solve:

\[Ux = c\] \[x = U^{-1}c\]

which makes sense since \( x = U^{-1}L^{-1} b = (LU)^{-1} b = A^{-1} b \).

Solving the systems \( Lc=b \) and \( Ux=c \) is fast, since the matrices \( L \) and \( U \) are triangular. It’s just forward and back substitution to solve.

Solving \( Lc=b \) brings the vector b to vector c, which is what it would have transformed to if you manipulated the augmented matrix into row echelon form, that is \( [\bf{A} b] \) into \( [\bf{U} c] \). In other words, \( L^{-1} \) carries out the row operations that bring \( A \) to \( U \).

Solving \( Ux=c \) brings the vector c to vector x, which is what you would have solved for if you manipulated the augmented matrix into row-reduced echelon form, that is \( [\bf{A} b] \) to \( [\bf{U} c] \) to \( [\bf{I} x] \) (for invertible n\(\times\)n A). In other words, \( U^{-1} \) carries out the row operations that bring \( U \) to \( I \).

Finding the matrix inverse \( A^{-1} \) is for suckers: Don’t invert that matrix!

\( A = LU \) also immediately gives you the determinant of \( A \). If a zero pivot was encountered during elimination of \( A \) (factorizing into \( LU \)), then you know \( det(A) = 0 \). If \( A \) successfully factorizes into \( LU \), then \( det(A) \) is just the product of the pivots which sit on the diagonal of \( U \): \( det(A) = u_{11} u_{22} u_{33} \ldots \).

Comments

Creative Commons License