GAUSS ELIMINATION

This method is a generalization of what I have shown earlier when dealing with two simultaneous equations. It relies on the result that addition to any column or row of a determinant of any other row or column, multiplied by a scalar, does not change the value of the determinant.

This rule is often used when evaluating determinants. In that way, a determinant is reduced to triangular form, so that its value is the product of the diagonal terms. For the sake of simplicity, augment in Gauss elimination the matrix by the column vector on the right hand side, forming what appears to be an n*(n+1) matrix and follow the algorithm:

1. Divide the first row by the first term and then subtract that row, after multiplication by the first term of the remaining rows from those rows, respectively, and thus reduce the original system to one with a first column unit vector.
2. Repeat the same steps for the second column, using the second row, etc. until the columns form an upper triagonal matrix with 1 along the diagonal.
3. Now use back substitution to find the variables from the triangular system.

COMPUTATION SCHEME

.

Here, the column with the sums provides a welcome check for manual calculations, since its entry should equal the sum of the individual terms in that row.

There may arise problems: for example, a diagonal element in the scheme vanishes and division becomes impossible. Then interchange of rows is required, i.e., application of partial pivoting. If one wants also to interchange columns, one speaks of total pivoting. The former is widely practiced, in order to avoid loss of accuracy. The aim is to always have a large element in the diagonal position.

If a system of linear equations is subject to loss of accuracy, it is said to ne ill-conditioned.

EXAMPLE

Consider the system of 3 equations:

and set up the scheme:

Hence, by back-substitution:

x₃ = 3.0,
x₂ = -7.7 + 1.9*3 = 2.0,
x₃ = 3.75 + 0.5*2 - 0.25*3 = 4.0,

and the determinant has the value:

1.8*(-2.5)*4 = -18.

This work shows that the solutions can be found for different right hand sides b. This can be done at the same time by adding two columns for each right hand side, namely the actual b column and the corresponding sum column.

What to do when there appears a 0 or a very small term on the diagonal? Interchange rows:

EXAMPLE

Consider the system

Note that a₁₁ is very small compared to the other a_ij. If Gauss elimination is used, find the non-normalized, augmented matrix

with the solution

Interchange Rows 1 and 2:

and repeat the calculations:

with the solution:

One could try to solve the original system using more digits, but it will not be much better. The point is that without pivoting, accuracy is lost!

Ill-conditioning may be very disturbing without any other way out but using more decimals:

EXAMPLE

Consider the system:

Pivoting and use Gauss elimination yield:

Note the large number of decimals! Only three digits were retained! The solution is:

Of course, one has been warned because the value of the determinant is

If one repeats the calculation with six digits, the solution is:

There is no other cure! Now experiment! If the coefficient a₁₁ is changed to 3.00, the exact solution is

This is a very big change for a small perturbation, the symptom of ill-conditioning!

These phenomena are displayed by the simple system:

with the solution

If we change the system slightly to:

the solution becomes:

Another change to:

yields the solution:

ILL-CONDITIONING CRITERION

The condition number of a coefficient matrix is defined as the product of two matrix norms:

a product of matrix norms. Unfortunately, if one wants to use norms, one must also find A^-1, the inverse of A. If the absolute value of this number is very large, there is trouble. As a rule, its value will be about 1.

last next