What are the techniques for improving Naïve Gauss Elimination Method?

As seen in the example, round off errors were large when five significant digits were used as opposed to six significant digits. So one way of decreasing round off error would be to use more significant digits, that is, use double or quad precision. However, this would not avoid division by zero errors in Naïve Gauss Elimination. To avoid division by zero as well as reduce (not eliminate) round off error, Gaussian Elimination with partial pivoting is the method of choice.

How does Gaussian elimination with partial pivoting differ from Naïve Gauss elimination?

The two methods are the same, except in the beginning of each step of forward elimination, a row switching is done based on the following criterion. If there are equations, then there are forward elimination steps. At the beginning of the k^th step of forward elimination, one finds the maximum of

, , …………,

Then if the maximum of these values is in the p^th row, k≤p≤n, then switch rows p and k. The other steps of forward elimination are the same as Naïve Gauss elimination method. The back substitution steps stay exactly the same as Naïve Gauss Elimination method.

Example 4

In the previous two examples, we used Naïve Gauss Elimination to solve

using five and six significant digits with chopping in the calculations. Using five significant digits with chopping, the solution found was

This is different from the exact solution

Find the solution using Gaussian elimination with partial pivoting using five significant digits with chopping in your calculations.

Solution

=

Forward Elimination of Unknowns

Now for the first step of forward elimination, the absolute value of first column elements are

, ,

or

10, 3, 5

So the largest absolute value is in the Row 1. So as per Gaussian Elimination with partial pivoting, the switch is between Row 1 and Row 1 to give

=

Dividing Row 1 by 10 and multiplying by –3, that is, multiplying the Row 1 by -0.3, and subtract it from Row 2 would eliminate a₂₁,

=

Again dividing Row 1 by 10 and multiplying by 5, that is, multiplying the Row 1 by 0.5, and subtract it from Row 3 would eliminate a_31,

₌

This is the end of the first step of forward elimination.

Now for the second step of forward elimination, the absolute value of the second column elements below the Row 2 is

,

or

0.001, 2.5

So the largest absolute value is in Row 3. So the Row 2 is switched with the Row 3 to give

=

Dividing row 2 by 2.5 and multiplying by –0.001, that is multiplying by 0.001/2.5=-0.0004, and then subtracting from Row 3 gives

=

Back substitution

=1

Substituting the value of in Row 2

=

=

=

Substituting the value of and in Row 1

So the solution is

=

This, in fact, is the exact solution. By coincidence only, in this case, the round off error is fully removed.

Can we use Naïve Gauss Elimination methods to find the determinant of a square matrix?

One of the more efficient ways to find the determinant of a square matrix is by taking advantage of the following two theorems on a determinant of matrices coupled with Naïve Gauss Elimination.

Theorem 1:

Let [A] be a nxn matrix. Then, if [B] is a matrix that results from adding or subtracting a multiple of one row to another row, then det(B) = det(A). (The same is true for column operations also).

Theorem 2:

Let [A] be a nxn matrix that is upper triangular, lower triangular or diagonal, then det(A) = a₁₁* a₂₂*…….. * a_nn

This implies that if we apply the forward elimination steps of Naive Gauss Elimination method, the determinant of the matrix stays the same according the Theorem 1. Then since at the end of the forward elimination steps, the resulting matrix is upper triangular, the determinant will be given by Theorem 2.

Example 5

Find the determinant of

[A]=

Solution

Remember earlier in this chapter, we conducted the steps of forward elimination of unknowns using Naïve Gauss Elimination method on [A] to give

According to Theorem 2

det (A) = det (B)