Gauss-Jordan algorithm

from Wikipedia, the free encyclopedia

The Gauss-Jordan algorithm is an algorithm from the mathematical sub-areas of linear algebra and numerics . The method can be used to calculate the solution of a linear system of equations . It is an extension of the Gaussian elimination method , in which the system of equations or its extended coefficient matrix is brought to the reduced step form in an additional step . The solution can then be read off directly. In addition, the Gauss-Jordan algorithm can be used to compute the inverse of a matrix.

In addition to Carl Friedrich Gauß , the namesake is not, as is sometimes assumed, the French mathematician Camille Jordan , who is also outstanding in linear algebra , but the German geodesist Wilhelm Jordan . However, it is very likely that the latter is not the “inventor” of the additional algorithm step, but only the one who brought it closer to his audience and audience.

Forming steps

  1. You choose the first column from the left, in which there is at least one non-zero value.
  2. If the top number of the selected column is a zero, you swap the first line with another line that does not contain a zero in this column.
  3. You divide the first row by the now top element of the selected column.
  4. Corresponding multiples of the first row are subtracted from the rows below with the aim that the first element of each row (except the first) becomes zero.
  5. By deleting the first row and column you get a remainder matrix to which you can apply these steps again. This is done until the matrix is ​​in line step form.
  6. You then subtract corresponding multiples from the lines above so that there are only zeros above a leading 1.

example

The following system of linear equations is given:

The extended coefficient matrix of the equation system is now formed. The first column contains the factors of the variable  a , the second those of the variable  b , the third those of the variable  c and the fourth the right side of the equation system. From the individual lines of this matrix, such multiples of the remaining lines should now be subtracted that finally the identity matrix is on the left side :

The following line transformations are now carried out:

  • Line 2 is subtracted: 4 × line 1.
  • Line 3 is subtracted: 9 × line 1.

This results in:

  • Line 3 is subtracted: 3 × line 2.
  • Line 2 is divided by −2.
  • Line 1 is subtracted: 1 × line 3.
  • Line 2 is subtracted: 3/2 × line 3.
  • Line 1 is subtracted: 1 × line 2.

This matrix is ​​transferred back to our equations. We obtain:

.

literature

  • Howard Anton: Linear Algebra . Spectrum Akademischer Verlag GmbH Heidelberg, Berlin, ISBN 3-8274-0324-3 .

Web links

Individual evidence

  1. ^ Rainer Ansorge, Hans Joachim Oberle: Mathematics for Engineers, Volume 1. Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim 2000, p. 110.
  2. Steven C. Althoen, Renate McLaughlin: Gauss-Jordan Reduction: A Brief History (English; PDF, 370 kB). In: American Mathematical Monthly, Vol. 94, 1987, pp. 130-142.