The second approach to the analysis of Petri nets is based on the matrix representation of Petri nets. An alternative to the definition of the Petri net in the form (P, T, I, O) is the definition of two matrices D - and D + , representing the input and output functions. Each matrix has m rows (one per transition) and n columns (one per position). Define D - = #(p i , I(t j)), and D + = #(p i , O(t j)). D - defines transition inputs, D + - outputs.
The matrix form of the definition of the Petri net (P, T, D - , D +) is equivalent to the standard form used by us, but allows definitions in terms of vectors and matrices. Let e[j] be an m-vector containing zeros everywhere except j-th component equal to one. The transition t j is represented by an m-row vector e[j].
Now the transition t j in the marking µ is allowed if µ > e[j] D - , and the result of running the transition t j in the marking µ is written as:
δ(t j) = µ - e[j] D - + e[j] D + = µ + e[j] D
where D = D + - D - is a composite change matrix.
Then for the transition trigger sequence σ = t j 1 , t j 2 , … , t jk we have:
δ(σ) = µ + e D + e D + … + e D =
= µ + (e + e + … + e)D = µ + f(σ) D
The vector f(σ) = e + e + ... + e is called the launch vector of the sequence σ = t j 1 , t j 2 , … , t jk , f(σ) j p is the number of runs of the transition t p in the sequence t j 1 , t j 2 , … , t jk . The trigger vector f(σ) is therefore a vector with non-negative integer components. (The vector f(σ) is the Parikh mapping of the sequence σ = t j 1 , t j 2 , … , t jk).
In order to show the usefulness of such a matrix approach to Petri nets, consider, for example, the conservation problem: is a given labeled Petri net preserving? In order to show conservation, it is necessary to find a (non-zero) weighting vector for which the weighted sum over all reachable markings is constant.
Let w = (w 1 ,w 2 , … , w n) be a column vector. Then, if µ is the initial marking and µ" is an arbitrary reachable marking, i.e. µ" belongs to R(C,µ), it is necessary that µ w = µ" w. Now, since µ" is reachable, there is a sequence of runs transitions σ = t j 1 , t j 2 , … , t jk , which takes the network from µ to µ". Therefore
µ" = µ + f(σ) D
Hence,
µ w = µ" w = (µ + f(σ) D) w = µ w + f(σ) D w, so f(σ) D w = 0.
Since this must be true for all f(σ) , we have D w = 0.
Thus, a Petri net is preserving if and only if there exists a positive vector w such that D w = 0.
This provides a simple persistence check algorithm and also allows a weighting vector w to be obtained.
The developed matrix theory of Petri nets is a tool for solving the reachability problem. Assume that the marking µ" is reachable from the marking µ. Then there is a sequence (possibly empty) of transition starts σ that leads from µ to µ". This means that f(σ) is a non-negative integer solution of the following matrix equation for x:
µ" = µ + xD
Therefore, if µ" is reachable from µ, then the given equation has a solution in non-negative integers; if the given equation has no solution, then µ" is unreachable from µ.
Consider, for example, the labeled Petri net shown in Figure 1:
Rice. 1. Petri net illustrating an analysis method based on matrix equations
The matrices D - and D + have the form:
t 1 t 2 t 3 t 1 t 2 t 3
p 1 1 0 0 p 1 1 0 0
D - = p 2 1 0 0 D + = p 2 0 2 0
p 3 1 0 1 p 3 0 1 0
p 4 0 1 0 p 4 0 0 1
and matrix D:
In the initial marking µ = (1, 0, 1, 0) the transition t 3 is allowed and leads to the marking µ" = (1, 0, 0, 1).
µ" = µ + e D = (1, 0, 1, 0) + (0, 0, 1) D =
= (1, 0, 1, 0) + (0, 0, -1, 1) = (1, 0, 0, 1).
The sequence σ = t 3 , t 2 , t 3 , t 2 , t 1 is represented by the launch vector f(σ) = (1, 2, 2) and is labeled µ":
µ" = (1, 0, 1, 0) + (1, 2, 2) D = (1, 0, 1, 0) + (0, 3, -1, 0) = (1, 3, 0, 0)
To determine if the label (1, 8, 0, 1) is reachable from the label (1,0, 1, 0), we have the equation:
(1, 8, 0, 1) = (1, 0, 1.0) + x D
which has a solution x =(0, 4, 5). This corresponds to the sequence σ = t 3 , t 2 , t 3 , t 2 , t 3 , t 2 , t 3 , t 2 , t 3
(1, 7,0, 1)=(1, 0, 1, 0) + x D
has no solution.
The matrix approach to the analysis of Petri nets is very promising, but it also has some difficulties. First of all, we note that the matrix D by itself does not fully reflect the structure of the Petri net. Transitions that have both inputs and outputs from the same position (loops) are represented by the corresponding matrix elements D+ and D - , but then cancel each other out in the matrix D = D + - D - . This is reflected in the previous example by the position p 4 , and the transition t3.
Another problem is the lack of sequence information in the launch vector. Consider the Petri net in fig. 2. Suppose we want to determine if the marking (0, 0, 0, 0, 1) is reachable from (1, 0, 0, 0, 0). Then we have the equation
(1, 0, 0, 0, 0)=(0, 0, 0, 0, 1) + x D
Rice. 2. Another Petri net to illustrate matrix analysis
This equation does not have a unique solution, but reduces to a set of solutions (a\f(o) =(1, x 2, x 6 - 1, 2x 6, x e - 1, x 6)). It defines the relationship between transition triggers. If we put x 6= 1 and x 2= 1, then /(o) = (1, 1, 0, 2, 0, 1), but this trigger vector corresponds to both the sequence 44444. launch is unknown.
Another difficulty is that solving the equation is necessary for attainability but not sufficient. Consider the simple Petri net shown in Fig. 3. If we want to determine if (0, 0, 0, 1) is reachable from (1, 0, 0, 0), we need to solve the equation
Rice. 3. Petri net showing that the solution of the matrix equation is a necessary but not sufficient condition for solving the reachability problem
This equation has a solution f(a) = (1, 1) corresponding to two sequences: tit 2 and /3/t. But neither of these two transition sequences is possible, since in (1,0, 0, 0) neither tit neither 4 are allowed. Thus, solving the equation is not enough to prove reachability.
test questions and tasks
1. Build a Petri net graph for the following Petri net:
P=(p 1 ,p 2 ,p 3 ,p 4 ), T=(t 1 ,t 2 ,t 3 ,t 4 ,t 5 ),
I(t 1)=(), O(t 1)=(p 1 ),
I(t 2)=(p 1 ), O(t 2)=(p 2 ),
I(t 3)=(p 2 ,p 2 ,p 4 ), O(t 3)=(p 1 ,p 3 ),
I(t 4)=(), O(t 4)=(p 3 ),
I(t 5)=(p 3 ), O(t 5)=(p 4 ,p 4 ).
2. Build a Petri net graph for the following Petri net:
P=(p 1 ,p 2 ,p 3 ,p 4 ), T=(t 1 ,t 2 ,t 3 ,t 4 ),
I(t 1)=(), O(t 1)=(p 1 ,p 1 ,p 1 ,p 1 ,p 2 ),
I(t 2)=(p 2 ), O(t 2)=( p 1 ,p 1 p 1 ,p 1 ,p 1 ,p 1 ,p 3 ),
I(t 3)=(p 1 ,p 1 ,p 1 ,p 1 ,p 1 ,p 1 ), O(t 3)=( p 2 ,p 2 p 2 ,p 2 p 4 ,p 4 ),
I(t 4)=( p 2 ,p 3 p 4 ,p 4 ), O(t 4)=(p 3 ).
3. For the Petri net from exercise 1 for marking m=(5,4,0,0) indicate the allowed transitions.
4. For the Petri net from exercise 2, for marking m=(7,12,2,1), indicate the allowed transitions.
5. Show that ÈR(C,m)=N n , where mнN n .
6. Prove that if m‘н R(C,m), then R(C,m‘)н R(C,m).
7. Prove that m‘н R(C,m) if and only if R(C,m‘)н R(C,m).
8. Build the reachability set for the Petri net from Exercise 1.
9. Construct the reachable set for the Petri net from Exercise 2.
10. Petri nets with their chips and launch rules are in many ways reminiscent of games that have a playing field: checkers, backgammon, him, go, etc. You can come up with a game for one or four people, consisting of a playing field (a Petri net is used as a field) and a set of chips. The tokens are distributed over the positions of the Petri net, and the players take turns choosing the allowed transitions and launching them. Define the rules of the game, providing for the following:
a How is the initial position of the tiles determined? (For example, each player starts the game with one chip in the house, or each player receives n tiles on the entire field at will, etc.).
b What is the purpose of the game? (Capture your opponent's chips; get the most chips; get rid of your chips as soon as possible, etc.).
c Is it necessary to color the pieces for different players? (Determine the rules for triggering transitions accordingly.)
d Shouldn't we assign points to different transitions? (Then the player's score is determined by the sum of the transitions he fired).
Based on this, describe the game, give an example of the game.
11. Develop a program that implements the game from exercise 10, where your opponent is a computer for a given Petri net.
12. Build a simulation system to perform a Petri net. The start of allowed transitions is set by the user of the simulation system.
13. Wise men sit at a large round table, on which there are many dishes of Chinese cuisine. Between the neighbors lies one chopstick. However, two chopsticks are needed to eat Chinese food, so every sage should take chopsticks from the right and left. The problem is that if all the sages take the sticks on the left side and then wait for the sticks on the right side to be released, they will wait forever and starve to death (dead end state). It is necessary to build such a Petri net that sets the strategy for holding a dinner and has no dead ends.
14.Build a Petri net representing a finite automaton that calculates the two's complement of a binary number.
15.Build a Petri net representing a finite state machine for determining the parity of the input binary number.
16.Build a Petri net representing a finite state machine that defines a trigger with a counting input.
17.Build a Petri net representing a state machine that defines a trigger with separate inputs.
18.Develop an algorithm for modeling flowcharts with a Petri net.
19.PERT-diagram is a graphical representation of the relationships between the various stages that make up the project. A project is a collection of a large number of activities, and activities must be completed before others can begin. In addition, each job takes a certain amount of time to complete. Works are graphically represented by vertices, and arcs are used to show cause and effect relationships between them. The PETR diagram is a directed graph with weighted edges. The task is to determine minimum time project execution. Develop an algorithm for modeling PERT diagrams using Petri nets.
20. Develop a model based on Petri nets to simulate chemical reactions.
21. Consider building not a tree, but a reachability graph. If a vertex x generates a subsequent vertex z with m[z]=m[y] for some non-boundary vertex y, an appropriately labeled arc from x to y is introduced. Describe the algorithm for constructing a reachability graph.
22. Show that the reachability graph construction algorithm converges and examine its properties by comparing it with the reachability tree construction algorithm.
23. A reachability tree cannot be used to solve a reachability problem, because information is lost in connection with the introduction of the concept of the symbol w. It is introduced when we arrive at the marking m‘ and on the path from the root to m‘ there is a marking m such that m‘>m. In this case, all markings of the form m+n(m‘-m) can be obtained. Explore the possibility of using the expression a+bn i instead of w to represent component values. If you can define a reachability tree in which all marking vectors are represented by expressions, then the solution to the reachability problem is determined simply by solving the system of equations.
24. Generalize the definition of conservation by allowing negative weights. What would be a reasonable interpretation of a negative weight? Is the problem of determining the persistence of a Petri net solvable if negative weights are allowed?
25. Develop an algorithm for determining the boundedness of a Petri net using a matrix approach to analysis.
26.Develop an algorithm for solving the problem of equality of two Petri nets. Petri net C 1 =(P 1 ,T 1 ,I 1 ,O 1) labeled m 1 is equal to Petri net C 2 =(P 2 ,T 2 ,I 2 ,O 2) labeled m 2 if R(C 1 ,m 1)= R(C 2 ,m 2).
27.Develop an algorithm for solving the problem of a subset of two Petri nets. Petri net C 1 =(P 2 ,T 2 ,I 2 ,O 2) labeled m 2 is a subset of Petri net C 1 =(P 1 ,T 1 ,I 1 ,O 1) labeled m 1 if R( C 1 ,m 1)Н R(C 2 ,m 2).
28.Develop an algorithm for solving the reachability problem. In a Petri net C=(P,T,I,O) with marking m, marking m‘ is reachable from m if m‘ ОR(C,m).
29.Develop an algorithm for the subtagging reachability problem. Given a subset P’ Н P and a marking m‘, does there exist m‘’ ОR(C,m) such that m‘’(p i)=m‘(p i) for all p i ОP’?.
30.Develop an algorithm for the zero reachability problem. Does m‘нR(C,m), where m‘(p i)=0, hold for all p i нP?
31.Develop an algorithm for the task of reaching zero in one position. For a given position p i ОP, does m‘ОR(C,m) exist with m‘(p i)=0?
32.Develop an algorithm for solving the Petri net activity problem. Are all transitions t j ОT active?
33.Develop an algorithm for solving the problem of the activity of one transition. Is this transition t j ОT active?
34. A Petri net is called reversible if for each transition t j ОT there is a transition t k ОT such that
#(p i ,I(t j))=#(p i ,O(t k)), #(p i ,O(t j))=#(p i ,I(t k)),
those. for each transition there is another transition with reverse inputs and outputs. Develop an algorithm for solving the reachability problem for reversible Petri nets.
35. Develop an algorithm for solving the equality problem for reversible Petri nets.
36. The task of smokers. Each of the three smokers continuously makes a cigarette and smokes it. To make a cigarette, you need tobacco, paper and matches. One of the smokers always has paper, another always has matches, the third always has tobacco. The agent has an endless supply of paper, matches and tobacco. The agent puts the two components on the table. A smoker with a third missing ingredient can make and smoke a cigarette, signaling this to the agent. The agent then places the other two of the three ingredients and the cycle repeats. Propose an active Petri net that models the problem of smokers.
37. An automaton Petri net is a Petri net in which each transition can have exactly one output and one input, i.e. for all t j ОT ½I(t j)1=1 and ½O(t j)1=1. Develop an algorithm for constructing a finite automaton that is equivalent to a given automaton Petri net.
38. A labeled graph is a Petri net in which each position is an input for exactly one transition and an output for exactly one transition, i.e. for each transition p i ОP ½I(p i)1=1 and ½O(p i)1=1. Develop an algorithm for solving the reachability problem for labeled graphs.
39. Consider the class of Petri nets that are both labeled graphs and automaton Petri nets.
40.Build a Petri net that simulates the systems described in Appendix 8. Describe the events that occur in the system and the conditions that describe the system. Construct a reachable tree for the constructed Petri net. Describe the states that the system can be in.
UDC 681.51.011
MATRIX ANALYSIS IN THE ENTERPRISE MANAGEMENT SYSTEM
© 2006 A.V. Volgin1, G.E. Belashevsky2
LLC "Samara - AviaGaz"
Samara State aerospace university
The paper analyzes various ways of using matrices in enterprise management. The relationship (connection) between the elements of two or more sets can be represented in matrix form. The composition of relations allows you to simplify the analysis of relationships between elements of sets. An example of the use of priority matrices in the enterprise management system is given.
Matrices, as an analysis tool, have long been used in the enterprise management system. Suffice it to name such quality tools as matrix charts, priority matrices, matrix analysis in Quality Function Deployment.
1. The use of matrices in management is due to the fact that almost any enterprise is characterized by a large set of objects (various equipment, divisions, suppliers, consumers), and it is difficult to describe the relationships between them with dependencies like y \u003d f (x) . Real connections are multidimensional and implicit. Matrices, on the other hand, make it possible to identify such relationships in a fairly visual form and analyze them. In the task of forming the production structure of an enterprise, a matrix of relationships between groups of parts B = ], where ^ is the number of units, can be used.
the main equipment used in the processing of the 1st and] -th parts, the technical level matrix u = \u^] is used in marketing research, where
and y - technical level of the 1st enterprise in the ] -th market and the price matrix.
From the standpoint of mathematics, the assignment of a matrix can be interpreted as a specification of a relationship (connection) between the objects of two sets. The matrix element in this case can mean both the connection of objects (such as "yes" or "no"), and the strength of the connection, expressed as a number. In the case of three or more sets, one can build multidimensional relations and, accordingly, multidimensional matrices. However, this approach loses clarity and ease of interpretation. The complexity of the analysis of multidimensional relations
ions can be overcome with the help of relationship composition.
2. Let's assume that the company has suppliers P1 P2, ... P5, which supply materials (parts, assemblies, components) Mі, M2, M3. From these materials, the enterprise manufactures products Ib I2, ... I, for customers (consumers) Zi, Z2, ... Z5. For these sets, you can compose matrices of connections. Let, for example, relationships be established between suppliers and the materials they supply (Table 1), products and necessary materials(table 2), customers and products (table 3). The sign "x" denotes the connection of objects of two sets.
Table 1. Supplier Relationship Matrix
and supplied materials (PM)
PM Pі P2 Pz P4 P5
Table 2. Matrix of relations between products and materials (IM)
IM Mі M2 Mz
Table 3. Matrix of relationships between customers and products (PI)
ZI II I2 From From
Using the composition of the ratios given by the matrices PM, MI, and ZI, it is not difficult to compose a matrix of the ratio of PP. The PZ matrix (Table 4) shows the links established by the enterprise between suppliers P and customers Z^ So, for example, the interaction of the customer Z3 with the enterprise takes place on the product I3, which requires materials M! and M3 supplied by Pn P3 and P5.
Table 4. Relationship matrix between supplier-
Detailed scheduling of technological processes (product lines) with the help of relationship matrices simplifies the determination of added value for the customer, the profit of the enterprise and its losses.
3. The construction of an enterprise quality management system is associated with the allocation of a network of processes. The distribution of processes by business units, the implementation of the requirements of the standard, for example, ISO 9001-2000, can be carried out using matrices. Let's say the processes are highlighted: contracting, QMS documentation management, internal audit, procurement, manufacturing, monitoring customer satisfaction, and the company has divisions: marketing department, purchasing department, chief designer department, chief technologist department, production, warranty support department. Based on the results of discussion with representatives of departments, a PP matrix can be compiled (Table 5). On the other hand, dedicated processes should cover the requirements of a standard, such as ISO 9001-2000. Linking processes to ISO 9001-2000 results in a TP matrix (Table 6).
Using the composition of relations, we obtain the ISO matrix (Table 7).
us and customers (PP)
ПЗ Зі 32 Зз 34 35
Table 5. Matrix of links between processes and departments (SP)
PP matrix Marketing department Procurement department Chief designer department Chief technologist department Production Warranty support department
Contracting X X
Internal audit X
Procurement X
Manufacturing X
Table 6. Relationship of processes to ISO 9001-2000
TP matrix Quality management systems Management responsibility Resource management Processes life cycle products Measure, analyze and improve
Contracting X
QMS documentation management X X
Internal audit X X
Procurement X
Production X X X
Customer Satisfaction Monitoring X
ISO Matrix Marketing Department Purchasing Department Chap. designer department chap. technologist Production Warranty Support Department
Quality management systems X X
Management responsibility X X X
Resource management X
Product Life Cycle Processes X X X
Measurement, analysis and improvement X X
Obviously, with such a distribution of ISO requirements, one can expect inconsistencies in clause 5 "Management responsibility", since the quality policy is the responsibility of top management.
4. Expanding each element of the relationship matrix, for example, "Management Responsibility - Marketing Department" can be using the priority matrix underlying the hierarchy analysis method. The requirements of the ISO 9000-2000 series establish the scope and depth of the regulatory and technical documentation necessary for the functioning of the enterprise's QMS. One of the obligatory documents of the QMS of the enterprise is the policy and goals in the field of quality. The goals of the enterprise are formulated in various areas: finance, market, competition
(benchmarking), customer satisfaction, improvement of product and process performance. The goals of the entire organization must be projected (deployed, decomposed) into its divisions, so that the staff is aware of their involvement and responsibility for achieving a particular goal of the entire organization.
Planning, choosing goals, optimizing behavior in a competitive environment is always on certain stage require a decision. It became almost obvious that social processes, in particular, management processes are poorly formalized within the framework of the classical
topics. In this case, the method of analyzing hierarchies can be quite effective.
The method of analysis of hierarchies is based on the so-called priority matrix. Assume that the task is to compare the factors influencing the selected object. As a rule, the number of influencing factors is quite large, the exact dependencies are unknown, and it is practically impossible to perform the mathematical formalization of the problem. The expert also experiences difficulties in assessing the influence of factors on the object. Surprisingly, the problem is solved more easily if a pairwise comparison of the influence of factors on the object is carried out. (The bottom line is that it is difficult to answer the question how much A weighs, it is much easier to decide which is heavier: A or B)
For analytical planning of the development of an enterprise, it is necessary to describe the initial state (the “as is” position), the target state (goals) and the means to link these states. Below is an example of applying the method of analysis of hierarchies, as an object, the goal from the quality policy "Sustainable growth in enterprise profits" is selected and some factors influencing the goal are highlighted (Table 8).
Specialists - experts of the enterprise compiled priority matrices according to the selected criteria (an example is given in table 9).
Management Logistics
Planning, Procurement,
Investments, supplier relationships,
Advertising, entrance control,
Selling prices, control of resources.
Marketing strategy. Personnel and Development
production qualification,
Compliance with deadlines, staff training,
Technology, staff motivation,
Quality, creativity,
Organization of production, cost control. planning new developments
Table 9. Example of the matrix "Production"
Production Compliance with the terms of delivery of products Technology Quality Organization of production Cost control
Compliance with product delivery dates 1 5 1 3 3
Technology 1/5 1 3 1 3
Quality 1 1/3 1 3 1
Organization of production 1/3 1 1/3 1 1
Cost control 1/3 1/3 1 1 1
Scale of relationships and filling in tables 1 - equivalence of factors, 3 - dominance of one factor over another factor,
5 - strong dominance of one factor over another factor, 2.4 - possible intermediate values.
Mathematical processing matrices was to find the priority vector as an eigenvector corresponding to the maximum eigenvalue. As an example, below are the results of processing the estimates of expert N (table 10). The columns indicate the components of the vector of priorities by various factors, for example, by the criterion "Management"
Priority is given to investment.
On fig. 1. The results of calculating the priorities of experts according to the above criteria are given. Goal achievement is associated with investment, quality,
planning new developments and controlling resources.
Table 10. Results of processing the estimates of expert N
Goal - Sustainable growth of the company's profit
Management Production Mat - technical supply Personnel and development
0,1084 0,3268 0,3072 0,1625
0,4198 0,1280 0,2059 0,0773
0,1084 0,2829 0,1552 0,1007
0,2356 0,1002 0,3316 0,2080
0,1279 0,1621 0,4516
Management
Production
S&I^TO o i_CO
Personnel and Development
Rice. 1. Results of calculating the priorities of experts
Knowing the distribution of priorities according to the selected criteria allows the top management of the enterprise to pursue a sound policy to achieve the goal.
Bibliography
1. Gludkin O.P., Gorbunov NM., Gurov A.I., Zorin Yu.V. Total Quality Management. - M.: Radio and communication, 1999.
2. Kuzin B., Yuriev V., Shakhdinarov G. Methods and models of firm management. - St. Petersburg: Peter, 2001.
3. Faure R., Kofman A., Denis-Papin M. Modern mathematics. - M.: Mir, 1966.
4. Saati T. Decision making. Hierarchy analysis method. / per. from English. - M.: Radio and communication, 1993.
MATRIX ANALYSIS IN ENTERPRISE EXECUTIVE SYSTEM
© 2006 A.V. Volgin1, G.E. Belachewskij2
\cSamara - Aviagas»
Samara State Aerospace University
In work various ways of matrixes application in business operation are analyzed. The relation (connection) between elements of two and more sets can be submitted in the matrix form. The composition of relations allows to simplify the analysis of connections between elements of sets. The example of use of priorities matrixes in a control system of the enterprise is the result.
Course of lectures on discipline
"Matrix Analysis"
for 2nd year students
Faculty of Mathematics specialty
"Economic cybernetics"
(lecturer Dmitruk Maria Aleksandrovna)
Chapter 3. Matrix Functions.
1. Function definition.
Df. Let be 
is a scalar argument function. It is required to define what is meant by f(A), i.e. we need to extend the function f(x) to the matrix value of the argument.
The solution to this problem is known when f(x) is a polynomial: , then .
Definition of f(A) in the general case.
Let m(x) be the minimal polynomial A and it has such a canonical decomposition , 
, are the eigenvalues of A. Let the polynomials g(x) and h(x) take the same values.
Let g(A)=h(A) (1), then the polynomial d(x)=g(x)-h(x) is the annihilating polynomial for A, since d(A)=0, hence d(x ) is divisible by a linear polynomial, i.e. d(x)=m(x)*q(x) (2).
Then , i.e. (3) 
, 
, .
We will agree to call m numbers for f(x) such values of the function f(x) on the spectrum of the matrix A, and the set of these values will be denoted by .
If the set f(Sp A) is defined for f(x), then the function is defined on the spectrum of the matrix A.
It follows from (3) that the polynomials h(x) and g(x) have the same values on the spectrum of the matrix A.
Our reasoning is reversible, i.e. from (3) Þ (3) Þ (1). Thus, if the matrix A is given, then the value of the polynomial f(x) is completely determined by the values of this polynomial on the spectrum of the matrix A, i.e. all polynomials g i (x) that take the same values on the spectrum of the matrix have the same matrix values g i (A). We require that the definition of the value of f(A) in the general case obey the same principle.
The values of the function f(x) on the spectrum of the matrix A must fully determine f(A), i.e. functions having the same values on the spectrum must have the same matrix value f(A). Obviously, to determine f(A) in the general case, it suffices to find a polynomial g(x) that would take the same values on the spectrum A as the function f(A)=g(A).
Df. If f(x) is defined on the spectrum of the matrix A, then f(A)=g(A), where g(A) is a polynomial that takes the same values on the spectrum as f(A), 
Df. The value of the function from the matrix A is the value of the polynomial from this matrix for .
Among the polynomials from С[x], which take the same values on the spectrum of the matrix A, as f(x), of degree not higher than (m-1), which takes the same values on the spectrum A, as f(x) is the remainder of the division any polynomial g(x) having the same values on the spectrum of the matrix A as f(x) to the minimal polynomial m(x)=g(x)=m(x)*g(x)+r(x) .
This polynomial r(x) is called the Lagrange-Sylvester interpolation polynomial for the function f(x) on the spectrum of the matrix A.
Comment. If the minimal polynomial m(x) of matrix A has no multiple roots, i.e. , then the value of the function on the spectrum .
Find r(x) for arbitrary f(x) if the matrix
. Let us construct f(H 1). Find the minimal polynomial H 1 - the last invariant factor :
, d n-1 = x 2 ; d n-1 =1;
m x =f n (x)=d n (x)/d n-1 (x)=x n Þ 0 – n-fold root m(x), i.e. n-fold eigenvalues of H 1 .
R(0)=f(0), r’(0)=f’(0),…,r (n-1) (0)=f (n-1) (0) Þ .
Three of a kind is the solution to the game<=>, when is a solution to the game, where a is any real number, k>0 CHAPTER 2. Zero-sum games in pure strategies 2.1 Calculation of optimal strategies on the example of problem solving Using the minimax theorem, we can state that each antagonistic game has optimal strategies. Theorem: let A be a matrix game and the rows of the given...
A picture that does not match it is a candidate for exclusion from the scope of the corporation. 5. Developing a corporate strategy The previous analysis has set the stage for developing strategic steps to improve the performance of a diversified company. The main conclusion about what to do depends on the conclusions regarding the entire set of activities in the economic ...
method scientific research properties of objects based on the use of the rules of the theory of matrices, which determine the value of the elements of the model, reflecting the relationship of economic objects. It is used in cases where the main object of study is the balance ratio of costs and results of production and economic activities and the standards of costs and outputs.
- - pseudobridge, matrix bridge
Molecular biology and genetics. Dictionary
- - English. matrix analysis; German Matrixanalysis. In sociology - a method of studying the properties of social. objects based on the use of the rules of matrix theory...
Encyclopedia of Sociology
- - in the printing industry - a press for embossing stereotypical matrices or non-metal. stereotypes are usually hydraulic...
Big encyclopedic polytechnic dictionary
- - A device used for pressing cardboard or vinyl plastic matrices, as well as plastic stereotypes ...
Brief explanatory dictionary of polygraphy
- - See: dot matrix printer...
Glossary of business terms
- - a method of scientific study of the properties of objects based on the use of the rules of the theory of matrices, which determine the value of the elements of the model, reflecting the relationship of economic objects ...
Big Economic Dictionary
- - in economics, a method of scientific study of the properties of objects based on the use of the rules of the theory of matrices, which determine the value of the elements of the model, reflecting the relationship of economic objects ...
Great Soviet Encyclopedia
- - a method for studying the relationships between economic objects using their matrix modeling ...
Large encyclopedic Dictionary
- - ...
Spelling Dictionary of the Russian Language
- - MATRI-A, -s, f. ...
Explanatory dictionary of Ozhegov
- - MATRIX, matrix, matrix. adj. to matrix. Matrix cardboard...
Explanatory Dictionary of Ushakov
- - matrix I adj. rel. with noun. matrix I associated with it II adj. 1. ratio with noun. matrix II, associated with it 2. Provides printing using a matrix. III adj. ratio...
Explanatory Dictionary of Efremova
- - m "...
Russian orthographic dictionary
- - ...
Word forms
- - adj., number of synonyms: 1 matrix-vector ...
Synonym dictionary
- - adj., number of synonyms: 1 four ...
Synonym dictionary
"ANALYSIS MATRIX" in books
T.N. Panchenko. Strawson and Wittgenstein. Analysis as revealing the formal structure of informal language and analysis as therapy
From the book Philosophical Ideas by Ludwig Wittgenstein author Gryaznov Alexander FeodosievichT.N. Panchenko. Strawson and Wittgenstein. Analysis as the revelation of the formal structure of informal language and analysis as therapy *** Ludwig Wittgenstein and Peter Strawson in some way define the boundaries of the philosophy of analysis, its beginning and end. One of them belongs to
§ 34. Fundamental development of the phenomenological method. Transcendental analysis as eidetic analysis
From the book Cartesian Reflections author Husserl Edmund§ 34. Fundamental development of the phenomenological method. Transcendental analysis as eidetic analysis
2.6. Biosynthesis of proteins and nucleic acids. Matrix nature of biosynthetic reactions. Genetic information in a cell. Genes, genetic code and its properties
From the book Biology [ Complete reference to prepare for the exam] author Lerner Georgy Isaakovich2.6. Biosynthesis of proteins and nucleic acids. Matrix nature of biosynthetic reactions. Genetic information in a cell. genes, genetic code and its properties Terms and concepts tested in examination work: anticodon, biosynthesis, gene, genetic information,
Matrix Analysis
From the book Big Soviet Encyclopedia(MA) author TSB2.4. ANALYSIS OF REQUIREMENTS FOR THE SYSTEM (SYSTEM ANALYSIS) AND FORMULATION OF GOALS
From the book Programming Technologies the author Kamaev V A2.4. ANALYSIS OF REQUIREMENTS TO THE SYSTEM (SYSTEM ANALYSIS) AND FORMULATION OF GOALS The task of optimizing the development of programs is to achieve goals with the least possible expenditure of resources.
Matrix metering
From the book Digital Photography from A to Z author Gazarov Artur YurievichMatrix metering Matrix metering (Pattern Evaluative, E) is also called multi-zone, multi-zone, multi-segment, evaluative. In automatic mode, the camera sets the standard matrix metering used more often than others. This is the most intelligent measurement
Question 47 Factual and legal basis. Evidence analysis.
From the book The Author's Lawyer ExamQuestion 47 Actual and legal basis. Evidence analysis. Honest, reasonable and conscientious provision legal assistance in any form, whether it is consulting, drafting various documents, representing interests or defending within
9. Science at the service of toxicology. Spectral analysis. Crystals and melting points. Structural analysis by X-ray. Chromatography
From the book One Hundred Years of Forensics author Thorvald Jürgen9. Science at the service of toxicology. Spectral analysis. Crystals and melting points. Structural analysis by X-ray. Chromatography In the meantime, the events that took place in the trial against Buchanan became known throughout the world. With all disrespect for American science of those years, these
12.9. Matrix solution development method
From the book Systematic Problem Solving author Lapygin Yuri Nikolaevich12.9. Matrix method of developing decisions Decision-making based on the matrix method is reduced to making a choice, taking into account the interests of all interested parties. Schematically, the decision process in this case looks like it is shown in Fig. 12.7. As we see, there is
4. Market research and analysis (analysis of the business environment of the organization)
From the book Business Planning: Lecture Notes the author Beketova Olga4. Market research and analysis (analysis of the organization's business environment) Market research and analysis is one of the most important stages in the preparation of business plans, which should answer questions about who, why and in what quantities buys or will buy products
5.1. Analysis of the external and internal environment of the organization, SWOT analysis
author Lapygin Yuri Nikolaevich5.1. Analysis of the external and internal environment of the organization, SWOT analysis External environment and system adaptation Organizations, like any systems, are isolated from external environment and at the same time are connected with the external environment in such a way that from the external environment they receive the resources they need and
8.11. Matrix method RUR
From the book Management Decisions author Lapygin Yuri Nikolaevich8.11. Matrix method RSD Decision-making based on the matrix method is reduced to making a choice, taking into account the interests of all stakeholders. Schematically, the RUR process in this case looks like it is shown in Fig. 8.13. Rice. 8.13. The RUR model by the matrix method
4. Analysis of the strengths and weaknesses of the project, its prospects and threats (SWOT analysis)
author Filonenko Igor4. Analysis of strengths and weaknesses project, its prospects and threats (SWOT-analysis) When assessing the feasibility of launching a new project, a combination of factors plays a role, and not always the financial result is of paramount importance. For example, for an exhibition company
5. Political, economic, social and technological analysis (PEST-analysis)
From the book Exhibition Management: Management Strategies and Marketing Communications author Filonenko Igor5. Political, Economic, Social and Technological Analysis (PEST Analysis)
11.3. Matrix strategy development method
From the book Strategic Management: tutorial author Lapygin Yuri Nikolaevich11.3. The matrix method for developing strategies Development of an organization's vision The various states of the external and internal environment of organizations explain the diversity of the organizations themselves and their actual state. The multifactorial nature of the parameters that determine the position of each
Course of lectures on discipline
"Matrix Analysis"
for 2nd year students
Faculty of Mathematics specialty
"Economic cybernetics"
(lecturer Dmitruk Maria Aleksandrovna)
Chapter 3. Matrix Functions.
- Function definition.
Df. Let the function be a scalar argument. It is required to define what is meant by f(A), i.e. we need to extend the function f(x) to the matrix value of the argument.
The solution to this problem is known when f(x) is a polynomial: , then.
Definition of f(A) in the general case.
Let m(x) be the minimal polynomial A and it has such a canonical decomposition, eigenvalues A. Let the polynomials g(x) and h(x) take the same values.
Let g(A)=h(A) (1), then the polynomial d(x)=g(x)-h(x) is the annihilating polynomial for A, since d(A)=0, hence d(x) is divisible by a linear polynomial, i.e. d(x)=m(x)*q(x) (2).
Then, i.e. (3), .
Let us agree to call m numbers for f(x) such values of the function f(x) on the spectrum of the matrix A, and the set of these values will be denoted.
If the set f(Sp A) is defined for f(x), then the function is defined on the spectrum of the matrix A.
It follows from (3) that the polynomials h(x) and g(x) have the same values on the spectrum of the matrix A.
Our reasoning is reversible, i.e. from (3) (3) (1). Thus, if the matrix A is given, then the value of the polynomial f(x) is completely determined by the values of this polynomial on the spectrum of the matrix A, i.e. all polynomials gi(x) that take the same values on the spectrum of the matrix have the same matrix values gi(A). We require that the definition of the value of f(A) in the general case obey the same principle.
The values of the function f(x) on the spectrum of the matrix A must fully determine f(A), i.e. functions having the same values on the spectrum must have the same matrix value f(A). Obviously, to determine f(A) in the general case, it suffices to find a polynomial g(x) that would take the same values on the spectrum A as the function f(A)=g(A).
Df. If f(x) is defined on the spectrum of matrix A, then f(A)=g(A), where g(A) is a polynomial that takes the same values on the spectrum as f(A),
Df. The value of the function from the matrix A we call the value of the polynomial in this matrix at.
Among the polynomials from С[x], taking the same values on the spectrum of the matrix A, as f(x), of degree not higher than (m-1), taking the same values on the spectrum A, as f(x) is the remainder of the division of any polynomial g(x) having the same values on the spectrum of the matrix A as f(x) by the minimal polynomial m(x)=g(x)=m(x)*g(x)+r(x).
This polynomial r(x) is called the Lagrange-Sylvester interpolation polynomial for the function f(x) on the spectrum of the matrix A.
Comment. If the minimal polynomial m(x) of matrix A has no multiple roots, i.e. , then the value of the function on the spectrum.
Example:
Find r(x) for arbitrary f(x) if the matrix
. Let us construct f(H1 ). Find the minimal polynomial H1 last invariant factor :
, dn-1=x2 ; dn-1=1;
mx=fn(x)=dn(x)/dn-1(x)=xn 0 nmultiple root m(x), i.e. n-fold eigenvalues H1 .
, r(0)=f(0), r(0)=f(0),…,r(n-1)(0)=f(n-1)(0) .
- Properties of functions from matrices.
Property #1. If the matrix has eigenvalues (there may be multiples among them), and, then the eigenvalues of the matrix f(A) are the eigenvalues of the polynomial f(x): .
Proof:
Let the characteristic polynomial of matrix A have the form:
Let's count. Let's move from equality to determinants:
Let's make a change in equality:
Equality (*) is valid for any set f(x), so we replace the polynomial f(x) with, we get:
On the left, we have obtained the characteristic polynomial for the matrix f(A), decomposed on the right into linear factors, whence it follows that the eigenvalues of the matrix f(A).
CHTD.
Property #2. Let the matrix and the eigenvalues of the matrix A, f(x) be an arbitrary function defined on the spectrum of the matrix A, then the eigenvalues of the matrix f(A) are equal.
Proof:
Because function f(x) is defined on the spectrum of the matrix A, then there is an interpolation polynomial of the matrix r(x) such that, and then f(A)=r(A), and the matrix r(A) has eigenvalues according to property No. 1 which are respectively equal.
CHTD.
Property #3 If A and B are similar matrices, i.e. , and f(x) is an arbitrary function defined on the spectrum of the matrix A, then
Proof:
Because A and B are similar, then their characteristic polynomials are the same and their eigenvalues, so the value of f(x) on the spectrum of matrix A coincides with the value of the function f(x) on the spectrum of matrix B, and there is an interpolation polynomial r(x) such that that f(A)=r(A), .
CHTD.
Property number 4. If A is a block diagonal matrix, then
Consequence: If, then, where f(x) is a function defined on the spectrum of matrix A.
- Lagrange-Sylvester interpolation polynomial.
Case number 1.
Let it be given. Consider the first case: the characteristic polynomial has exactly n roots, among which there are no multiples, i.e. all eigenvalues of the matrix A are different, i.e. , Sp A is simple. In this case, we construct the basic polynomials lk(x):
Let f(x) be a function defined on the spectrum of the matrix A and let the values of this function on the spectrum be. We must build.
Let's build:
Let's note that.
Example: Construct a Lagrange-Sylvester interpolation polynomial for a matrix.
Let's construct basic polynomials:
Then for the function f(x) defined on the spectrum of the matrix A, we get:
Let's take, then the interpolation polynomial
Case number 2.
The characteristic polynomial of matrix A has multiple roots, but the minimal polynomial of this matrix is a divisor of the characteristic polynomial and has only simple roots, i.e. . In this case, the interpolation polynomial is constructed in the same way as in the previous case.
Case number 3.
Let's consider the general case. Let the minimal polynomial have the form:
where m1+m2+…+ms=m, deg r(x) Let's compose a fractional-rational function: and decompose it into simple fractions. Let's designate: . Multiply (*) by and get where is some function that does not go to infinity at. If we put in (**), we get: In order to find ak3 one has to (**) differentiate twice, and so on. Thus, the coefficient aki is uniquely determined. After finding all the coefficients, we return to (*), multiply by m(x) and get the interpolation polynomial r(x), i.e. Example: Find f(A) if, where tsome parameter,
Let's check whether the function is defined on the spectrum of the matrix A Multiply (*) by (x-3) at x=3 Multiply (*) by (x-5) Thus,is an interpolation polynomial. Example 2 If a, then prove that Let's find the minimal polynomial of the matrix A: is the characteristic polynomial. d2
(x)=1, then the minimal polynomial Consider f(x)=sin x on the matrix spectrum: the function is defined on the spectrum. Multiply (*) by
.
Multiply (*) by:
Calculate by taking the derivative (**): . Assuming,
, i.e..
So,,
Example 3 Let f(x) be defined on the spectrum of a matrix whose minimal polynomial has the form. Find the interpolation polynomial r(x) for the function f(x). Solution: By condition f(x) is defined on the spectrum of the matrix A f(1), f(1), f(2), f(2), f(2) defined. We use the method of indefinite coefficients: If f(x)=log x f(1)=0f(1)=1
f(2)=log 2f(2)=0.5
f(2)=-0.25
4. Simple matrices.
Let the matrix, since C is an algebraically closed field, then x