14
$\begingroup$

Many linear algebra books include two versions of row reduction for solving systems of linear equations:

(1) Reduce to echelon form, and then use back substitution.

(2) Reduce to reduced echelon form (i.e. Gauss-Jordan elimination) and then read off the answer directly from the matrix.

My question is: what are the pedagogical reasons for including both of these approaches? In particular, why not just use the Gauss-Jordan approach from the beginning? Is there some advantage to covering back substitution?

Improve this question
$\endgroup$
1
  • $\begingroup$ AFAIR, reducing to echelon form is more efficient, but a bit harder to understand... $\endgroup$
    – vonbrand
    Commented Mar 15, 2014 at 18:25

3 Answers 3

Reset to default
15
$\begingroup$

One reason to know back substitution is that it is relevant when doing numerical mathematics.

A standard procedure to numerically solve linear systems $Ax =b$ especially if one wants to solve for more then one $b$ (which is very common) is to perform an $LU$-decomposition of $A$ (or something similar like a Cholesky decomposition), that is one decomposes $A$ as a product of a lower triangular matrix $L$ and an upper triangualar matrix $U$ (sometimes one needs permutation matrices in addition but let us ignore this detail).

Then, one solves the two triangular systems $Ly=b$ and $Ux=y$, via back substitution, which is very 'cheap' relative to solving a general linear system ($O(n^2)$ vs $O(n^3)$).

One might now ask why not solve the triangular systems via Gauss--Jordan elimination, and I do not fully oversee momentarily if there is even a difference depending on how one sets things up precisely. Still the two things, reducing to triangular systems and solving the triangular systems, are conceptually quite different, and that this difference is stressed when one uses back substitution could be considered as an advantage.

Improve this answer
$\endgroup$
11
$\begingroup$

When I teach the $L U$-decomposition, mentioned in quid's answer, I use the following mnemonic:

Single $\vec{b}$? Use GE.
Several to do? Use LU.

The point being that if you need to solve $A \vec{x} = \vec{b}$ for several $\vec{b}$ then the $L U$-method is more efficient than setting up a full Gaussian Elimination for each individual $\vec{b}$. In terms of the algorithm, the forward bit is the same for any $\vec{b}$ but the back part depends on $\vec{b}$. Yes, you can do the back part with a generic $\vec{b}$ and then substitute in for your actual $\vec{b}$, but that doesn't actually save you many computation steps and may cost you some depending on the actual values you're computing with.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I accept this as a reason why someone might still teach the back-substitution, but the necessity of doing LU is a bit lost on me. Firstly, if the matrix isn't square then you can't do LU. But even if it is, if you had several $b$'s, couldn't you put them all as columns in one big augmented matrix $[A|b_1|b_2|...]$ and do Gauss-Jordan on it and read off all the answers? Alternatively, you could do all the matching row ops on an identity matrix as you go to produce a matrix $E$ (like you do when you find the inverse) and then use it to find the answers $Eb_1$, $Eb_2$ etc. $\endgroup$
    – DavidButlerUofA
    Commented Nov 5, 2014 at 3:04
  • 3
    $\begingroup$ @DavidButlerUofA You are incorrect. You can do LU on any matrix. The L part will be square and the U part will be the same shape as the original matrix. LU is also more flexible than doing Gauss-Jordan on a massive matrix since you might not know all of the b's at the same time to make that massive matrix: maybe each b corresponds to the data from a different day and you want to do the calculation as each b is known. Lastly, back substitution is more efficient than matrix multiplication and the key benefit of LU that I am advocating here is efficiency. $\endgroup$
    – Andrew Stacey
    Commented Nov 6, 2014 at 17:42
  • $\begingroup$ Thanks for clearing that up @loop-space. When I read online about LU decomposition it said U had to be upper triangular, and I always thought the definition of "upper triangular" included the stipulation that the matrix had to be square. As to the efficiency I can see how back-substitution might use less multiplications and additions overall than matrix multiplication. I am less sure this payoff will offset having to solve $Ux=b$ first every time, but I can possibly believe it. $\endgroup$
    – DavidButlerUofA
    Commented Nov 6, 2014 at 21:18
  • $\begingroup$ ... my problem is that if I as a mathematician (albeit a pure mathematician whith no experience in numerical methods) had to be convinced, will discussing this actually help, say, a first year student? Especially considering the systems they encounter are so small that the difference would be minimal? $\endgroup$
    – DavidButlerUofA
    Commented Nov 6, 2014 at 21:21
  • $\begingroup$ @DavidButlerUofA Actually, I found that students were interested in, and saw the necessity of, efficiency of algorithms more than pure mathematicians tend to be. Solving Ux=b is back-substitution. What you have to do first is replace b by L^{-1}b (and, incidentally, the LU method computes L^{-1} rather than L so there's no matrix inversion going on here) but as L is triangular, this is a cheap matrix multiplication. $\endgroup$
    – Andrew Stacey
    Commented Nov 6, 2014 at 22:21
-1
$\begingroup$

If both approaches are known, then one can be used as a check on the other. If the answers disagree, there has been a mistake somewhere.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.