Gaussian Elimination

The Gaussian elimination is a procedure for solving systems of linear equations. The addition method is applied to the expanded coefficient matrix.

The coefficient matrix is transformed in such a way that there are only zeros under the diagonal, it is then in row step form:

\displaystyle \def\arraystretch{1.25} \left(\begin{array}{ccccc|c} a_{11}&\ a_{12}&\dots&\dots&a_{1n}&b_1\\0&a_{22}&a_{23}&\dots&a_{2n}&b_2\\\vdots&&\ddots&&\vdots&\vdots\\0&\dots&0&a_{(n-1)2}&a_{(n-1)n}&b_{n-1}\\0&\dots&\dots&0&a_{nn}&b_n\end{array}\right)

With this form you can now easily calculate the entries of the solution vector from bottom to top.

Example

In the following, the procedure of the Gaussian method is explained by an example.

Consider the following system of equations:

\displaystyle \def\arraystretch{1.25} \left(\begin{array}{ccccc|c} a_{11}&\ a_{12}&\dots&\dots&a_{1n}&b_1\\0&a_{22}&a_{23}&\dots&a_{2n}&b_2\\\vdots&&\ddots&&\vdots&\vdots\\0&\dots&0&a_{(n-1)2}&a_{(n-1)n}&b_{n-1}\\0&\dots&\dots&0&a_{nn}&b_n\end{array}\right)

First, you should rewrite it to an extended coefficient matrix:

\displaystyle \def\arraystretch{1.25} \left(\begin{array}{ccccc|c} a_{11}&\ a_{12}&\dots&\dots&a_{1n}&b_1\\0&a_{22}&a_{23}&\dots&a_{2n}&b_2\\\vdots&&\ddots&&\vdots&\vdots\\0&\dots&0&a_{(n-1)2}&a_{(n-1)n}&b_{n-1}\\0&\dots&\dots&0&a_{nn}&b_n\end{array}\right)

As the first step of the Gaussian method you now use the addition method to bring the two entries, which are now marked orange, to zero.

To do this, you subtract twice the first line from the second line $\left( \mathrm{II}-2\cdot\mathrm{I}\right)$ . Then you subtract the first line from the third line multiplied by $\dfrac32$ , which reads $\left( \mathrm{III} - \frac32 \cdot\mathrm{I}\right)$ :

\displaystyle \def\arraystretch{1.25} \left(\begin{array}{ccccc|c} a_{11}&\ a_{12}&\dots&\dots&a_{1n}&b_1\\0&a_{22}&a_{23}&\dots&a_{2n}&b_2\\\vdots&&\ddots&&\vdots&\vdots\\0&\dots&0&a_{(n-1)2}&a_{(n-1)n}&b_{n-1}\\0&\dots&\dots&0&a_{nn}&b_n\end{array}\right)

Now there is only one non-zero entry in your extended coefficient matrix below the diagonal, it is marked green in the matrix.

So that there is also a zero in this entry of the matrix, you now subtract half of the second row from the third row: $\left( \mathrm{III} - \frac12 \cdot\mathrm{II}\right)$ :

\displaystyle \def\arraystretch{1.25} \left(\begin{array}{ccccc|c} a_{11}&\ a_{12}&\dots&\dots&a_{1n}&b_1\\0&a_{22}&a_{23}&\dots&a_{2n}&b_2\\\vdots&&\ddots&&\vdots&\vdots\\0&\dots&0&a_{(n-1)2}&a_{(n-1)n}&b_{n-1}\\0&\dots&\dots&0&a_{nn}&b_n\end{array}\right)

Now your matrix is in a "stair form", so you can easily determine the solution of the equation system. The best way to see how this works is to look at the matrix again in the original representation:

\displaystyle \def\arraystretch{1.25} \left(\begin{array}{ccccc|c} a_{11}&\ a_{12}&\dots&\dots&a_{1n}&b_1\\0&a_{22}&a_{23}&\dots&a_{2n}&b_2\\\vdots&&\ddots&&\vdots&\vdots\\0&\dots&0&a_{(n-1)2}&a_{(n-1)n}&b_{n-1}\\0&\dots&\dots&0&a_{nn}&b_n\end{array}\right)

By dividing the equation $\mathrm{III}$ by $-3$ , you get the solution $\mathbf{z = 2}$ . You can now substitute this value into the other two equations:

\displaystyle \def\arraystretch{1.25} \left(\begin{array}{ccccc|c} a_{11}&\ a_{12}&\dots&\dots&a_{1n}&b_1\\0&a_{22}&a_{23}&\dots&a_{2n}&b_2\\\vdots&&\ddots&&\vdots&\vdots\\0&\dots&0&a_{(n-1)2}&a_{(n-1)n}&b_{n-1}\\0&\dots&\dots&0&a_{nn}&b_n\end{array}\right)

Here you can now solve the equation $\mathrm{II}$ , by first subtracting $2$ , which yields $-7y = 7$ . Then, you divide by $-7$ , wihch gives you $\mathbf{y = -1}$ . You can also plug this value into equation $\mathrm{I}$ :

\displaystyle \def\arraystretch{1.25} \left(\begin{array}{ccccc|c} a_{11}&\ a_{12}&\dots&\dots&a_{1n}&b_1\\0&a_{22}&a_{23}&\dots&a_{2n}&b_2\\\vdots&&\ddots&&\vdots&\vdots\\0&\dots&0&a_{(n-1)2}&a_{(n-1)n}&b_{n-1}\\0&\dots&\dots&0&a_{nn}&b_n\end{array}\right)

If you solve this equation for $x$ you get $x=1$ .

So the total solution of the system of equations is:

\displaystyle \def\arraystretch{1.25} \left(\begin{array}{ccccc|c} a_{11}&\ a_{12}&\dots&\dots&a_{1n}&b_1\\0&a_{22}&a_{23}&\dots&a_{2n}&b_2\\\vdots&&\ddots&&\vdots&\vdots\\0&\dots&0&a_{(n-1)2}&a_{(n-1)n}&b_{n-1}\\0&\dots&\dots&0&a_{nn}&b_n\end{array}\right)

Gauß-Jordan method

The Gauss-Jordan method is a variation of the Gauss method. Here, the addition method is also applied to the expanded coefficient matrix. However, the coefficient matrix is transformed in such a way that the value 1 is everywhere on the diagonal and the remaining entries of the matrix are zeros. The result should look like this:

\displaystyle \def\arraystretch{1.25} \left(\begin{array}{ccccc|c} a_{11}&\ a_{12}&\dots&\dots&a_{1n}&b_1\\0&a_{22}&a_{23}&\dots&a_{2n}&b_2\\\vdots&&\ddots&&\vdots&\vdots\\0&\dots&0&a_{(n-1)2}&a_{(n-1)n}&b_{n-1}\\0&\dots&\dots&0&a_{nn}&b_n\end{array}\right)

With the Gauss-Jordan method you have to use the addition method more often than with the Gauss method, but it has the advantage that you can read the solution vector immediately in the right column:

\displaystyle \def\arraystretch{1.25} \left(\begin{array}{ccccc|c} a_{11}&\ a_{12}&\dots&\dots&a_{1n}&b_1\\0&a_{22}&a_{23}&\dots&a_{2n}&b_2\\\vdots&&\ddots&&\vdots&\vdots\\0&\dots&0&a_{(n-1)2}&a_{(n-1)n}&b_{n-1}\\0&\dots&\dots&0&a_{nn}&b_n\end{array}\right)

Example

Here you can understand how the Gauss-Jordan method works by means of an example:

This still has to be converted!!!

This content is licensed under
CC BY-SA 4.0 → Info