Gaussian Elimination
The system of linear equations $Ax = b$ may be solved by using Gaussian Elimination (GE) arriving to a Row Echelon Form R of the augmented matrix $[A b]$, and then using back-substitution.
LU Decomposition
Another way to solve $Ax = b$ is to use LU Decomposition. It follows the same procedure than GE, but it records the Elimination steps (inverse) into a matrix L, and does not augment $A$. So it just involves operating on $A$.
One could describe it as:
$A \rightarrow_{E_1} B \rightarrow_{E_2} C \ldots \rightarrow_{E_n} \rightarrow U$
And in compact manner $E_n\ldots{}E_2E_1 A = U$ or just $E_{total} A = U$ and then also $ A = E_{total}^{-1} U $, where the new $E^{-1} = L$
It seems this would still require solving $Ux=Eb$, but I may be wrong.
Comparison
LU has some extra work compared to plain GE:
- Record the elimination changes
- Get the inverse of $E$ i.e $L$ (but in this case inverse seems straight forward)
- LU allows easy calculation of the determinant $det(A) = det(L) det(U)$ as compared to GE, since GE calculates as
where $d$ is the product of constants and also signs (details in the wikipedia article.)
- LU does not take the $b$ into account, $b$ is not appended onto $A$, which makes the solution more general/robust.
On the other hand, GE uses an expanded matrix with $b$ appended as a column, which means that for another $b$ and same A we would be repeating calculations.
Question
- Are these the reasons to do LU decomposition i.e that we reuse U for more $b$s just by applying $Lb$ and that we can compute D(A) more easily ?
- Is this even correct ?
I've read this related posts, none actually asks this exact question I think first, second.