Menu
In the "black book", Numerical Recipes 3rd edition, the Gauss-Jordan algorithm for solving a system of linear equations is given. Directly afterwards is a section on computing an LU decomposition and then subsequently using that to solve a system of linear equations (see LUdcmp::solve on p. 53). Unfortunately, the book does not explain why one would prefer one method to another. Are the two approaches equivalent, or are there reasons to prefer one method to the other for particular situation?
771
LU decomposition is a better way to implement Gauss elimination, especially for repeated solving a number of equations with the same left-hand side. That is, for solving the equation Ax = b with different values of b for the same A.
In this case, LU−decomposition works more efficiently than Gauss elimination as you do not need to solve all augmented matrices. You just have to decompose A into LU (or Gaussian elimination with cost ~ n3) once.
The Gauss-Jordan method is similar to the Gaussian elimination process, except that the entries both above and below each pivot are zeroed out. After performing Gaussian elimination on a matrix, the result is in row echelon form, while the result after the Gauss-Jordan method is in reduced row echelon form.
The difference between Gaussian elimination and the Gaussian Jordan elimination is that one produces a matrix in row echelon form while the other produces a matrix in row reduced echelon form.
The advantages of using an LU decomposition would be that it can be reused to compute multiple solutions.
For example if you want to solve the equation
Ax = b
for a constant A and many different bs then you only need to calculate the LU decomposition of A once and it can be reused for each b. However with Gauss-Jordan elimination you would have to re-do all the work for each b
The reason this is faster is because Gauss-Jordan elimination scales as O(n^3) but the substitution step of the LU decomposition method only scales as O(n^2). Therefore for the LU case you would only have to do the expensive O(n^3) step once for each b.
A reasonable set of notes on exactly this can be found here
171
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
