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.
(SLAE), consisting of equations with unknowns:
It is assumed that there is a unique solution to the system, that is.
This article will discuss the reasons for the error that arises when solving a system using the Gauss method, ways to identify and eliminate (reduce) this error.
Description of the method
Process of solving a system of linear equations
according to the Gauss method consists of 2 stages:
1. We assume that . Then we divide the first equation of the system by the coefficient, and as a result we obtain the equation. Then, from each of the remaining equations, the first one is subtracted, multiplied by the corresponding coefficient. As a result, the system is transformed to the form: 2. Assuming that , we divide the second equation by the coefficient and exclude the unknown from all subsequent equations, etc. 3. We obtain a system of equations with a triangular matrix:- Reverse stroke Direct determination of unknowns
Analysis of the method
This method belongs to the class of direct methods for solving a system of equations, which means that in a finite number of steps you can obtain an exact solution, provided that the input data (matrix and the right side of the equation - ) are specified exactly and the calculation is carried out without rounding. To obtain a solution, multiplications and divisions are required, that is, the order of operations.
The conditions under which the method produces an exact solution are not feasible in practice - both input data errors and rounding errors are inevitable. Then the question arises: how accurate a solution can be obtained using the Gauss method, how correct is the method? Let us determine the stability of the solution with respect to the input parameters. Along with the original system, consider the perturbed system:
Let some norm be introduced. - is called the condition number of the matrix.
There are 3 possible cases:
The condition number of a matrix is always . If it is large (), then the matrix is said to be ill-conditioned. In this case, small disturbances on the right sides of the system, caused either by inaccuracy in specifying the initial data, or caused by calculation errors, significantly affect the solution of the system. Roughly speaking, if the error of the right-hand sides is , then the error of the solution will be .
Let us illustrate the results obtained with the following numerical example: Given a system
She has a solution.
Now consider the perturbed system:
The solution to such a system will be a vector.
With a very small perturbation of the right side, we obtained a disproportionately large perturbation of the solution. This “unreliability” of the solution can be explained by the fact that the matrix is almost singular: the straight lines corresponding to the two equations almost coincide, as can be seen in the graph:
This result could have been predicted due to the poor conditionality of the matrix:
The calculation is quite complex, comparable to the solution of the entire system, therefore, cruder but simpler to implement methods are used to estimate the error.
Methods for assessing errors
1) Check sum: usually used to prevent random errors in the calculation process without the help of computers.We compose a control column consisting of control elements of the system:
When transforming equations, the same operations are performed on the control elements as on the free terms of the equations. As a result, the control element of each new equation must be equal to the sum of the coefficients of this equation. A large discrepancy between them indicates errors in the calculations or the instability of the calculation algorithm with respect to the computational error.
2) Relative error of a known solution allows you to obtain a judgment about the error of the decision without significant additional costs.
A certain vector is specified with components that have, if possible, the same order and sign as the components of the desired solution. The vector is calculated, and the system is solved along with the original system of equations.
Let and be the actually obtained solutions of these systems. A judgment about the error of the desired solution can be obtained based on the hypothesis: the relative errors when solving systems with the same matrix and different right-hand sides, which are respectively the quantities and by the elimination method, do not differ by a very large number of times.
3) Changing scales - a technique used to obtain an idea of the real magnitude of the error arising due to rounding in calculations.
Along with the original system, the system is solved using the same method
, where and are numbersIf there were no rounding error, then equality would hold for the solutions of the original and scaled systems: . Therefore, for and , which are not powers of two, comparison of vectors gives an idea of the magnitude of the computational error
Improving the Gaussian Elimination Method
The modifications of the Gauss method discussed below can reduce the error of the result.
Selecting the main element
The main increase in error in the method occurs during the forward move, when the leading -th row is multiplied by the coefficients. If the coefficients are 1%20" alt=" >1 ">, then the errors obtained in the previous steps accumulate. To avoid this, a modification of the method is applied Gaussian with selection of the main element.At each step, the selection of the maximum element by column is added to the usual scheme as follows:
Let the system of equations be obtained by eliminating the unknowns:
, .Let's find something such that we swap the -e and -e levels.
In many cases, such a transformation significantly reduces the sensitivity of the solution to rounding errors in calculations.
Iterative improvement of the result
If there is a suspicion that the resulting solution is severely distorted, then you can improve the result as follows. The quantity is called the residual. The error satisfies the system of equations
.Solving this system, we obtain an approximation to and assume
.If the accuracy of this approximation is unsatisfactory, then we repeat this operation.
The process can be continued until all components are small enough. In this case, you cannot stop the calculations just because all the components of the residual vector have become sufficiently small: this may be the result of poor conditioning of the coefficient matrix.
Numerical example
Consider, for example, a 7x7 Vandermonde matrix and 2 different right-hand sides:
These systems were solved in two ways. Data type - float. As a result, we got the following results:
| Regular method | |||
|---|---|---|---|
| 1 | 2 | ||
| 1 | 2 | 1 | 2 |
| 0.999991 | 1 | 0.999996 | 1 |
| 1.00019 | 1 | 7.4774e-005 | 2.33e-008 |
| 0.998404 | 1 | 0.999375 | 1 |
| 1.00667 | 1 | 0.00263727 | 1.12e-006 |
| 0.985328 | 1 | 0.994149 | 1 |
| 1.01588 | 1 | 0.00637817 | 3.27e-006 |
| 0.993538 | 1 | 0.99739 | 1 |
| 0,045479 | 2.9826e-006 | 0,01818 | 8.8362e-006 |
| 0,006497 | 4.2608e-007 | 0,0045451 | 2.209e-006 |
| 0,040152 | 4.344e-005 | 0,083938 | 2.8654e-006 |
| With leading element selection by line | |||
|---|---|---|---|
| 1 | 2 | ||
| 1 | 2 | 1 | 2 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | -3.57628e-005 | 1.836e-007 |
| 1.00001 | 1 | 1.00031 | 1 |
| 0.999942 | 1 | -0.00133276 | 7.16e-006 |
| 1.00005 | 1 | 1.00302 | 0,99998 |
| 1.00009 | 1 | -0.0033505 | 1.8e-005 |
| 0.99991 | 1 | 1.00139 | 0,99999 |
| 0,000298 | 4.3835e-007 | 0,009439 | 5.0683e-005 |
| 4.2571e-005 | 6.2622e-008 | 0,0023542 | 1.2671e-005 |
| 0,010622 | 9.8016e-007 | 0,29402 | 1.4768e-006 |
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 return to the simplest system from the lesson 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 there are (or have appeared) proportional (as a special case - identical) rows in the matrix, then you should 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 is very useful because it simplifies further transformations of the matrix.
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. Let's look at our matrix from a 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, this is a fairly easy example, since the first column already has one zero, and there are fewer elementary transformations 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. This way we will get the required 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 a more complex example to solve on their own:
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 :
When solving a system of equations
The simplest version of the Gaussian method results in large errors. The reason is the appearance of large coefficients, the rounding of which results in a large absolute error D ~ 0.5. In turn, large coefficients are obtained after dividing by a small leading coefficient 
.
Conclusion: To reduce the impact of rounding errors, you need to choose a leading element that is not just different from 0, but also large enough.
First modification of Gauss's method– search by strings. In the algorithm, the leading element must be selected from the condition.
Lack of modification. Suppose x i is found with an error of D. Then, when searching for any x s, it is necessary, according to the inverse formula, to multiply . In this case, the error D will also be multiplied by . If the value is large, the error will increase.
Conclusion: it is necessary to ensure that the leading element is not just large, but the largest modulo in its line. Then, when normalizing the leading line, all other coefficients, according to formula (5), will be less than 1 in absolute value, and the errors will be decrease.
Second modification of the Gauss method– search by columns. This requirement can be met if the unknowns x i are excluded in random order, and the leading line is searched for , delivering . This will be the next leading element. After determining the leading element, swap the k-th and r-th columns.
Attention. With such a replacement, the numbering of the unknowns x i changes. To ensure such a replacement, it is necessary to enter an array p 1 ,…p n with the real numbers of the unknowns during programming. At the beginning of the forward stroke, all p i = i are the usual numbering. After finding the leading element, swap p k and p r . During the reverse stroke, the renumbered x i are calculated using formula (7). After calculating all the unknowns, we must put y]:=x[i], and an array y[i] will be the final solution to the problem.
The third modification of the Gauss method– full search. The delivering element is selected as the leader. In this case, the k-th and r-th columns, p k and p r, as well as the m-th and k-th rows are swapped. This modification provides maximum accuracy, but is also the most complex.
Application of the Gauss method to solve various linear algebra problems
1. Matrix inversion. Let it be necessary to calculate the inverse matrix of the square matrix A. Let us denote X = A –1. As you know, AX = I, where I is the identity matrix, in which 1s are located along the diagonal, and the remaining elements are 0. In other words, the i-th column of matrix I is equal to
(1 is in the i-th place). Let x (i) be the i-th column of the matrix X. Then, by virtue of the matrix multiplication rule (the row is multiplied by the column), we have A x (i) = e (i). This means that to invert the matrix we need to solve n systems of linear equations with identical matrices and different right-hand sides:
Oh = e (1) ; Oh = e (2) ; …; Oh = e (n) . (2.1)
Having solved these systems, we find that the found solutions x (1), x (2), ..., x (n) are columns of the matrix A –1.
2. Calculation of determinants. In the process of converting matrix A to triangular form using the Gaussian method, we performed the following actions with it:
1) rearranged rows or columns depending on the modification of the method;
2) divide the leading line by a non-zero leading element;
3) a leading row multiplied by a certain number was added to the rows of the matrix.
As is known, during such transformations the determinant of the matrix undergoes corresponding changes:
1) changes sign;
2) is divided by the same element;
3) does not change.
After the forward move, matrix A will be reduced to upper triangular form with ones on the main diagonal. The determinant of such a matrix is obviously equal to 1. Taking into account the changes that the determinant of matrix A underwent during the transformation process, we have the following formula:
det A = (–1) s × a 11 × a 22 ×…× a n n ,
where a j j are leading elements, s is the number of permutations of rows and/or columns when searching for leading elements.
TEST QUESTIONS AND TASKS
1. Manually implement the Gaussian method (with search in rows, columns, throughout the entire matrix - depending on the task option) for a given system of equations
and complete the following tasks
1) Solve this system of equations
2) Calculate the determinant of the matrix of this system ( Gaussian method– see p 2 ).
3) Invert the matrix of this system ( Gaussian method– see p 1 ).
In the future, use the result of solving this problem as a test example.
2. Create a program for solving a linear system using the Gaussian method (with a search in rows, columns, throughout the entire matrix - depending on the version of the task) and perform matrix inversion using this program.
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 turned 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