Gaussian solution. Reverse the Gaussian method
Today we are dealing with the Gauss method for solving systems of linear algebraic equations... You can read about what kind of systems these are in the previous article devoted to solving the same SLAEs by Cramer's method. The Gauss method does not require any specific knowledge, only care and consistency are needed. Despite the fact that from the point of view of mathematics, school preparation is enough for its application, for students mastering this method often causes difficulties. In this article, we will try to nullify them!
Gauss method
M Gauss method- the most universal method solutions of the SLAE (except, well, very large systems). Unlike the one considered earlier, it is suitable not only for systems with only decision, but also for systems that have an infinite number of solutions. There are three possibilities here.
- The system has a unique solution (the determinant of the main matrix of the system is not equal to zero);
- The system has an infinite number of solutions;
- There are no solutions, the system is incompatible.
So, we have a system (let it have one solution), and we are going to solve it using the Gaussian method. How it works?
Gauss's method consists of two stages - forward and backward.
Forward traverse of the Gaussian method
First, we write down the extended matrix of the system. To do this, add a column of free members to the main matrix.
The whole essence of the Gauss method is to bring a given matrix to a stepped (or, as they say, triangular) form by means of elementary transformations. In this form, there should be only one zeros under (or above) the main diagonal of the matrix.
What you can do:
- You can rearrange the rows of the matrix in places;
- If the matrix contains the same (or proportional) rows, you can delete all but one of them;
- You can multiply or divide a string by any number (except zero);
- Zero lines are removed;
- You can append to a string a string multiplied by a nonzero number.
Reverse the Gaussian method
After we transform the system in this way, one unknown Xn becomes known, and it is possible in reverse order find all the remaining unknowns by substituting the already known xes into the equations of the system, up to the first.
When the Internet is always at hand, you can solve the system of equations using the Gaussian method online. You just need to drive the coefficients into the online calculator. But you must admit that it is much more pleasant to realize that the example was solved not by a computer program, but by your own brain.
An example of solving a system of equations by the Gauss method
And now - an example to make everything clear and understandable. Let the system be given linear equations, and you need to solve it using the Gauss method:
First, let's write the expanded matrix:
Now let's do some transformations. Remember that we need to achieve a triangular look for the matrix. Multiply the 1st row by (3). Multiply the 2nd row by (-1). Add the 2nd line to the 1st and get:
Then multiply the 3rd row by (-1). Let's add the 3rd line to the 2nd:
Multiply the 1st row by (6). Multiply the 2nd row by (13). Let's add the 2nd line to the 1st:
Voila - the system has been brought to the appropriate form. It remains to find unknowns:
System in this example has only one solution. We will consider the solution of systems with an infinite number of solutions in a separate article. Perhaps at first you will not know where to start transforming the matrix, but after the appropriate practice you will get your hands on and click the SLAE using the Gaussian method like nuts. And if you suddenly come across a SLAE that turns out to be too tough, contact our authors! you can by leaving an application in the correspondence course. Together we will solve any problem!
We continue to consider systems of linear equations. This lesson is the third on the topic. If you have a vague idea of what a system of linear equations is in general, you feel like a teapot, then I recommend starting from the basics on the page Further it is useful to study the lesson.
Gauss's method is easy! Why? The famous German mathematician Johann Karl Friedrich Gauss during his lifetime was recognized as the greatest mathematician of all time, a genius and even the nickname "king of mathematics". And everything ingenious, as you know, is simple! By the way, not only suckers, but also geniuses get paid for money - Gauss's portrait was on the 10 Deutschmark banknote (before the introduction of the euro), and Gauss still smiles mysteriously at the Germans from ordinary postage stamps.
The Gauss method is simple in that the knowledge of a 5-grade student is ENOUGH to master it. You must be able to add and multiply! It is no coincidence that teachers often consider the method of successive elimination of unknowns at school math electives. Paradoxically, the Gauss method is the most difficult for students. No wonder - the whole point is in the methodology, and I will try to tell you about the algorithm of the method in an accessible form.
First, let's systematize the knowledge about systems of linear equations a little. A system of linear equations can:
1) Have a unique solution. 2) Have infinitely many solutions. 3) Have no solutions (be inconsistent).
Gaussian method is the most powerful and versatile tool for finding a solution any systems of linear equations. As we remember Cramer's rule and matrix method unsuitable in cases where the system has infinitely many solutions or is incompatible. And the method successive elimination unknown anyway will lead us to the answer! In this lesson, we will again consider the Gauss method for case No. 1 (the only solution to the system), an article is reserved for the situation of points No. 2-3. Note that the algorithm of the method itself works the same in all three cases.
Back to the simplest system from the lesson How to solve a system of linear equations? and solve it by the Gauss method.
At the first stage, you need to write extended system matrix:. On what principle the coefficients are written, I think everyone can see. The vertical bar inside the matrix does not carry any mathematical meaning - it is just an underline for ease of design.
reference : I recommend to remember terms linear algebra. System Matrix Is a matrix composed only of the coefficients with unknowns, in this example the matrix of the system: . Extended system matrix - this is the same matrix of the system plus a column of free members, in this case: ... Any of the matrices can be called simply a matrix for brevity.
After the expanded matrix of the system is written down, it is necessary to perform some actions with it, which are also called elementary transformations.
There are the following elementary transformations:
1) Strings matrices can rearrange places. For example, in the matrix under consideration, you can painlessly rearrange the first and second rows: 
2) If the matrix contains (or appears) proportional (as a special case - the same) rows, then it follows delete from the matrix all these rows except one. Consider, for example, the matrix 
... In this matrix, the last three rows are proportional, so it is enough to leave only one of them: 
.
3) If a zero row appeared in the matrix during the transformations, then it also follows delete... I will not draw, of course, the zero line is the line in which only zeros.
4) The row of the matrix can be multiply (divide) by any number, nonzero... Consider, for example, a matrix. Here it is advisable to divide the first line by –3, and multiply the second line by 2: 
... This action is very useful as it simplifies further matrix transformations.
5) This transformation is the most difficult, but in fact, there is nothing complicated either. To a row of a matrix, you can add another string multiplied by a number nonzero. Consider our matrix from practical example:. First, I'll describe the conversion in great detail. Multiply the first line by –2: 
, and to the second line add the first line multiplied by –2: 
... Now the first line can be split "back" by –2:. As you can see, the line that ADD LEE – has not changed. Is always changes the line TO WHICH THE INCREASE UT.
In practice, of course, they do not describe in such detail, but write shorter: 
Once again: to the second line added the first line multiplied by –2... The string is usually multiplied orally or on a draft, while the mental course of the calculations is something like this:
“I rewrite the matrix and rewrite the first line: 
»
“First column first. At the bottom, I need to get zero. Therefore, I multiply the unit at the top by –2:, and add the first to the second line: 2 + (–2) = 0. I write the result into the second line: 
»
“Now for the second column. Above –1 multiplied by –2:. I add the first to the second line: 1 + 2 = 3. I write the result into the second line: 
»
“And the third column. Above –5 multiplied by –2:. I add the first to the second line: –7 + 10 = 3. I write the result into the second line: 
»
Please, carefully comprehend this example and understand the sequential algorithm of calculations, if you understand this, then the Gauss method is practically "in your pocket". But, of course, we will work on this transformation.
Elementary transformations do not change the solution of the system of equations
! ATTENTION: considered manipulations can not use, if you are offered a task where the matrices are given "by themselves". For example, with "classic" actions with matrices In no case should you rearrange something inside the matrices! Let's go back to our system. She's practically taken apart to pieces.
We write down the extended matrix of the system and, using elementary transformations, reduce it to stepped view:
(1) The first line multiplied by –2 was added to the second line. And again: why the first line is multiplied exactly by –2? In order to get zero at the bottom, which means get rid of one variable in the second line.
(2) Divide the second row by 3.
The goal of elementary transformations
–
bring the matrix to a stepped form: 
... In the design of the assignment, the "ladder" is marked out with a simple pencil, and the numbers that are located on the "steps" are circled. The term "step type" itself is not entirely theoretical; in scientific and educational literature it is often called trapezoidal view or triangular view.
As a result of elementary transformations, we obtained equivalent original system of equations:
Now the system needs to be "unrolled" in the opposite direction - from bottom to top, this process is called backward Gaussian method.
In the lower equation, we already have a ready-made result:.
Let us consider the first equation of the system and substitute the already known value of "game" into it:
Let us consider the most common situation when the Gauss method requires solving a system of three linear equations with three unknowns.
Example 1
Solve the system of equations by the Gauss method: 
Let's write down the extended matrix of the system: 
Now I will immediately draw the result that we will come to in the course of the solution: 
And again, our goal is to bring the matrix to a stepped form using elementary transformations. Where to start the action?
First, we look at the top-left number: 
It should almost always be here unit... Generally speaking, –1 will be fine (and sometimes other numbers), but somehow it so traditionally happened that the unit is usually placed there. How to organize a unit? We look at the first column - we have a ready-made unit! First transformation: swap the first and third lines: 
Now the first line will remain unchanged until the end of the solution.... Now fine.
The unit in the upper left is organized. Now you need to get zeros in these places: 
We get the zeros just with the help of the "difficult" transformation. First, we deal with the second line (2, –1, 3, 13). What should be done to get zero in the first position? Need to to the second line add the first line multiplied by –2... Mentally or on a draft, multiply the first line by –2: (–2, –4, 2, –18). And we consistently carry out (again mentally or on a draft) addition, to the second line we add the first line, already multiplied by –2:
We write the result to the second line: 
We deal with the third line in the same way (3, 2, –5, –1). To get zero in the first position, you need to the third line add the first line multiplied by –3... Mentally or on a draft, multiply the first line by –3: (–3, –6, 3, –27). AND to the third line add the first line multiplied by –3:
We write the result in the third line:
In practice, these actions are usually performed orally and recorded in one step: 
You don't need to count everything at once and at the same time... The order of calculations and "writing" the results consistent and usually like this: first we rewrite the first line, and we puff ourselves on the sly - SEQUENTIAL and CAREFULLY:
And I have already examined the mental course of the calculations themselves above.
In this example, this is easy to do, the second line is divided by –5 (since all numbers are divisible by 5 without remainder). At the same time, we divide the third line by –2, because the smaller the numbers, the easier the solution:
At the final stage of elementary transformations, you need to get another zero here: 
For this to the third line add the second line multiplied by –2:
Try to parse this action yourself - mentally multiply the second line by –2 and add.
The last performed action is the hairstyle of the result, divide the third line by 3.
As a result of elementary transformations, an equivalent initial system of linear equations was obtained: 
Cool.
The reverse of the Gaussian method now comes into play. The equations "unwind" from bottom to top.
In the third equation, we already have a ready-made result:
We look at the second equation:. The meaning of "z" is already known, thus:
And finally, the first equation:. "Y" and "z" are known, the matter is small:
Answer: 
As has already been noted many times, for any system of equations it is possible and necessary to check the solution found, fortunately, it is easy and fast.
Example 2
This is a do-it-yourself sample, a finishing sample, and the answer at the end of the tutorial.
It should be noted that your decision course may not coincide with my course of decision, and this is a feature of the Gauss method... But the answers must be the same!
Example 3
Solve a system of linear equations by the Gaussian method 
We look at the upper left "step". We should have a unit there. The problem is that there are no ones in the first column at all, so rearranging the rows will not solve anything. In such cases, the unit needs to be organized using an elementary transformation. This can usually be done in several ways. I did this: (1) To the first line add the second line multiplied by -1... That is, we mentally multiplied the second line by –1 and added the first and second lines, while the second line did not change.
Now at the top left is "minus one", which is fine for us. Anyone who wants to get +1 can perform an additional body movement: multiply the first line by –1 (change its sign).
(2) The first line multiplied by 5 was added to the second line. The first line multiplied by 3 was added to the third line.
(3) The first line was multiplied by -1, in principle, this is for beauty. We also changed the sign of the third line and moved it to the second place, thus, on the second “step, we have the required unit.
(4) The second row, multiplied by 2, was added to the third row.
(5) The third line was divided by 3.
A bad sign that indicates an error in calculations (less often - a typo) is the "bad" bottom line. That is, if at the bottom we got something like, and, accordingly, 
, then with a high degree of probability it can be argued that a mistake was made in the course of elementary transformations.
We charge the reverse stroke, in the design of examples, the system itself is often not rewritten, and the equations "are taken directly from the given matrix." The reverse move, I remind you, works from the bottom up. Yes, here the gift turned out:
Answer: 
.
Example 4
Solve a system of linear equations by the Gaussian method 
This is an example for an independent solution, it is somewhat more complicated. It's okay if anyone gets confused. Complete solution and sample design at the end of the tutorial. Your solution may differ from mine.
In the last part, we will consider some of the features of the Gauss algorithm. The first feature is that sometimes some variables are missing in the equations of the system, for example: 
How to write the extended system matrix correctly? I already talked about this moment in the lesson. Cramer's rule. Matrix method... In the extended matrix of the system, we put zeros in place of the missing variables: 
By the way, this is a fairly easy example, since there is already one zero in the first column, and there are fewer elementary transformations to be performed.
The second feature is as follows. In all the considered examples, we placed either –1 or +1 on the “steps”. Could other numbers be there? In some cases, they can. Consider the system: 
.
Here, on the upper left "step" we have a two. But we notice the fact that all the numbers in the first column are divisible by 2 without a remainder - and the other two and six. And the deuce at the top left will suit us! At the first step, you need to perform the following transformations: add the first line multiplied by –1 to the second line; to the third line add the first line multiplied by –3. This will give us the desired zeros in the first column.
Or else such conditional example: 
... Here the three on the second "step" also suits us, since 12 (the place where we need to get zero) is divisible by 3 without a remainder. It is necessary to carry out the following transformation: to the third line add the second line multiplied by –4, as a result of which the zero we need will be obtained.
The Gauss method is universal, but there is one peculiarity. Confidently learn how to solve systems by other methods (using the Cramer method, matrix method) you can literally the first time - there is a very tough algorithm. But in order to feel confident in the Gauss method, you should "fill your hand" and solve at least 5-10 ten systems. Therefore, at first, confusion, errors in calculations are possible, and there is nothing unusual or tragic in this.
Rainy autumn weather outside the window ... Therefore, for everyone, a more complex example for an independent solution:
Example 5
Solve the system of 4 linear equations with four unknowns by the Gauss method. 
Such a task in practice is not so rare. I think that even a teapot who has thoroughly studied this page, the algorithm for solving such a system is intuitively clear. Basically, everything is the same - there are just more actions.
Cases when the system has no solutions (inconsistent) or has infinitely many solutions are considered in the lesson Incompatible systems and systems with a common solution... The considered algorithm of the Gauss method can also be fixed there.
Wish you success!
Solutions and Answers:
Example 2:
Solution
:
Let us write down the extended matrix of the system and, using elementary transformations, bring it to a stepwise form.
Elementary transformations performed:
(1) The first line multiplied by –2 was added to the second line. The first line multiplied by -1 was added to the third line.
Attention!
Here it may be tempting to subtract the first from the third line, I highly discourage subtracting - the risk of an error is greatly increased. Just add up!
(2) The sign of the second line was changed (multiplied by –1). The second and third lines were swapped.
note
that on the "steps" we are satisfied with not only one, but also –1, which is even more convenient.
(3) The second row was added to the third row, multiplied by 5.
(4) The sign of the second line was changed (multiplied by –1). The third line was split by 14.
Reverse:
Answer
:
.
Example 4:
Solution
:
Let us write down the extended matrix of the system and, using elementary transformations, bring it to a stepwise form:
Conversions performed: (1) The second was added to the first line. Thus, the desired unit is organized on the upper left "rung". (2) The first line multiplied by 7 was added to the second line. The first line multiplied by 6 was added to the third line.
The second step is getting worse , "Candidates" for it are the numbers 17 and 23, and we need either one or -1. Transformations (3) and (4) will be aimed at obtaining the desired unit (3) The second line was added to the third line, multiplied by –1. (4) The third line was added to the second line, multiplied by –3. The necessary thing on the second step is received . (5) The second line was added to the third line, multiplied by 6. (6) The second line was multiplied by -1, the third line was divided by -83.
Reverse:
Answer :
Example 5:
Solution
:
Let us write down the matrix of the system and, using elementary transformations, bring it to a stepwise form:
Conversions performed: (1) The first and second lines are reversed. (2) The first line multiplied by –2 was added to the second line. The first line multiplied by –2 was added to the third line. The first line multiplied by –3 was added to the fourth line. (3) The second line was added to the third line, multiplied by 4. The second line was added to the fourth line, multiplied by –1. (4) The sign of the second line was changed. The fourth line was split by 3 and placed in place of the third line. (5) The third line multiplied by –5 was added to the fourth line.
Reverse:
Answer :
Let a system be given, ∆ ≠ 0. (one)Gauss method Is a method of successive elimination of unknowns.
The essence of the Gauss method consists in transforming (1) to a system with a triangular matrix, from which the values of all unknowns are then sequentially (in reverse) obtained. Let's consider one of the computational schemes. This scheme is called a single division scheme. So let's take a look at this circuit. Let a 11 ≠ 0 (pivot) divide the first equation by a 11. We get
(2)
Using equation (2), it is easy to exclude the unknowns x 1 from the rest of the equations of the system (for this, it is enough to subtract equation (2) from each equation, previously multiplied by the corresponding coefficient at x 1), that is, at the first step, we get
.
In other words, at step 1, each element of subsequent rows, starting from the second, is equal to the difference between the original element and the product of its “projection” onto the first column and the first (transformed) row.
After that, leaving the first equation alone, over the rest of the equations of the system obtained in the first step, we perform a similar transformation: choose from their number an equation with a pivot element and exclude it from the remaining equations x 2 (step 2).
After n steps, instead of (1), we obtain an equivalent system 
(3)
Thus, at the first stage, we get a triangular system (3). This stage is called the forward run.
At the second stage (reverse), we find successively from (3) the values x n, x n -1, ..., x 1.
Let us denote the resulting solution as x 0. Then the difference ε = b-A x 0 called the residual.
If ε = 0, then the found solution x 0 is correct.
Gaussian calculations are performed in two stages:
- The first stage is called the direct flow of the method. At the first stage, the original system is converted to a triangular form.
- The second stage is called reverse. At the second stage, a triangular system is solved, which is equivalent to the original one.
At each step, it was assumed that the pivot is nonzero. If this is not the case, then any other element can be used as a leading element, as if rearranging the equations of the system.
Purpose of the Gaussian method
Gauss's method is designed to solve systems of linear equations. Refers to direct methods of solving.Types of the Gaussian method
- Classical Gauss method;
- Modifications of the Gauss method. One of the modifications of the Gauss method is the circuit with the choice of the main element. A feature of the Gauss method with the choice of the pivot element is such a permutation of equations so that at the k-th step the leading element is the largest element in the k-th column in modulus.
- Jordano-Gauss method;
Let's illustrate the difference the Jordano-Gauss method from the Gauss method by examples.
An example of a Gaussian solution
Let's solve the system: 
For the convenience of calculations, let's swap the lines: 
Multiply the 2nd row by (2). Add the 3rd line to the 2nd 
Multiply the 2nd row by (-1). Add the 2nd line to the 1st 
From the 1st line, we express x 3:
From the 2nd line, we express x 2:
From the 3rd line, we express x 1: 
An example of a solution by the Jordano-Gauss method
We will solve the same SLAE by the Jordano-Gauss method. 
We will sequentially choose the resolving element of the RE, which lies on the main diagonal of the matrix.
The resolving element is (1).
NE = SE - (A * B) / RE
RE - resolving element (1), A and B - matrix elements forming a rectangle with STE and RE elements.
Let's present the calculation of each element in the form of a table:
| x 1 | x 2 | x 3 | B |
| 1 / 1 = 1 | 2 / 1 = 2 | -2 / 1 = -2 | 1 / 1 = 1 |
 |  |  |  |
The resolving element is equal to (3).
In place of the resolving element, we get 1, and write zeros in the column itself.
All other elements of the matrix, including the elements in column B, are determined by the rectangle rule.
To do this, select four numbers that are located at the vertices of the rectangle and always include the resolving element of the RE.
| x 1 | x 2 | x 3 | B |
 |  |
||
| 0 / 3 = 0 | 3 / 3 = 1 | 1 / 3 = 0.33 | 4 / 3 = 1.33 |
 |
The resolving element is (-4).
In place of the resolving element, we get 1, and write zeros in the column itself.
All other elements of the matrix, including the elements in column B, are determined by the rectangle rule.
To do this, select four numbers that are located at the vertices of the rectangle and always include the resolving element of the RE.
Let's present the calculation of each element in the form of a table:
| x 1 | x 2 | x 3 | B |
 |  |  |  |
 |  |
||
| 0 / -4 = 0 | 0 / -4 = 0 | -4 / -4 = 1 | -4 / -4 = 1 |
Answer: x 1 = 1, x 2 = 1, x 3 = 1
Implementation of the Gauss method
The Gauss method is implemented in many programming languages, in particular: Pascal, C ++, php, Delphi, and there is also an online implementation of the Gauss method.Using the Gaussian method
Application of the Gauss method in game theory
In game theory, when finding the maximin optimal strategy of a player, a system of equations is drawn up, which is solved by the Gauss method.Application of the Gauss method to solving differential equations
To find a particular solution to a differential equation, first find the derivatives of the corresponding degree for the written particular solution (y = f (A, B, C, D)), which are substituted into the original equation. Next to find variables A, B, C, D a system of equations is drawn up, which is solved by the Gauss method.Application of the Jordan-Gauss method in linear programming
In linear programming, in particular in the simplex method, to transform the simplex table at each iteration, the rectangle rule is used, which uses the Jordan-Gauss method.Here you can solve a system of linear equations for free Gaussian method online large sizes in complex numbers with a very detailed solution. Our calculator is able to solve online both the usual definite and indefinite system of linear equations by the Gauss method, which has an infinite number of solutions. In this case, in the answer you will receive the dependence of some variables through others, free. You can also check the system of equations for consistency online using the Gaussian solution.
About the method
When solving a system of linear equations online method Gauss, the following steps are performed.
- We write down the expanded matrix.
- In fact, the solution is divided into forward and reverse steps of the Gauss method. The direct course of the Gauss method is called the reduction of the matrix to a stepped form. The reverse of the Gaussian method is called the reduction of the matrix to a special stepped form. But in practice, it is more convenient to immediately zero out what is both above and below the element in question. Our calculator uses exactly this approach.
- It is important to note that when solving by the Gaussian method, the presence in the matrix of at least one zero row with a nonzero right side(column of free members) indicates an inconsistency of the system. Solution linear system in such a case does not exist.
To best understand how the Gauss algorithm works online, enter any example, select "very detailed solution"and see his solution online.
Solution of systems of linear equations by the Gauss method. Let us need to find a solution to the system from n linear equations with n unknown variables
the determinant of the main matrix of which is nonzero.
The essence of the Gauss method consists in the successive elimination of unknown variables: first, the x 1 from all equations of the system, starting with the second, further exclude x 2 of all equations, starting with the third, and so on, until only the unknown variable remains in the last equation x n... Such a process of transforming the equations of the system for the successive elimination of unknown variables is called by the direct course of the Gauss method... After completing the forward run of the Gauss method, from the last equation, we find x n, using this value from the penultimate equation is calculated x n-1, and so on, from the first equation we find x 1... The process of calculating unknown variables when moving from the last equation of the system to the first is called backward Gaussian method.
Let us briefly describe the algorithm for eliminating unknown variables.
We will assume that, since we can always achieve this by rearranging the equations of the system. Eliminate the unknown variable x 1 from all equations of the system, starting with the second. To do this, to the second equation of the system we add the first, multiplied by, to the third equation we add the first, multiplied by, and so on, to nth to the equation we add the first, multiplied by. The system of equations after such transformations takes the form 
where, and 
.
We would arrive at the same result if we expressed x 1 through other unknown variables in the first equation of the system and the resulting expression was substituted into all other equations. So the variable x 1 excluded from all equations, starting with the second.
Next, we act in a similar way, but only with a part of the resulting system, which is marked in the figure 
To do this, to the third equation of the system we add the second multiplied by, to the fourth equation we add the second multiplied by, and so on, to nth to the equation we add the second, multiplied by. The system of equations after such transformations takes the form 
where, and 
... So the variable x 2 excluded from all equations starting with the third.
Next, we proceed to eliminate the unknown x 3, in this case we act in the same way with the part of the system marked in the figure 
So we continue the direct course of the Gauss method until the system takes the form 
From this point on, we begin the reverse course of the Gauss method: calculate x n from the last equation as, using the obtained value x n find x n-1 from the penultimate equation, and so on, we find x 1 from the first equation.
Example.
Solve a system of linear equations 
by the Gauss method.
