Extrapolated triangular splitting method to interval system of linear algebraic equations

Document Type : Research Paper


1 Faculty of Mathematical Science, University of Tabriz, 51666-14766, Tabriz, Iran.

2 Federal Research Center for Information and Computational Technologies, (previously Institute of Computational Technologies SB RAS), Novosi-birsk, Russia.


This paper presents an extrapolated triangular splitting method (\texttt{ETrnSplit}) to find the formal solution for the interval system of linear algebraic equations in which this method uses Kaucher interval arithmetic. Some numerical experiments are given to show the efficiency of this method.


  • [1] P. Albrecht and M. P. Klein, Extrapolated iterative methods for linear systems approximation, SIAM J. Numer. Anal., 21(1) (1984), 192-201.
  • [2] G. Alefeld and G. Mayer, Interval analysis: theory and applications, J. Comput. Appl. Math., 121(1-2) (2000), 421-464.
  • [3] G. Birkho, Lattice theory, Colloquium Publications, 25, AMS, Providence, RI (1940).
  • [4] J. Brains, IntelliJ IDEA (2000). URL https://www.jetbrains.com/idea/
  • [5] E. Hansen, On the solution of linear algebraic equations with interval coefficients, Linear Algebra Appl., 2(2) (1969), 153-165.
  • [6] R. A. Horn and C. R. Johnson, Matrix Analysis (2nd ed.), Cambridge University Press, Cambridge, UK (2012).
  • [7] L. Jaulin, M. Kieer, O. Didrit, and E. Walter, Applied Interval Analysis, Springer, London (2001).
  • [8] A. Y. Karlyuk, Numerical method for finding algebraic solution to islae based on triangular splitting, Comput. technol. (in Russian), 4(4) (1999), 14-23.
  • [9] E. Kaucher, Über metrische und algebraische Eigenschaften einiger beim numerischen Rechnen auftretender Räume, Ph.D. dissertation, Universität Karlsruhe, Karlsruhe 1973.
  • [10] E. Kaucher, Algebraische erweiterungen der intervallrechnung unter erhaltung der ordnungs-und verbandsstruk- turen, in: Grundlagen der Computer-Arithmetik (R. Albrecht, U. Kulisch, eds.). Computing Supplementum, vol. 1. Springer, Vienna, (1977), 65-79.
  • [11] E. Kaucher, Interval analysis in the extended interval space IR, in: Fundamentals of Numerical Computation (Computer-Oriented Numerical Analysis) (G. Alefeld, R.D. Grigorieff, eds.). Computing Supplementum, Springer, Vienna, 2 (1980), 33-49.
  • [12] R. B. Kearfott, M. T. Nakao, A. Neumaier, S. M. Rump, S. P. Shary, and P. Van Hentenryck, Standardized notation in interval analysis, in: 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, 106-113.
  • [13] A. V. Lakeyev, Linear algebraic equations in kaucher arithmetic, Reliab. Comput., (Supplement (Extended Ab- stracts of APIC’95: International Workshop on Applications of Interval Computations, El Paso, TX, Febr. 23-25, 1995)) (1995), 130-133.
  • [14] P. Lancaster and M. Tismenetsky, The Theory of Matrices: With Applications, Academic Press, Orlando, FL, (1985).
  • [15] G. Y. Meng and R. P. Wen, Self-adaptive extrapolated gauss-seidel iterative methods, J. Math. Study, 48(1) (2015), 18-29.
  • [16] R. E. Moore, Methods and Applications of Interval Analysis, SIAM, Philadelphia, PA, (1979).
  • [17] S. Markov, An iterative method for algebraic solution to interval equations, Appl. Numer. Math., 30(2-3) (1999), 225-239.
  • [18] R. E. Moore, R. B. Kearfott and M. J. Cloud, Introduction to Interval Analysis, SIAM, Philadelphia, PA (2009).
  • [19] K. Nickel, Die Auflo¨sbarkeit linearer Kreisscheiben- und intervall-Gleichungssysteme, Linear Algebra Appl., 44 (1982), 19-40.
  • [20] A. Neumaier, Linear interval equations, in: Interval Mathematics 1985 (K. Nickel, ed.), IMath 1985. Lecture Notes in Computer Science, vol. 212, Springer, Berlin, Heidelberg, (1986), 109-120.
  • [21] A. Neumaier, Interval Methods for Systems of Equations, 37, Cambridge university press, Cambridge, UK (1990).
  • [22] W. Oettli, On the solution set of a linear system with inaccurate coefficients, J. SIAM Numer. Anal. Ser. B, 2(1) (1965), 115-118.
  • [23] W. Oettli and W. Prager, Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides, Numer. Math., 6(1) (1964), 405-409.
  • [24] J. Rohn, Inner solutions of linear interval systems, in: Interval Mathematics 1985 (K. Nickel, ed.), IMath 1985. Lecture Notes in Computer Science, vol. 212, Springer, Berlin, Heidelberg, (1986), 157-158.
  • [25] M. A. Sainz, E. Gardenes, and L. Jorba, Formal solution to systems of interval linear or non-linear equations, Reliab. Comput., 8(3) (2002), 189-211.
  • [26] S. P. Shary, A new technique in systems analysis under interval uncertainty and ambiguity, Reliab. Comput., 8(5) (2002), 321-418.
  • [27] S. P. Shary, Algebraic approach in the "outer problem" for interval linear equations, Reliab. Comput., 3(2) (1997), 103-135.
  • [28] S. P. Shary, Algebraic approach to the interval linear static identication, tolerance, and control problems, or one more application of kaucher arithmetic, Reliab. Comput., 2(1) (1996), 3-33.
  • [29] S. P. Shary, Parameter partition methods for optimal numerical solution of interval linear systems, in: Compu- tational Science and High Performance Computing III ( E. Krause, Y.I. Shokin, M. Resch, N. Shokina, eds.), Notes on Numerical Fluid Mechanics and Multidisciplinary Design, vol 101. Springer, Berlin, Heidelberg, (2008), 184-205.
  • [30] S. P. Shary, Numerical computation of algebraic solution to interval linear systems, Discrete Math (in Russian), (1996), 129-145.
  • [31] S. P. Shary, Numerical computation of formal solutions to interval linear systems of equations, arXiv preprint arXiv:1903.10272 (2019).
  • [32] S. P. Shary, On optimal solution of interval linear equations, SIAM J. Numer. Anal., 32(2) (1995), 610-630.
  • [33] S. P. Shary, Finite-Dimensional Interval Analysis, (XYZ Publishers, Institute of Computational Technologies SB RAS, Novosibirsk, 2020) (in Russian).
  • [34] R. Shokrpour and E. Ebadi, Extrapolated positive denite and positive semi-definite splitting methods for solving non-Hermitian positive definite linear systems, Appl. Math., 67(3) (2022), 251-272.
  • [35] R. Shokrpour and E. Ebadi, Extrapolated diagonal and off-diagonal splitting iteration method, Filomat, 36(8) (2022), 2749-59.
  • [36] R. S. Varga, Matrix Iterative Analysis, Springer Series in Computational Mathematics, 27, Springer Berlin, Heidelberg, 1999.
  • [37] M. E. Wieser and T. B. Coplen, Atomic weights of the elements 2009 (iupac technical report), Pure Appl. Chem., 83(2) (2010), 359-396.
  • [38] D. M. Young, Iterative Solution of Large Linear Systems, Academic Press, Orlando, FL (1971).
  • [39] V. Zyuzin, An iterative method for solving system of algebraic segment equations of the first order, Dierential Equations and the Theory of Functions, Saratov State University, Saratov (in Russian), (1990), 72-82.