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) is known in various options 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's consider first simplest option 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 elimination step using formulas (5.29), (5.31) require division, multiplication and subtraction, i.e. total number arithmetic operations is Similarly, a step requires operations, and a step requires operations.
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 last date up 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 B 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, and some slowly growing function depending on the order of the system (such as power function with a small indicator), growth rate.
The presence of a multiplier in estimate (5.43) indicates that when large diagram partial selection may be ill-conditioned and there may be a significant loss of accuracy. 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. For this, in addition to arithmetic operations It is required 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 modern programs. effective methods tracking the growth of matrix elements.
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 more than the amount modules of all other elements of the line.
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 way scaling the system The first consists of multiplying each of the equations by some scaling factor. The second consists of multiplying each column of the matrix by the scaling factor, which corresponds to the replacement of variables (in fact, this is a replacement of 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.
So, Gauss's method is applicable to any system linear equations, it is ideal for solving systems containing more than three linear equations. Due to the simplicity and uniformity of the operations performed, the Gauss method for solving SLAEs with numerical coefficients is suitable for calculation on electronic computers.
Advantages of the method:
a) less labor-intensive compared to other methods;
b) allows you to unambiguously determine whether the system is compatible or not, and if it is compatible, find its solution;
c) allows you to find maximum number linearly independent equations - rank of the system matrix.
A significant disadvantage of this method is the inability to formulate conditions for consistency and definiteness of the system depending on the values of the coefficients and free terms. On the other hand, even in the case of a specific system, this method does not allow one to find general formulas expressing the solution of the system through its coefficients and free terms, which are necessary for theoretical studies.
In addition to the analytical solution of SLAE, the Gaussian method is also used for:
a) finding the matrix inverse to the given one (a unit matrix of the same size as the original one is assigned to the matrix on the right: , after which it is reduced to the form identity matrix Gauss-Jordan method; as a result, in place of the original identity matrix, the inverse of the original matrix appears on the right :);
b) determining the rank of the matrix (according to the corollary of the Kronecker-Capelli theorem, the rank of the matrix is equal to the number of its main variables);
c) numerical solution of SLAE in computer technology(due to the calculation error, the Gaussian Method is used with the selection of the main element, the essence of which is to select as the main variable at each step the one in which among the remaining rows and columns after deleting is the coefficient with the maximum absolute value).
There are other methods for solving and studying systems of linear equations that do not have the noted disadvantages. These methods are based on the theory of matrices and determinants.
Combinatorics.
In how many ways can three boys - Almas, Bolat, Sabyr - stand in the same row? - It’s not difficult, let’s write all possible cases (combinations): ABS, ASB, BAS, BSA, SAB, SBA. There are six combinations in total.
Let's say another boy Dauren joined them. What will be the arrangement methods in this case? In six possible cases, Dauren can be first, second, third and last:
DABS, DASB, DBAS, DBSA, DSAB, DSBA;
ADBS, ADSB, BDAS, BDSA, SDAB, SDBA;
ABDS, ASDB, BADS, BSDA, SADB, SBDA;
ABSD, ASBD, BASD, BSAD, SABD, SBAD.
Total 24 different ways. What if we increase the number of children? It is difficult to write and display the total number each time. We need to define the number of ways, not the types of ways. Are there other methods for determining this number? - Eat. And in probability theory we are more interested in the number of ways of arrangement than in the types of arrangement. A branch of mathematics called combinatorics makes it possible to immediately determine the number of such ways. Let's get acquainted with the basic concepts of combinatorics necessary for solving problems in probability theory. These are permutations, placements and combinations. Let's look at each one separately.
1. Rearrangement. Consider the number of cases in the previous problem. We rearranged the letters A, B, C and counted the number of possible combinations, it was 6. And when the number of boys increased by one, rearranged the letters A, B, C, D, we found the number of possible combinations, it was 24.
DEFINITION. Permutation of n various elements are called combinations that consist of n elements and differ from each other only in the order of their arrangement.
The number of permutations of n different elements is denoted by P n and is calculated using the formula:
here n! (read "en factorial") means the product of all natural numbers from 1 to n:
It is clear that one factorial equal to one, 1! = 1, at the same time, in mathematics it is generally accepted that zero factorial is equal to one. And so 0! = 1.
Let's go back to the example. Here n=3. Therefore, you can find the required number of permutations using formula (1): P 3 =3!=1 2 3=6. Similarly, the number of permutations of four letters is: P 4 =4!=1 2 3 4=24
Example 7. Let's find the value of the expression with factorials 8!/6! 2!
First we transform 8!=1 2 3 4 5 6 7 8=6! 7 8
Let's substitute this transformation into an expression and simplify it. 8!/6! 2=6! 7 8/6! 2=7 8/2=28
2. Placements. Let's look at an example. How many two-digit numbers (digits are not repeated) can be written using the numbers 7, 8, 9. This can be done in two stages: the first stage is determining the number of selection of tens places of the number, it is equal to 3 (any of these 3 digits can occupy the tens place) ; the second stage is determining the number of selection of units digits of the number, it is equal to 2 (any digit from the remaining two can occupy the units digit). According to the multiplication rule, from three numbers you can make a total of 3 2 = 6 different two-digit numbers. Indeed, you can verify this by directly writing down these numbers 78, 79, 87, 89, 97, 98. When solving the problem, we arranged two elements out of three, and these combinations differ either in composition (78, 98) or in the order of their arrangement ( 78, 87).
DEFINITION. Arrangement of n elements by m elements (m n) are combinations consisting of m elements taken from given n different elements, differing from each other either in the elements themselves or in the order of their arrangement.
The number of placements of n elements by m elements is denoted and read as follows: “A from en to em.” To find use the formula:
(15)
Let's look at another example. In the 5th grade they study 10 subjects. In how many ways can a schedule be made if there are 4 different lessons that day?
To find the number of ways to arrange 10 items of four items each, we use formula (15) for finding the number of arrangements of 10 items of 4 items each:
So, 10 items of 4 items can be arranged 5040 different ways.
3. Combinations. Example. You need to compose the products of two different numbers from the given three numbers 7, 8, 9.
Taking into account the commutative property of multiplication, we have: 7 8=56, 7 9=63, 8 9=72. When solving the problem, we selected two elements out of three, and these combinations differ only in composition (78, 98), and their locations do not affect the product.
DEFINITION. A combination of n elements of m elements (m n) are combinations consisting of m elements taken from given n different elements, differing from each other only in composition.
The number of combinations of n elements by m elements is denoted and read as follows: “tse from en to em.” To find use the formula:
(16)
In our example, n=3 and m=2. Then 
Let's look at another example. There are 25 students in the class, 12 of them are boys. a) It is necessary to form a duty of two people, and the pairs should consist of either boys or girls. b) How many groups can be created for duty, consisting of two boys and one girl?
Solution. a) When solving this problem, we will use the addition rule and the combination formula. First, let's count how many pairs can be created from boys (m 1) and girls (m 2), then find their sum (m=m 1 +m 2).
To determine how many pairs can be created from 12 boys, we will use the formula for counting the number of combinations of 12 elements of 2 elements
You can create 78 different pairs of girls. Then, two boys and two girls, a total of m=66+78=144 different pairs can be created.
b) When solving this problem, we will use the multiplication rule and the combination formula. There are two boys and one girl in the group. First, let's count how many ways we can select two boys from 12 boys (m 1) and one girl from 13 girls (m 2), then multiply the results obtained (m=m 1 m 2).
Out of 12 boys, 2 boys can be selected in 66 different ways. And out of 13 girls, 1 girl can be selected as follows:
Then a group of two boys and one girl can be created m=66 13=856 in various ways.
Definition of a matrix. Determinants of the second and third orders, their basic properties. Minors and algebraic additions, expansion of the determinant in a row (column). Methods for calculating determinants. The concept of the nth order determinant.
Definition 1.1. Matrix called a rectangular table of numbers.
Designations: A – matrix, - matrix element, number of the row in which this element is located, number of the corresponding column; m is the number of rows of the matrix, n is the number of its columns.
Definition 1.2. The numbers m and n are called dimensions matrices.
Definition 1.3. The matrix is called square, if m = n. The number n in this case is called in order square matrix.
Each square matrix can be associated with a number that is uniquely determined using all the elements of the matrix. This number is called the determinant.
Definition 1.4 . Second order determinant is a number obtained using the elements of a 2nd order square matrix as follows:
.
Moreover, from the product of elements located on the so-called main diagonal of the matrix (going from the upper left to the right bottom corner) the product of the elements located on the second, or secondary, diagonal is subtracted.
1. 
2.
Definition 1.5. Third order determinant is a number determined using the elements of a 3rd order square matrix as follows:
A`, called transposed relative to the matrix A, whose elements are connected to the elements A ratio a` ij = a ji .
Let it be necessary to solve a linear system of equations of the form:
or in another form
In a linear algebra course, solutions to the system of equations (5.2) are represented according to Cramer’s rule in the form of ratios of the corresponding determinants. If you use the most optimal method of calculating the determinant, then according to Cramer’s rule, approximately -|n is required! arithmetic operations. However, there is a more optimal way to solve the system of equations (5.2) - the Gaussian elimination method, which requires -|n 3 arithmetic operations.
Let us begin our study of the system of equations (5.2) with the special case when the matrix of the system is upper triangular, that is, all its elements below the main diagonal are equal to zero. By executing the spy(triu(randn(25))) operation in the MATLAB command window, we will generate the upper triangular matrix and its graphical image. In Fig. Figure 5.1 shows a corresponding example of an upper triangular matrix.
From the last equation of the system with the upper triangular matrix we find Xl, substituting it into the penultimate equation, we find X„_i, etc. - we find the entire solution. General formula to determine Xj-ro has the form:
The Gaussian method is expressed in the procedure of reducing the matrix of a system of equations to triangular form (for example, to the upper triangular form in Fig. 5.1). This can be done as follows. Let us subtract the first equation from the second equation, multiplied by such a number that the coefficient of X] becomes zero; similarly, we subtract the first equation from the second, third, etc. up to the Pth. The result should be new system equations in which the first column has zeros everywhere except the diagonal element A c. Then, using the second equation, we use the same procedure to reset the elements of the second column that lie below the main diagonal. Continuing this procedure for the third and all subsequent equations, we transform the system matrix to upper triangular form.
Rice. 5.1.
Let the elements be excluded from k- 1 column. The remaining equations with non-zero columns can be written as:
Multiply k-k) line by number With tk =/oIf 1, t > k, and subtract from wth
lines. The first non-zero element of this line becomes zero, and the other elements can be recalculated using the formulas:
Carrying out algorithm (5.4), (5.5) of zeroing each column of the matrix below the main diagonal ends (P- 1)th column, and the whole procedure is called straight forward exceptions.
Putting (5.4), (5.5) together, we have
or in expanded form 
System of equations (5.6) is easily solved in reverse according to formulas (5.3).
A possible violation in the operation of algorithm (5.4), (5.5) may be due to the fact that on the main diagonal there is a zero element a kk " = 0. In this case, it is necessary among the rows of the matrix below To-th find one that has To- m place there is a non-zero element. Such a line must be found; if it is not found, it means that in To- m column, starting from the kth number, all elements are zero, and therefore the determinant of the matrix A equal to zero. By rearranging rows, you can move the appropriate row to the desired position.
If it turns out that the element on the main diagonal is small, then the coefficients S t k become large numbers, and when recalculating matrix elements according to (5.5), there may be a significant loss of accuracy due to rounding errors when subtracting large numbers. To prevent this from happening, among the column elements a^k, t>k, find main or maximum and rearranging the lines transfers it to the main diagonal. This method is called Gaussian method with the choice of the main element. WITH by choosing the main element, rounding errors in the Gaussian method are usually small.
The Gauss method with the choice of the main element is the simplest, most reliable and profitable and for this reason is most in demand when solving linear systems of equations with a densely filled order matrix P
Let's consider the solution procedure linear system equations in MATLAB. Let us show experimentally that on average the number of operations performed by the central processor when solving a linear system of equations is proportional to the cube of the order of the matrix. Let us show that asymptotically the relation time(n)/n 3 tends to some pre-power constant at P -> oh where time(n)- operating time of the central processor for a given matrix order P.
Listing 5.1 shows the code for the corresponding program.
Listing 5.1
“/“Program for studying the time spent”/“of the central processor when solving %systems of linear equations%clear the workspace clear all
“/“we determine the maximum order of “/“invertible matrices
ptah =1 0 0 0; k =0;
“/“we organize a cycle of solving systems of “/“equations of the form A X = b for n = 1: 10: pmax k = k +1; order) к) =п;
“/we form a random matrix A %i right side b A=r andn(n); b=randn(n, 1) ;
“/“remember the initial moment of time”/operation of the central processor 10 =с рut i me;
“/we solve the linear system of equations %A X = b using the formula: X = A b A b;
“/we find the next moment in time,
“/subtract the previous one from it and “/divide by a cube of the order of the matrix
t (k) = (with put i me-10) / n l3; end
“/“construct a graph of the dependence of the pre-power constant”/on the order of matrix A semilogy(order,t);
Rice. 5.2.
In Fig. Figure 5.2 shows a graph of the dependence of the pre-power constant of the ratio of the operating time of the central processor to the cube of the matrix order on the matrix order. It is clear that when P-> oo really attitude time(n)/n 3 tends to some constant, which confirms the cubic dependence of the number of operations in the Gauss method on the order of the matrix.
The determinant and inverse matrix can also be found by Gaussian elimination. During the process of elimination, subtracting rows does not change the determinant, but the hundredth decimal place may change when the rows are rearranged. After reducing the matrix to triangular form, we can find the determinant of the matrix in the form of the product of its diagonal elements:
where the choice of "+" or depends on whether the total permutation of rows was even or odd.
Let us study the procedure for finding the determinant of matrix (5.7) using the example of the standard MATLAB function det(A), where A is an arbitrary PHP matrix. Let us study the dependence of the determinant value of a matrix with random elements distributed over normal law with mean 0 and standard deviation 1, depending on the order of the matrix.
Listing 5.2 shows the code for the corresponding program.
Listing 52
%Program for studying the procedure for searching for the determinant of a %matrix whose elements random variables,
“/“distributed according to the normal law with a mean of 0% and a standard deviation of 1%, clear the workspace clear all
“/“we determine the maximum order% of the analyzed matrices
ptah =3 0 0;
%organize a cycle of searching for the determinant of %matrix A - det(A) for n=l: 5: nmax k =k +1; order) k) =n;
%form a random matrix A A=r a n d n (n) ;
%calculate the determinant of matrix A
%we switch to a logarithmic scale% when fixing the values of the determinant d(k) =si gn(d(k)) *1 оg 10(d(k)); end
%build a graph of the dependence of the values of the %determinant of the matrix on the order of the matrix
plot(order, d);
In Fig. Figure 5.3 shows a graph of the dependence of the logarithm of the determinant of a random matrix on the order of the matrix. It can be seen that the determinant of a random matrix grows exponentially with increasing order of the matrix.
Rice. 5.3.
To calculate inverse matrix let's denote its elements by a 1t, 1,t = 1, and we will proceed from the relation AA 1 = E, then the following entry is correct:
According to (5.8), the /th column of the inverse matrix can be considered as an unknown vector of a linear system of equations with a matrix A with a special right side. Thus, matrix inversion is reduced to solving a linear system of equations P times with the same matrix, but with different right-hand sides. Reducing the system to triangular form is carried out only 1 time, therefore the number of arithmetic operations when inverting a matrix is only three times greater than when solving a system of linear equations, i.e., of the order of * 2P 3.
Consider now the inv(A) function in MATLAB, which returns the inverse of A matrix. Listing 5.3 shows the code for the corresponding program.
Listing 53
%A program for studying the procedure for searching for an inverse matrix, the elements of which are random variables distributed according to a normal law with a mean of 0 and a standard deviation of 1
Cleaning up the workspace
%determine the maximum order of %the analyzed matrices
pshah=1 0 00; k =0;
Let's reorganize the cycle of searching for the inverse Romatrix to A - i ПV(А) for n=1: 5: ptah k =k +1; o g d e g (k) = n;
Let's reform the random matrix A
We calculate the matrix Ai nv=i nv(A) inverse to A;
We find the inversion error E =еуе(n);
e g (k) = p o g w (A* Ai nv- E); end
Let's plot the dependence of the error values
% of matrix inversions from matrix order
semilogy(order.er);
In Fig. Figure 5.4 shows the dependence of the matrix inversion error on its order. It can be seen that as the order of the matrix increases from 1 to 800, the inversion error, expressed in a certain norm, increases by five orders of magnitude.
2. Modifications of the Gauss method
Gaussian method with selection of the main element. The main limitation of the Gauss method is the assumption that all elements into which division is performed at each forward step are not equal to zero. These elements are called principal elements and are located on the main diagonal of the matrix A.
If at some step of the forward motion the main element = 0, then further solution of the system is impossible. If the main element has a small value, close to zero, then a strong increase in error is possible due to a sharp increase in the absolute value of the coefficients obtained as a result of division. In such situations, the Gaussian method becomes unstable.
The Gauss method with the choice of the main element allows us to exclude the occurrence of such cases.
The idea of this method is as follows. At some point kth step forward stroke, it is not the next numbered variable x k that is excluded from the equations, but the variable whose coefficient is the largest absolute value. This ensures that there is no division by zero and that the method remains stable.
If at the kth step ¹ is chosen as the main element, then in the matrix A¢ the rows with numbers k and p and the columns with numbers k and q must be swapped.
Rearranging the rows does not affect the solution, since it corresponds to reversing the equations in the system, but rearranging the columns means changing the numbering of the variables. Therefore, information about all rearranged columns must be preserved so that after the reverse move is completed, the original numbering of the variables can be restored.
There are two simpler modifications of the Gauss method:
With selection of the main element by column;
With selection of the main element by line.
In the first case, the largest element in absolute value is selected as the main element kth line(among elements , i = ). In the second - the largest element in absolute value of the kth column (among the elements , i = ). The first approach is most widespread, since the numbering of variables does not change here.
It should be noted that these modifications apply only to the forward motion of the Gaussian method. The reverse move is performed without changes, but after obtaining a solution, it may be necessary to restore the original numbering of the variables.
LU decomposition. In modern computer software, the Gaussian method is implemented using LU decomposition, which is understood as representing the coefficient matrix A as the product A = LU of two matrices L and U, where L is the lower triangular matrix, U is the upper triangular matrix
If the LU expansion is obtained, then the solution of the original system of equations (2) is reduced to the sequential solution of the following two systems of equations with triangular coefficient matrices
linear algebraic equation numerical
where Y = is a vector of auxiliary variables.
This approach allows you to repeatedly solve systems of linear equations with different right-hand sides B. In this case, the most labor-intensive part (LU decomposition of the matrix A) is performed only once. This procedure corresponds to the forward run of the Gaussian method and has a complexity estimate of O(n 3). Further solution of systems of equations (6) and (7) can be performed many times (for different B), and the solution of each of them corresponds to the inverse of the Gaussian method and has the estimate computational complexity O(n 2).
To obtain the LU decomposition, you can use the following algorithm.
1. For the original system (1), perform the forward progression of the Gaussian method and obtain a system of triangular equations (5).
2. Determine the elements of the matrix U according to the rule
u ij = C ij (i = ; j = )
3. Calculate the elements of matrix L according to the rules
Calculation formulas for solving system (6) have next view:
y 1 = b 1 / l 11 ;
Calculation formulas for solving system (7)
(i = n - 1, n - 2, …, 1).
At the same time, actually finding the inverse matrix is a rather labor-intensive process and its programming can hardly be called an elementary task. Therefore, in practice, numerical methods for solving systems of linear equations are more often used. Numerical methods for solving systems of linear equations include the following: Gauss method, Cramer method, iterative methods. In the Gauss method, for example, they work on...
35437 x4=0.58554 5 x1=1.3179137 x2=-1.59467 x3=0.35371 x4=0.58462 6 x1=1.3181515 x2=-1.59506 x3=0.35455 x4=0.58557 5. Comparative analysis various methods numerical differentiation and integration 5.1 Methods of numerical differentiation 5.1.1 Description of the method Let us assume that in the neighborhood of the point xi the function F (x) is differentiable a sufficient number of times. ...
In Turbo Pascal 7.0 for solving systems of linear algebraic equations using the simple iteration method. 1.2 Mathematical formulation of the problem Let A be a non-singular matrix and we need to solve a system where the diagonal elements of matrix A are non-zero. 1.3 Review of existing numerical methods for solving the problem Gaussian method In the Gaussian method, the SLAE matrix using equivalent...
Numbers). Next, using formulas (2), xn-1, xn-2,..., x1 are successively found for i=n-1, n-2,...,1, respectively. Thus, the solution of equations of the form (1) is described by a method called the sweep method, which is reduced to calculations using three simple formulas: finding the so-called sweep coefficients δi, λi using formulas (3) for i=1,2,...,n (direct sweep) and then unknown xi by...
We continue to consider systems of linear equations. This lesson is the third on the topic. If you have a vague idea of what a system of linear equations is in general, if you feel like a teapot, then I recommend starting with the basics on the page Next, it’s useful to study the lesson.
The Gaussian method is easy! Why? The famous German mathematician Johann Carl Friedrich Gauss, during his lifetime, received recognition as the greatest mathematician of all time, a genius, and even the nickname “King of Mathematics.” And everything ingenious, as you know, is simple! By the way, not only suckers get money, but also geniuses - Gauss’s portrait was on the 10 Deutschmark banknote (before the introduction of the euro), and Gauss still smiles mysteriously at Germans from ordinary postage stamps.
The Gauss method is simple in that the KNOWLEDGE OF A FIFTH-GRADE STUDENT IS ENOUGH to master it. You must know how to add and multiply! It is no coincidence that teachers often consider the method of sequential exclusion of unknowns in school mathematics electives. It’s a paradox, but students find the Gaussian method the most difficult. Nothing surprising - it’s all about the methodology, and I will try to talk about the algorithm of the method in an accessible form.
First, let's systematize a little knowledge about systems of linear equations. A system of linear equations can:
1) Have a unique solution. 2) Have infinitely many solutions. 3) Have no solutions (be non-joint).
The Gauss method is the most powerful and universal tool for finding a solution any systems of linear equations. As we remember, Cramer's rule and matrix method are unsuitable in cases where the system has infinitely many solutions or is inconsistent. And the method of sequential elimination of unknowns Anyway will lead us to the answer! In this lesson, we will again consider the Gauss method for case No. 1 (the only solution to the system), an article is devoted to the situations of points No. 2-3. I note that the algorithm of the method itself works the same in all three cases.
Let's go back to the simplest system from class How to solve a system of linear equations? and solve it using the Gaussian method.
The first step is to write down extended system matrix: . I think everyone can see by what principle the coefficients are written. The vertical line inside the matrix does not have any mathematical meaning - it is simply a strikethrough for ease of design.
Reference : I recommend you remember terms linear algebra. System Matrix is a matrix composed only of coefficients for unknowns, in this example the matrix of the system: . Extended System Matrix – this is the same matrix of the system plus a column of free terms, in this case: . For brevity, any of the matrices can be simply called a matrix.
After the extended system matrix is written, it is necessary to perform some actions with it, which are also called elementary transformations.
The following elementary transformations exist:
1) Strings matrices Can rearrange in some places. For example, in the matrix under consideration, you can painlessly rearrange the first and second rows: 
2) If the matrix has (or has appeared) proportional (like special case– identical) lines, then it follows delete from the matrix all these rows except one. Consider, for example, the matrix 
. In this matrix, the last three rows are proportional, so it is enough to leave only one of them: 
.
3) If a zero row appears in the matrix during transformations, then it should also be delete. I won’t draw, of course, the zero line is the line in which all zeros.
4) The matrix row can be multiply (divide) to any number non-zero. Consider, for example, the matrix . Here it is advisable to divide the first line by –3, and multiply the second line by 2: 
.
This action very useful because it simplifies further matrix transformations.
5) This transformation causes the most difficulties, but in fact there is nothing complicated either. To a row of a matrix you can add another string multiplied by a number, different from zero. Consider our matrix of practical example: . First I'll describe the transformation in great detail. Multiply the first line by –2: 
, And to the second line we add the first line multiplied by –2: 
. Now the first line can be divided “back” by –2: . As you can see, the line that is ADDED LI – hasn't changed. Always the line TO WHICH IS ADDED changes UT.
In practice, of course, they don’t write it in such detail, but write it briefly: 
Once again: to the second line added the first line multiplied by –2. A line is usually multiplied orally or on a draft, with the mental calculation process going something like this:
“I rewrite the matrix and rewrite the first line: 
»
“First column. At the bottom I need to get zero. Therefore, I multiply the one at the top by –2: , and add the first one to the second line: 2 + (–2) = 0. I write the result in the second line: 
»
“Now the second column. At the top, I multiply -1 by -2: . I add the first to the second line: 1 + 2 = 3. I write the result in the second line: 
»
“And the third column. At the top I multiply -5 by -2: . I add the first to the second line: –7 + 10 = 3. I write the result in the second line: 
»
Please carefully understand this example and understand the sequential calculation algorithm, if you understand this, then the Gaussian method is practically in your pocket. But, of course, we will still work on this transformation.
Elementary transformations do not change the solution of the system of equations
! ATTENTION: considered manipulations can not use, if you are offered a task where the matrices are given “by themselves.” For example, with “classical” operations with matrices Under no circumstances should you rearrange anything inside the matrices! Let's return to our system. It is practically taken to pieces.
Let us write down the extended matrix of the system and, using elementary transformations, reduce it to stepped view:
(1) The first line was added to the second line, multiplied by –2. And again: why do we multiply the first line by –2? In order to get zero at the bottom, which means getting rid of one variable in the second line.
(2) Divide the second line by 3.
The purpose of elementary transformations
–
reduce the matrix to stepwise form: 
. In the design of the task, they just mark out the “stairs” with a simple pencil, and also circle the numbers that are located on the “steps”. The term “stepped view” itself is not entirely theoretical, in scientific and educational literature it is often called trapezoidal view or triangular view.
As a result of elementary transformations, we obtained equivalent original system of equations:
Now the system needs to be “unwinded” in the opposite direction - from bottom to top, this process is called inverse of the Gaussian method.
In the lower equation we already have a ready-made result: .
Let's consider the first equation of the system and substitute the already known value of “y” into it:
Let's consider the most common situation, when the Gaussian method requires solving a system of three linear equations with three unknowns.
Example 1
Solve the system of equations using the Gauss method: 
Let's write the extended matrix of the system: 
Now I will immediately draw the result that we will come to during the solution: 
And I repeat, our goal is to bring the matrix to a stepwise form using elementary transformations. Where to start?
First, look at the top left number: 
Should almost always be here unit. Generally speaking, –1 (and sometimes other numbers) will do, but somehow it has traditionally happened that one is usually placed there. How to organize a unit? We look at the first column - we have a finished unit! Transformation one: swap the first and third lines: 
Now the first line will remain unchanged until the end of the solution. Now fine.
The unit in the top left corner is organized. Now you need to get zeros in these places: 
We get zeros using a “difficult” transformation. First we deal with the second line (2, –1, 3, 13). What needs to be done to get zero in the first position? Need to to the second line add the first line multiplied by –2. Mentally or on a draft, multiply the first line by –2: (–2, –4, 2, –18). And we consistently carry out (again mentally or on a draft) addition, to the second line we add the first line, already multiplied by –2:
We write the result in the second line: 
We deal with the third line in the same way (3, 2, –5, –1). To get a zero in the first position, you need to the third line add the first line multiplied by –3. Mentally or on a draft, multiply the first line by –3: (–3, –6, 3, –27). AND to the third line we add the first line multiplied by –3:
We write the result in the third line:
In practice, these actions are usually performed orally and written down in one step: 
No need to count everything at once and at the same time. The order of calculations and “writing in” the results consistent and usually it’s like this: first we rewrite the first line, and slowly puff on ourselves - CONSISTENTLY and ATTENTIVELY:
And I have already discussed the mental process of the calculations themselves above.
In this example, this is easy to do; we divide the second line by –5 (since all numbers there are divisible by 5 without a remainder). At the same time, we divide the third line by –2, because the smaller the numbers, the simpler the solution:
At the final stage of elementary transformations, you need to get another zero here: 
For this to the third line we add the second line multiplied by –2:
Try to figure out this action yourself - mentally multiply the second line by –2 and perform the addition.
The last action performed is the hairstyle of the result, divide the third line by 3.
As a result of elementary transformations, an equivalent system of linear equations was obtained: 
Cool.
Now the reverse of the Gaussian method comes into play. The equations “unwind” from bottom to top.
In the third equation we already have a ready result:
Let's look at the second equation: . The meaning of "zet" is already known, thus:
And finally, the first equation: . “Igrek” and “zet” are known, it’s just a matter of little things:
Answer: 
As has already been noted several times, for any system of equations it is possible and necessary to check the solution found, fortunately, this is easy and quick.
Example 2
This is an example for an independent solution, a sample of the final design and an answer at the end of the lesson.
It should be noted that your progress of the decision may not coincide with my decision process, and this is a feature of the Gauss method. But the answers must be the same!
Example 3
Solve a system of linear equations using the Gauss method 
We look at the upper left “step”. We should have one there. The problem is that there are no units in the first column at all, so rearranging the rows will not solve anything. In such cases, the unit must be organized using an elementary transformation. This can usually be done in several ways. I did this: (1) To the first line we add the second line, multiplied by –1. That is, we mentally multiplied the second line by –1 and added the first and second lines, while the second line did not change.
Now at the top left there is “minus one”, which suits us quite well. Anyone who wants to get +1 can perform an additional movement: multiply the first line by –1 (change its sign).
(2) The first line multiplied by 5 was added to the second line. The first line multiplied by 3 was added to the third line.
(3) The first line was multiplied by –1, in principle, this is for beauty. The sign of the third line was also changed and it was moved to second place, so that on the second “step” we had the required unit.
(4) The second line was added to the third line, multiplied by 2.
(5) The third line was divided by 3.
A bad sign that indicates an error in calculations (more rarely, a typo) is a “bad” bottom line. That is, if we got something like , below, and, accordingly, 
, then with a high degree of probability we can say that an error was made during elementary transformations.
We charge the reverse, in the design of examples they often do not rewrite the system itself, but the equations are “taken directly from the given matrix.” The reverse stroke, I remind you, works from bottom to top. Yes, here is a gift:
Answer: 
.
Example 4
Solve a system of linear equations using the Gauss method 
This is an example for you to solve on your own, it is somewhat more complicated. It's okay if someone gets confused. Full solution and sample design at the end of the lesson. Your solution may be different from my solution.
In the last part we will look at some features of the Gaussian algorithm. The first feature is that sometimes some variables are missing from the system equations, for example: 
How to correctly write the extended system matrix? I already talked about this point in class. Cramer's rule. Matrix method. In the extended matrix of the system, we put zeros in place of missing variables: 
By the way, that's pretty easy example, since there is already one zero in the first column, and there are fewer elementary conversions to perform.
The second feature is this. In all the examples considered, we placed either –1 or +1 on the “steps”. Could there be other numbers there? In some cases they can. Consider the system: 
.
Here on the upper left “step” we have a two. But we notice the fact that all the numbers in the first column are divisible by 2 without a remainder - and the other is two and six. And the two at the top left will suit us! In the first step, you need to perform the following transformations: add the first line multiplied by –1 to the second line; to the third line add the first line multiplied by –3. So we get necessary zeros in the first column.
Or another conventional example: 
. Here the three on the second “step” also suits us, since 12 (the place where we need to get zero) is divisible by 3 without a remainder. It is necessary to carry out the following transformation: add the second line to the third line, multiplied by –4, as a result of which the zero we need will be obtained.
Gauss's method is universal, but there is one peculiarity. You can confidently learn to solve systems using other methods (Cramer’s method, matrix method) literally the first time - they have a very strict algorithm. But in order to feel confident in the Gaussian method, you should “get your teeth into” and solve at least 5-10 ten systems. Therefore, at first there may be confusion and errors in calculations, and there is nothing unusual or tragic about this.
Rainy autumn weather outside the window.... Therefore, for everyone who wants more complex example for independent solution:
Example 5
Solve a system of 4 linear equations with four unknowns using the Gauss method. 
Such a task is not so rare in practice. I think even a teapot who has thoroughly studied this page will understand the algorithm for solving such a system intuitively. Fundamentally, everything is the same - there are just more actions.
Cases when the system has no solutions (inconsistent) or has infinitely many solutions are discussed in the lesson Incompatible systems and systems with a common solution. There you can fix the considered algorithm of the Gaussian method.
I wish you success!
Solutions and answers:
Example 2:
Solution
:
Let us write down the extended matrix of the system and, using elementary transformations, bring it to a stepwise form.
Elementary transformations performed:
(1) The first line was added to the second line, multiplied by –2. The first line was added to the third line, multiplied by –1.
Attention!
Here you may be tempted to subtract the first from the third line; I highly recommend not subtracting it - the risk of error greatly increases. Just fold it!
(2) The sign of the second line was changed (multiplied by –1). The second and third lines have been swapped.
note
, that on the “steps” we are satisfied not only with one, but also with –1, which is even more convenient.
(3) The second line was added to the third line, multiplied by 5.
(4) The sign of the second line was changed (multiplied by –1). The third line was divided by 14.
Reverse:
Answer
:
.
Example 4:
Solution
:
Let us write down the extended matrix of the system and, using elementary transformations, bring it to a stepwise form:
Conversions performed: (1) A second line was added to the first line. Thus, the desired unit is organized on the upper left “step”. (2) The first line multiplied by 7 was added to the second line. The first line multiplied by 6 was added to the third line.
With the second “step” everything gets worse , the “candidates” for it are the numbers 17 and 23, and we need either one or –1. Transformations (3) and (4) will be aimed at obtaining the desired unit (3) The second line was added to the third line, multiplied by –1. (4) The third line was added to the second line, multiplied by –3. The required item on the second step has been received. . (5) The second line was added to the third line, multiplied by 6. (6) The second line was multiplied by –1, the third line was divided by -83.
Reverse:
Answer :
Example 5:
Solution
:
Let us write down the matrix of the system and, using elementary transformations, bring it to a stepwise form:
Conversions performed: (1) The first and second lines have been swapped. (2) The first line was added to the second line, multiplied by –2. The first line was added to the third line, multiplied by –2. The first line was added to the fourth line, multiplied by –3. (3) The second line was added to the third line, multiplied by 4. The second line was added to the fourth line, multiplied by –1. (4) The sign of the second line was changed. The fourth line was divided by 3 and placed in place of the third line. (5) The third line was added to the fourth line, multiplied by –5.
Reverse:
Answer :