Gauss method for solving matrices algorithm examples. Gauss method according to Vilenkin

Two systems of linear equations are said to be equivalent if the set of all their solutions is the same.

Elementary transformations of the system of equations are:

1. Deletion from the system of trivial equations, i.e. those for which all coefficients are equal to zero;
2. Multiplying any equation by a non-zero number;
3. Addition to any i -th equation of any j -th equation, multiplied by any number.

The variable x i is called free if this variable is not allowed, and the whole system of equations is allowed.

Theorem. Elementary transformations transform the system of equations into an equivalent one.

The meaning of the Gauss method is to transform the original system of equations and obtain an equivalent allowed or equivalent inconsistent system.

So, the Gauss method consists of the following steps:

1. Consider the first equation. We choose the first non-zero coefficient and divide the whole equation by it. We obtain an equation in which some variable x i enters with a coefficient of 1;
2. Let us subtract this equation from all the others, multiplying it by numbers such that the coefficients for the variable x i in the remaining equations are set to zero. We get a system that is resolved with respect to the variable x i and is equivalent to the original one;
3. If trivial equations arise (rarely, but it happens; for example, 0 = 0), we delete them from the system. As a result, the equations become one less;
4. We repeat the previous steps no more than n times, where n is the number of equations in the system. Each time we select a new variable for “processing”. If conflicting equations arise (for example, 0 = 8), the system is inconsistent.

As a result, after a few steps we obtain either an allowed system (possibly with free variables) or an inconsistent one. Allowed systems fall into two cases:

1. The number of variables is equal to the number of equations. So the system is defined;
2. Number of variables more number equations. We collect all free variables on the right - we get formulas for allowed variables. These formulas are written in the answer.

That's all! The system of linear equations is solved! This is a fairly simple algorithm, and to master it, you do not need to contact a tutor in mathematics. Consider an example:

A task. Solve the system of equations:

Description of steps:

1. We subtract the first equation from the second and third - we get the allowed variable x 1;
2. We multiply the second equation by (−1), and divide the third equation by (−3) - we get two equations in which the variable x 2 enters with a coefficient of 1;
3. We add the second equation to the first, and subtract from the third. Let's get the allowed variable x 2 ;
4. Finally, we subtract the third equation from the first - we get the allowed variable x 3 ;
5. We have received an authorized system, we write down the answer.

The general solution of the joint system of linear equations is new system, which is equivalent to the original one, in which all allowed variables are expressed in terms of free ones.

When might a general solution be needed? If you have to take fewer steps than k (k is how many equations in total). However, the reasons why the process ends at some step l< k , может быть две:

1. After the l -th step, we get a system that does not contain an equation with the number (l + 1). In fact, this is good, because. the resolved system is received anyway - even a few steps earlier.
2. After the l -th step, an equation is obtained in which all coefficients of the variables are equal to zero, and the free coefficient is different from zero. This is an inconsistent equation, and, therefore, the system is inconsistent.

It is important to understand that the appearance of an inconsistent equation by the Gauss method is a sufficient reason for inconsistency. At the same time, we note that as a result of the l -th step, trivial equations cannot remain - all of them are deleted directly in the process.

Description of steps:

1. Subtract the first equation times 4 from the second. And also add the first equation to the third - we get the allowed variable x 1;
2. We subtract the third equation, multiplied by 2, from the second - we get the contradictory equation 0 = −5.

So, the system is inconsistent, since an inconsistent equation has been found.

A task. Investigate compatibility and find the general solution of the system:

Description of steps:

1. We subtract the first equation from the second (after multiplying by two) and the third - we get the allowed variable x 1;
2. Subtract the second equation from the third. Since all the coefficients in these equations are the same, the third equation becomes trivial. At the same time, we multiply the second equation by (−1);
3. We subtract the second equation from the first equation - we get the allowed variable x 2. The entire system of equations is now also resolved;
4. Since the variables x 3 and x 4 are free, we move them to the right to express the allowed variables. This is the answer.

So, the system is joint and indefinite, since there are two allowed variables (x 1 and x 2) and two free ones (x 3 and x 4).

One of the universal and effective methods for solving linear algebraic systems is Gauss method , consisting in the successive elimination of unknowns.

Recall that the two systems are called equivalent (equivalent) if the sets of their solutions are the same. In other words, systems are equivalent if every solution to one of them is a solution to the other, and vice versa. Equivalent systems are obtained with elementary transformations system equations:

multiplying both sides of the equation by a non-zero number;

adding to some equation the corresponding parts of another equation, multiplied by a number other than zero;

permutation of two equations.

Let the system of equations

The process of solving this system by the Gauss method consists of two stages. At the first stage (forward run), the system is reduced by means of elementary transformations to stepped , or triangular mind, and at the second stage (reverse move) there is a sequential, starting from the last variable, the definition of unknowns from the resulting step system.

Let us assume that the coefficient of this system
, otherwise in the system the first row can be interchanged with any other row so that the coefficient at was different from zero.

Let's transform the system, eliminating the unknown in all equations except the first. To do this, multiply both sides of the first equation by and add term by term with the second equation of the system. Then multiply both sides of the first equation by and add it to the third equation of the system. Continuing this process, we obtain an equivalent system

Here
are the new values ​​of the coefficients and free terms, which are obtained after the first step.

Similarly, considering the main element
, exclude the unknown from all equations of the system, except for the first and second. We continue this process as long as possible, as a result we get a step system

,

where ,
,…,- the main elements of the system
.

If in the process of bringing the system to a step form, equations appear, i.e., equalities of the form
, they are discarded, since any set of numbers satisfies them
. If at
an equation of the form that has no solutions appears, this indicates the inconsistency of the system.

In the reverse course, the first unknown is expressed from the last equation of the transformed step system through all the other unknowns
who are called free . Then the variable expression from the last equation of the system is substituted into the penultimate equation and the variable is expressed from it
. The variables are defined in a similar way
. Variables
, expressed in terms of free variables, are called basic (dependent). As a result, the general solution of the system of linear equations is obtained.

To find private solution systems, free unknown
in the general solution, arbitrary values ​​are assigned and the values ​​of the variables are calculated
.

It is technically more convenient to subject elementary transformations not to the equations of the system, but to the extended matrix of the system

.

The Gauss method is a universal method that allows you to solve not only square, but also rectangular systems in which the number of unknowns
not equal to the number of equations
.

The advantage of this method also lies in the fact that in the process of solving we simultaneously examine the system for compatibility, since, having reduced the augmented matrix
to the stepped form, it is easy to determine the ranks of the matrix and extended matrix
and apply the Kronecker-Capelli theorem .

Example 2.1 Solve the system using the Gauss method

Solution. Number of Equations
and the number of unknowns
.

Let us compose the extended matrix of the system by assigning to the right of the matrix of coefficients free members column .

Let's bring the matrix to a triangular shape; to do this, we will get "0" below the elements on the main diagonal using elementary transformations.

To get "0" in the second position of the first column, multiply the first row by (-1) and add to the second row.

We write this transformation as a number (-1) against the first line and denote it by an arrow going from the first line to the second line.

To get "0" in the third position of the first column, multiply the first row by (-3) and add to the third row; Let's show this action with an arrow going from the first line to the third.

.

In the resulting matrix, written second in the matrix chain, we get "0" in the second column in the third position. To do this, multiply the second line by (-4) and add to the third. In the resulting matrix, we multiply the second row by (-1), and divide the third row by (-8). All elements of this matrix that lie below the diagonal elements are zeros.

Because , the system is collaborative and specific.

The system of equations corresponding to the last matrix has a triangular form:

From the last (third) equation
. Substitute in the second equation and get
.

Substitute
and
into the first equation, we find


.

The essence of the Gauss method is to transform (1) to a system with a triangular matrix , from which the values ​​of all unknowns are then sequentially (reversely) obtained. Let's consider one of the computational schemes. This circuit is called the single division circuit. So let's take a look at this diagram. Let a 11 ≠0 (leading element) divide by a 11 the first equation. Get
(2)
Using equation (2), it is easy to exclude unknown x 1 from the remaining equations of the system (for this, it is enough to subtract equation (2) from each equation preliminarily multiplied by the corresponding coefficient at x 1), that is, at the first step we obtain
.
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” on the first column and the first (transformed) row.
Following this, leaving the first equation alone, we will perform a similar transformation over the remaining equations of the system obtained at the first step: we select from among them an equation with a leading element and use it to exclude x 2 from the remaining equations (step 2).
After n steps, instead of (1) we get an equivalent system
(3)
Thus, at the first stage, we will obtain a triangular system (3). This step is called forward.
At the second stage (reverse move) we sequentially find from (3) the values ​​x n , x n -1 , …, x 1 .
Let's denote the obtained solution as x 0 . Then the difference ε=b-A x 0 is called residual.
If ε=0, then the found solution x 0 is correct.

Calculations by the Gauss method are performed in two stages:

1. The first stage is called the direct course of the method. At the first stage, the original system is converted to a triangular form.
2. The second stage is called reverse. At the second stage, a triangular system equivalent to the original one is solved.

Purpose of the Gauss method

Types of Gauss method

1. Classical Gauss method;
2. Modifications of the Gauss method. One of the modifications of the Gaussian method is the circuit with the choice of the main element. A feature of the Gauss method with the choice of the main element is such a permutation of the equations so that at the k-th step the leading element is the largest element in the k-th column.
3. Jordan-Gauss method;

Gauss solution example
Let's solve the system:

For the convenience of calculations, we 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 row 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 Jordan-Gauss method
We will solve the same SLAE using the Jordano-Gauss method.

We will sequentially choose the resolving element of the RE, which lies on the main diagonal of the matrix.
The enabling element is equal to (1).



NE \u003d SE - (A * B) / RE
RE - enabling element (1), A and B - matrix elements forming a rectangle with elements of STE and RE.
Let's present the calculation of each element in the form of a table:

Implementation of the Gauss method

Using the Gauss Method

Application of the Gauss method in game theory

Application of the Gauss method in solving differential equations

Application of the Jordano-Gauss method in linear programming

Today we deal with the Gauss method for solving systems of linear algebraic equations. You can read about what these systems are in the previous article devoted to solving the same SLAE by the Cramer 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, mastering this method often causes difficulties for students. In this article, we will try to reduce them to nothing!

Gauss method

M Gauss method is the most universal method for solving SLAE (with the exception of, well, very large systems). Unlike the one discussed earlier, it is suitable not only for systems that have a unique solution, but also for systems that have an infinite number of solutions. There are three options here.

1. The system has a unique solution (the determinant of the main matrix of the system is not equal to zero);
2. The system has an infinite number of solutions;
3. There are no solutions, the system is inconsistent.

So, we have a system (let it have one solution), and we are going to solve it using the Gaussian method. How it works?

The Gaussian method consists of two stages - direct and inverse.

Direct Gauss method

First, we write the augmented matrix of the system. To do this, we add a column of free members to the main matrix.

The whole essence of the Gaussian method is to reduce this matrix to a stepped (or, as they say, triangular) form by means of elementary transformations. In this form, there should be only zeros under (or above) the main diagonal of the matrix.

What can be done:

1. You can rearrange the rows of the matrix;
2. If there are identical (or proportional) rows in the matrix, you can delete all but one of them;
3. You can multiply or divide a string by any number (except zero);
4. Zero lines are removed;
5. You can add a string multiplied by a non-zero number to a string.

Reverse Gauss method

After we transform the system in this way, one unknown xn becomes known, and it is possible to find all the remaining unknowns in reverse order, substituting the already known x's 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 Gauss method online . All you have to do is enter the odds into the online calculator. But you must admit, it is much more pleasant to realize that the example was not solved computer program but with your own brain.

An example of solving a system of equations using the Gauss method

And now - an example, so that everything becomes clear and understandable. Let a system of linear equations be given, and it is necessary to solve it by the Gauss method:

First, let's write the augmented matrix:

Now let's take a look at the transformations. Remember that we need to achieve a triangular form of the matrix. Multiply the 1st row by (3). Multiply the 2nd row by (-1). Let's add the 2nd row 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 is brought to the appropriate form. It remains to find the unknowns:

The system in this example has a unique solution. We will consider the solution of systems with an infinite set of solutions in a separate article. Perhaps at first you will not know where to start with matrix transformations, but after appropriate practice you will get your hands on it and will click the Gaussian SLAE like nuts. And if you suddenly come across a SLAU, which turns out to be too tough a nut to crack, contact our authors! you can by leaving an application in the Correspondence. Together we will solve any problem!

Let a system of linear algebraic equations be given, which must be solved (find such values ​​of the unknowns хi that turn each equation of the system into an equality).

We know that a system of linear algebraic equations can:

1) Have no solutions (be incompatible).
2) Have infinitely many solutions.
3) Have a unique solution.

As we remember, Cramer's rule and the matrix method are unsuitable in cases where the system has infinitely many solutions or is inconsistent. Gauss method – the most powerful and versatile tool for finding solutions to any system of linear equations, which the in every case lead us to the answer! The algorithm of the method in all three cases works the same way. If the Cramer and matrix methods require knowledge of determinants, then the application of the Gauss method requires knowledge of only arithmetic operations, which makes it accessible even to primary school students.

Extended matrix transformations ( this is the matrix of the system - a matrix composed only of the coefficients of the unknowns, plus a column of free terms) systems of linear algebraic equations in the Gauss method:

1) With troky matrices can rearrange places.

2) if the matrix has (or has) proportional (as special case are the same) strings, then it follows delete from the matrix, all these rows except one.

3) if a zero row appeared in the matrix during the transformations, then it also follows delete.

4) the row of the matrix can multiply (divide) to any number other than zero.

5) to the row of the matrix, you can add another string multiplied by a number, different from zero.

In the Gauss method, elementary transformations do not change the solution of the system of equations.

The Gauss method consists of two stages:

1. "Direct move" - ​​using elementary transformations, bring the extended matrix of the system of linear algebraic equations to a "triangular" stepped form: the elements of the extended matrix located below the main diagonal are equal to zero (top-down move). For example, to this kind:

To do this, perform the following steps:

1) Let us consider the first equation of a system of linear algebraic equations and the coefficient at x 1 is equal to K. The second, third, etc. we transform the equations as follows: we divide each equation (coefficients for unknowns, including free terms) by the coefficient for unknown x 1, which is in each equation, and multiply by K. After that, subtract the first from the second equation (coefficients for unknowns and free terms). We get at x 1 in the second equation the coefficient 0. From the third transformed equation we subtract the first equation, so until all equations except the first, with unknown x 1, will not have a coefficient 0.

2) Move on to the next equation. Let this be the second equation and the coefficient at x 2 is equal to M. With all the "subordinate" equations, we proceed as described above. Thus, "under" the unknown x 2 in all equations will be zeros.

3) We pass to the next equation and so on until one last unknown and transformed free term remains.

1. « Reverse» the Gauss method - obtaining a solution to a system of linear algebraic equations (going "bottom-up"). From the last "lower" equation we get one first solution - the unknown x n. To do this, we solve the elementary equation A * x n \u003d B. In the example above, x 3 \u003d 4. We substitute the found value in the “upper” next equation and solve it with respect to the next unknown. For example, x 2 - 4 \u003d 1, i.e. x 2 \u003d 5. And so on until we find all the unknowns.

Example.

We solve the system of linear equations using the Gauss method, as some authors advise:

We write the extended matrix of the system and, using elementary transformations, bring it to a step form:

We look at the upper left "step". There we should have a unit. The problem is that there are no ones in the first column at all, so nothing can be solved by rearranging the rows. In such cases, the unit must be organized using an elementary transformation. This can usually be done in several ways. Let's do it like this:
1 step . To the first line we add the second line, multiplied by -1. That is, we mentally multiplied the second line by -1 and performed the addition of the first and second lines, while the second line did not change.

Now at the top left "minus one", which suits us perfectly. Whoever wants to get +1 can perform an additional action: multiply the first line by -1 (change its sign).

2 step . 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 step . The first line was multiplied by -1, in principle, this is for beauty. The sign of the third line was also changed and moved to the second place, thus, on the second “step, we had the desired unit.

4 step . To the third line, add the second line, multiplied by 2.

5 step . The third line is divided by 3.

A sign that indicates an error in calculations (less often a typo) is a “bad” bottom line. That is, if we got something like (0 0 11 | 23) below, and, accordingly, 11x 3 = 23, x 3 = 23/11, then with a high degree of probability we can say that a mistake was made during elementary transformations.

We perform the reverse move, 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." In this example, the gift turned out:

x 3 = 1
x 2 = 3
x 1 + x 2 - x 3 \u003d 1, therefore x 1 + 3 - 1 \u003d 1, x 1 \u003d -1

Answer:x 1 \u003d -1, x 2 \u003d 3, x 3 \u003d 1.

Let's solve the same system using the proposed algorithm. We get

4 2 –1 1
5 3 –2 2
3 2 –3 0

Divide the second equation by 5 and the third by 3. We get:

4 2 –1 1
1 0.6 –0.4 0.4
1 0.66 –1 0

Multiply the second and third equations by 4, we get:

4 2 –1 1
4 2,4 –1.6 1.6
4 2.64 –4 0

Subtract the first equation from the second and third equations, we have:

4 2 –1 1
0 0.4 –0.6 0.6
0 0.64 –3 –1

Divide the third equation by 0.64:

4 2 –1 1
0 0.4 –0.6 0.6
0 1 –4.6875 –1.5625

Multiply the third equation by 0.4

4 2 –1 1
0 0.4 –0.6 0.6
0 0.4 –1.875 –0.625

We subtract the second equation from the third equation, we get the “stepped” augmented matrix:

4 2 –1 1
0 0.4 –0.6 0.6
0 0 –1.275 –1.225

Thus, since an error accumulated in the process of calculations, we get x 3 \u003d 0.96, or approximately 1.

x 2 \u003d 3 and x 1 \u003d -1.

Solving in this way, you will never get confused in the calculations and, despite the calculation errors, you will get the result.

This method of solving a system of linear algebraic equations is easily programmable and does not take into account the specific features of the coefficients for unknowns, because in practice (in economic and technical calculations) one has to deal with non-integer coefficients.

Wish you success! See you in class! Tutor Dmitry Aistrakhanov.

site, with full or partial copying of the material, a link to the source is required.