Elimination of Gauss-Jordan

History

This method was named according to the Mathématicien Carl Friedrich Gauss, but it is known Chinese since at least the 1st century of our era. It is referred in the important Chinese book Jiuzhang suanshu or the nine chapters on mathematical art, of which it constitutes the eighth chapter, under the title “Fang cheng” (the rectangular provision). The method is presented by means of 18 exercises. In its very detailed comment gone back to 263, Liu Hui allots paternity of it to Chang Ts' ang chancellor of the emperor of China at the 2nd century before our era.

Numerical analysis

The asymptotic algorithmic complexity of the elimination of Gauss is $O (n^3)$ (Notations of Pram), therefore the number of instructions necessary is proportional to n³ if the matrix is of n*n type. This algorithm can be used on a computer for systems with thousands of unknown factors and equations. However, the Algorithm of Strassen, which is in $O (n^ {2,807})$ has a better asymptotic algorithmic complexity. Moreover, the elimination of Gauss is numerically unstable, the rounding errors carried out during calculation are accumulated and the found result can be far from the solution if calculations are not made in exact Arithmétique. But the elimination of Gauss is a good method for the systems of equations on a field where calculations are by nature exact like the Corps finished S.

Calculation of the reverse of a square matrix by the algorithm of Gauss-Jordan

To reverse a matrix has square invertible of order N , amounts solving N systems Af_i = e_i for I going of 1 to N. For that, one creates a table with N lines and 2 N columns by bordering the matrix has by the Matrice identity I_n .

Thus, to reverse the matrix A= (a_{i j}) of format (N, N), the following increased matrix will be used:

\ Big (has \; \ Big|\, I_ {N} \ Big) = \ left (\ begin {array} {ccc|ccc}

a_ {1,1} & \ cdots & a_ {1, N} & 1 & \ cdots & 0 \ \ \ vdots & \ ddots & \ vdots & \ vdots & \ ddots & \ vdots \ \ a_ {N, 1} & \ cdots & a_ {N, N} & \ 0 & \ cdots & 1 \ \ \ end {array} \ right)

The transformation of Gauss-Jordan consists in transforming this system into a system equivalent of which the left block is the identity, i.e. it is necessary to modify the matrix $(has|I)$ so that it becomes form $(I|A^ {- 1})$ by using the properties of the algorithm. One will note:

$l_i^k$ line I of the matrix has with the iteration K
$a_ {ij} ^k$ the Scalaire a_{i j} of the matrix has with the iteration K

The algorithm of Gauss-Jordan is the following:

For $k$ energy of $1$ with $n$

If there exists a line

i \ geq k

such as

a_ {ik} ^ {k-1} \ not=0

to exchange this line

i

and the line

k

l_i \ leftrightarrow l_k

l_k^k \ leftarrow \ frac {1} {a_ {kk} ^ {k-1}} l_k^ {k-1}

For

i

energy of

1

with

n

and

i \ neq k

l_i^k \ leftarrow l_i^ {k-1} - a_ {ik} ^ {k-1} \ times l_k^ {K}

If not

A

is not invertible, to give up (it is known here that the row matrix is

k-1

After the stage $k$ of the algorithm, the column $k$ has all these null coefficients except one: that of the diagonal, which is worth 1.

Alternative: one can also seek the coefficient $a_ {ik} ^ {k-1}, the I \ geq k$ largest (in absolute value) before exchanging the lines. That improves the stability of the algorithm. In the same way one can also make exchanges on the columns to find a coefficient larger, but it is necessary to keep the trace of these permutations.

With the reverse of the matrix $A$ , can solve the equations of the form $A.X=B$ , where $B$ is a fixed vector, and $X$ the unknown factor. But there exists also another presentation.

Resolution of a System of linear equations by the algorithm of Gauss-Jordan

One wants to solve a system of equations $A.X=B$ , where $B$ is a fixed vector, and $X$ the unknown vector. One creates a table with $n$ lines and $n+1$ columns by bordering the matrix $A$ by the vector $B$ . One uses the same algorithm as above. One obtains at the end a matrix identity, and in the last column the required vector $X$ .

Alternative: in the preceding algorithm, if one carries out the internal loop only for $i$ energy of $k+1$ with $n$ , one obtains a higher triangular matrix. It any more but does not remain “to go up” to find the values of the coefficients of $X$ .

Example

That is to say the system of equations according to:

$\ left \ {\ begin {array} {* {7} {C}}
X &-& there &+& 2z &=& 5 \ \
3x &+& 2y &+&z &=& 10 \ \
2x &-& 3y &-& 2z &=& -10 \\
\end{array}\right.$

The corresponding matrix is established and one applies the first stage of Gauss-Jordan, the pivot is 1:

$\ left (\ begin {array} {ccc|C}
(1) & -1 & 2 & 5 \ \
3 & 2 & 1 & 10 \ \
2 & -3 & -2 & -10
\end{array}\right)$

One adds a multiple of the first line to the two other lines to obtain from the zeros (respectively $-3 \ times l_1$ and $-2 \ times l_1$ ); the new pivot is then 5:

$\ left (\ begin {array} {ccc|C}
1 & -1 & 2 & 5 \ \
0 & (5) & -5 & -5 \ \
0 & -1 & -6 & -20
\end{array}\right)$

The second line is multiplied by 1/5:

$\ left (\ begin {array} {ccc|C}
1 & -1 & 2 & 5 \ \
0 & (1) & -1 & -1 \ \
0 & -1 & -6 & -20
\end{array}\right)$

One adds this second line to the third and with the first, the new pivot is -7:

$\ left (\ begin {array} {ccc|C}
1 & 0 & 1 & 4 \ \
0 & 1 & -1 & -1 \ \
0 & 0 & (- 7) & -21
\end{array}\right)$

One divides the 3rd line by -7:

$\ left (\ begin {array} {ccc|C}
1 & 0 & 1 & 4 \ \
0 & 1 & -1 & -1 \ \
0 & 0 & (1) & 3
\end{array}\right)$

One uses the 3rd line to eliminate from the coefficients in the first and second line. We are then in the presence of a form spread out reduced with the matrix identity on a side and the value of the variables in the other:

$\ left (\ begin {array} {ccc|C}
1 & 0 & 0 & 1 \ \
0 & 1 & 0 & 2 \ \
0 & 0 & 1 & 3
\end{array}\right)$

The solution of the system is as follows:

$\ left \ {\ begin {array} {ccc}
X &=& 1 \ \
there &=& 2 \ \
Z &=& 3 \ \
\end{array}\right.$

Determinant

This algorithm also makes it possible to calculate the determinant of a matrix: in the algorithm above, it is the product of the “ $a_ {ik} ^ {k-1} \ not=0$ ” which are selected like pivot with each iteration. If the algorithm stops because there is no more pivot not no one, then the matrix is not invertible, its determinant is null, but one can calculate his row.

See too

External bonds

Method of the pivot of Gauss

Random links: