wikiHow is a “wiki,” similar to Wikipedia, which means that many of our articles are cowritten by multiple authors. To create this article, volunteer authors worked to edit and improve it over time.
This article has been viewed 18,230 times.
Learn more...
To solve systems of three or more linear equations, one typically converts the problem into an augmented matrix and row reduces from there. However, this is slow and woefully inefficient with more equations. The number of arithmetic operations one needs to compute goes up by the factorial of the dimension of the matrix, so that systems of six or more equations are impractical to solve by hand. In real life, systems of 1000 equations are not uncommon  even 50 equations involves computing a comparable number of operations to the number of atoms in the visible universe.
There is another method that reduces the amount of operations to the cube of the dimension of the matrix. This is called LU factorization  it decomposes a matrix into two triangular matrices  for upper triangular, and for lower triangular  and after the appropriate setup, the solutions are found by back substitution. Some computers use this method to quickly solve systems that would be impractical to deal with via rowreduction.
In this article, we will show how to perform an LU factorization for a system of three equations, for simplicity.
Steps Download Article

1Begin with the matrix equation. Fundamentally, a system of equations can be written in terms of a matrix equation where matrix acts on a vector to output another vector It is often the case that we wish to know and this is no exception. In LU factorization, we will see that we can define the relation where and are both triangular matrices.

2Rowreduce to rowechelon form. The rowechelon form will become our matrix


 The matrix is in rowechelon form now.
Advertisement 

3Obtain by undoing your rowreduction steps. This step may be a bit tricky at first, but we are essentially constructing a matrix by going backwards.
 Let's look at the most recent row reduction We found the new row 3 by replacing it with a linear combination of the old rows of the matrix. Now, we wish to find the old row 3, so simply solve.
 This undoes the second rowreduction. Now, we put it in matrix form. Let's call this matrix The column vector to the right simply clarifies what we are doing  this matrix we are constructing is a linear transformation that does the same thing as what we just wrote above. Observe that, since we didn't do anything to the top two rows, the resulting elements for the two rows in this matrix are the same as in the identity matrix. Only the third row changes.
 Construct the matrix that undoes the first rowreduction. Similarly, we are solving for the old row 2 and 3. We'll call this matrix
 Multiply the matrices in the order that we found them. This means that If you did the multiplication correctly, you should get a lower triangular matrix.
 Let's look at the most recent row reduction We found the new row 3 by replacing it with a linear combination of the old rows of the matrix. Now, we wish to find the old row 3, so simply solve.

4Rewrite the matrix equation in terms of . Now that we have both matrices, we can see below that acting on the vector outputs
 Since is a vector, let Then, we see that The goal here is to first solve for then plug into to solve for

5Solve for . Because we are dealing with triangular matrices, backsubstitution is the way to go.

6Solve for . This will again involve backsubstitution, because is triangular.
 Although this method may not seem very efficient to you (and indeed, LU factorization for systems of three equations is no better than rowreduction), computers are wellequipped to perform backsubstitution, so the results really show as the number of equations goes up.
Advertisement