Homework 10
Version 1

 

Due by 8:00 AM on Monday, November 8, 1999

Clarifications: This assignment is somewhat vague about the format for printing output, so the graders will accept a range of output formats. However, be sure to display your output in a way that is easy for the graders to read. In particular, make your numbers line up in columns and limit precision to relatively few (e.g. 2 or 3) digits after the decimal point.

In this assignment you will write a program called Gauss which solves linear equations using a technique called Gaussian Elimination. This program will consist of a series of methods, each doing part of the task.

Don't worry, it's not nearly as hard as it sounds! There are just a few simple steps. To help you understand, let's look at the process in terms of an example. Consider the following set of three linear equations in three unknowns (the variables x, y, and z):

2x + 4y + 5z = 34
2x + 7y + 4z = 36
3x + 5y + 4z = 35

Our goal is to do a series of operations such that the coefficients along the diagonal all end up 1, and all the other coefficients end up 0. When we have reached this configuration, we will be able to read off the values of the variables directly. Obviously, the operations we perform must be such that they do not disturb the meaning of the equations.

Throughout this example, we'll always show all the variables and coefficients, even when the coefficient is 0 or 1, just to make things clear. Also, in each step we'll draw a pointer in front of each equation that has changed since the previous step.

The first step is to divide the first equation by 2, which is the coefficient of x in that equation. That will make the coefficient of x in the first equation 1:

--> 1x + 2y + 2.5z = 17
2x + 7y + 4z = 36
3x + 5y + 4z = 35

Now, notice that if we subtract twice the new first equation from the second equation, the coefficient of x in the second equation will become 0. Similarly for the third equation, if we use thrice the new first equation. So that's what we do:

1x + 2y + 2.5z = 17
--> 0x + 3y + -1z = 2
--> 0x + -1y + -3.5z = -16

Next we repeat the process, dividing the second equation by 3 so that its y coefficient becomes 1:

1x + 2y + 2.5z = 17
--> 0x + 1y + -0.33z = 0.66
0x + -1y + -3.5z = -16

Then we subtract twice the second equation from the first, and minus-one of it from the third. This will get the coefficient of y to 0 in the first and third equations (notice that since we have zeroed out the coefficients of x in all but the first equation, we won't mess up the x coefficients by doing this):

--> 1x + 0y + 3.16z = 15.66
0x + 1y + -0.33z = 0.66
--> 0x + 0y + -3.83z = -15.33

Finally, we divide the third equation by -3.83 to get its z coefficient to 1, and subtract 3.16 and -0.33 of the result from the first and second equations, respectively, to zero their z coefficients:

--> 1x + 0y + 0z = 3
--> 0x + 1y + 0z = 2
--> 0x + 0y + 1z = 4

Thus, the solution of these equations is:

x = 3
y = 2
z = 4

Now, the thing to notice is that the variables play no role in this process; only the coefficients matter. If we take the variables out, all we are doing to solve a system of 3 equations in 3 unknowns is manipulating a 3 by 4 array of coefficients.

Here is a description of the methods you need to write to implement the linear equation solver. All the methods operate on N by (N+1) array of doubles. So, in the example, the 3 by 4 coefficient array started out as:

2 4 5 34
2 7 4 36
3 5 4 35

The first method takes no parameters, and returns the coefficient array as input by the user. All of the remaining methods take a coefficient array and manipulate its contents in place. Therefore, they have return type void since they have nothing to return. In describing each method I have also specified the names you should give the formal parameters to simplify grading.

  1. Write a method readCoeffs which asks the user for the number of equations. It then allocates an n by n+1 (where n is the number of equations) array, coeffs, and fills it in using input from the user. It then returns this array as the method's result.

  2. Write a method printCoeffs which takes the coefficient array, coeffs, and displays it in a readable manner for the user.

  3. Write a method normalizeEquation which takes the coefficient array coeffs and an integer eqnNum as parameters. It then divides the coefficients of the eqnNum'th equation by the coefficient of the eqnNum'th variable in that equation. So, in the first step of the example we called normalizeEquation with 0 for eqnNum (this refers to the first equation). So all of the coefficients in row 0 of the array were divided by the value in column 0 (the first column) of that row, which had the value 2.

  4. Write a method subtractEquation which takes the coefficient array coeffs, and two integers, eqn1 and eqn2, as parameters. eqn2 identifies the row being subtracted from, and eqn1 identifies the row being subtracted from it. Now, the goal is to get the eqn1'th coefficient of the eqn2'th row to be 0. So, subtract coeffs[eqn2][eqn1] times the eqn1'th row from the eqn2'th row. (This assumes, as you may, that the eqn1'th equation has already been normalized so its eqn1'th coefficient is 1.) So, in the second step of the example we called subtractEquation twice. In each case eqn1 was 0 (the first equation) and eqn2 was 1 in the first call and 2 in the second call (designating the second and third equations, respectively.)

  5. Write a method solveColumn which takes the coefficient array coeffs and an integer column number colNum as parameters, and uses the methods written in the last two parts to get that column to be all zeroes except for a 1 in the appropriate row. So, the first two steps of the example can be seen as the results of a single call to solveColumn with colNum set to 0.

  6. Write the method solve which takes the coefficient array as a parameter and calls the method solveColumn as needed to solve the system of equations.

Use these methods to write a program that will input coefficients from the user, solve the corresponding system of equations, and print the solution array.

NOTE: In general Gaussian Elimination can be tricky as the input may not be well behaved. In particular, you may find that you don't actually have n distinct equations because one may be a linear combination of some of the others. If this happens there is not enough information to solve the system completely, and Gaussian elimination will lead one of the rows of the array to be all zeroes. This in turn will likely lead to a division by zero error. You need not worry about this and related problems. Just implement the naive algorithm; we will only test it on well behaved input. If you are interested in the more general solution, see me and I can point you at some references.

Last modified August 28 for Fall 99 cs5 by fleck@cs.hmc.edu

This page copyright ©1998 by Joshua S. Hodas. It was built with Frontier on a Macintosh . Last rebuilt on Wed, Oct 21, 1998 at 1:31:16 AM.
http://www.cs.hmc.edu/~hodas/courses/cs5/week_10/homework.html