Mathematical Modeling for Systems of Large Dimension Through a Modification of the Method of Iterative Aggregation

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

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 If there is an operator inverse to the operator (I-A1), then the equation (1) will be such that Using the method of successive approximations to (3), we get

m  1,2,...

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

0t1 0 (2  c) c (1  c) 2 1

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  fi (n 1, n) (9)

j1 Let x=x1 for solution x* of equation (9) and l0(x) be a functionality: (2) (3) (4) (5) (6) (7) (8) n l0 (x)   xi i1

(x  (x1 , x2 ,..., xn )) ,

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 : ≥ . If the condition (17) is true, that the equation (16) has a unique solution t=t(x1) and t(x1) be Finally, let find the element x2: Using induction, we have the assertion (20): l0 (x1 )  l0 (I  A1 1 A2 x1 ) 0 t( x1 ) 

l0 I  A1 1  f  l0 ( x1 )  l0 I  A1 1 A2 x1 

x2 t(x1) Ax1  f xm1  t(xm ) Axm  f (m 1, 2, ...) When the value t=t(x1) is founded, let find an element x2 by using the formula: Using induction, we have the assertion (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  l0 (I  A1 )1  f  where t be an unknown scalar.

Let we have the condition (17) ( 11 ) (12) (13) (14) (15) (16) (17) (18) (19) (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. 3.1 The first example Let consider the system of linear algebraic equations Values\Number of iteration n=1 1.06 0.73 0.74 n=1 1.06 0.742 0.706 Let consider the modification of method of iterative aggregation – «mixed method». n=20 0.757 0.46 0.487 n=15 0.757 0.46 0.487 0.757 0.46 0.487 n=20 0.757 0.46 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.

0.1 0.1 Let = (00..11)be a free vector, 1 = (00..11) be a start value. We get the results: 0.1 0.1

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 n=1 0.468 n=30 Values\Number of 3.3 The Third Example Let consider the system of fifth equations with five unknown variables.

1 = 0.1 ∙ 1 + 2 = 0.2 ∙ 1 + 3 = 0.1 ∙ 1 + 4 = 0.2 ∙ 1 + { 5 = 0.1 ∙ 1 + 0.2 ∙ 2 + 0.1 ∙ 2 + 0.1 ∙ 2 + 0.2 ∙ 2 + 0.1 ∙ 2 + 0.1 ∙ 3 + 0.2 ∙ 3 + 0.2 ∙ 3 + 0.1 ∙ 3 + 0.1 ∙ 3 + 0.2 ∙ 4 + 0.1 ∙ 4 + 0.2 ∙ 4 + 0.1 ∙ 4 + 0.1 ∙ 4 + 0.1 ∙ 5 + 0.1 0.2 ∙ 5 + 0.1 0.1 ∙ 5 + 0.1 0.2 ∙ 5 + 0.1 0.1 ∙ 5 + 0.1 0.1 0.2 0.1 0.2 ( 0.1 0.2 0.1 0.1 0.2 0.1 n=10 0.359 0.382 0.356 0.384 0.280 n=10 0.342 0.364 0.339 0.366 0.268

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 .