Generalized interval AOR method for solving interval linear equations

Jahnabi Chakravarty; Manideepa Saha

doi:10.3934/mfc.2023035

Article Contents

2025, Volume 8, Issue 1: 16-35. Doi: 10.3934/mfc.2023035

This issue Previous Article Study on the well-posedness of stochastic Boussinesq equations with Navier boundary conditions Next Article On interval-valued vector variational-like inequalities and vector optimization problems with generalized approximate invexity via convexificators

Generalized interval AOR method for solving interval linear equations

Jahnabi Chakravarty and
Manideepa Saha^,

Department of Mathematics, National Institute of Technology Meghalaya, Shillong, India-793003

^*Corresponding author: Manideepa Saha
^*Corresponding author: Manideepa Saha

Received: April 2023

Revised: July 2023

Early access: August 21, 2023

Published online: August 21, 2023

Abstract / Introduction Full Text(HTML) Figure(3) / Table(6) Related Papers Cited by

Abstract

Interval accelerated overrelaxation (IAOR) method to solve interval linear systems, was first introduced by Cvetković and Herceg in 1989 and convergence of which were discussed for a few classes of interval matrices. In this paper we introduce a generalization of IAOR method and termed it as generalized interval accelerated overrelaxation (GIAOR) method. We discuss the convergence of the proposed method for solving interval linear systems of equations with interval strictly diagonally dominant matrices, interval $ M $-matrices, irreducible interval $ M $-matrices or interval $ H $-matrices as the coefficient interval matrices of the systems. At last numerical examples are studied for each type of mentioned interval matrices illustrating the efficiency of the proposed method.

Keywords:

Mathematics Subject Classification: 15A30, 65G40, 65H10; Secondary: 65G30.

Citation:

Full Text(HTML)

Figure 1. Plot of the residual vs iteration with bandwidth $ m = 0,1,2,3 $

Download: Full-size image PowerPoint slide

Figure 2. Plot of residual vs iteration with bandwidth m = 0, 1, 2

Download: Full-size image PowerPoint slide

Figure 3. Plot of residual vs no. of iterations with $ m = 0,1,2 $

Download: Full-size image PowerPoint slide

Table 1. Enclosure of the solution set for $ m = 3 $

GIAOR	GISOR	GIGS	GIJ
$ {\bf{x}}=\left(\begin{array}{l} {[-1.9166,1.3166]} \\ {[-2.0099,1.4099]} \\ {[-0.8980,2.2980]} \\ {[-1.3166,1.9166]} \\ {[-1.6451,1.6451]} \end{array}\right)$	$ {\bf{x}}=\left(\begin{array}{l} {[-1.9165,1.3165]} \\ {[-2.0099,1.4099]} \\ {[-0.8979,2.2979]} \\ {[-1.3166,1.9166]} \\ {[-1.6451,1.6451]} \end{array}\right)$	$ {\bf{x}}=\left(\begin{array}{l} {[-1.9153,1.3153]} \\ {[-2.0086,1.4086]} \\ {[-0.8967,2.2967]} \\ {[-1.3154,1.9154]} \\ {[-1.6442,1.6442]} \end{array}\right)$	$ {\bf{x}}=\left(\begin{array}{l} {[-1.9154,1.3154]} \\ {[-2.0087,1.4087]} \\ {[-0.8968,2.2968]} \\ {[-1.3154,1.9154]} \\ {[-1.6442,1.6442]} \end{array}\right)$

| Show Table

DownLoad: CSV

Table 2. Numerical result for the interval SDD-matrix with $ m = 0,1,2,3 $

$ m $	Iterative method	No. of iterations	$ r_k $	Time in second
0	IAOR	$ 47 $	$ 3.731\times10^{-4} $	$ 0.0227 $
	ISOR	$ 31 $	$ 3.729\times 10^{-4} $	$ 0.0236 $
	IGS	$ 31 $	$ 3.739\times 10^{-4} $	$ 0.0211 $
	IJ	$ 50 $	$ 3.722 \times 10^{-4} $	$ 0.0288 $
1	GIAOR	$ 32 $	$ 8.186\times 10^{-4} $	$ 0.0174 $
	GISOR	$ 19 $	$ 7.626\times 10^{-4} $	$ 0.0118 $
	GIGS	$ 19 $	$ 3.726\times 10^{-4} $	$ 0.0227 $
	GIJ	$ 35 $	$ 2.884\times 10^{-4} $	$ 0.0194 $
2	GIAOR	$ 18 $	$ 2.871\times 10 ^{-3} $	$ 0.0328 $
	GISOR	$ 11 $	$ 1.918\times 10^{-3} $	$ 0.0022 $
	GIGS	$ 11 $	$ 3.061\times 10^{-4} $	$ 0.0251 $
	GIJ	$ 19 $	$ 1.207\times 10^{-3} $	$ 0.0286 $
3	GIAOR	$ 11 $	$ 2.481\times 10^{-3} $	$ 0.0236 $
	GISOR	$ 8 $	$ 2.399\times 10^{-3} $	$ 0.0079 $
	GIGS	$ 8 $	$ 2.619\times 10^{-4} $	$ 0.0075 $
	GIJ	$ 12 $	$ 1.303\times 10^{-4} $	$ 0.0091 $

| Show Table

DownLoad: CSV

Table 3. Enclosure of the solution set for the interval $ M $-matrix with $ m = 2 $

GIAOR	GISOR	GIGS	GIJ
$ {\bf{x}}=\left(\begin{array}{l} {[-2.6722,3.6936]} \\ {[-3.1839,4.4323]} \\ {[-2.3472,3.5459]} \\ {[-3.5365,4.0551]} \end{array}\right)$	$ {\bf{x}}=\left(\begin{array}{l} {[-2.6722,3.6936]} \\ {[-3.1840,4.4324]} \\ {[-2.3472,3.5459]} \\ {[-3.5366,4.0552]} \end{array}\right)$	$ {\bf{x}}=\left(\begin{array}{l} {[-2.6674,3.6888]} \\ {[-3.1781,4.4264]} \\ {[-2.3425,3.5412]} \\ {[-3.5309,0.0495]} \end{array}\right)$	$ {\bf{x}}=\left(\begin{array}{l} {[-2.6672,3.6886]} \\ {[-3.1780,4.4264]} \\ {[-2.3424,3.5411]} \\ {[-3.5307,4.0493]} \end{array}\right)$

| Show Table

DownLoad: CSV

Table 4. Numerical result for the interval $ M $-matrix with $ m = 0,1,2 $

$ m $	Iterative method	No. of iterations	$ r_k $	Time in second
0	IAOR	$ 77 $	$ 4.01\times 10^{-3} $	$ 0.0251 $
	ISOR	$ 59 $	$ 4.01\times 10^{-3} $	$ 0.0183 $
	IGS	$ 59 $	$ 2.50 \times 10^{-3} $	$ 0.0126 $
	IJ	$ 110 $	$ 2.48\times 10^{-3} $	$ 0.0299 $
1	GIAOR	$ 41 $	$ 4.53\times 10^{-3} $	$ 0.0151 $
	GISOR	$ 29 $	$ 4.78\times 10^{-3} $	$ 0.0128 $
	GIGS	$ 29 $	$ 2.48\times 10^{-3} $	$ 0.0126 $
	GIJ	$ 53 $	$ 2.45\times 10^{-3} $	$ 0.0177 $
2	GIAOR	$ 18 $	$ 4.65\times 10^{-3} $	$ 0.0104 $
	GISOR	$ 13 $	$ 4.12\times 10^{-3} $	$ 0.0086 $
	GIGS	$ 13 $	$ 2.32 \times 10^{-3} $	$ 0.0087 $
	GIJ	$ 22 $	$ 2.14\times 10^{-3} $	$ 0.0114 $

| Show Table

DownLoad: CSV

Table 5. Enclosure of the solution set for the interval $ H $-matrix with $ m = 2 $

GIAOR	GISOR	GIGS	GIJ
$ {\bf{x}}=\left(\begin{array}{l} {[-0.3826,0.2675]} \\ {[-0.2797,0.4191]} \\ {[-0.2920,0.3587]} \\ {[-0.2010,0.0985]} \end{array}\right)$	$ {\bf{x}}=\left(\begin{array}{l} {[-0.3832,0.2681]} \\ {[-0.2810,0.4204]} \\ {[-0.2937,0.3604]} \\ {[-0.2019,0.0995]} \end{array}\right)$	$ {\bf{x}}=\left(\begin{array}{l} {[-0.3831,0.2681]} \\ {[-0.2808,0.4202]} \\ {[-0.2936,0.3602]} \\ {[-0.2019,0.0995]} \end{array}\right)$	$ {\bf{x}}=\left(\begin{array}{l} {[-0.3890,0.2739]} \\ {[-0.2909,0.4303]} \\ {[-0.3065,0.3732]} \\ {[-0.2125,0.1101]} \end{array}\right)$

| Show Table

DownLoad: CSV

Table 6. Numerical result for the interval $ H $-matrix with $ m = 0,1,2 $

$ m $	Iterative method	No. of iterations	$ r_k $	Time in second
0	IAOR	$ 32 $	$ 3.373 \times 10^{-2} $	$ 0.0153 $
	ISOR	$ 21 $	$ 2.313 \times 10^{-2} $	$ 0.0121 $
	IGS	$ 21 $	$ 2.315 \times 10^{-2} $	$ 0.0123 $
	IJ	$ 34 $	$ 3.696 \times 10^{-2} $	$ 0.0188 $
1	GIAOR	$ 22 $	$ 5.062\times 10^{-2} $	$ 0.0128 $
	GISOR	$ 12 $	$ 3.791 \times 10^{-2} $	$ 0.0107 $
	GIGS	$ 12 $	$ 3.778 \times 10^{-2} $	$ 0.0112 $
	GIJ	$ 24 $	$ 5.426 \times 10^{-2} $	$ 0.0135 $
2	GIAOR	$ 12 $	$ 3.926 \times 10^{-2} $	$ 0.0401 $
	GISOR	$ 7 $	$ 4.164 \times 10^{-2} $	$ 0.0095 $
	GIGS	$ 7 $	$ 4.141 \times 10^{-2} $	$ 0.0125 $
	GIJ	$ 13 $	$ 6.121\times 10^{-2} $	$ 0.0139 $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	G. Alefeld and J. Herzberger, Introduction to Interval Computation, Academic press, 2012.
[2]	A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Science, Classics Appl. Math., 9. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. doi: 10.1137/1.9781611971262.
[3]	J. Chakravarty, A. Athikho and M. Saha, Convergence of interval AOR method for linear interval equations, Numer. Algebra Control Optim., 12 (2022), 293-308. doi: 10.3934/naco.2021006.
[4]	S. Chakraverty, M. Hladík and N. R. Mahato, A sign function approach to solve algebraically interval system of linear equations for nonnegative solutions, Fundamenta Informaticae, 152 (2017), 13-31. doi: 10.3233/FI-2017-1510.
[5]	J. Chakravarty and M. Saha, Generalization of interval Jacobi and Gauss-Seidel methods for interval linear system, Journal of Computational Analysis & Applications, 31 (2023).
[6]	D. Cordes and E. Kaucher, Self-validating computation for sparse matrix problems, Computer Arithmetic: Scientific Computation and Programming Languages, (1987), 133-149.
[7]	L. Cvetković and D. Herceg, The AOR method for solving linear interval equations, Computing, 41 (1989), 359-364. doi: 10.1007/BF02241224.
[8]	M. T. Darvishi and P. Hessari, On convergence of the generalized AOR method for linear systems with diagonally dominant coefficient matrices, Applied Mathematics and Computation, 176 (2006), 128-133. doi: 10.1016/j.amc.2005.09.051.
[9]	A. Frommer and D. B. Szyld, H-splittings and two-stage iterative methods, Numerische Mathematik, 63 (1992), 345-356. doi: 10.1007/BF01385865.
[10]	M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Ser. Books Math. Sci., W. H. Freeman and Co., San Francisco, CA, 1979.
[11]	A. Hadjidimos, Accelerated overrelaxation method, Mathematics of Computation, 32 (1978), 149-157. doi: 10.1090/S0025-5718-1978-0483340-6.
[12]	M. Hladík, Interval linear programming: A survey, Linear Programming: New Frontiers in Theory and Applications, Nova Science Publishers, New York, (2012), 85-120.
[13]	M. Hladík, New Operator and method for solving real interval preconditioned interval linear equations, SIAM J. Numer. Anal., 52 (2014), 194-206. doi: 10.1137/130914358.
[14]	M. Hladík and J. Horáček, Interval linear programming techniques in constraint programming and global optimization, Constraint Programming and Decision Making, 539 (2014), 44-59.
[15]	M. Hladík and I. Skalna, Relation between various methods for solving linear interval and parametric equations, Linear Alg. Appl., 574 (2019), 1-21. doi: 10.1016/j.laa.2019.03.019.
[16]	R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 1990.
[17]	R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, 1994.
[18]	R. E. Moore, Methods and Applications of Interval Analysis, SIAM, Philadelphia, PA, 1979.
[19]	A. Neumaier, New techniques for the analysis of linear interval equations, Linear Algebra and its Applications, 58 (1984), 273-325. doi: 10.1016/0024-3795(84)90217-9.
[20]	A. Neumaier, Interval Methods for Systems of Equations, Encyclopedia Math. Appl., 37. Cambridge University Press, Cambridge, 1990.
[21]	W. Oettli, On the solution set of a linear system with inaccurate coefficients, SIAM Journal of Numerical Analysis, 2 (1965), 115-118. doi: 10.1137/0702009.
[22]	K. Perumandla and S. Chakraverty, Solving fully interval linear systems of equations using tolerable solution criteria, Soft Computing, 22 (2018), 4811-4818.
[23]	L. Qingrong and J. Zhiying, The SOR method for solving linear interval equations, Volume 87 of Freiburger Intervall-Berichte, 1987.
[24]	J. Rohn, Systems of linear interval equations, Linear Algebra and its Applications, 126 (1989), 39-78. doi: 10.1016/0024-3795(89)90004-9.
[25]	J. Rohn, Solvability of systems of linear interval equations, SIAM Journal of Matrix Analysis and its Applications, 25 (2003), 237-245. doi: 10.1137/S0895479801398955.
[26]	J. Rohn and S. P. Shary, Interval matrices: Regularity generates singularity, Linear Algebra and its Applications, 540 (2018), 149-159. doi: 10.1016/j.laa.2017.11.020.
[27]	S. M. Rump, INTLAB-INTerval LABoratory, Springer, Dordrecht, (1999), 77-104.
[28]	Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. doi: 10.1137/1.9780898718003.
[29]	M. Saha and J. Chakravarty, Convergence of generalized SOR, Jacobi and Gauss-Seidel methods for linear systems, International Journal of Applied and Computational Mathematics, 6 (2020), Paper No. 77, 12 pp. doi: 10.1007/s40819-020-00830-5.
[30]	D. K. Salkuyeh, Generalized Jacobi and Gauss-Seidel methods for solving linear system of equations, Numer. Math. J. Chinese Univ. (English Ser.), 16 (2007), 164-170.
[31]	D. K. Salkuyeh, Generalized AOR method for solving system of linear equations, Australian J. of Basic and Appl. Sci., 5 (2011), 351-358.
[32]	H. Schwandt, An interval arithmetic approach for the construction of an almost globally convergent method for the solution of the nonlinear Poisson equation on the unit square, SIAM Journal on Scientific and Statistical Computing, 5 (1984), 427-452. doi: 10.1137/0905032.
[33]	S. P. Shary, A new technique in systems analysis under interval uncertainty and ambiguity, Reliable Computing, 8 (2002), 321-418. doi: 10.1023/A:1020505620702.
[34]	S. P. Shary, Interval Gauss-Seidel method for generalized solution sets to interval linear systems, Reliable Computing, 7 (2001), 141-155. doi: 10.1023/A:1011422215157.
[35]	R. S. Varga, Matrix Iterative Analysis, Prentice-Hall, Englewood Cliffs, NJ, 1962.