Approach to Solve the Set of Linear Algebraic Equations with Interval Uncertainty of Data Given

The set of linear algebraic equations with interval matrixes of coefficients and interval right part is considered in the paper. The pseudosolution for such systems is introduced. The existence of pseudosolution for all interval sets of algebraic linear equations is proved in the paper, the way for pseudosolution analysis is shown on the basis of the solution the corresponding linear programming problem. It is necessary to use computation guaranteeing sufficient accuracy over standard data types of programming languages because of obtained problem degeneracy. Simplex method coupled with accurate rational-fractional computation gives effective solution to the problem. Coarse-grained parallelism for distributed computer systems with MPI is the instrument of realization. CUDA C software engineering is applied for accurate rational-fractional calculations.

Keywords

interval set of linear equations, pseudosolution of interval equation set, linear programming, exact comtutations.

References

1. Kearfott R.B., Nakao M.T., Neumaier A., Rump S.M., Shary S.P., van Hentenryck P. Standardized Notation in Interval Analysis. Proc. XIII Baikal International School-seminar: Optimization methods and their applications, Irkutsk, Baikal, July 2-8, 2005. Vol. 4 Interval analysis. Irkutsk, Institute of Energy Systems SB RAS, 2005, pp. 106-113.
2. Neumaier A. Interval Methods for Systems of Equations. Cambridge University Press, 1990.
3. Shary S.P. Solving the Linear Interval Tolerance Problem. Mathematics and Computers in Simulation, 1996, vol. 39, pp. 53-85.
4. Shary S.P. A New Technique in Systems Analysis Under Interval Uncertainty and Ambiguity. Reliable Computing, 2002, vol. 8, no. 5, pp. 321-418.
5. Shary S.P. An Interval Linear Tolerance Problem. Automation and Remote Control, 2004, vol. 65, no. 10, pp. 1653-1666.
6. Lakeyev A.V., Kreinovich V. Optimal Solution of Interval Linear Systems Is Intractable (np-Hard). Interval Computations, 1993, no. 1, pp. 6-14.
7. Lakeyev A.V., Kreinovich V. Np-Hard Classes of Linear Algebraic Systems with Uncertainties. Reliable Computing, 1997, no. 3, pp. 51-81.
8. Rohn J. Inner Solutions of Linear Interval Systems. Interval Mathematics and Springer Verlag, 1985, pp. 157-158.
9. Stecjuk P.I. Subgradient Methods with Space Trasform for Ravine Functions [Subgradientnye metody s preobrazovaniem prostranstva dlja minimizacii ovrazhnyh vypuklyh funkcij]. Mezhdunarodnaja konferencija Covremennye problemy prikladnoj matematiki i mehaniki: teorija, jeksperiment i praktika, posvjashhennaja 90-letiju so dnja rozhdenija akademika N.N. Janenko. [International Conference 'Recent Developments in Applied Mathematics and Mechanics: Theory, Experiment and Practice. Devoted to the 90th Anniversary of Academician N.N.Yanenko'], 2011. BibUrlAvailable at: http://conf.nsc.ru/niknik-90/ru/reportview/37828 (accessed 25 December 2013).
10. Interval'nyj analiz i ego prilozhenija [Interval Analysis and Application]. Available at: http://www.nsc.ru/interval (accessed 25 December 2013).
11. Ivanov V.K. About Linear Ill-Conditioned Problems [O linejnyh nekorrektnyh zadachah]. DAN USSR, 1962, vol. 145, no. 2, pp. 270-272.
12. Tihonov A.N., Arsenin V.Ja. Metody reshenija nekorrektnyh zadach [Ill-Posed Problems-Solving Procedures]. Moscow, Nauka, 1979. 285 p.
13. Panyukov A.V., Golodov V.A. Tehnika programmnoj realizacii algoritma reshenija sistemy linejnyh algebraicheskih uravnenij s interval'noj neopredelennost'ju v ishodnyh dannyh [Software Engendering for Algorithm of Solving a Linear Equation Set under Interval Uncertainty.] Parallel Computing and Control Problems (PACO'2012). Sixth international conference, Moscow, Russia, October 24-26, 2012, vol. 2, pp. 155-166.
14. The GNU MP Bignum Library. Available at: http://gmplib.org/(accessed 25 December 2013).
15. Panyukov A.V., Gorbik V.V. Using Massively Parallel Computations for Absolutely Precise Solution of the Linear Programming Problems. Automation and Remote Control, 2012, vol. 73, no. 2, pp. 276-290.
16. Schrijver A. Theory of Linear and Integer Programming. Wiley, 1998. 484 p.
17. Golodov V.A. Distibuted Symbolic Rational Calculations with the x86 and x64 Processors [Raspredelennye simvol'nye drobno-racional'nye vychislenija na processorah x86 i x64]. Parallel'nye vychislitel'nye tehnologii (PaVT'2012): trudy mezhdunarodnoj nauchnoj konferencii [Proc. Parallel Computational Technologies (PCT)]. Chelyabinsk: SUSU, 2012, pp. 719.
18. Panyukov A.V., Gorbik V.V. The Parallel Symplex-Method Achievements for Errorless Solving of Linear programming problems. Bulletin of the South Ural State university. Series "Mathematical Modelling, Programming & Computer Software", 2011, no. 25 (242), issue 9, pp. 107-118. (in Russian)