24. Gaussian elimination

Bisection and Newton's method let you find solutions to an equation of the form F(x) = 0. Gaussian elimination lets you find the solution to a system of linear equations of the following form:

For example, consider the following equations where n is 2:

The solution to these equations includes the values for x₁ and x₂ that make both of the equations true. In this example, you can plug in the values x₁ = -1 and x₂ = 4 to verify that those values form a solution.

This problem asks you to use Gaussian elimination to solve systems of equations. Unfortunately, you need to know a fair amount of background to use Gaussian elimination.

To perform Gaussian elimination, you first represent the equations as a matrix multiplied by a vector of variables x₁, x₂, ... , x_n giving a vector of constants C₁, C₂, ... , C_n, as shown in the following matrix equation:

Next, you convert this into an augmented matrix that holds the original coefficients plus two extra columns, one to hold the C values and one to hold the final solution. Initially, that final column should be initialized to all zeros, as shown in the following matrix:

Now you perform row operations to reduce this augmented matrix into an upper triangular form.

In a row operation, you can add multiples of one row to another row. For example, if you add –A₂/A₁ times the first row to the second row, then the new second row has a 0 in its first position. That row's other positions will depend on the other values in the two rows. For example, the entry in its second column will be B₂ - A₂/A₁ × B₁.

The important thing about row operations is that they do not change the truth of the system of equations. If a set of values (x₁, x₂, ..., x_n) solves the original equations, then those values also solve the equations after you perform row operations.

Start by using row operations on the first row to zero out the first entries in all rows after row zero. Next, use row operations with the second row to zero out the entries in the second column below that row. Continue using the k^th row to zero out the entries in column k in the rows that follow until the augmented matrix has an upper triangular form, like the following:

You may run into a problem when you try to put the augmented matrix into upper triangular form. When you're considering row k, you may find that it has a 0 in column k. In that case, you cannot use that row to zero out column k in the following rows because that would require you to divide by zero.

In that case, simply swap row k with a later row that does not have a 0 in column k. Then you can continue converting the matrix into upper triangular form. If you ever find that all of the remaining rows have 0 in column k, then there is no unique solution to the system of equations.

After the augmented matrix is in upper triangular form, you are ready to pull out the solution. At this point, the augmented array represents the following system equations:

Now, you can easily solve the last equation and get x_n = C'_n / N'_n. You can save that value in the final column of the augmented matrix's last row. Then, you can plug the value for x_n into the second-to-last equation to find x_n-1 and save the result in the second-to-last row's final column.

Next, you plug x_n and x_n-1 into the third-to-last equation to find x_n-2.

You continue using the values that you have found so far to find new values farther up in the augmented matrix until you have found all of the values and saved them in the matrix's final column. This process is called backsolving.

Now that you understand how Gaussian elimination works, here's your problem. Write a program similar to the one shown in the following screenshot that allows the user to enter the coefficients for a set of linear equations and then solves them:

Use the program to solve the following systems of equations: