Mathematical Modeling for Systems of Large Dimension Through a Modification of the Method of Iterative Aggregation Tatyana Grobova Alexey Troyanov Vladislav Lysov Vladimir Antonov Department of applied Department of applied Department of Department of applied mathematics and mathematics and computer Information security mathematics and computer security security North Caucasus computer security North Caucasus North Caucasus University, North Caucasus University, University, Stavropol, University, Stavropol, Stavropol, Russian Federation Stavropol, Russian Federation Russian Federation Junior77708@rambler.ru Russian Federation grobova@yandex.ru a.troyanov108@gmail.com ant.vl.02@gmail.com Abstract This article provides a new method for accelerating the convergence such that is a synthesis of two methods: Seidel method and an iterative method for solving a linear system of equations. Using a new method accelerating the convergence for various grades of operator equations allows to construct a sequence of approximations that more convergence to solve the operator equations. In this paper, the method allows to significantly speed up the process of convergence to the precise solution. There is an implementation of the resulting method and sufficient conditions of convergence. Keywords: approximate methods, operator equations, spectral radius, Seidel method, method of iterative aggregation. 1 Introduction A development of mankind result in speed up the amount of processed information, that`s why it is required to solve optimization problems of large dimensions. This is particularly marked in areas such as bioengineering and economy. To meet the challenges of large dimension along with the increased processing power of computers it is necessary to develop new algorithms and methods to effectively use computing resources and to obtain solutions to previously unsolvable tasks. Many algorithms and methods has been developed for solving various optimization integrated problems. Many practical problems are characterized by high dimensionality and a presence of difficulty formalizable restrictions. Both the formalization as well as numerical solution of problem of decision-making in planning, allocation of resources, optimize complex processes in various application cause the known issues [Arh75], [Dud79], [Gol04]. Significant difficulties, inter alia, connected with the large dimensionality of problems, which is not solved by traditional ways, so develop the new approaches of solution involving powerful computing resources is therefore required. It is required to find the precise solution of linear and nonlinear algebraic equations systems for solving many problems of analysis and algebra. Typically, the modeling of complex systems confronted with large dimension tasks, a considerable number of internal linkages and different stochastic properties. The modeling process is difficult to implement at a sufficiently large number of unknown parameters. In such case, it is required to use the various methods to find the precise solution by using iterative processes. One of the simplest and well-known approximate method is Seidel method, which is a derivative of the method of successive approximations. In the papers [Kra69] and [Gro11], authors provided the Seidel method and various modification of it. Consider now a one of the possible modification of Seidel method for solving the linear algebraic equations systems. Let x be an operator equation of the form Copyright c 2017 by the paper’s authors. Copying permitted for private and academic purposes. In: S. Hölldobler, A. Malikov, C. Wernhard (eds.): YSIP2 – Proceedings of the Second Young Scientist’s International Workshop on Trends in Information Processing, Dombai, Russian Federation, May 16–20, 2017, published at http://ceur-ws.org. 84 x=Ax+f (1) where x be an unknown vector of Banach space E, f be a prescribed vector of E, A be a linear operator in the Banach space E. Let the operator A be as a sum of operators A1 and A2 A=A1+A2 (2) If there is an operator inverse to the operator (I-A1), then the equation (1) will be such that x  ( I  A1 ) 1  A2 x  ( I  A1 ) 1  f (3) Using the method of successive approximations to (3), we get x m 1  I  A1  A2 x m  I  A1  f , m  1,2,...  1 1 (4) There has been a significant acceleration of convergence to the solution compared with the method of successive approximations when solving the equation (1) by Seidel method [MEU99]. This article provides a modification of method of one-parameter iterative aggregation: the solution for equation (3) will search by using method of one-parameter iterative aggregation and we get a new method of accelerating for convergence in the result. 2 Approach There were the methods of one-parameter and multiparameter aggregation, and their conditions of convergence in the paper [GRO14]. Consider now the convergence for method of one-parameter aggregation to solve an integral equation (1) with integral operator A 1 Ax(t )   K (t , s) x( s) ds 0 where a kernel K(t,s) be an nonnegative measurable function and f(t) be a nonnegative constant term, when the kernel K(t,s) is enough small. In paper [GRO14], if the conditions (5) and (6) are true, the method of one-parameter aggregation is just an equation, if “aggregation” functionality is (7). 1 A  sup  K (t , s) ds  c  1 (5) 0t 1 0 (2  c) c (6) 1 (1  c) 2 1 l 0 [ x(t )]   x( s) ds (7) 0 In paper [GRO14] the condition of convergence method of one-parameter aggregation is true, if the parameter c in the inequality (5) be 2 (8) c 1   0, 292 2 Moreover, the method ensures convergence to the precise solution with denominator q < 1 of geometric progression. The condition (8) is a sufficient condition for convergence of method of one-parameter aggregation and the experimental material shows that the convergence of method is relevant at less stringent requirements on the smallness of the kernel. The close condition to the condition (8) on the smallness of the rules of the matrix operator A be obtained as a sufficient condition for convergence of method of one-parameter iterative aggregation in solving linear system of algebraic equations. Consider now an algorithm of method for solving linear system of algebraic equations. Suppose that A be a nonnegative matrix and it is required to solve the following set of equations: n xi   aij x j  f i (n  1, n) (9) j 1 Let x=x1 for solution x* of equation (9) and l0(x) be a functionality: 85 n l 0 ( x)   x i ( x  ( x1 , x 2 , ..., x n )) , i 1 Using (1), we get the equation (10) with an unknown scalar t. Let the condition (11) will be fulfilled, if for any 𝛼 ∈ [0; 1) a condition (12) is true where A* be a transpose for matrix A: t l 0 ( x1 )  t l 0 ( Ax1 )  l 0 ( f ) (10) l 0 ( x1 )  l 0 ( Ax1 )  0 (11) A* l 0   l 0  1 (12) If the condition (12) is true then the equation (10) has a unique solution (13) t=t(x1) and this solution will be positive, if the vector f is positive 𝑓: 𝑓 ≥ 𝜃. l0 ( f ) l0 ( f ) (13) t ( x1 )   l 0 ( x1 )  l 0 ( Ax1 ) (l 0  A* l 0 )( x1 ) When the value t=t(x1) is founded, let find an element x2 by using the formula: x2  t ( x1 ) Ax1  f (14) Using induction, we have the assertion (15): x m 1  t ( x m ) Ax m  f (m 1, 2, ...) (15) This means that the method of one-parameter iterative aggregation is to construct a sequence {xm}. In papers [GRO14] and [Gro11], author`s computational experiments indicate, that the method of one-parameter iterative aggregation, firstly, isn`t depend from functionality, secondly, the method converges fast enough for relatively large values 𝜌(𝐴). It is interesting, that the method converges for 𝜌(𝐴) be close to the unit and greater than the unit as opposed to the method of successive approximations, which isn`t convergence for 𝜌(𝐴) 1. Therefore, let interpret Seidel method to use the aggregation coefficient to the both part of equation (7):    tl0 x1   tl0 ( I  A1 ) 1  A2 x1  l 0 ( I  A1 ) 1  f  (16) where t be an unknown scalar. Let we have the condition (17)  l 0 ( x1 )  l 0 (I  A1  A2 x1 )  0 1  (17) If the condition (17) is true, that the equation (16) has a unique solution t=t(x1) and t(x1) be t ( x1 )   l 0 I  A1   f 1  (18)  l 0 ( x1 )  l 0 I  A1  A2 x1 1  Finally, let find the element x2: x2  t ( x1 ) Ax1  f (19) Using induction, we have the assertion (20): x m1  t ( x m ) Ax m  f (m  1, 2, ...) (20) These computational experiments indicate that the proposed modification method of one-parameter iterative aggregation has the higher speed of convergence than Seidel method for the large values of spectral radius 𝜌(𝐴) and the faster than the method of successive approximations. 3 Usage Examples For the examples from 1 to 3, an A be a prescribed nonnegative matrix of order n, f be prescribed vector and x1 be a start value. 86 3.1 The first example Let consider the system of linear algebraic equations 𝑥 = 0.15 ∙ 𝑥 + 0.2 ∙ 𝑦 + 0.31 ∙ 𝑧 + 0.4 { 𝑦 = 0.2 ∙ 𝑥 + 0.33 ∙ 𝑦 + 0.4 ∙ 𝑧 + 0.1 𝑧 = 0.3 ∙ 𝑥 + 0.2 ∙ 𝑦 + 0.14 ∙ 𝑧 + 0.1 Table 1: Start parameters Matrix A 𝜌(𝐴) Free vector f Precise solution Initial value x1 x* 0.15 0.2 0.31 0.4 0.756 1 ( 0.2 0.03 0.4 ) 𝑓 = (0.1) (0.460) ( 1) 0.644 0.3 0.2 0.14 0.1 0.487 1 Compare the results of the given system on method of successive approximations, Seidel method and modification of method of one-parameter iterative aggregation. We get the following results. Table 2: Method of Successive Approximations Values\Number of n=1 n=10 n=20 n=25 n=30 iteration x1( n ) 1.06 0.762 0.757 0.757 0.756 x 2( n ) 0.73 0.465 0.46 0.46 0.46 x3( n ) 0.74 0.492 0.487 0.487 0.487 Table 3: Seidel Method Values\Number of iteration n=1 n=10 n=15 n=20 n=21 x1( n ) 1.06 0.757 0.757 0.757 0.756 x 2( n ) 0.742 0.461 0.46 0.46 0.46 x 3( n ) 0.706 0.488 0.487 0.487 0.487 Let consider the modification of method of iterative aggregation – «mixed method». 87 Table 4: Mixed Method Values\Number of n=1 n=2 n=4 n=5 iteration x1( n ) 0.816 0.749 0.757 0.756 x 2( n ) 0.497 0.451 0.46 0.46 x 3( n ) 0.503 0.483 0.487 0.487 We have the precise solution on the fifth iteration. As can be seen, the mixed method provides the convergence better in comparison with considerable methods. 3.2 The Second Example Let consider the system of forth equations with forth unknown variables. 𝑥1 = 0.1 ∙ 𝑥1 + 0.2 ∙ 𝑥2 + 0.3 ∙ 𝑥3 + 0.2 ∙ 𝑥4 + 0.1 𝑥2 = 0.2 ∙ 𝑥1 + 0.3 ∙ 𝑥2 + 0.4 ∙ 𝑥3 + 0.2 ∙ 𝑥4 + 0.1 { 𝑥3 = 0.3 ∙ 𝑥1 + 0.2 ∙ 𝑥2 + 0.1 ∙ 𝑥3 + 0.2 ∙ 𝑥4 + 0.1 𝑥4 = 0.1 ∙ 𝑥1 + 0.1 ∙ 𝑥2 + 0.1 ∙ 𝑥3 + 0.1 ∙ 𝑥4 + 0.1 0.1 0.1 Let 𝑓 = (0.1 0.1 0.1) be a free vector, 𝑥1 = (0.1) be a start value. We get the results: 0.1 0.1 Table 5: Start Parameters Matrix А 𝜌(𝐴) Free vector f The precise Initial solution x* value x1 0.1 0.2 0.3 0.2 0.1 0.471 0.1 (0.2 0.3 0.4 0.2) 0.787 𝑓 = (0.1) (0.629) (0.1) 0.3 0.2 0.1 0.2 0.1 0.471 0.1 0.1 0.1 0.1 0.1 0.1 0.286 0.1 Table 6: Method of Successive Approximations Values\Number of iteration n=1 n=10 n=20 n=30 n=33 x1( n ) 0.18 0.437 0.468 0.471 0.471 88 x 2( n ) 0.21 0.58 0.624 0.628 0.629 x 3( n ) 0.18 0.438 0.468 0.471 0.471 x 4( n ) 0.14 0.269 0.284 0.286 0.286 Table 7: Seidel method Values\Number of iteration n=1 n=10 n=15 n=16 n=17 x1( n ) 0.296 0.461 0.47 0.47 0.471 x 2( n ) 0.196 0.615 0.626 0.627 0.629 x 3( n ) 0.178 0.463 0.47 0.471 0.471 x 4( n ) 0.150 0.282 0.285 0.285 0.286 Table 8: Mixed method Values\Number of iteration n=1 n=2 n=3 x1( n ) 0.498 0.471 0.471 x 2( n ) 0.648 0.628 0.629 x 3( n ) 0.498 0.471 0.471 x 4( n ) 0.299 0.285 0.286 In this case, the mixed method has a priority of thirty iteration order as compared with the method of successive approximations and a priority of fourteen iterations as compared with Seidel method. 3.3 The Third Example Let consider the system of fifth equations with five unknown variables. 𝑥1 = 0.1 ∙ 𝑥1 + 0.2 ∙ 𝑥2 + 0.1 ∙ 𝑥3 + 0.2 ∙ 𝑥4 + 0.1 ∙ 𝑥5 + 0.1 𝑥2 = 0.2 ∙ 𝑥1 + 0.1 ∙ 𝑥2 + 0.2 ∙ 𝑥3 + 0.1 ∙ 𝑥4 + 0.2 ∙ 𝑥5 + 0.1 𝑥3 = 0.1 ∙ 𝑥1 + 0.1 ∙ 𝑥2 + 0.2 ∙ 𝑥3 + 0.2 ∙ 𝑥4 + 0.1 ∙ 𝑥5 + 0.1 𝑥4 = 0.2 ∙ 𝑥1 + 0.2 ∙ 𝑥2 + 0.1 ∙ 𝑥3 + 0.1 ∙ 𝑥4 + 0.2 ∙ 𝑥5 + 0.1 {𝑥5 = 0.1 ∙ 𝑥1 + 0.1 ∙ 𝑥2 + 0.1 ∙ 𝑥3 + 0.1 ∙ 𝑥4 + 0.1 ∙ 𝑥5 + 0.1 89 Table 9: Start Parameters Matrix А 𝜌(𝐴) Free vector f The precise solution Initial value x1 x* 0.1 0.2 0.1 0.2 0.1 0.1 0.339 0.1 0.2 0.1 0.2 0.1 0.2 0.7 0.1 0.361 0.1 0.1 0.1 0.2 0.2 0.1 𝑓 = 0.1 0.337 0.1 0.2 0.2 0.1 0.1 0.2 0.1 0.363 0.1 (0.1 0.1 0.1 0.1 0.1) (0.1) (0.267) (0.1) We get the following results: Table 10: Method of Successive Approximations Values\Number of iteration n=1 n=5 n=10 n=20 n=24 x1( n ) 0.8 0.455 0.359 0.34 0.339 x 2( n ) 0.9 0.486 0.382 0.361 0.361 x 3( n ) 0.8 0.452 0.356 0.337 0.337 x 4( n ) 0.9 0.49 0.384 0.364 0.363 x5( n ) 0.6 0.347 0.280 0.267 0.267 Table 11: Seidel method Values\Number of iteration n=1 n=5 n=10 n=14 n=15 x1( n ) 0.776 0.345 0.342 0.339 0.339 x 2( n ) 0.81 0.366 0.364 0.361 0.361 x 3( n ) 0.721 0.341 0.339 0.337 0.337 x 4( n ) 0.809 0.367 0.366 0.364 0.363 x 5( n ) 0.534 0.269 0.268 0.267 0.267 90 Table 12: Mixed method Values\Number of iteration n=1 n=2 n=3 n=4 x1( n ) 0.34 0.341 0.339 0.339 x 2( n ) 0.374 0.361 0.361 0.361 x 3( n ) 0.34 0.337 0.336 0.337 x 4( n ) 0.374 0.364 0.363 0.363 x 5( n ) 0.271 0.267 0.267 0.267 As can be seen, four iterations of method of one-parameter iterative aggregation result in precise solution to within 10-4, while the method of successive approximations convergences on twenty forth iteration and Seidel method on fifteens iteration. 4 Conclusion These computational experiments indicate that the proposed modification method of one-parameter iterative aggregation has the higher speed of convergence than Seidel method for the large values of spectral radius 𝜌(𝐴) and the faster than the method of successive approximations. The above mentioned method can significantly speed up the convergence to the precise solution, that’s a big advantage. References [MEU99] Meurant G. Computer Solution of Large Linear Systems, Volume 28 1st Edition, 1999 [GRO14] Grobova T.A, Pilipenko A.V., Denisenko I.V. The convergence of method of iterative aggregation for solving systems of linear algebraic equations depending on the amount of free vectors, Infocom 2014. p. 96-99, 2014 [KRA69] Krasnoselsky М.А., Vainikko G.М., Zabreiko P.P., Ryticky Y.B.,Statsenko V.Y. Approximate solution of operator equations., 1969. [Gro11] Grobova T.A. Investigation of properties of nonlinear operator multiparameter iterative aggregation. Science. Innovations. Technologies. p. 26-30, 2011 [Arh75] Arhangelsky U.S., Vahytinsky I.A., Dudkin L.M. and etc. Numerical studies of iterative aggregation methods for solving the problem of multiproduction balance. Automatics and telemechanic. p. 75-82, 1975 [Bab82] Babadgayan A.A. About the rate of convergence of an iterative one aggregation method. Automatics and telemechanic. p. 171-173, 1982 [Dud79] Edited by Dudkin L.M. Iterative aggregation and use it in planning. 1979 [Gro01] Grobova T.A. About the method of one-parameter iterative aggregation for solving system of linear and nonlinear algebraic equations, integral equations. 2001. [Gro 01] Grobova T.A. About a new modification Seidel method. Scientific and methodological conference for professors and students «XXI century – age of education», p. 12-16. 2001. [Gro 01] Grobova T.A., Stetsenko V.Y. A method of multiparameter iterative aggregation for solving integral equations. 28: p. 12-16. 2001. [Gol04] Golikov A.I., Evtushenko U.G. Method of the solution of linear programming problems of large dimension. DAN, t. 397, N6, p. 727-732. 2004. 91