Computer Science
15-111 (Sections A & B), Spring 2007
Class Notes: 31-Jan-2007
Logistics
Topic Outline:
1. 2d Arrays: Gaussian Elimination
See the appended discussion, then review the code we wrote in class: GaussianElimination.java.
2. Quiz 2.
Discussion on Gaussian
Elimination
We discussed how to solve a system of N linear equations in N unknowns using
Gaussian Elimination. Here is a full
example of this approach which demonstrates precisely how our code in
GaussianElimination.java works.
Step 1: Start with the answer (well,
when you are making the problems up, this is the easiest way to do it):
x = 1
y
= 2
z = 3
Step 2: Write N equations for your N
variables, choosing random coefficients and solving using the values from
above.
(Note: I’ll rewrite the equations on the
right without the variables, so they appear as the 2d array of doubles that
we’ll actually use in Java):
2x + 3y - 4z = -4 |
2 3 -4 -4
x – 2y + z =
0 | 1
-2 1 0
-x +
y + 2z = 7 |
-1 1 2 7
Step 3: Our target is to manipulate
these equations into this form:
1x + 0y
+ 0z = ?
| 1 0
0 ?
0x + 1y
+ 0z = ?
| 0 1
0 ?
0x + 0y + 1z
= ?
| 0 0
1 ?
The reason: once we are in this form, we can read our
answer directly (the first line gives the answer for x, the second for y, the
third for z). For those interested, in
math this is called reduced row echelon form.
Step 4: To get to that form, we move
along the diagonal. For each coefficient
on the diagonal, we first set it equal to 1, then use that 1 to set all the
other coefficients in its column to 0.
Step 4.0: Process Column 0
Step 4.0.a: Set c[0][0] to 1. Do this by dividing the equation by 2 in this
case. In general, we divide the entire
row by the value stored at c[0][0]. This
gives us:
1x + 1.5y -
2z = -2 | 1 1.5 -2 -2
1x – 2y + 1z =
0 | 1
-2 1 0
-1x +
1y + 2z = 7 |
-1 1 2 7
Step 4.0.b.1: Set c[1][0] to 0. Do this by subtracting c[1][0] times equation
0 (that is, row 0) from equation 1 (that is, row 1). THINK ABOUT THIS!!!!! This gives us:
1x + 1.5y - 2z = -2 | 1
1.5
-2 -2
0x – 3.5y
+ 3z = 2
| 0
-3.5 3
2
-1x +
1y + 2z = 7 |
-1 1 2 7
Step 4.0.b.2: Set c[2][0] to 0. Do this by subtracting c[2][0] times equation
0 (that is, row 0) from equation 2 (that is, row 2). THINK ABOUT THIS!!!!! This gives us:
1x + 1.5y - 2z = -2 |
1 1.5 -2 -2
0x – 3.5y + 3z = 2
| 0 -3.5 3 2
0x + 2.5y
+ 0z = 5
| 0 2.5 0 5
Now look at Column 0: it is in the final
form (a 1 on the diagonal, 0’s elsewhere)!!!
Step 4.1: Process Column 1
Step 4.1.a: Set c[1][1] to 1. Do this by dividing equation 1 by -3.5 in
this case. In general, we divide the
entire row by the value stored at c[1][1].
This gives us:
1x + 1.5y - 2z = -2
| 1 1.5 -2 -2
0x + 1y - 0.86z = -0.57 | 0 1 -0.86 -0.57
0x + 2.5y + 0z = 5 | 0 2.5 0 5
As you can see, even if
our original coefficients and our solutions are all integers, we can get some
doubles along the way, which creates some roundoff error. So our answers with this technique are approximate.
Step 4.1.b.1: Set c[0][1] to 0 by
subtracting c[0][1] times equation 1 from equation 0:
1x + 0y – 0.71z = -1.15 | 1 0 -0.72 -1.15
0x + 1y - 0.86z = -0.57 | 0 1
-0.86 -0.57
0x + 2.5y + 0z = 5 | 0 2.5 0 5
Step 4.1.b.2: Set c[2][1] to 0 by subtracting c[2][1] times
equation 1 from equation 2:
1x + 0y – 0.71z = -1.15 | 1 0 -0.72 -1.15
0x + 1y - 0.86z = -0.57 | 0 1
-0.86 -0.57
0x + 0y + 2.15z
= 6.43
| 0 0 2.15 6.43
Now look at Column
1: it is in the final form (a 1 on the
diagonal, 0’s elsewhere)!!!
Step 4.2: Process Column 2
Step 4.2.a: Set c[2][2] to 1. Do this by dividing equation 2 by 2.15 in
this case. In general, we divide the
entire row by the value stored at c[2][2].
This gives us:
1x + 0y – 0.71z = -1.15 | 1 0 -0.72 -1.15
0x + 1y - 0.86z = -0.57 | 0 1
-0.86 -0.57
0x + 0y + 1z = 2.99 |
0 0 1 2.99
Step 4.2.b.0: Set c[0][2] to 0 by
subtracting c[0][2] times equation 2 from equation 0:
1x + 0y + 0z = 0.97
| 1 0 0 0.97
0x + 1y - 0.86z = -0.57 | 0 1
-0.86 -0.57
0x + 0y + 1z = 2.99 | 0 0 1 2.99
Step 4.2.b.0: Set c[1][2] to 0 by
subtracting c[1][2] times equation 2 from equation 1:
1x + 0y + 0z = 0.97
| 1 0 0 0.97
0x + 1y + 0z = 2.00 | 0 1 0 2.00
0x + 0y + 1z = 2.99 | 0 0 1 2.99
And now we are in reduced row echelon form!!!
So:
Step 5: Read your answer from the
rightmost column!
x = 0.97
y
= 2.00
z = 2.99
Yikes! These are almost
correct (the correct answers are 1,2,3).
The reason for the errors is that we rounded off our values along the
way to 2 decimal places. Hence, here we
should round our answers, say, to one decimal
place. If we do that, we get:
x = 1.0
y
= 2.0
z = 3.0
Whew! That’s better! Now, Java will suffer this same problem of
double math being only approximate and not exact, but fortunately Java uses
many more significant digits than we did here, so the answers still work out to
be very close to the exact answers.