Gauss method (successive exclusion of unknowns). Examples of solutions for dummies

Let us consider exact methods for solving the system ; here is the dimension matrix

A method for solving a problem is classified as exact if, under the assumption that there are no roundings, it gives an exact solution to the problem after a finite number of arithmetic and logical operations. If the number of nonzero elements of the matrix of the system is of the order of , then for most of the currently used exact methods for solving such systems, the required number of operations is of the order of . Therefore, for the applicability of exact methods, it is necessary that such an order of the number of operations be acceptable for a given computer; other restrictions are imposed by the volume and structure of computer memory.

The clause about "methods currently in use" has the following meaning. There are methods for solving such systems with a lower number of operations, but they are not actively used due to the strong sensitivity of the result to the computational error.

The most famous of the exact methods for solving systems of linear equations is the Gauss elimination method. Let's consider one of its possible implementations. Assuming that , the first equation of the system

divide by the coefficient , as a result we obtain the equation

Then, from each of the remaining equations, the first equation is subtracted, multiplied by the appropriate coefficient . As a result, these equations are transformed to the form

The first unknown turned out to be excluded from all equations except the first one. Further, under the assumption that , we divide the second equation by the coefficient and exclude the unknown from all equations, starting from the second, and so on. As a result of successive elimination of unknowns, the system of equations is transformed into a system of equations with a triangular matrix

The set of calculations performed, during which the original problem was transformed to the form (2), is called the direct course of the Gauss method.

From the equation of system (2) we determine , from , etc. up to . The totality of such calculations is called the reverse course of the Gauss method.

It is easy to check that the implementation of the forward move of the Gaussian method requires arithmetic operations, and the reverse run requires arithmetic operations.

The exception occurs as a result of the following operations: 1) dividing the equation by , 2) subtracting the equation obtained after such division, multiplied by , from equations with numbers k . The first operation is equivalent to multiplying the system of equations on the left by the diagonal matrix

the second operation is equivalent to multiplication on the left by the matrix

Thus, system (2) obtained as a result of these transformations can be written as

The product of left (right) triangular matrices is a left (right) triangular matrix, so C is a left triangular matrix. From the formula for the elements of the inverse matrix

it follows that the matrix inverse to a left (right) triangular one is a left (right) triangular one. Therefore, the matrix is left triangular.

Let's introduce the notation . According to the construction, everything and the matrix D are right triangular. From here we get the representation of the matrix A as a product of the left and right triangular matrices:

Equality, together with the condition , forms a system of equations with respect to the elements of the triangular matrices B and : . Since for and for , this system can be written as

(3)

or, which is the same,

Using the condition that all we get a system of recurrence relations for determining the elements and :

Calculations are carried out sequentially for sets . Here and below, in the case when the upper summation limit is less than the lower one, it is assumed that the entire sum is equal to zero.

Thus, instead of successive transformations of the system (1) to the form (2), one can directly calculate the matrices B and using formulas (4). These calculations can only be carried out if all elements are different from zero. Let be matrices of principal minors of the order of matrices A, B, D. According to (3) . Because , then . Hence,

So, in order to carry out calculations according to formulas (4), it is necessary and sufficient to fulfill the conditions

In some cases, it is known in advance that condition (5) is satisfied. For example, many problems of mathematical physics are reduced to solving systems with a positive-definite matrix A. However, in the general case, this cannot be said in advance. Such a case is also possible: everything, but among the quantities there are very small ones, and when divided by them, large numbers with large absolute errors will be obtained. As a result, the solution will be strongly distorted.

Let's denote . Since and , then the equalities hold. Thus, after decomposing the matrix of the original system into the product of the left and right triangular matrices, the solution of the original system is reduced to the sequential solution of two systems with triangular matrices; this would require arithmetic operations.

It is often convenient to combine the sequence of operations for decomposing the matrix A into the product of triangular matrices and for determining the vector d. Equations

systems can be written as

Therefore, the values can be calculated simultaneously with the rest of the values using formulas (4).

When solving practical problems, it often becomes necessary to solve systems of equations with a matrix containing a large number of zero elements.

Typically, these matrices have a so-called band structure. More precisely, the matrix A is called -diagonal or has a band structure, if at . The number is called the width of the tape. It turns out that when solving a system of equations with a tape matrix by the Gauss method, the number of arithmetic operations and the required amount of computer memory can be significantly reduced.

Task 1. Investigate the characteristics of the Gauss method and the method of solving the system using the decomposition of the band matrix A into the product of the left and right triangular matrices. Show that arithmetic operations are required to find the solution (for ). Find the leading member of the number of operations under the condition .

Task 2. Estimate the amount of loaded computer memory in the Gauss method for band matrices.

When calculating without the help of a computer, the probability of random errors is high. To eliminate such errors, sometimes a control system is introduced, consisting of control elements of the equations of the system

When transforming equations, the same operations are performed on the control elements as on the free members of the equations. As a result, the control element of each new equation must be equal to the sum of the coefficients of this equation. A large discrepancy between them indicates errors in the calculations or the instability of the calculation algorithm in relation to the computational error.

For example, in the case of bringing the system of equations to the form using formulas (4), the control element of each of the equations of the system is calculated using the same formulas (4). After calculating all the elements at a fixed control is carried out by checking the equality

The reverse course of the Gauss method is also accompanied by the calculation of the control elements of the system rows.

To avoid the catastrophic influence of the computational error, the Gaussian method is used with the choice of the main element.

Its difference from the scheme of the Gaussian method described above is as follows. Let, in the course of eliminating the unknowns, the system of equations

Let us find such that and re-denote and ; then we will eliminate the unknown from all equations, starting with . Such a redesignation leads to a change in the order of elimination of unknowns and in many cases significantly reduces the sensitivity of the solution to rounding errors in calculations.

Often it is required to solve several systems of equations , with the same matrix A. It is convenient to proceed as follows: by introducing the notation

Let us perform calculations using formulas (4), and calculate the elements at . As a result, p systems of equations with a triangular matrix will be obtained, corresponding to the original problem

We solve these systems each separately. It turns out that the total number of arithmetic operations in solving p systems of equations in this way is .

The technique described above is sometimes used in order to obtain a judgment on the error of the solution, which is a consequence of rounding errors in calculations, without significant additional costs. They are given by the vector z with components having, if possible, the same order and sign as the components of the desired solution; often due to lack of sufficient information they take . The vector is calculated, and along with the original system of equations, the system is solved.

Let and z be actually obtained solutions of these systems. Judgment on the error of the desired solution can be obtained based on the hypothesis: the relative errors in solving by the elimination method of systems with the same matrix and different right-hand sides, which are, respectively, the values and , differ not by a very large number of times.

Another method for obtaining a judgment about the real value of the error that arises due to rounding off in calculations is to change the scale, which changes the picture of the accumulation of the computational error.

Along with the original system, the system is solved by the same method

For and , which are not integer powers of two, the comparison of the vectors and gives an idea of the magnitude of the computational error. For example, you can take .

The study of many problems leads to the need to solve systems of linear equations with a symmetric positive definite matrix. Such systems arise, for example, when solving differential equations by the finite element method or by finite difference methods. In these cases, the matrix of the system also has a band structure.

To solve such systems, as well as systems of equations of a more general form with a Hermitian matrix that is not necessarily positive definite, the square root method (the Cholesky method) is used. Matrix A is represented as

where S is a right triangular matrix, is its conjugate, i.e.

with all being a diagonal matrix with elements equal to or -1. Matrix equality (6) forms a system of equations

Similar equations for are discarded, since the equations corresponding to the pairs and are equivalent. From here we obtain recurrent formulas for determining the elements and :

The matrix S is right triangular, and thus, after obtaining representation (6), the solution of the original system is also reduced to the Sequential solution of two systems with triangular matrices. Note that in the case of all and .

Task 3. Estimate the number of arithmetic operations and computer memory load (assuming the amount of memory required to store the matrix A decreases) when solving a system with a real positive definite matrix A by the square root method.

Many software packages for solving boundary value problems of mathematical physics by the finite element method are organized according to the following scheme. After the matrix of system A is formed by rearranging rows and columns (both rows and columns are simultaneously rearranged), the system is converted to the form with the smallest tape width. Next, the square root method is applied. At the same time, in order to reduce the amount of calculations when solving a system with other right-hand sides, the matrix S is memorized.

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 they don't have it at all.

What does Gauss mean?

First you need to write down our system of equations in It looks like this. The system is taken:

The 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. The matrix that includes this column is called extended.

Further, 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 row 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 solution by the Gauss method 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 is 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.

The matrix has a 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 A m×n . If m=n, then this matrix is square, and m=n is its order. Accordingly, any element of the matrix A can be denoted by the number of its row and column: a xy ; x - row number, changes , y - column number, changes .

B is not the main point of the solution. In principle, all operations can be performed directly with the equations themselves, but the notation will turn out to be much more cumbersome, and it will be much easier to get confused in it.

Determinant

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 is called the basis minor of the original rectangular matrix.

Before proceeding with the solution of the 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.

System classification

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).

According to how things are with the rank, SLAE can be divided into:

Joint. At of 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:
- certain- having a unique solution. In certain systems, the rank of the matrix and the number of unknowns (or the number of columns, which is the same thing) are equal;
- indefinite - with an infinite number of solutions. The rank of matrices for such systems is less than the number of unknowns.
Incompatible. At such systems, the ranks of the main and extended matrices do not coincide. Incompatible systems have no solution.

The Gauss method is good in that it allows one 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

Before proceeding directly to the solution of the system, it is possible to 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:

String permutation. It is obvious that if we change the order of the equations in the system record, then this will not affect the solution in any way. Consequently, it is also possible to interchange 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 is not equal to zero.
Delete rows 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.
Removing 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 the elements of another (in the corresponding columns), multiplied by a certain 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:

a 11 a 12 ... a 1n | b1

a 21 a 22 ... a 2n | b 2

Suppose you need to add the first to the second, multiplied by the coefficient "-2".

a" 21 \u003d a 21 + -2 × a 11

a" 22 \u003d a 22 + -2 × a 12

a" 2n \u003d a 2n + -2 × a 1n

Then in the matrix the second row is replaced with a new one, and the first one remains unchanged.

a 11 a 12 ... a 1n | b1

a" 21 a" 22 ... a" 2n | b 2

It should be noted that the multiplication factor can be chosen in such a way that, as a result of the addition of 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 called solving the system using the Gaussian method.

In general

Let there be a system. It has m equations and n unknown roots. You can write it down like this:

The main matrix is compiled from the coefficients of the system. A column of free members is added to the extended matrix and separated by a bar for convenience.

the first row of the matrix is multiplied by the coefficient k = (-a 21 / a 11);
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 row is a 11 × (-a 21 /a 11) + a 21 = -a 21 + a 21 = 0.

Now the same series of transformations is performed, only the first and third rows are involved. Accordingly, in each step of the algorithm, the element a 21 is replaced by a 31 . Then everything is repeated for a 41 , ... a m1 . The result is a matrix where the first element in the rows is equal to zero. Now we need to forget about line number one and execute the same algorithm starting from the second line:

coefficient k \u003d (-a 32 / a 22);
the second modified line is added to the "current" line;
the result of the addition is substituted in the third, fourth, and so on lines, while the first and second remain unchanged;
in the rows of the matrix, the first two elements are already equal to zero.

The algorithm must be repeated until the coefficient k = (-a m,m-1 /a mm) appears. This means that the last time the algorithm was executed was only for the lower equation. Now the matrix looks like a triangle, or has a stepped shape. The bottom line contains the equality a mn × x n = b m . The coefficient and free term are known, and the root is expressed through them: x n = b m /a mn. The resulting root is substituted into the top row to find x n-1 = (b m-1 - a m-1,n ×(b m /a mn))÷a m-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, you can find many solutions. 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 given 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?

All variables 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 for this particular case calculate the values of the basic variables. There are infinitely many particular solutions.

Solution with specific examples

Here is the system of equations.

For convenience, it is better to immediately create its matrix

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 elements of the remaining rows after the operations will turn to zero. This means that in the compiled matrix it will be advantageous to put the second in place of the first row.

second line: k = (-a 21 / a 11) = (-3/1) = -3

a" 21 \u003d a 21 + k × a 11 \u003d 3 + (-3) × 1 \u003d 0

a" 22 \u003d a 22 + k × a 12 \u003d -1 + (-3) × 2 \u003d -7

a" 23 = a 23 + k×a 13 = 1 + (-3)×4 = -11

b "2 \u003d b 2 + k × b 1 \u003d 12 + (-3) × 12 \u003d -24

third line: k = (-a 3 1 /a 11) = (-5/1) = -5

a" 3 1 = a 3 1 + k×a 11 = 5 + (-5)×1 = 0

a" 3 2 = a 3 2 + k×a 12 = 1 + (-5)×2 = -9

a" 3 3 = a 33 + k×a 13 = 2 + (-5)×4 = -18

b "3 \u003d b 3 + k × b 1 \u003d 3 + (-5) × 12 \u003d -57

Now, in order not to get confused, it is necessary to write down the matrix with the intermediate results of the transformations.

It is obvious that such a matrix can be made more convenient for perception with the help of some operations. For example, you can remove all "minuses" from the second line by multiplying each element by "-1".

It is also worth noting that in the third row all elements are multiples of three. Then you can reduce 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 a 32 becomes equal to zero.

k = (-a 32 / a 22) = (-3/7) = -3/7 fractions, and only then, when the answers are received, decide whether to round up and translate into another form of notation)

a" 32 = a 32 + k × a 22 = 3 + (-3/7) × 7 = 3 + (-3) = 0

a" 33 \u003d a 33 + k × a 23 \u003d 6 + (-3/7) × 11 \u003d -9/7

b "3 \u003d b 3 + k × b 2 \u003d 19 + (-3/7) × 24 \u003d -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 everything is beautiful. 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)

The algorithm by which the roots will now be found is called the reverse move in the Gauss method. Equation (3) contains the value of z:

y = (24 - 11×(61/9))/7 = -65/9

And the first equation allows you to find x:

x = (12 - 4z - 2y)/1 = 12 - 4x(61/9) - 2x(-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 response is written in the following form:

x 1 \u003d -2/3, y \u003d -65/9, z \u003d 61/9.

An 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.

x 1 + x 2 + x 3 + x 4 + x 5 = 7 (1)

3x 1 + 2x 2 + x 3 + x 4 - 3x 5 = -2 (2)

x 2 + 2x 3 + 2x 4 + 6x 5 = 23 (3)

5x 1 + 4x 2 + 3x 3 + 3x 4 - x 5 = 12 (4)

The very form of the system is already alarming, because the number of unknowns is n = 5, and the rank of the matrix of the system 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. This means that there are an infinite number of solutions, and it is necessary to look for its general form. The Gauss method for linear equations makes it possible to do this.

First, as usual, the augmented matrix is compiled.

Second line: coefficient k = (-a 21 / a 11) = -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 = (-a 4 1 /a 11) = -5

Multiplying the elements of the first row by each of their coefficients in turn and adding them to the desired rows, we obtain a matrix of the following form:

As you can see, the second, third and fourth rows consist of elements that are 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.

It turned out such a matrix. The system has not yet been written down, it is necessary here to determine the basic variables - standing at the coefficients a 11 \u003d 1 and a 22 \u003d 1, and free - all the rest.

The second equation has only one basic variable - x 2 . Hence, it can be expressed from there, writing through the variables x 3 , x 4 , x 5 , which are free.

We substitute the resulting expression into the first equation.

It turned out an equation in which the only basic variable is x 1. Let's do the same with it as with x 2 .

All basic variables, of which there are two, are expressed in terms of three free ones, now you can write the answer in a 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 incompatible system

The 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 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 it is reduced to a stepped form:

k 1 \u003d -2k 2 \u003d -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

having no solution. Therefore, the system is 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 the 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 - determinant, minors, inverse, 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 only add matrices of the same size!), Multiplication by a number, matrix multiplication (also with certain 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, to establish its compatibility or inconsistency.

Let the system be given, ∆≠0. (one)
Gauss method is a method of successive elimination of unknowns.

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 the unknowns 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.
After that, leaving the first equation alone, over the rest of the equations of the system obtained at the first step, we will perform a similar transformation: we choose 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:

The first stage is called the direct course 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 equivalent to the original one is solved.

Coefficients a 11 , a 22 , ..., are called leading elements.
At each step, it was assumed that the leading element is different from zero. If this is not the case, then any other element can be used as a leader, as if rearranging the equations of the system.

Purpose of the Gauss method

The Gauss method is intended for solving systems of linear equations. Refers to direct methods of solution.

Types of Gauss method

Classical Gauss method;
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.
Jordan-Gauss method;

The difference between the Jordan-Gauss method and the classical one Gauss method consists in applying the rectangle rule when the direction of the search for a solution is along the main diagonal (transformation to the identity matrix). In the Gauss method, the direction of the search for a solution occurs along the columns (transformation to a system with a triangular matrix).
Illustrate the difference Jordan-Gauss method from the Gauss method on examples.

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:

x 1	x2	x 3	B
1 / 1 = 1	2 / 1 = 2	-2 / 1 = -2	1 / 1 = 1

The enabling element is equal to (3).
In place of the resolving element, we get 1, and in the column itself we write zeros.
All other elements of the matrix, including the elements of 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 enabling element of the RE.

x 1	x2	x 3	B

0 / 3 = 0	3 / 3 = 1	1 / 3 = 0.33	4 / 3 = 1.33

The enabling element is (-4).
In place of the resolving element, we get 1, and in the column itself we write zeros.
All other elements of the matrix, including the elements of 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 enabling element of the RE.
Let's present the calculation of each element in the form of a table:

x 1	x2	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 Gauss 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 compiled, which is solved by the Gauss method.

Application of the Gauss method in solving differential equations

To search for 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. Further, to find the variables A, B, C, D, a system of equations is compiled, 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 a simplex table at each iteration, the rectangle rule is used, which uses the Jordan-Gauss method.

Gauss method great for solving systems of linear algebraic equations (SLAE). It has several advantages over other methods:

firstly, there is no need to pre-investigate the system of equations for compatibility;
secondly, the Gauss method can be used to solve not only SLAEs in which the number of equations coincides with the number of unknown variables and the main matrix of the system is nondegenerate, but also systems of equations in which the number of equations does not coincide with the number of unknown variables or the determinant of the main matrix is equal to zero;
thirdly, the Gauss method leads to a result with a relatively small number of computational operations.

Brief review of the article.

First, we give the necessary definitions and introduce some notation.

Next, we describe the algorithm of the Gauss method for the simplest case, that is, for systems of linear algebraic equations, the number of equations in which coincides with the number of unknown variables and the determinant of the main matrix of the system is not equal to zero. When solving such systems of equations, the essence of the Gauss method is most clearly visible, which consists in the successive elimination of unknown variables. Therefore, the Gaussian method is also called the method of successive elimination of unknowns. Let us show detailed solutions of several examples.

In conclusion, we consider the Gaussian solution of systems of linear algebraic equations whose main matrix is either rectangular or degenerate. The solution of such systems has some features, which we will analyze in detail using examples.

Page navigation.

Basic definitions and notation.

Consider a system of p linear equations with n unknowns (p can be equal to n ):

Where are unknown variables, are numbers (real or complex), are free members.

If a , then the system of linear algebraic equations is called homogeneous, otherwise - heterogeneous.

The set of values of unknown variables, in which all equations of the system turn into identities, is called SLAU decision.

If there is at least one solution to a system of linear algebraic equations, then it is called joint, otherwise - incompatible.

If a SLAE has a unique solution, then it is called certain. If there is more than one solution, then the system is called uncertain.

The system is said to be written in coordinate form if it has the form
.

This system in matrix form records has the form , where - the main matrix of SLAE, - the matrix of the column of unknown variables, - the matrix of free members.

If we add to the matrix A as the (n + 1)-th column the matrix-column of free terms, then we get the so-called expanded matrix systems of linear equations. Usually, the augmented matrix is denoted by the letter T, and the column of free members is separated by a vertical line from the rest of the columns, that is,

The square matrix A is called degenerate if its determinant is zero. If , then the matrix A is called non-degenerate.

The following point should be noted.

If the following actions are performed with a system of linear algebraic equations

swap two equations,
multiply both sides of any equation by an arbitrary and non-zero real (or complex) number k,
to both parts of any equation add the corresponding parts of the other equation, multiplied by an arbitrary number k,

then we get an equivalent system that has the same solutions (or, like the original one, has no solutions).

For an extended matrix of a system of linear algebraic equations, these actions will mean elementary transformations with rows:

swapping two strings
multiplication of all elements of any row of the matrix T by a non-zero number k ,
adding to the elements of any row of the matrix the corresponding elements of another row, multiplied by an arbitrary number k .

Now we can proceed to the description of the Gauss method.

Solving systems of linear algebraic equations, in which the number of equations is equal to the number of unknowns and the main matrix of the system is nondegenerate, by the Gauss method.

What would we do at school if we were given the task of finding a solution to a system of equations .

Some would do so.

Note that by adding the left side of the first equation to the left side of the second equation, and the right side to the right side, you can get rid of the unknown variables x 2 and x 3 and immediately find x 1:

We substitute the found value x 1 \u003d 1 into the first and third equations of the system:

If we multiply both parts of the third equation of the system by -1 and add them to the corresponding parts of the first equation, then we get rid of the unknown variable x 3 and can find x 2:

We substitute the obtained value x 2 \u003d 2 into the third equation and find the remaining unknown variable x 3:

Others would have done otherwise.

Let's solve the first equation of the system with respect to the unknown variable x 1 and substitute the resulting expression into the second and third equations of the system in order to exclude this variable from them:

Now let's solve the second equation of the system with respect to x 2 and substitute the result obtained into the third equation in order to exclude the unknown variable x 2 from it:

It can be seen from the third equation of the system that x 3 =3. From the second equation we find , and from the first equation we get .

Familiar solutions, right?

The most interesting thing here is that the second solution method is essentially the method of sequential elimination of unknowns, that is, the Gauss method. When we expressed unknown variables (first x 1 , next x 2 ) and substituted them into the rest of the equations of the system, we thereby excluded them. We carried out the exception until the moment when the last equation left only one unknown variable. The process of sequential elimination of unknowns is called direct Gauss method. After the forward move is completed, we have the opportunity to calculate the unknown variable in the last equation. With its help, from the penultimate equation, we find the next unknown variable, and so on. The process of successively finding unknown variables while moving from the last equation to the first is called reverse Gauss method.

It should be noted that when we express x 1 in terms of x 2 and x 3 in the first equation, and then substitute the resulting expression into the second and third equations, the following actions lead to the same result:

Indeed, such a procedure also allows us to exclude the unknown variable x 1 from the second and third equations of the system:

Nuances with the elimination of unknown variables by the Gauss method arise when the equations of the system do not contain some variables.

For example, in SLAU in the first equation, there is no unknown variable x 1 (in other words, the coefficient in front of it is zero). Therefore, we cannot solve the first equation of the system with respect to x 1 in order to exclude this unknown variable from the rest of the equations. The way out of this situation is to swap the equations of the system. Since we are considering systems of linear equations whose determinants of the main matrices are different from zero, there always exists an equation in which the variable we need is present, and we can rearrange this equation to the position we need. For our example, it is enough to swap the first and second equations of the system , then you can solve the first equation for x 1 and exclude it from the rest of the equations of the system (although x 1 is already absent in the second equation).

We hope you get the gist.

Let's describe Gauss method algorithm.

Let us need to solve a system of n linear algebraic equations with n unknown variables of the form , and let the determinant of its main matrix be nonzero.

We will assume that , since we can always achieve this by rearranging the equations of the system. We exclude the unknown variable x 1 from all equations of the system, starting from the second one. To do this, add the first equation multiplied by to the second equation of the system, add the first multiplied by to the third equation, and so on, add the first multiplied by to the nth equation. The system of equations after such transformations will take the form

where , a .

We would come to the same result if we expressed x 1 in terms of other unknown variables in the first equation of the system and substituted the resulting expression into all other equations. Thus, the variable x 1 is excluded from all equations, starting from the second.

Next, we act similarly, but only with a part of the resulting system, which is marked in the figure

To do this, add the second multiplied by to the third equation of the system, add the second multiplied by to the fourth equation, and so on, add the second multiplied by to the nth equation. The system of equations after such transformations will take the form

where , a . Thus, the variable x 2 is excluded from all equations, starting from the third.

Next, we proceed to the elimination of the unknown x 3, while acting similarly 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 moment, we begin the reverse course of the Gauss method: we calculate x n from the last equation as , using the obtained value of x n we find x n-1 from the penultimate equation, and so on, we find x 1 from the first equation.

Let's analyze the algorithm with an example.

Example.

Gaussian method.

Decision.

The coefficient a 11 is different from zero, so let's proceed to the direct course of the Gauss method, that is, to the elimination of the unknown variable x 1 from all equations of the system, except for the first one. To do this, to the left and right parts of the second, third and fourth equations, add the left and right parts of the first equation, multiplied by , respectively, and :

The unknown variable x 1 has been eliminated, let's move on to the exclusion x 2 . To the left and right parts of the third and fourth equations of the system, we add the left and right parts of the second equation, multiplied by and :

To complete the forward course of the Gauss method, we need to exclude the unknown variable x 3 from the last equation of the system. Add to the left and right sides of the fourth equation, respectively, the left and right sides of the third equation, multiplied by :

You can start the reverse course of the Gauss method.

From the last equation we have ,
from the third equation we get ,
from the second
from the first.

To check, you can substitute the obtained values of unknown variables into the original system of equations. All equations turn into identities, which means that the solution by the Gauss method was found correctly.

Answer:

And now we will give the solution of the same example by the Gauss method in matrix form.

Example.

Find a solution to the system of equations Gaussian method.

Decision.

The extended matrix of the system has the form . Above each column, unknown variables are written, which correspond to the elements of the matrix.

The direct course of the Gauss method here involves bringing the extended matrix of the system to a trapezoidal form using elementary transformations. This process is similar to the exclusion of unknown variables that we did with the system in coordinate form. Now you will be convinced of it.

Let's transform the matrix so that all elements in the first column, starting from the second, become zero. To do this, to the elements of the second, third and fourth rows, add the corresponding elements of the first row multiplied by , and on respectively:

Next, we transform the resulting matrix so that in the second column, all elements, starting from the third, become zero. This would correspond to excluding the unknown variable x 2 . To do this, add to the elements of the third and fourth rows the corresponding elements of the first row of the matrix, multiplied by and :

It remains to exclude the unknown variable x 3 from the last equation of the system. To do this, to the elements of the last row of the resulting matrix, we add the corresponding elements of the penultimate row, multiplied by :

It should be noted that this matrix corresponds to the system of linear equations

which was obtained earlier after the direct move.

It's time to turn back. In the matrix form of the notation, the reverse course of the Gauss method involves such a transformation of the resulting matrix so that the matrix marked in the figure

became diagonal, that is, took the form

where are some numbers.

These transformations are similar to those of the Gauss method, but are performed not from the first line to the last, but from the last to the first.

Add to the elements of the third, second and first rows the corresponding elements of the last row, multiplied by , on and on respectively:

Now let's add to the elements of the second and first rows the corresponding elements of the third row, multiplied by and by, respectively:

At the last step of the reverse motion of the Gaussian method, we add the corresponding elements of the second row, multiplied by , to the elements of the first row:

The resulting matrix corresponds to the system of equations , from which we find the unknown variables.

Answer:

NOTE.

When using the Gauss method to solve systems of linear algebraic equations, approximate calculations should be avoided, as this can lead to absolutely incorrect results. We recommend that you do not round decimals. It is better to move from decimal fractions to ordinary fractions.

Example.

Solve System of Three Equations by Gaussian Method .

Decision.

Note that in this example, the unknown variables have a different designation (not x 1 , x 2 , x 3 , but x, y, z ). Let's move on to ordinary fractions:

Eliminate the unknown x from the second and third equations of the system:

In the resulting system, there is no unknown variable y in the second equation, and y is present in the third equation, therefore, we swap the second and third equations:

At this point, the direct course of the Gauss method is over (you do not need to exclude y from the third equation, since this unknown variable no longer exists).

Let's go back.

From the last equation we find ,
from penultimate

from the first equation we have

Answer:

X=10, y=5, z=-20.

The solution of systems of linear algebraic equations, in which the number of equations does not coincide with the number of unknowns or the main matrix of the system is degenerate, by the Gauss method.

Systems of equations whose main matrix is rectangular or square degenerate may have no solutions, may have a single solution, or may have an infinite number of solutions.

Now we will understand how the Gauss method allows us to establish the compatibility or inconsistency of a system of linear equations, and in the case of its compatibility, determine all solutions (or one single solution).

In principle, the process of eliminating unknown variables in the case of such SLAEs remains the same. However, it is worth dwelling in detail on some situations that may arise.

Let's move on to the most important step.

So, let us assume that the system of linear algebraic equations after the completion of the forward run of the Gauss method takes the form and none of the equations reduced to (in this case, we would conclude that the system is inconsistent). A logical question arises: "What to do next"?

We write out the unknown variables that are in the first place of all the equations of the resulting system:

In our example, these are x 1 , x 4 and x 5 . In the left parts of the equations of the system, we leave only those terms that contain the written out unknown variables x 1, x 4 and x 5, we transfer the remaining terms to the right side of the equations with the opposite sign:

Let us assign arbitrary values to the unknown variables that are on the right-hand sides of the equations, where - arbitrary numbers:

After that, the numbers are found in the right parts of all the equations of our SLAE and we can proceed to the reverse course of the Gauss method.

From the last equation of the system we have , from the penultimate equation we find , from the first equation we get

The solution of the system of equations is the set of values of unknown variables

Giving numbers different values, we will get different solutions to the system of equations. That is, our system of equations has infinitely many solutions.

Answer:

where - arbitrary numbers.

To consolidate the material, we will analyze in detail the solutions of several more examples.

Example.

Solve Homogeneous System of Linear Algebraic Equations Gaussian method.

Decision.

Let us exclude the unknown variable x from the second and third equations of the system. To do this, add the left and right parts of the first equation, respectively, to the left and right parts of the second equation, multiplied by , and to the left and right parts of the third equation, the left and right parts of the first equation, multiplied by :

Now we exclude y from the third equation of the resulting system of equations:

The resulting SLAE is equivalent to the system .

We leave only the terms containing the unknown variables x and y on the left side of the equations of the system, and transfer the terms with the unknown variable z to the right side: