Computer Science 130
Solution Of Linear Systems By Gaussian Elimination
Block III - Assignment 1
Here's some additional help
and here's some base code to start with.
Use it cause it makes it A LOT easier and the TA's will be
a lot more willing to help if you start with the base
code.
Here's an example program
and some test files (Reducable and Not Reducable)
that you can try with your program and here's a file with the matrix from the notes.
To use these just download the files all to the same directory and then run "matrix.exe". Type 'y' to indicate
that you want to input the matrix from a file and then type the name of the text file that you want to
analyze and just let it do its thing. NOTE: The example program prints out a lot of info and you don't need to print in your program. It just prints a lot so that you can see exactly what's happening. And the
two test files should be general cases that you can use to test and make sure that your program
is working. Hope that helps (Later, There will be a larger test file that you can test your program with,
but these files will work for now).
A linear system is a set of linear equations in a set of
variables (unknowns). The following is a set of three equations in four variables:
3x+2y-z+w=7;
Any set of values for the equations that simultaneously satisfied all of the equations
is called a solution of the system. The system above has infinitely many solutions. One
of them is . You should try and find another solution. If the number of equations and
variables in a linear system are equal it frequently has a unique solution, exactly
one
set of values that satisfy all equations. One method for finding the unique solution of
such a system is called Gaussian reduction.
In Gaussian reduction a system is represented by its rectangular array (matrix) of
coefficients. The method of solution is to use equivalence preserving row operations on the rows of the matrix so as
to generate a sub-matrix equivalence to the identity matrix. The n-row, n-column identity matrix has
the value 1 in location (k,k) and value 0 elsewhere. Note that location (k,k) refers to the element
in the k-row and the k-column. The three by three identity matrix is given below.
When the matrix of coefficients is put in this form the values on the
rightmost column are the solutions to the set of equations.
Row Operations-The valid row operations are :(I) switch rows (II) multiply (divide) any row
by any non-zero constant (iii) add any non-zero multiple of any row to any other row, changing
only the row added to.
An example-Consider the following system of three equations in three unknowns.
Now we need 1 in the main diagonal.
Multiply row 0 by 1/2 and all values on the rows multiply this value too.
| 1 |
0.5 |
-0.5 |
0.5 |
| 0 |
3 |
3 |
0 |
| 4 |
2 |
3 |
2 |
We then look to get 0's below the main diagonal.
In row 1 there is 0 ,but not row 2. Multiply row 0 by -4 and add the result to row 2 Column
0 is now completed.
| 1 |
0.5 |
-0.5 |
0.5 |
| 0 |
3 |
3 |
0 |
| 0 |
0 |
5 |
0 |
Moving on to column 1, We need to find 1 in the main
diagonal. We multiply row 1 by 1/3. Next, we need 0's beneath the main diagonal.
0 is already in row 2.
| 1 |
0.5 |
-0.5 |
0.5 |
| 0 |
1 |
1 |
0 |
| 0 |
0 |
5 |
0 |
We then look to get 0's above the main diagonal.
We multiply row 1 by -0.5 and add this value to row 0
Moving to column 2, we multiply row 2 by -0.5 to get a
1 in the main diagonal.
| 1 |
0 |
-1 |
0.5 |
| 0 |
1 |
1 |
0 |
| 0 |
0 |
5 |
0 |
We move to column2,we multiply row 2 by 1/5.
Next we try to get 0's below the main diagonal,
and find there are no rows below the main diagonal. Finally, we get
0's above the main diagonal. We multiply row 0 by
1 and add the result to row 2. Then multiply
row 1 by -1 and add the result to row 2.
| 1 |
0 |
0 |
0.5 |
| 0 |
1 |
0 |
0 |
| 0 |
0 |
1 |
0 |
Now that you have the IDENTITY MATRIX (1's down
the main diagonal, 0's everywhere else except the answer column), the solution
for the matrix is the list of variables in the answer column (the last
column), or in this case:
-
What about a matrix where a solution cannot be found?
Your first sign of trouble is when you have a 0 in the main diagonal.
Check for this before you try to get a 1 in the main diagonal. If
you have a 0 in the main diagonal, search the rows below it for
another row that does not have a 0 in that same column. If you can
find some row that works, then switch the two rows (see the example above).
If you cannot find some other row that does not have a 0 in that column,
then a solution cannot be found for this matrix. Simply print a message
stating the problem and stop your program.
Return to the Block 3 Index
Return to the Lab Index
Return to the CS 130 Home Page