Description
Design and Implement an Algorithm in Java to solve the following problem in solving linear equations using the Gaussian Elimination method.
Definition:
A system of linear equations can be placed into matrix form. Each equation becomes a row and each variable becomes a column. An additional column is added for the right hand side. A system of linear equations and the resulting matrix are shown.
Sample of linear equations …
3x + 2y – 4z = 3
2x + 3y + 3z = 15
5x – 3y + z = 14
becomes the augmented matrix … (transform the Linear Equation into Matrix form)
x y z Constants
3 2 -4 3
2 3 3 15
5 -3 1 14
The goal when solving a system of equations is to place the augmented matrix into reduced row-echelon form, if possible.
There are three elementary row operations that you may use to accomplish placing a matrix into reduced row-echelon form.
Each of the requirements of a reduced row-echelon matrix can satisfied using the elementary row operations.
• If there is a row of all zeros, then it is at the bottom of the matrix.
Interchange two rows of a matrix to move the row of all zeros to the bottom.
• The first non-zero element of any row is a one. That element is called the leading one.
Multiply (divide) the row by a non-zero constant to make the first non-zero element into a one.
• The leading one of any row is to the right of the leading one of the previous row.
Multiply a row by a non-zero constant and add it to another row, replacing that row. The point of this elementary row operation is to make numbers into zeros. By making the numbers under the leading ones into zero, it forces the first non-zero element of any row to be to the right of the leading one of the previous row.
• All elements above and below a leading one are zero.
Multiply a row by a non-zero constant and add it to another row, replacing that row. The point of this elementary row operation is to make numbers into zero. The difference here is that you’re clearing (making zero) the elements above the leading one instead of just below the leading one.
Definition of pivoting?
The objective of pivoting is to make an element above or below a leading one into a zero.
The “pivot” or “pivot element” is an element on the left hand side of a matrix that you want the elements above and below to be zero.
Normally, this element is a one. If you can find a book that mentions pivoting, they will usually tell you that you must pivot on a one. If you restrict yourself to the three elementary row operations, then this is a true statement.
However, if you are willing to combine the second and third elementary row operations, you come up with another row operation (not elementary, but still valid).
• You can multiply a row by a non-zero constant and add it to a non-zero multiple of another row, replacing that row.
So what? If you are required to pivot on a one, then you must sometimes use the second elementary row operation and divide a row through by the leading element to make it into a one. Division leads to fractions. While fractions are your friends, you’re less likely to make a mistake if you don’t use them.
What’s the catch? If you don’t pivot on a one, you are likely to encounter larger numbers. Most people are willing to work with the larger numbers to avoid the fractions.
The Pivot Process
Pivoting works because a common multiple (not necessarily the least common multiple) of two numbers can always be found by multiplying the two numbers together. Let’s take the example we had before, and clear the first column.
x y z Const
3 2 -4 3
2 3 3 15
5 -3 1 14
Selecting a Pivot
• Pick the column with the most zeros in it.
• Use a row or column only once
• Pivot on a one if possible
• Pivot on the main diagonal
• Never pivot on a zero
• Never pivot on the right hand side
Since there is no one in the first row, we have two options: Either we divide the first row by three and work with fractions, or we pivot on the three and get large numbers. That is the option I’m going to use. I’ll pivot on the three in R1C1. Go ahead and circle that as the pivot element. Depending on your browser, you may see the pivot elements circled in red or just with a * in front of it.
x y z Const
*3 2 -4 3
2 3 3 15
5 -3 1 14
The idea is to make the boxed numbers into zero. Using the combined row operation that could be done by 3R2 – 2R1 → R2 and 3R3 – 5R1 → R3.
The only row not being changed is the row containing the pivot element (the 3). The whole point of the pivot process is to make the boxed values into zero. Go ahead and rewrite the pivot row and clear (make zero) the pivot column.
x y z Const
*3 2 -4 3
0
0
To replace the values in row 2, each new element is obtained by multiplying the element being replaced in the second row by 3 and subtracting 2 times the element in the first row from the same column as the element being replaced.
To perform the pivot, place one finger on the pivot (circled number), and one finger on the element being replaced. Multiply these two numbers together. Now, place one finger on the boxed number in the same row as the element you’re replacing and the other finger in the pivot row and the same column as the number your replacing. Multiply these two numbers together. Take the product with the pivot and subtract the product without the pivot.
x y z Const
*3 2 -4 3
2 3 3 15
5 -3 1 14
To replace the 3 in R2C2, you would take 3(3) – 2(2) = 9 – 4 = 5.
To replace the 3 in R2C3, you would take 3(3) – 2(-4) = 9 +8 = 17.
To replace the 15 in R2C4, you would take 3(15) – 2(3) = 45 – 6 = 39.
To replace the -3 in R3C2, you would take 3(-3) – 5(2) = -9 – 10 = -19.
To replace the 1 in R3C3, you would take 3(1) – 5(-4) = 3 + 20 = 23
To replace the 14 in R3C4, you would take 3(14) – 5(3) = 42 – 15 = 27.
Here’s how the process looks.
x y z rhs
pivot row, copy
3 pivot row, copy
2 pivot row, copy
-4 pivot row, copy
3
pivot column, clear
0 3(3) – 2(2)
5 3(3) – 2(-4)
17 3(15) – 2(3)
39
pivot column, clear
0 3(-3) – 5(2)
-19 3(1) – 5(-4)
23 3(14) – 5(3)
27
Or, if you remove the comments, the matrix after the first pivot looks like this.
x y z rhs
3 2 -4 3
0 5 17 39
0 -19 23 27
It is now time to repeat the entire process. We go through and pick another place to pivot. We would like it to be on the main diagonal, a one, or have zeros in the column. Unfortunately, we can’t have any of those. But since we have to multiply all the other numbers by the pivot, we want it to be small, so we’ll pivot on the 5 in R2C2 and clear out the 2 and -19.
x y z Const
3 2 -4 3
0 *5 17 39
0 -19 23 27
Begin by copying down the pivot row (2nd row) and clearing the pivot column (2nd column). Previously cleared columns will remain cleared.
x y z Const
0
0 *5 17 39
0 0
Here are the calculations to find the next interation. Pay careful attention to the 3rd row where we’re subtracting -19 times a value. Since we’re subtracting a negative, I went ahead and wrote it as plus 19.
x y z rhs
5(3) – 2(0)
15 pivot column, clear
0 5(-4) – 2(17)
-54 5(3) – 2(39)
-63
pivot row, copy
0 pivot row, copy
5 pivot row, copy
17 pivot row, copy
39
previously cleared
0 pivot column, clear
0 5(23) + 19(17)
438 5(27) + 19(39)
876
And the resulting matrix.
x y z Const
15 0 -54 -63
0 5 17 39
0 0 438 876
Notice that all the elements in the first row are multiples of 3 and all the elements in the last row are multiples of 438. We’ll divide to reduce the rows.
x y z Const
5 0 -18 -21
0 5 17 39
0 0 1 2
That had the added benefit of giving us a 1, exactly where we want it to be to pivot. So, we’ll pivot on the 1 in R3C3 and clear out the -18 and 17. Circle your pivot and box the other numbers in that column to clear.
x y z Const
5 0 -18 -21
0 5 17 39
0 0 *1 2
Copy down the pivot row and clear the pivot column. Previously cleared columns will remain cleared as long as you don’t pivot in a row or column twice.
x y z Const
0 0
0 0
0 0 *1 2
Notice that each time, there are fewer calculations to perform. Here are the calculations for this pivot. Again, since the value in the pivot column in the first row is -18 and we’re subtracting, I wrote it as + 18.
x y z rhs
1(5) +18(0)
5 previously cleared
0 pivot column, clear
0 1(-21) + 18(2)
15
previously cleared
0 1(5) – 17(0)
5 pivot column, clear
0 1(39) – 17(2)
5
pivot row, copy
0 pivot row, copy
0 pivot row, copy
1 pivot row, copy
2
And the resulting matrix.
x y z Const
5 0 0 15
0 5 0 5
0 0 1 2
Notice that the first and second rows are multiples of 5, so we can reduce those rows.
x y z Const
1 0 0 3
0 1 0 1
0 0 1 2
And the final answer is x = 3, y = 1, and z = 2. You can also write that as an ordered triplet {(3,1,2)}.
Hopefully, you noticed that when I worked this example, I didn’t follow the hints I gave. That’s because I wanted you to see what happens if you don’t pivot on a one. There was a one, on the main diagonal, in the original matrix, and it would have been better to start there.
Summary
• Pick your pivot element wisely.
• Picking a column with zeros in it means less pivoting.
• Picking a one as the pivot makes the numbers smaller, the multiplication easier, and leaves the non-zero elements in a cleared column the same (less pivoting)
• Pivoting on the main diagonal means you won’t have to switch rows to put the matrix into reduced row-echelon form.
• Do not pivot on a zero.
• Do not pivot on the right hand side.
• Only use a row or column once
• Take the product with the pivot minus the product without the pivot
Special Cases
If you get a row of all zeros except for the right hand side, then there is no solution to the system.
If you get a row of all zeros, and the number of non-zero rows is less than the number of variables, then the system is dependent, you will have many answers, and you need to write your answer in parametric form.
