In this article, the method is considered as a way to solve systems of linear equations (SLAE). The method is analytical, that is, it allows you to write a solution algorithm in a general form, and then substitute values from specific examples there. Unlike the matrix method or Cramer's formulas, when solving a system of linear equations using the Gauss method, you can also work with those that have infinitely many solutions. Or don't have it at all.
What does it mean to solve by Gauss method?
First, we need to write down our system of equations as a matrix. It looks like this. The system is taken:
Coefficients are written in the form of a table, and on the right in a separate column - free members. The column with free members is separated for convenience by a vertical bar. A matrix that includes this column is called extended.
Next, the main matrix with coefficients must be reduced to the upper triangular shape. This is the main point of solving the system by the Gauss method. Simply put, after certain manipulations, the matrix should look like this, so that there are only zeros in its lower left part:
Then, if you write the new matrix again as a system of equations, you will notice that the last line already contains the value of one of the roots, which is then substituted into the equation above, another root is found, and so on.
This is a description of the Gaussian solution in the most general terms. And what happens if suddenly the system does not have a solution? Or are there an infinite number of them? To answer these and many more questions, it is necessary to consider separately all the elements used in the solution by the Gauss method.
Matrices, their properties
There is no hidden meaning in the matrix. It's just a convenient way to record data for later operations. Even schoolchildren should not be afraid of them.
The matrix is always rectangular because it's more convenient. Even in the Gauss method, where everything boils down to building a triangular matrix, a rectangle appears in the entry, only with zeros in the place where there are no numbers. Zeros can be omitted, but they are implied.
Matrix has size. Its "width" is the number of rows (m), its "length" is the number of columns (n). Then the size of the matrix A (capital Latin letters are usually used for their designation) will be denoted as Am×n. If m=n, then this matrix is square, andm=n - its order. Accordingly, any element of the matrix A can be denoted by the number of its row and column: axy; x - row number, change [1, m], y - column number, change [1, n].
In the Gaussian method, matrices are not the main point of the solution. In principle, all operations can be performed directly with the equations themselves, however, the notation will be much more cumbersome, and it will be much easier to get confused in it.
Qualifier
The matrix also has a determinant. This is a very important feature. Finding out its meaning now is not worth it, you can simply show how it is calculated, and then tell what properties of the matrix it determines. The easiest way to find the determinant is through diagonals. Imaginary diagonals are drawn in the matrix; the elements located on each of them are multiplied, and then the resulting products are added: diagonals with a slope to the right - with a "plus" sign, with a slope to the left - with a "minus" sign.
It is extremely important to note that the determinant can only be calculated for a square matrix. For a rectangular matrix, you can do the following: choose the smallest of the number of rows and the number of columns (let it be k), and then randomly mark k columns and k rows in the matrix. The elements located at the intersection of the selected columns and rows will form a new square matrix. If the determinant of such a matrix is a number other than zero, then it will be called the basic minor of the original rectangular matrix.
Beforehow to start solving a system of equations by the Gauss method, it does not hurt to calculate the determinant. If it turns out to be zero, then we can immediately say that the matrix has either an infinite number of solutions, or there are none at all. In such a sad case, you need to go further and find out about the rank of the matrix.
Classification of systems
There is such a thing as the rank of a matrix. This is the maximum order of its non-zero determinant (remembering the basis minor, we can say that the rank of a matrix is the order of the basis minor).
The way things are with rank, SLOW can be divided into:
- Joint. For joint systems, the rank of the main matrix (consisting only of coefficients) coincides with the rank of the extended one (with a column of free terms). Such systems have a solution, but not necessarily one, therefore, joint systems are additionally divided into:
- - definite - having a unique solution. In certain systems, the rank of the matrix and the number of unknowns are equal (or the number of columns, which is the same);
- - indefinite - with an infinite number of solutions. The rank of matrices for such systems is less than the number of unknowns.
- Incompatible. For such systems, the ranks of the main and extended matrices do not match. Incompatible systems have no solution.
The Gauss method is good because it allows you to obtain either an unambiguous proof of the inconsistency of the system (without calculating the determinants of large matrices) or a general solution for a system with an infinite number of solutions.
Elementary transformations
Beforehow to proceed directly to the solution of the system, you can make it less cumbersome and more convenient for calculations. This is achieved through elementary transformations - such that their implementation does not change the final answer in any way. It should be noted that some of the above elementary transformations are valid only for matrices, the source of which was precisely the SLAE. Here is a list of these transformations:
- Change strings. It is obvious that if the order of the equations is changed in the system record, then this will not affect the solution in any way. Therefore, it is also possible to swap rows in the matrix of this system, not forgetting, of course, about the column of free members.
- Multiplying all elements of a string by some factor. Very useful! With it, you can reduce large numbers in the matrix or remove zeros. The set of solutions, as usual, will not change, and it will become more convenient to perform further operations. The main thing is that the coefficient should not be equal to zero.
- Delete lines with proportional coefficients. This partly follows from the previous paragraph. If two or more rows in the matrix have proportional coefficients, then when multiplying / dividing one of the rows by the proportionality coefficient, two (or, again, more) absolutely identical rows are obtained, and you can remove the extra ones, leaving only one.
- Delete the null line. If in the course of transformations a string is obtained somewhere in which all elements, including the free member, are zero, then such a string can be called zero and thrown out of the matrix.
- Adding to the elements of one row of elements of another (according tocorresponding columns) multiplied by some coefficient. The most obscure and most important transformation of all. It is worth dwelling on it in more detail.
Adding a string multiplied by a factor
For ease of understanding, it is worth disassembling this process step by step. Two rows are taken from the matrix:
a11 a12 … a1n | b1
a21 a22 … a2n | b2
Let's say you need to add the first one multiplied by the coefficient "-2" to the second one.
a'21 =a21 + -2×a11
a'22 =a22 + -2×a12
a'2n =a2n + -2×a1n
Then the second row in the matrix is replaced with a new one, while the first one remains unchanged.
a11 a12 … a1n | b1
a'21 a'22 … a'2n | b2
It should be noted that the multiplication factor can be chosen in such a way that, as a result of adding two strings, one of the elements of the new string is equal to zero. Therefore, it is possible to obtain an equation in the system, where there will be one less unknown. And if you get two such equations, then the operation can be done again and get an equation that will already contain two less unknowns. And if each time we turn to zero one coefficient for all rows that are lower than the original one, then we can, like steps, go down to the very bottom of the matrix and get an equation with one unknown. This is calledsolve the system using the Gauss method.
Generally
Let there be a system. It has m equations and n unknown roots. You can write it like this:
The main matrix is compiled from the coefficients of the system. A column of free members is added to the expanded matrix and separated by a bar for convenience.
Next:
- the first row of the matrix is multiplied by the coefficient k=(-a21/a11);
- the first modified row and the second row of the matrix are added;
- instead of the second row, the result of the addition from the previous paragraph is inserted into the matrix;
- now the first coefficient in the new second line is a11 × (-a21/a11) + a21 =-a21 + a21=0.
Now the same series of transformations is performed, only the first and third lines are involved. Accordingly, in each step of the algorithm, the element a21 is replaced by a31. Then everything repeats for a41, … am1. The result is a matrix where the first element in the rows [2, m] is equal to zero. Now you need to forget about line number one and perform the same algorithm starting from the second line:
- k coefficient=(-a32/a22);
- the second modified line is added to the "current" line;
- the result of the addition is substituted into the third, fourth and so on lines, while the first and second remain unchanged;
- in the rows [3, m] of the matrix, the first two elements are already equal to zero.
The algorithm must be repeated until the coefficient k=(-am, m-1/amm appears). This means that the algorithm was last run only for the lower equation. Now the matrix looks like a triangle, or has a stepped shape. The bottom line contains the equation amn × x =bm. The coefficient and free term are known, and the root is expressed through them: x =bm/amn. The resulting root is substituted into the top row to find xn-1=(bm-1 - am-1, n ×(bm/amn))÷am-1, n-1. And so on by analogy: in each next line there is a new root, and, having reached the "top" of the system, one can find a set of solutions [x1, … x ]. It will be the only one.
When there are no solutions
If in one of the matrix rows all elements, except for the free term, are equal to zero, then the equation corresponding to this row looks like 0=b. It has no solution. And since such an equation is included in the system, then the set of solutions of the entire system is empty, that is, it is degenerate.
When there are an infinite number of solutions
It may turn out that in the reduced triangular matrix there are no rows with one element - the coefficient of the equation, and one - a free member. There are only strings that, when rewritten, would look like an equation with two or more variables. This means that the system has an infinite number of solutions. In this case, the answer can be given in the form of a general solution. How to do it?
Allvariables in the matrix are divided into basic and free. Basic - these are those that stand "on the edge" of the rows in the stepped matrix. The rest are free. In the general solution, the basic variables are written in terms of the free ones.
For convenience, the matrix is first rewritten back into a system of equations. Then in the last of them, where exactly only one basic variable remained, it remains on one side, and everything else is transferred to the other. This is done for each equation with one basic variable. Then, in the rest of the equations, where possible, instead of the basic variable, the expression obtained for it is substituted. If the result is again an expression containing only one basic variable, it is expressed from there again, and so on, until each basic variable is written as an expression with free variables. This is the general solution of SLAE.
You can also find the basic solution of the system - give the free variables any values, and then calculate the values of the basic variables for this particular case. There are infinitely many particular solutions.
Solution with specific examples
Here is a system of equations.
For convenience, it is better to make its matrix right away
It is known that when solving by the Gauss method, the equation corresponding to the first row will remain unchanged at the end of the transformations. Therefore, it will be more profitable if the upper left element of the matrix is the smallest - then the first elementsthe rest of the rows after the operations will turn to zero. This means that in the compiled matrix it will be beneficial to put the second row in place of the first one.
Next, you need to change the second and third lines so that the first elements become zero. To do this, add them to the first one, multiplied by a coefficient:
second line: k=(-a21/a11)=(-3/1)=-3
a'21 =a21 + k×a11=3 + (-3)×1=0
a'22 =a22 + k×a12 =-1 + (- 3)×2=-7
a'23 =a23 + k×a13 =1 + (-3)×4=-11
b'2 =b2 + k×b1=12 + (-3)×12=-24
third line: k=(-a31/a11)=(- 5/1)=-5
a'31 =a31+ k×a11=5 + (-5)×1=0
a'32 =a32+ k×a12 =1 + (-5)×2=-9
a'33 =a33 + k×a13 =2 + (-5)×4=-18
b'3=b3 + k×b1=3 + (-5)×12=-57
Now, in order not to get confused, you need to write a matrix with intermediate results of transformations.
Obviously, such a matrix can be made more readable with the help of some operations. For example, you can remove all "minuses" from the second line by multiplying each element by "-1".
It's also worth noting that in the third line all elements are multiples of three. Then you cancut the string by this number, multiplying each element by "-1/3" (minus - at the same time to remove negative values).
Looks much nicer. Now we need to leave alone the first line and work with the second and third. The task is to add the second row to the third row, multiplied by such a coefficient that the element a32 becomes equal to zero.
k=(-a32/a22)=(-3/7)=-3/7 (if during some transformations in the answer turned out to be not an integer, it is recommended to leave it “as is”, in the form of an ordinary fraction, and only then, when the answers are received, decide whether to round and convert to another form of notation)
a'32=a32 + k×a22=3 + (-3 /7)×7=3 + (-3)=0
a'33=a33 + k×a23=6 + (-3 /7)×11=-9/7
b'3 =b3 + k×b2=19 + (-3 /7)×24=-61/7
The matrix is written again with new values.
| 1 | 2 | 4 | 12 |
| 0 | 7 | 11 | 24 |
| 0 | 0 | -9/7 | -61/7 |
As you can see, the resulting matrix already has a stepped form. Therefore, further transformations of the system by the Gauss method are not required. What can be done here is to remove the overall coefficient "-1/7" from the third line.
Now everyonenice. The point is small - write the matrix again in the form of a system of equations and calculate the roots
x + 2y + 4z=12 (1)
7y + 11z=24 (2)
9z=61 (3)
The algorithm by which the roots will now be found is called the reverse move in the Gauss method. Equation (3) contains the value z:
z=61/9
Next, return to the second equation:
y=(24 - 11×(61/9))/7=-65/9
And the first equation allows you to find x:
x=(12 - 4z - 2y)/1=12 - 4×(61/9) - 2×(-65/9)=-6/9=-2/3
We have the right to call such a system joint, and even definite, that is, having a unique solution. The answer is written in the following form:
x1=-2/3, y=-65/9, z=61/9.
Example of an indefinite system
The variant of solving a certain system by the Gauss method has been analyzed, now it is necessary to consider the case if the system is indefinite, that is, infinitely many solutions can be found for it.
x1 + x2 + x3 + x 4 + x5=7 (1)
3x1 + 2x2 + x3 + x 4 - 3x5=-2 (2)
x2 + 2x3 + 2x4 + 6x 5=23 (3)
5x1 + 4x2 + 3x3 + 3x 4 - x5=12 (4)
The very form of the system is already alarming, because the number of unknowns is n=5, and the rank of the system matrix is already exactly less than this number, because the number of rows is m=4, that is, the largest order of the square determinant is 4. So,There are an infinite number of solutions, and we must look for its general form. The Gauss method for linear equations allows you to do this.
First, as usual, the augmented matrix is compiled.
Second line: coefficient k=(-a21/a11)=-3. In the third line, the first element is before the transformations, so you don't need to touch anything, you need to leave it as it is. Fourth line: k=(-a41/a11)=-5
Multiplying the elements of the first row by each of their coefficients in turn and adding them to the required rows, we get a matrix of the following form:
As you can see, the second, third and fourth rows consist of elements proportional to each other. The second and fourth are generally the same, so one of them can be removed immediately, and the rest multiplied by the coefficient "-1" and get line number 3. And again, leave one of two identical lines.
The result is such a matrix. The system has not yet been written down, it is necessary here to determine the basic variables - standing at the coefficients a11=1 and a22=1, and free - all the rest.
There is only one basic variable in the second equation - x2. Hence, it can be expressed from there by writing through the variables x3, x4, x5, which are free.
Substitute the resulting expression into the first equation.
It turned out an equation in whichthe only basic variable is x1. Let's do the same with it as with x2.
All basic variables, of which there are two, are expressed in terms of three free ones, now you can write the answer in general form.
You can also specify one of the particular solutions of the system. For such cases, as a rule, zeros are chosen as values for free variables. Then the answer will be:
-16, 23, 0, 0, 0.
An example of an inconsistent system
Solution of inconsistent systems of equations by the Gauss method is the fastest. It ends as soon as at one of the stages an equation is obtained that has no solution. That is, the stage with the calculation of the roots, which is quite long and dreary, disappears. The following system is being considered:
x + y - z=0 (1)
2x - y - z=-2 (2)
4x + y - 3z=5 (3)
As usual, the matrix is compiled:
| 1 | 1 | -1 | 0 |
| 2 | -1 | -1 | -2 |
| 4 | 1 | -3 | 5 |
And reduced to a stepped form:
k1 =-2k2 =-4
| 1 | 1 | -1 | 0 |
| 0 | -3 | 1 | -2 |
| 0 | 0 | 0 | 7 |
After the first transformation, the third line contains an equation of the form
0=7, no solution. Therefore, the systemis inconsistent, and the answer is the empty set.
Advantages and disadvantages of the method
If you choose which method to solve SLAE on paper with a pen, then the method that was considered in this article looks the most attractive. In elementary transformations, it is much more difficult to get confused than it happens if you have to manually look for a determinant or some tricky inverse matrix. However, if you use programs for working with data of this type, for example, spreadsheets, then it turns out that such programs already contain algorithms for calculating the main parameters of matrices - the determinant, minors, inverse and transposed matrices, and so on. And if you are sure that the machine will calculate these values itself and will not make a mistake, it is more expedient to use the matrix method or Cramer's formulas, because their application begins and ends with the calculation of determinants and inverse matrices.
Application
Since the Gaussian solution is an algorithm, and the matrix is, in fact, a two-dimensional array, it can be used in programming. But since the article positions itself as a guide "for dummies", it should be said that the easiest place to shove the method into is spreadsheets, for example, Excel. Again, any SLAE entered in a table in the form of a matrix will be considered by Excel as a two-dimensional array. And for operations with them, there are many nice commands: addition (you can add only matrices of the same size!), Multiplication by a number, matrix multiplication (also withcertain restrictions), finding the inverse and transposed matrices and, most importantly, calculating the determinant. If this time-consuming task is replaced by a single command, it is much faster to determine the rank of a matrix and, therefore, establish its compatibility or inconsistency.
