On the stability of Gauss-Jordan elimination with pivoting

ABSTRACT

The stability of the Gauss-Jordan algorithm with partial pivoting for the solution of general systems of linear equations is commonly regarded as suspect. It is shown that in many respects suspicions are unfounded, and in general the absolute error in the solution is strictly comparable with that corresponding to Gaussian elimination with partial pivoting plus back substitution. However, when A is ill conditioned, the residual corresponding to the Gauss-Jordan solution will often be much greater than that corresponding to the Gaussian elimination solution.

REFERENCES

• 1: Forsythge, G. E., and Moler, C. B., Computer Solution of Linear Algebraic Systems. Prentice-Hall, Englewood Cliffs, N.J., 1967.
• 2: J. H. Wilkinson, Error Analysis of Direct Methods of Matrix Inversion, Journal of the ACM (JACM), v.8 n.3, p.281-330, July 1961 [doi>10.1145/321075.321076]
• 3: James H. Wilkinson, Rounding Errors in Algebraic Processes, Dover Publications, Incorporated, 1994
• 4: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Error analysis

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Stability (and instability)

General Terms:
Algorithms, Design, Reliability, Theory

Keywords:
Gauss-Jordan algorithm, Gaussian elimination, back-substitution, backward error analysis, bound for residual, bounds for error in solution