Find basic solutions online. Solving systems of linear equations using the Jordan-Gauss method. §1. Systems of linear equations

§1. Systems linear equations.

View system

called a system m linear equations with n unknown.

Here
- unknown, - coefficients for unknowns,
- free terms of the equations.

If all free terms of the equations are equal to zero, the system is called homogeneous.By decision system is called a collection of numbers
, when substituting them into the system instead of unknowns, all equations turn into identities. The system is called joint, if it has at least one solution. A compatible system that has a unique solution is called certain. The two systems are called equivalent, if the sets of their solutions coincide.

System (1) can be represented in matrix form using the equation

(2)

.

§2. Compatibility of systems of linear equations.

Let us call the extended matrix of system (1) the matrix

Kronecker-Capelli theorem. System (1) is consistent if and only if the rank of the system matrix is ​​equal to the rank of the extended matrix:

.

§3. Systems solutionn linear equations withn unknown.

Consider an inhomogeneous system n linear equations with n unknown:

(3)

Cramer's theorem.If the main determinant of the system (3)
, then the system has a unique solution, determined by the formulas:

those.
,

Where - determinant obtained from the determinant replacement th column to the column of free members.

If
, and at least one of ≠0, then the system has no solutions.

If
, then the system has infinitely many solutions.

System (3) can be solved using its matrix form (2). If the matrix rank A equals n, i.e.
, then the matrix A has an inverse
. Multiplying the matrix equation
to the matrix
on the left, we get:

.

The last equality expresses the method of solving systems of linear equations using an inverse matrix.

Example. Solve a system of equations using an inverse matrix.

Solution. Matrix
non-degenerate, since
, which means there is an inverse matrix. Let's calculate the inverse matrix:
.

,

Exercise. Solve the system using Cramer's method.

§4. Solving arbitrary systems of linear equations.

Let a non-homogeneous system of linear equations of the form (1) be given.

Let us assume that the system is consistent, i.e. the condition of the Kronecker-Capelli theorem is satisfied:
. If the matrix rank
(number of unknowns), then the system has a unique solution. If
, then the system has infinitely many solutions. Let me explain.

Let the rank of the matrix r(A)= r< n. Because the
, then there is some non-zero minor of order r. Let's call it the basic minor. The unknowns whose coefficients form a basis minor will be called basic variables. We call the remaining unknowns free variables. Let's rearrange the equations and renumber the variables so that this minor is located in the upper left corner of the system matrix:

.

First r lines are linearly independent, the rest are expressed through them. Therefore, these lines (equations) can be discarded. We get:

Let's give the free variables arbitrary numerical values: . Let us leave only the basic variables on the left side and move the free ones to the right side.

Got the system r linear equations with r unknown, whose determinant is different from 0. It has a unique solution.

This system is called the general solution of the system of linear equations (1). Otherwise: the expression of basic variables through free ones is called general decision systems. From it you can get an infinite number of private solutions, giving free variables arbitrary values. A particular solution obtained from a general one for zero values ​​of free variables is called basic solution. The number of different basic solutions does not exceed
. A basic solution with non-negative components is called supporting system solution.

Example.

,r=2.

Variables
- basic,
- free.

Let's add up the equations; let's express
through
:

- common decision.

- private solution for
.

- basic solution, reference.

§5. Gauss method.

The Gauss method is a universal method for studying and solving arbitrary systems of linear equations. It consists of reducing the system to a diagonal (or triangular) form by sequentially eliminating unknowns using elementary transformations that do not violate the equivalence of systems. A variable is considered excluded if it is contained in only one equation of the system with a coefficient of 1.

Elementary transformations systems are:

Multiplying an equation by a number other than zero;

Adding an equation multiplied by any number with another equation;

Rearranging equations;

Rejecting the equation 0 = 0.

Elementary transformations can be performed not on equations, but on extended matrices of the resulting equivalent systems.

Example.

Solution. Let us write down the extended matrix of the system:

.

Carrying out elementary transformations, we will reduce the left side of the matrix to unit form: we will create ones on the main diagonal, and zeros outside it.

Comment. If, when performing elementary transformations, an equation of the form 0 is obtained = k(Where To0), then the system is inconsistent.

The solution of systems of linear equations by the method of sequential elimination of unknowns can be written in the form tables.

The left column of the table contains information about excluded (basic) variables. The remaining columns contain the coefficients of the unknowns and the free terms of the equations.

The extended matrix of the system is recorded in the source table. Next, we begin to perform Jordan transformations:

1. Select a variable , which will become the basis. The corresponding column is called the key column. Choose an equation in which this variable will remain, being excluded from other equations. The corresponding table row is called a key row. Coefficient , standing at the intersection of a key row and a key column, is called a key.

2. The key string elements are divided into the key element.

3. The key column is filled with zeros.

4. The remaining elements are calculated using the rectangle rule. Make up a rectangle, at the opposite vertices of which there is a key element and a recalculated element; from the product of the elements located on the diagonal of the rectangle with the key element, the product of the elements of the other diagonal is subtracted, and the resulting difference is divided by the key element.

Example. Find the general solution and basic solution of the system of equations:

Solution.

General solution of the system:

Basic solution:
.

A single substitution transformation allows you to move from one basis of the system to another: instead of one of the main variables, one of the free variables is introduced into the basis. To do this, select a key element in the free variable column and perform transformations according to the above algorithm.

§6. Finding support solutions

The reference solution of a system of linear equations is a basic solution that does not contain negative components.

The reference solutions of the system are found by the Gaussian method when the following conditions are met.

1. In the original system, all free terms must be non-negative:
.

2. The key element is selected among the positive coefficients.

3. If a variable introduced into the basis has several positive coefficients, then the key line is the one in which the ratio of the free term to the positive coefficient is the smallest.

Note 1. If, in the process of eliminating unknowns, an equation appears in which all coefficients are non-positive and the free term
, then the system has no non-negative solutions.

Note 2. If there is not a single positive element in the columns of coefficients for free variables, then transition to another reference solution is impossible.

Example.

Since not every basic solution is a reference solution, computational difficulties arise when finding reference solutions of the system the usual method Gauss. We have to find all the basic solutions and select the reference ones from them. There is an algorithm that allows you to immediately find reference solutions.

1. When filling out the original Gauss table, all free terms are made non-negative.
2. The key element is selected in a special way:
1. a) any column of coefficients for unknowns is chosen as a key column if it contains at least one positive element;
2. b) the key row is taken to be the one whose ratio of the free term to the positive element of the key column is minimal.

At the intersection of a key row and a key column is the key element. Next, carry out the usual Jordan transformation.

Homogeneous systems of linear equations

Let a homogeneous system be given

Let us consider the corresponding inhomogeneous system

Using matrices

these systems can be written in matrix form.

A`x = . (8.3)

A`x = `b . (8.4)

The following are true properties of solutions of homogeneous and inhomogeneous systems.

Theorem 8.23. A linear combination of solutions to a homogeneous system (8.1) is a solution to a homogeneous system.

Proof. Let `x , `y And `z - solutions of a homogeneous system. Let's consider `t = α `x + β `y + γ `z , where α, β and γ are some arbitrary numbers. Because `x , `y And `z are solutions, then A`x = , A`y = and A`z = . We'll find A`t .

A`t = A · (α `x + β `y + γ `z ) = A · α `x +A · β `y + A γ `z =

= α A`x + β A`y + γ A`z = α + β + γ = .

A`t = Þ `t is a solution to the system.

Theorem 8.24. The difference between two solutions of the inhomogeneous system (8.2) is a solution to the homogeneous system (8.1).

Proof. Let `x And ` y- system solutions. Let's consider `t = `x - `y .

A`x = `b , A`y = `b

A`t = A (`x - `y ) = A`x - A`y = `b - `b =.

`t = `x + `y is a solution to a homogeneous system.

Theorem 8.25. The sum of a solution of a homogeneous system with a solution of an inhomogeneous system is a solution of the inhomogeneous system.

Proof. Let `x - solution of a homogeneous system, `y - solution of a heterogeneous system. Let's show that `t = `x + `y - solution of a heterogeneous system.

A`x = , A`y = `b

A`t = A (`x + `y ) = A`x + A`y = `b + = `b .

A`t = `b Þ `t is a solution to the inhomogeneous system.

Consider a homogeneous system

x 1 = x 2 = … = x n

Theorem 8.26.

Proof. s 1, s 2, …, s n m

A linearly dependent. A n, i.e. r(A)< n.

Consequence.

Proof. Because r(A)< n

Compatibility of a homogeneous system

Consider a homogeneous system

A homogeneous system is always consistent, since it has a trivial (zero) solution x 1 = x 2 = … = x n= 0. Let's find out when this system has a non-trivial solution.

Theorem 8.26. A homogeneous system has a nontrivial solution if and only if the rank of the matrix composed of the coefficients of the unknowns is less than the number of unknowns.

Proof. Let the system have a nontrivial solution. This can be if and only if the numbers are found s 1, s 2, …, s n, not all equal to zero, when substituting them into the system we obtain m identities. These m identities can be written in the form

Consequently, the system of matrix column vectors A linearly dependent. A this can be the case if and only if the rank of the column vector system is less n, i.e. r(A)< n.

Consequence. A homogeneous system with a square matrix has a nontrivial solution if and only if the determinant of the matrix composed of the coefficients of the unknowns is equal to zero.

Proof. Because r(A)< n , then the columns of the matrix are linearly dependent and, therefore, the determinant of the matrix is ​​equal to zero.

General solution of a homogeneous system

System (8.1) always has a trivial solution. If the rank of the matrix composed of the coefficients of the unknowns is less than the number of unknowns, then system (8.1) has nontrivial solutions.

1)r(A) = n - system (8.1) has only a trivial solution:

2)r(A) = r< n - system (8.1) has non-trivial solutions.

The number of free variables in the second case will be equal to n-r, and basic r. Giving free variables arbitrary values, we will obtain different solutions to system (8.1), i.e., to any vector of dimension n-r

(c r + 1, c r + 2, …, c n)

will correspond to the solution of system (8.1)

(c 1, c 2, …, c r, c r + 1, …, c n).

Definition 8.51. A fundamental system of solutions to a homogeneous system (8.1) is a maximal linearly independent system of solutions to system (8.1). The fundamental system contains n-r linearly independent solutions of system (8.1).

To obtain a fundamental system of solutions, you need to (n - r)-dimensional space take linearly independent system from n-r vectors and use them to construct the corresponding solutions of system (8.1). The resulting solutions will form a fundamental system of solutions `x 1 , `x 2 , ..., `xn-r . Since this system is maximal, any solution to system (8.1) can be represented as a linear combination of solutions to the fundamental system `x = α 1 `x 1 ‌ α 2 `x 2 ‌ ... ‌ α n-r`xn-r . The resulting expression is the general solution of the homogeneous system (8.1).

Example 8.25.

x 1 , x 2 - basic, x 3 , x 4 , x 5- free. The last two equations are linearly expressed through the first two, so they can be discarded:

Let us express the basic variables.

Multiply the first equation by 2 and add it to the second. Divide the result by 8.

Multiply the first equation by 2, the second by -3 and add the resulting equations. Divide the result by 8.

As the values ​​of the free variables, we take the coordinates of the vectors of the three-dimensional unit basis.

`x = α 1 `x 1 + α 2 `x 2 + α 3 `x 3 - general solution of a homogeneous system.

The sum of the general solution of the homogeneous system (8.1) with any solution of the inhomogeneous system (8.2) is the general solution of the inhomogeneous system (8.2).

Application of linear algebra in economics

Production figures

The company produces four types of products every day, the main production and economic indicators of which are given in the following table.

The following daily indicators need to be determined: raw material consumption S, working time costs T and cost R manufactured products of the enterprise.

Based on the given data, we will create four vectors that characterize the entire production cycle:

`q = (20, 50, 30, 40) - assortment vector;

`s = (5, 2, 7, 4) - vector of raw material consumption;

= (10, 5, 15, 8) - vector of working time costs;

`p = (30, 15, 45, 20) - price vector.

Then the required quantities will be the corresponding scalar products of the assortment vector and three other vectors:

S = `q`s = 100 + 100 + 210 + 160 = 570 kg,

T = `q = 1220 h, P = `q`p = 3500 den. units

Raw material consumption

The company produces four types of products using four types of raw materials. Raw material consumption rates are given as matrix elements A:

Type of raw material 1 2 3 4

Product type.

It is required to find the costs of each type of raw material for a given production plan for each type of product: 60, 50, 35 and 40 units, respectively.

Let's draw up a vector plan for production:

`q = (60, 50, 35, 40).

Then the solution to the problem is given by a cost vector, the coordinates of which are the costs of raw materials for each type of raw material: this cost vector is calculated as the product of the vector `q to the matrix A:

End product of the industry

The industry consists of n enterprises producing one type of product each: let’s denote the volume of production i th enterprise through X i. Each of the enterprises in the industry, to ensure its production, consumes part of the products produced by itself and other enterprises. Let and ij - share of production i th enterprise, consumed j- an enterprise to ensure the production of its products in volume x j. Let's find the value y i- quantity of products i th enterprise intended for sale outside this industry (volume of the final product). This value can be easily calculated using the formula

Let us introduce into consideration a square matrix of order n, describing the domestic consumption of the industry

A = (a ij); i,j = 1, 2, ..., n.

Then the final product vector is a solution to the matrix equation

`x - A`x = `y

using identity matrix E we get

(E-A)`x = `y

Example 8.26. Let the vector of industry output and the matrix of domestic consumption have the form, respectively

We obtain a vector of volumes of the final product intended for sale outside the industry, consisting of three enterprises:

Product Output Forecast

Let C = (c ij); i = 1, 2, ..., m, j = 1, 2, ..., n, - raw material cost matrix t types when releasing products n species. Then, with known stock volumes of each type of raw material, which form the corresponding vector

`q = (q 1 , q 2 , ..., q m)

vector plan `x = (x 1 , x 2 , ..., x n) product output is determined from the system solution m equations with n unknown:

C`x T = `x T ,

where is the index " T" means transposing a row vector to a column vector.

Example 8.27. The company produces three types of products using three types of raw materials. The necessary production characteristics are presented by the following data:

It is required to determine the volume of output of each type of product with given reserves of raw materials.

Problems of this kind are typical when making forecasts and assessments of the functioning of enterprises, expert assessments projects for the development of mineral deposits, as well as in planning the microeconomics of enterprises.

Let us denote the unknown volumes of production by x 1, x 2 And x 3. Then, provided that the reserves of each type of raw material are completely consumed, it is possible to write down balance relationships that form a system of three equations with three unknowns:

Solving this system of equations in any way, we find that with given reserves of raw materials, production volumes will be for each type, respectively (in conventional units):

x 1 = 150, x 2 = 250, x 3 = 100.

Consider an arbitrary system

To find general method research and solutions of such a system will be introduced into consideration of it special case. View system

(16.2)

is called a system in basic form.

Unknown are called free, and - non-free or basic unknowns. The choice of basic and free variables may be different in the general case.

System (16.1) has a solution if and only if it can be written in basic form.

Let us transfer all free unknowns to the right-hand sides of the equations of system (16.2). Then we get

(16.3)

If free unknown give specific numerical values, then using formulas (16.3) you can calculate the basic unknowns. Thus, the basic system (16.2) always has a solution. Moreover, the following options are possible.

1). m=n, that is, the number of equations is equal to the number of unknowns. In this case, all variables are basic. The system has the form

and is definite because it has a single, obvious solution. The matrix of such a system is the identity matrix

.

2). m Then a system with an extended matrix of the form