Implementing Gaussian Elimination

We implement Gaussian Elimination in three stages of increasing sophistication,

following the development in Olver and Shakiban, "Applied Linear Algebra," Chapter 1.

The simplest case occurs when we always find the pivot positions to be occupied by non-zero elements. Following Olver and Shakiban, we call this the "regular case."

The next simplest case occurs when there will at least be a suitable nonzero pivot available somewhere, but we may have to swap rows in order to move it into position.

This occurs when the matrix is nonsingular.

In the third and final case, we institute a pivoting policy to improve the numerical performance of the algorithm.

NOTE: In this preliminary version, the algorithms are implemented for square matrices only

Gaussian Elimination - Regular Case

The "Regular Case" refers to a square matrix which can be row reduced to an upper triangular matrix by the following algorithm.

The critical point is that there must be a non-zero element in each pivot position for the algorithm to be successful.

We do not resort to swapping rows. A more general case is handled later.

See Olver and Shakiban, "Applied Linear Algebra," Section 1.3.

gaussianEliminationRegularCase

In[1]:=

In[2]:=

squareMatrixQ

In[3]:=

In[4]:=

Testing.

In[5]:=

Out[7]//MatrixForm=

In[8]:=

Out[9]=

Gaussian Elimination - Nonsingular Case

The following procedure will row reduce a nonsingular square matrix to an upper triangular matrix.

The naive pivoting policy is merely to move the nearest nonzero candidate into the pivot position.

See Olver and Shakiban, "Applied Linear Algebra," Section 1.4.

gaussianEliminationNonsingularCase

In[10]:=

In[11]:=

allZeroQ

In[12]:=

In[13]:=

indexOfFirstNonzeroEntry

In[14]:=

In[15]:=

Testing.

In[16]:=

Out[18]//MatrixForm=

In[19]:=

Out[21]//MatrixForm=

In[22]:=

Out[23]=

Gaussian Elimination - with Partial Pivoting

The following procedure will row reduce a nonsingular square matrix to an upper triangular matrix.

The Partial Pivoting version of Gaussian Elimination uses a more sophisticated pivoting policy to reduce accummulating roundoff errors which may lead to inaccurate solutions. The idea is to always move the largest (in absolute value) available element into the pivot position. Here, the "largest available element" means the largest element in the present column which is in or below the present pivot position. A yet more wide-ranging pivoting policy could even use column operations (which effectively only permute the ordering of the variables) to bring in even larger pivots, and further reduce roundoff errors. Such a policy is called Full Pivoting, but we do not implement it here. A more sophisticated version of partial or full pivoting would use a list of pointers to rows and pointers to columns and simply interchange pointers rather than interchanging whole rows or columns in computer memory.

See Olver and Shakiban, "Applied Linear Algebra," Section 1.7.

gaussianEliminationPartialPivoting

In[24]:=

In[25]:=

allZeroQ

In[26]:=

In[27]:=

indexOfLargestAvailableEntry

In[28]:=

In[29]:=

Testing.

In[30]:=

Out[32]//MatrixForm=

In[33]:=

Out[35]//MatrixForm=

In[36]:=

Out[37]=

Created by Mathematica (April 10, 2005) |