Let us represent the system of equations (1.1) in the form
There are a large number of elimination method schemes adapted for manual or machine calculation of matrices of general or special types.
The Gaussian method can be interpreted as a method in which the matrix is initially reduced to an upper triangular form (forward move), and then to a unit form (reverse move). Obviously, if the matrix is identity, then xt = b r
Let the matrix of system (1.3) be upper triangular, therefore a tj= 0 at i>j, that is, all elements below the main diagonal are zero. Then from the last equation we immediately determine x p. Substituting x n into the penultimate equation, we find x a_ x, etc. General formulas have the form
At k > I odds a s = 0.
Let us reduce the matrix of system (1.3) to an upper triangular one. Let us subtract from the second equation of system (1.3) the first, multiplied by a number such that the coefficient at x x will go to zero. Let's do the same with all the other equations. As a result, all coefficients of the first column lying below the main diagonal will go to zero. Then, using the second equation, we turn the corresponding coefficients of the second column to zero. Consistently continuing this process, we reduce the system matrix to the upper triangular form.
Let us write down the general formulas of the Gauss method. Let the coefficients be eliminated from the (A - 1)th column. Then there will be equations with non-zero elements below the main diagonal:
Let's multiply kth line to number with tk = t > k and subtract
from the mth line. The first non-zero element of this line will become zero, and the rest will change according to the formulas
Having carried out calculations using these formulas for all indicated indices, we turn the elements to zero k-ro columns below the main diagonal. A similar procedure reduces the matrix of the system to the upper triangular form, and the entire reduction process is called the DIRECT PROCESS OF THE GAUSSian METHOD. Calculation of unknowns using formulas (1.4) is called the REVERSE method.
The reverse move can be made differently if all coefficients lying above the main diagonal are turned to zero. For example, elements P of the th column become zero if ej^| multiply by (-a^V ax t = b | 2l), where b^n)- coefficients of the right side of the i-th equation after the indicated transformations.
At some forward step, it may turn out that the coefficient aj*" * 0, but is small compared to the other elements of the system matrix and, in particular, small compared to the elements of the first column. Dividing the system coefficients by a small value can lead to significant rounding errors .
To reduce rounding errors proceed as follows. Among the elements of the first column A^ of each intermediate matrix, select the largest modulus (main) element and by rearranging the i-th row with the row containing the main element, ensure that the main element becomes the leading one. This modification of the Gaussian elimination method is called the Gaussian method with principal element selection. The case of the appearance of zero elements is avoided by itself.
To implement the method, it takes approximately P 3/3 operations such as multiplication and P 3/3 operations like addition. It is useful to remember that the estimate of the number of operations is determined mainly by the operations spent in performing the forward stroke of the Gaussian method. The inverse of the Gaussian method requires approximately n 2 operations. Therefore, if you need to solve several systems of linear algebraic equations of the form Ax = b with the same matrix and different right-hand sides, then the total number of operations when solving S systems will be assessed size(2/3)p 3 + Sn 2 . In this case, it is advisable to implement the Gauss method algorithm in the form of two subroutines: the first subroutine should implement the forward progression of the algorithm and obtain an upper triangular matrix as output, and the second subroutine should, using the resulting matrix, calculate the solution of the system for an arbitrary right-hand side.
In this case, in addition to compliance with the requirement a kk0 when implementing formulas (6), additional requirements are imposed that the leading (main) element in the current column in the process of transformations of the original matrix has a maximum absolute value. This is also achieved by rearranging the rows of the matrix.
Example. To illustrate the advantages of the modified Gaussian method, consider a third-order system:
Direct stroke of the Gaussian method
We exclude X 1 from the second and third equations. To do this, multiply the first equation by 0.3 and add it with the second, and then multiply the first equation by (–0.5) and add it with the third. As a result we get
(b)
The second equation is not replaced by the third one, because calculations are performed within the framework of exact arithmetic.
Multiplying the second equation by 25 and adding it with the third, we get
(V)
Reverse Gaussian Method
We carry out calculations starting from the last equation in the resulting system:
Substituting the resulting solution into the original system, we are convinced of its truth.
Now we will change the coefficients of the system in such a way as to preserve the previous solution, but during the calculation we will use rounding within the framework of floating point arithmetic, maintaining five digits. The following system will correspond to this
(G)
Direct method for the system ( G) we will repeat using a similar technology with the original system ( A).
(d)
After elimination X 2, the third equation will take the form (the rest remain unchanged)
15005 X 3 = 15004. (e)
Carrying out the reverse move, we get
It is obvious that the obtained solutions and [–0.35; –1.4; 0.99993] are different. The reason for this is the small value of the leading element in the second transformation equation in ( d). To eliminate this, we rearrange in ( d) second and third lines
(and)
For this system after exclusion X 2 from the third equation, it will take the following form
6,002 X 3 = 6,002. (h)
In this case, performing the reverse move
we get a solution to the system ( G) which exactly coincides with the solution of the original system.
Solving the system ( G) we used a modified Gaussian method, in which the maximum element in the current column should be located on the diagonal.
Let's consider the block diagram of the modified Gaussian method (Fig. 2.1).
Rice. 2.1. Block diagram of the modified Gaussian method
Let us analyze the proposed scheme using the example of a system n=3 (=0,001)
(8)
;
.
(*)
Block 1. Entering initial data: n– order of the system, A– matrix of coefficients for unknowns, b– vector of free terms.
Block 2.I-th forward stroke cycle (for k, varying from 1 to the penultimate value, i.e. before n–1) provides exclusion from the main diagonal of the matrix A element a kk=0 thanks to the search for the maximum element a kk in the current column, carried out in blocks 36 using loopII.
Then calculations are carried out using formulas (6) of the forward Gaussian motion in blocks of cycles IV and V.
Let us carry out a block-by-block analysis in the environment of the considered cycles IV using example (8).
Block 3p =k = 1
Entering Cycle II
Block 4m =k+1 = 2 to n = 3
Block 5a 11 = 2 <a 21 = 4 of (*)
Block 6p= 2
Block 4m= 2+1 = 3
Block 5a 21 = 4 <a 31 = 6 from (*)
Block 6p= 3
Exiting cycle II and entering cycle III, blocks 710 perform permutation of matrix rows A element by element
Block 7j= 1 (j from 1 to 3)
Block 8 r = a 11 = 2 of (*)
Block 9 a 11 = a 31 = 6
Block 10 a 31 = r
Block 7 j = 2
Block 8 r = a 12 = 1
Block 9 a 12 = a 32 = 5
Block 10 a 32 = r = 1
Block 7j= 3 and by analogy r=a 13 ;a 13 =a 33 ;a 33 =r= −1.
Exiting cycle III and entering Block 11 and further 1213 perform a similar rearrangement of the values of the free terms
r=b 1 = 1;b 1 = b 3 = 14;b 3 =r= 1.
Entering cycle IV with a modified system
;
;
(**)
for recalculation b 2 vectors 
m=k+1 = 1+1 = 2 to n= 3
c = a mk / a kk = a 21 / a 11 = 4/6 of (**)
b 2 =b 2 –c b 1 = 6 – 4/614 = −20/6 from (**)
Entering nested loop V to recalculate the second row
i = 1 (i from 1 to 3); a 21 = a 21 – With a 11 = 4 – 4/6 6 = 0;
i = 2; a 22 = a 22 – With a 12 = 6 – 4/6 5 = 16/6;
i = 3; a 23 = a 23 – With a 13 = 2 – 4/6 8 = −20/6.
Exiting cycle V and entering cycle IV
m= 3;c=a 31 /a 11 = 2/6.
Login Block 16
b 3 =b 3 –c b 1 = 1 – 2/614 = −22/6.
Exiting cycle IV and entering cycle V and entering Block 17
i = 1 (i from 1 to 3); a 31 = a 31 – With a 11 = 2 – 2/6 6 = 0;
i = 2; a 32 = a 32 – With a 12 = 1 – 2/6 5 = −4/6;
i = 3; a 33 = a 33 – With a 13 = −1 – 2/6 8 = −22/6.
Exit from cycle V with transformed system
;
;
(***)
and line entry A in cycle I
k = 2;p =k = 2;m =k+1 = 3; entrance to Block 5
| a 22 | < |a 32 | = | 16/6 | > | 4/6 | from (***).
Exiting cycle II and entering cycle III
j = 2 (j from 2 to 3);
r = a kj = a 22 = 16/6; a 22 = a 22 ; a 22 = r= 16/6; from (***)
r=a 23 = −20/6;a 23 =a 23 ;a 23 =r= −20/6; from (***)
In this case, there is a maximum element on the diagonal, so the swap of the 2nd and 3rd rows is not performed.
Exiting cycle III and entering cycle Ic Block 11
r=b 2 ;b 2 = b 2 ;b 2 =r= −20/6.
Free member b 2 remains in place.
Entering Cycle IV
m=k+1 = 2+1 = 3;
c = a mk / a kk = a 32 / a 22 = (–4/6) / (16/6); from (***)
b 3 =b 3 –c b 2 = −22/6 – (–1/4)(–20/6) = −27/6 from (***)
Exiting cycle IV and entering cycle V
i = 2 (i from 2 to 3); a 32 = a 32 – With a 22 = −4/6 – (–1/4) 16/6 = 0;
i= 3;a 33 =a 33 –Witha 23 = −22/6 – (–1/4)(–20/6) = −27/6.
Exit from cycle V and exit from cycle I.
Reverse Gaussian Method
IN Blocks 1924 formulas (7) are implemented.
IN Block 19 from the last equation the value is found x n (n= 3)
x 3 =b n / a nn =b 3 / a 33 = (–27/6) / (–27/6) = 1.
Entering cycle VI( Block 20), in which the value of the loop variable k varies from n–1 to 1 in steps (–1)
Block 21s= 0
Entering cycle VII( Block 22)
i = k+1 = 2+1 = 3; n = 3; s = s + a ki x i = 0 + a 23 x 3 = −20/6 1 = −20/6.
Exit from cycle VII Block 24 per cycleVI:
k = 2; x 2 = (b k–s)/ a nn = (b 2 – s)/ a 22 = (–20/6 +20/6)/a 22 = 0.
k=k–1 = 2–1 = 1;
i = k + 1 = 2; s = 0 + a 12 x 2 = 5 0 = 0;
i = k + 1 = 3; s = 0 + a 13 x 3 = 8 1 = 8;
x 1 = (b 1 –s)/ a 11 = (14 – 8) / 6 = 1.
Exit from the last cycle VII.
IN Block 25 (cycle omitted) the resulting solution of the SLAE - vector is displayed on the screen 
those. x i ,i=1, ...,n. In our case (1; 0; 1).
Let's consider one of the most common methods for solving systems of linear algebraic equations - the Gauss method. This method (also called the method of sequential elimination of unknowns) has been known in various versions for more than 2000 years.
Calculations using the Gaussian method consist of two main steps, called forward movement and backward movement (backward substitution). The direct approach of the Gauss method consists in sequentially eliminating unknowns from system (5.1) to transform it to an equivalent system with an upper triangular matrix. Calculations of the values of the unknowns are carried out at the reverse stage.
1. Scheme of a single division.
Let us first consider the simplest version of the Gaussian method, called the single division scheme.
The forward move consists of elimination steps.
1st step. The purpose of this step is to eliminate the unknown from equations with numbers. Suppose that the coefficient We will call it the main (or leading) element of the 1st step.
Let's find the quantities
called 1st step multipliers. Let us subtract sequentially from the second, third, equations of system (5.1) the first equation, multiplied by respectively. This will allow us to turn into
zero coefficients in all equations except the first. As a result, we obtain an equivalent system
in which they are calculated using the formulas
2nd step. The purpose of this step is to eliminate the unknown from equations with numbers. Let where is a coefficient called the main (or leading) element of the step. Let's calculate the factors of the 2nd step
and subtract sequentially from the third, fourth, equations of system (5.30) the second equation, multiplied by , respectively. As a result, we obtain the system
Here the coefficients are calculated using the formulas
The remaining steps are carried out similarly. Let's describe the next step.
kth step. Assuming that the main (leading) element of the step is nonzero, we calculate the step multipliers
and subtract sequentially from the equations of the system obtained at the previous step the equation multiplied by
After the elimination step we obtain a system of equations
whose matrix is upper triangular. This completes the forward calculations.
Reverse move. From the last equation of system (5.33) we find. Substituting the found value into the penultimate equation, we obtain. Carrying out the reverse substitution, we then successively find. Calculations of unknowns are carried out here using the formulas
The complexity of the method. Let us estimate the number of arithmetic operations required to implement the single division scheme.
Calculations of the 1st step of elimination according to formulas (5.29), (5.31) require division, multiplication and subtraction, i.e. the total number of arithmetic operations is Similarly, operations are required at the step, and operations at the step.
Let us now approximately calculate the total number of forward arithmetic operations, considering the dimension of the system to be sufficiently large:
As is easy to see, to implement the reverse stroke according to formulas (5.34) you need a total of operations, which for large ones is negligible compared to the number of forward stroke operations.
Thus, to implement the Gaussian method, approximately arithmetic operations are required, and the overwhelming majority of these operations are performed at the forward stage.
Example 5.7. Using the Gaussian method we solve the system
Direct move. 1st step. Let's calculate the factors. Subtracting from the second, third and fourth equations of system (5.35) the first equation multiplied by, respectively, we get
2nd step. Let's calculate the factors. Subtracting from the third and fourth equations of system (5.36) the second equation multiplied by, respectively, we arrive at the system
3rd step. By calculating the factor and subtracting from the fourth equation of system (5.37) the third equation multiplied by we reduce the system to triangular form:
Reverse move. From the last equation of the system we find. Substituting the value into the third equation, we find
The calculation results can be summarized in the following table.
Table 5.2 (see scan)
The need to select the main elements. Note that the calculation of factors, as well as reverse substitution, require division by the main elements. Therefore, if one of the main elements is equal to zero, then the single division scheme cannot be implemented. Common sense dictates that in a situation where all the main elements are different from zero, but among them there are those close to zero, an uncontrolled increase in error is possible.
Example 5.8. Using the Gauss method, we solve the system of equations
on a -bit decimal computer.
Direct move. 1st step. We calculate the factors and transform the system to the form
All calculations in this step are performed without rounding.
2nd step. After calculating the multiplier, the last equation of the system must be converted to the form where However, on the computer used, the equation will be obtained
Indeed, the coefficient is determined precisely, since when calculating it, there are no numbers whose mantissas have more than 6 digits. At the same time, when calculating, multiplying the coefficient 3.0001 by gives a 7-digit number 105003.5, after rounding to 6 digits the result is 105004. Calculation 62) is completed by performing the subtraction operation: . After rounding the last number to 6 digits of the mantissa, we arrive at equation (5.41).
Reverse move. From equation (5.41) we also find 1.00001. Comparison with the true value shows that this value was obtained with very high accuracy for the computer used. Further calculations give
After rounding we have .
As is easy to see, the found values of the unknowns have little in common with the true values of the solution
What is the reason for such a significant error? There is no need to talk about the accumulation of rounding errors, since a total of 28 arithmetic operations were performed and only in 4 cases was rounding required. The assumption that the system is poorly conditioned is not confirmed; the calculation gives the value and 100.
In reality, the reason is the use of a small leading element in the step. The consequence of this was the appearance of a large
multiplier and a significant increase in the coefficient in the last equation of the system.
Thus, the above version of the Gauss method (single division scheme) turned out to be incorrect and, therefore, unsuitable for computer calculations. This method can lead to an emergency stop (if for some reason and the calculations using it may turn out to be unstable.
2. Gaussian method with selection of the main element by column (partial selection scheme).
Description of the method. At the forward step, the coefficients of the equations of the system with numbers are converted according to the formulas
It is intuitively clear that in order to avoid a strong increase in the system coefficients and associated errors, large multipliers should not be allowed to appear
In the Gaussian method with the selection of the main element by column, it is guaranteed that for all k. The difference between this version of the Gaussian method and the single division scheme is that at the elimination step the coefficient a, which has the maximum absolute value, is selected as the main element. for an unknown in equations with numbers Then the equation with number corresponding to the selected coefficient is swapped with the equation of the system so that the main element takes the place of the coefficient
After this permutation, the exclusion of the unknown is carried out, as in the single division scheme.
Example 5.9. Let us solve the system of equations (5.39) using the Gaussian method with the selection of the main element by column on a -bit decimal computer.
Direct move. 1st step. The maximum element of the matrix in the first column is in the first row, so rearranging the equations is not necessary. Here the 1st step is carried out exactly the same as in example 5.8.
2nd step. Among the elements of the matrix of system (5.40), the maximum one belongs to the third equation. Swapping the second and third equations, we obtain the system
After calculation, the last equation of the system is transformed to the form
Reverse move. From the last equation we find Further, we have In this case, the answer turned out to be accurate.
Note that additional work on selecting the main elements in the partial selection scheme requires a sequence of actions, which practically does not affect the overall complexity of the method.
Computational stability of the partial selection scheme. A detailed study of the Gauss method shows that the real reason for the instability of the single division scheme is the possibility of unlimited growth of the elements of intermediate matrices in the process of forward motion. Since at step 1 of the partial selection scheme, the following estimate is valid for the elements calculated using formulas (5.42): Therefore, the maximum absolute value of the matrix elements increases at one step by no more than 2 times and in the most unfavorable case, the forward step will give a growth coefficient
The guarantee that the growth of matrix elements is limited makes the partial selection scheme computationally stable. Moreover, the following error estimate turns out to be valid for it:
Here is a computer-computerized solution to the system; its relative error; matrix condition number em - machine epsilon; finally, some slowly growing function depending on the order of the system (such as a power function with a small exponent), the growth coefficient.
The presence of a multiplier in estimate (5.43) indicates that, if large, the partial choice scheme may turn out to be ill-conditioned and a significant loss of accuracy is possible. However, the practice of matrix calculations shows that significant growth of matrix elements occurs extremely rarely. In the vast majority of cases, the actual value of the growth coefficient does not exceed 8-10. If the system is well conditioned, then the error of the calculated solution is, as a rule, small.
Sometimes to check the quality of the approximate solution x
They calculate the discrepancy and try to judge the degree of closeness of the approximate solution to the exact one by how small the discrepancy is. This method is unreliable with respect to the partial choice scheme, since it is known that it is guaranteed to give small failures. More precisely, this statement can be formulated as follows: the estimate is fair
where is the same as in estimate (5.43). Note that inequality (5.44) does not include the condition number.
3. Gaussian method with samples of the main element throughout the matrix (full selection scheme).
This scheme allows for a violation of the natural order of eliminating unknowns.
At the 1st step of the method, among the elements, the element with the maximum absolute value is determined. The first equation of the system and the equation with the number are swapped. Next, the unknown x is excluded in a standard way from all equations except the first. (which is significantly less than the corresponding value for the partial selection scheme). We emphasize that a matrix has not yet been found for which a complete choice would give the value Thus, for well-conditioned systems, this version of the Gaussian method is well-conditioned.
However, the guarantee of good conditionality is achieved here at the cost of significant costs for the selection of the main elements. To do this, in addition to arithmetic operations, it is necessary to perform approximately comparison operations, which can significantly slow down the process of solving the problem on a computer. Therefore, in most cases, in practice, preference is still given to the partial choice scheme. As already noted, situations where a significant increase in elements occurs when using this version of the Gaussian method are extremely rare. Moreover, these situations can be easily identified using effective methods for monitoring the growth of matrix elements embedded in modern programs.
4. Cases when the selection of main elements is not necessary.
It is known that for some classes of matrices, when using a single division scheme, the main elements are guaranteed to be located on the main diagonal and therefore there is no need to use partial selection. This is the case, for example, for systems with positive definite matrices, as well as for matrices with the following property of diagonal dominance:
Matrices that satisfy condition (5.45) are such that in each row the modulus of the element located on the main diagonal is greater than the sum of the moduli of all other elements of the row.
5. Scaling.
Before starting the solution, it is advisable to scale the system so that its coefficients are on the order of unity.
There are two natural ways to scale a system. The first is to multiply each of the equations by some scaling factor. The second is to multiply each column of the matrix by a scaling factor, which corresponds to changing variables (in fact, this is changing units of measurement). In real-life situations, most often scaling can be accomplished without significant difficulties. However, we emphasize that in the general case a satisfactory scaling method has not yet been found.
In practice, scaling is usually done by dividing each equation by its largest coefficient in magnitude. This is a completely satisfactory method for most real-life problems.
One of the simplest ways to solve a system of linear equations is a technique based on the calculation of determinants ( Cramer's rule). Its advantage is that it allows you to immediately record the solution; it is especially convenient in cases where the coefficients of the system are not numbers, but some parameters. Its disadvantage is the cumbersomeness of calculations in the case of a large number of equations; moreover, Cramer's rule is not directly applicable to systems in which the number of equations does not coincide with the number of unknowns. In such cases, it is usually used Gaussian method.
Systems of linear equations having the same set of solutions are called equivalent. Obviously, the set of solutions of a linear system will not change if any equations are swapped, or if one of the equations is multiplied by some non-zero number, or if one equation is added to another.
Gauss method (method of sequential elimination of unknowns) is that with the help of elementary transformations the system is reduced to an equivalent system of a step type. First, using the 1st equation, we eliminate x 1 of all subsequent equations of the system. Then, using the 2nd equation, we eliminate x 2 from the 3rd and all subsequent equations. This process, called direct Gaussian method, continues until there is only one unknown left on the left side of the last equation x n. After this it is done inverse of the Gaussian method– solving the last equation, we find x n; after that, using this value, from the penultimate equation we calculate x n–1, etc. We find the last one x 1 from the first equation.
It is convenient to carry out Gaussian transformations by performing transformations not with the equations themselves, but with the matrices of their coefficients. Consider the matrix:
called extended matrix of the system, because, in addition to the main matrix of the system, it includes a column of free terms. The Gaussian method is based on reducing the main matrix of the system to a triangular form (or trapezoidal form in the case of non-square systems) using elementary row transformations (!) of the extended matrix of the system.
Example 5.1. Solve the system using the Gaussian method:
Solution. Let's write out the extended matrix of the system and, using the first row, after that we will reset the remaining elements:
we get zeros in the 2nd, 3rd and 4th rows of the first column:
Now we need all elements in the second column below the 2nd row to be equal to zero. To do this, you can multiply the second line by –4/7 and add it to the 3rd line. However, in order not to deal with fractions, let's create a unit in the 2nd row of the second column and only
Now, to get a triangular matrix, you need to reset the element of the fourth row of the 3rd column; to do this, you can multiply the third row by 8/54 and add it to the fourth. However, in order not to deal with fractions, we will swap the 3rd and 4th rows and the 3rd and 4th columns and only after that we will reset the specified element. Note that when rearranging the columns, the corresponding variables change places and this must be remembered; other elementary transformations with columns (addition and multiplication by a number) cannot be performed!
The last simplified matrix corresponds to a system of equations equivalent to the original one:
From here, using the inverse of the Gaussian method, we find from the fourth equation x 3 = –1; from the third x 4 = –2, from the second x 2 = 2 and from the first equation x 1 = 1. In matrix form, the answer is written as
We considered the case when the system is definite, i.e. when there is only one solution. Let's see what happens if the system is inconsistent or uncertain.
Example 5.2. Explore the system using the Gaussian method:
Solution. We write out and transform the extended matrix of the system
We write a simplified system of equations:
Here, in the last equation it turns out that 0=4, i.e. contradiction. Consequently, the system has no solution, i.e. she incompatible. à
Example 5.3. Explore and solve the system using the Gaussian method:
Solution. We write out and transform the extended matrix of the system:
As a result of the transformations, the last line contains only zeros. This means that the number of equations has decreased by one:
Thus, after simplifications, there are two equations left, and four unknowns, i.e. two unknown "extra". Let them be "superfluous", or, as they say, free variables, will x 3 and x 4 . Then
Believing x 3 = 2a And x 4 = b, we get x 2 = 1–a And x 1 = 2b–a; or in matrix form
A solution written in this way is called general, because, giving parameters a And b different values, all possible solutions of the system can be described. a
Gauss method perfect for solving systems of linear algebraic equations (SLAEs). It has a number of advantages compared to other methods:
- firstly, there is no need to first examine the system of equations for consistency;
- secondly, the Gauss method can 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 non-singular, 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 Gaussian method leads to results with a relatively small number of computational operations.
Brief overview of the article.
First, we give the necessary definitions and introduce notations.
Next, we will 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 is the sequential elimination of unknown variables. Therefore, the Gaussian method is also called the method of sequential elimination of unknowns. We will show detailed solutions of several examples.
In conclusion, we will consider the solution by the Gauss method of systems of linear algebraic equations, the main matrix of which is either rectangular or singular. The solution to such systems has some features, which we will examine in detail using examples.
Page navigation.
Basic definitions and notations.
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), and are free terms.
If 
, then the system of linear algebraic equations is called homogeneous, otherwise - heterogeneous.
The set of values of unknown variables for which all equations of the system become identities is called decision of the SLAU.
If there is at least one solution to a system of linear algebraic equations, then it is called joint, otherwise - non-joint.
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.
They say that the system is written in coordinate form, if it has the form
.
This system in matrix form records has the form , where 
- the main matrix of the SLAE, - the matrix of the column of unknown variables, - the matrix of free terms.
If we add a matrix-column of free terms to matrix A as the (n+1)th column, we get the so-called extended matrix systems of linear equations. Typically, an extended matrix is denoted by the letter T, and the column of free terms is separated by a vertical line from the remaining columns, that is, 
The square matrix A is called degenerate, if its determinant is zero. If , then matrix A is called non-degenerate.
The following point should be noted.
If you perform the following actions 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 sides of any equation add the corresponding parts of another equation, multiplied by an arbitrary number k,
then you get an equivalent system that has the same solutions (or, just like the original one, has no solutions).
For an extended matrix of a system of linear algebraic equations, these actions will mean carrying out elementary transformations with the rows:
- swapping two lines,
- multiplying all elements of any row of matrix T by a nonzero number k,
- adding to the elements of any row of a 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 non-singular, using 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 that.
Note that by adding the left side of the first 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 =1 into the first and third equations of the system: 
If we multiply both sides of the third equation of the system by -1 and add them to the corresponding parts of the first equation, we get rid of the unknown variable x 3 and can find x 2: 
We substitute the resulting value x 2 = 2 into the third equation and find the remaining unknown variable x 3: 
Others would have done differently.
Let us resolve 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 for x 2 and substitute the result obtained into the third equation to eliminate the unknown variable x 2 from it: 
From the third equation of the system it is clear 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 Gaussian method. When we expressed the unknown variables (first x 1, at the next stage x 2) and substituted them into the remaining equations of the system, we thereby excluded them. We carried out elimination until there was only one unknown variable left in the last equation. The process of sequentially eliminating unknowns is called direct Gaussian method. After completing the forward move, we have the opportunity to calculate the unknown variable found in the last equation. With its help, we find the next unknown variable from the penultimate equation, and so on. The process of sequentially finding unknown variables while moving from the last equation to the first is called inverse of the Gaussian 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 makes it possible to eliminate the unknown variable x 1 from the second and third equations of the system: 
Nuances with the elimination of unknown variables using the Gaussian 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 for x 1 in order to eliminate this unknown variable from the remaining 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 is always 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 resolve the first equation for x 1 and exclude it from the remaining equations of the system (although x 1 is no longer present in the second equation).
We hope you get the gist.
Let's describe Gaussian method algorithm.
Suppose we 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 different from zero.
We will assume that , since we can always achieve this by rearranging the equations of the system. Let's 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 the nth equation we add the first, multiplied by . The system of equations after such transformations will take the form 
where and 
.
We would have arrived at the same result if we had 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 proceed in a similar way, but only with 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 the nth equation we add the second, multiplied by . The system of equations after such transformations will take the form 
where and 
. Thus, the variable x 2 is excluded from all equations, starting from the third.
Next, we proceed to eliminating the unknown x 3, while we act similarly with the part of the system marked in the figure 
So we continue the direct progression of the Gaussian method until the system takes the form 
From this moment we begin the reverse of the Gaussian 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 look at the algorithm using an example.
Example.
Gauss method.
Solution.
The coefficient a 11 is different from zero, so let’s proceed to the direct progression of the Gaussian method, that is, to the exclusion of the unknown variable x 1 from all equations of the system except the first. To do this, to the left and right sides of the second, third and fourth equations, add the left and right sides of the first equation, multiplied by , respectively. 
And : 
The unknown variable x 1 has been eliminated, let's move on to eliminating x 2 . To the left and right sides of the third and fourth equations of the system we add the left and right sides of the second equation, multiplied by respectively 
And 
:
To complete the forward progression of the Gaussian method, we need to eliminate the unknown variable x 3 from the last equation of the system. Let us 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 begin the reverse of the Gaussian method.
From the last equation we have 
,
from the third equation we get,
from the second,
from the first one.
To check, you can substitute the obtained values of the unknown variables into the original system of equations. All equations turn into identities, which indicates that the solution using the Gauss method was found correctly.
Answer:
Now let’s give a solution to the same example using the Gaussian method in matrix notation.
Example.
Find the solution to the system of equations Gauss method.
Solution.
The extended matrix of the system has the form 
. At the top of each column are the unknown variables that correspond to the elements of the matrix.
The direct approach of the Gaussian method here involves reducing the extended matrix of the system to a trapezoidal form using elementary transformations. This process is similar to the elimination of unknown variables that we did with the system in coordinate form. Now you will see this.
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 lines we add the corresponding elements of the first line multiplied by , and accordingly: 
Next, we transform the resulting matrix so that in the second column all elements, starting from the third, become zero. This would correspond to eliminating the unknown variable x 2 . To do this, to the elements of the third and fourth rows we add the corresponding elements of the first row of the matrix, multiplied by respectively 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 a system of linear equations 
which was obtained earlier after a forward move.
It's time to turn back. In matrix notation, the inverse of the Gaussian method involves transforming the resulting matrix such that the matrix marked in the figure 
became diagonal, that is, took the form 
where are some numbers.
These transformations are similar to the forward transformations of the Gaussian 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 lines the corresponding elements of the last line, multiplied by 
, on and on 
respectively: 
Now add to the elements of the second and first lines the corresponding elements of the third line, multiplied by and by, respectively: 
At the last step of the reverse Gaussian method, to the elements of the first row we add the corresponding elements of the second row, multiplied by: 
The resulting matrix corresponds to the system of equations 
, from where 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 completely incorrect results. We recommend not rounding decimals. It is better to move from decimal fractions to ordinary fractions.
Example.
Solve a system of three equations using the Gauss method 
.
Solution.
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: 
Let us exclude the unknown x from the second and third equations of the system: 
In the resulting system, the unknown variable y is absent in the second equation, but y is present in the third equation, therefore, let’s swap the second and third equations: 
This completes the direct progression of the Gauss method (there is no need to exclude y from the third equation, since this unknown variable no longer exists).
Let's start the reverse move.
From the last equation we find 
,
from the penultimate 
from the first equation we have 
Answer:
X = 10, y = 5, z = -20.
Solving 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 singular, using the Gauss method.
Systems of equations, the main matrix of which is rectangular or square singular, 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 going into detail about some situations that may arise.
Let's move on to the most important stage.
So, let us assume that the system of linear algebraic equations, after completing the forward progression of the Gauss method, takes the form 
and not a single equation was reduced to (in this case we would conclude that the system is incompatible). A logical question arises: “What to do next”?
Let us write down the unknown variables that come first in all equations of the resulting system: 
In our example these are x 1, x 4 and x 5. On the left sides of the equations of the system we leave only those terms that contain the written unknown variables x 1, x 4 and x 5, the remaining terms are transferred to the right side of the equations with the opposite sign: 
Let's give the unknown variables that are on the right sides of the equations arbitrary values, where 
- arbitrary numbers: 
After this, the right-hand sides of all equations of our SLAE contain numbers and we can proceed to the reverse of the Gaussian method.
From the last equation of the system we have, from the penultimate equation we find, from the first equation we get 
The solution to a system of equations is a set of values of unknown variables 
Giving Numbers different values, we will obtain 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 a homogeneous system of linear algebraic equations 
Gauss method.
Solution.
Let us exclude the unknown variable x from the second and third equations of the system. To do this, to the left and right sides of the second equation, we add, respectively, the left and right sides of the first equation, multiplied by , and to the left and right sides of the third equation, we add the left and right sides of the first equation, multiplied by: 
Now let’s exclude y from the third equation of the resulting system of equations: 
The resulting SLAE is equivalent to the system 
.
We leave on the left side of the system equations only the terms containing the unknown variables x and y, and move the terms with the unknown variable z to the right side: 