Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Upper triangulation-based infinity norm bounds for the inverse of Nekrasov matrices with applications

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

The infinity norm bounds for the inverse of Nekrasov matrices play an important role in scientific computing. We in this paper propose a triangulation-based approach that can easily be implemented to seek sharper infinity norm bounds for the inverse of Nekrasov matrices. With the help of such sharper bounds, new error estimates for the linear complementarity problem of Nekrasov matrices are presented, and a new infinity norm estimate of the iterative matrix of parallel-in-time methods for an all-at-once system from Volterra partial integral-differential problems is given. Finally, these new bounds are compared with other state-of-the-art results so that the effectiveness of our proposed results is verified.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Algorithm 2
Fig. 1

Similar content being viewed by others

Data availability

Data sharing is not applicable to this article as no new data were created or analyzed in this study.

References

  1. Berman, A., Plemmons, R.J.: Nonnegative matrices in the mathematical sciences. Academic Press, New York, NY (1979)

    Google Scholar 

  2. Cvetković, L., Dai, P.F., Doroslovačkic, K., Li, Y.T.: Infinity norm bounds for the inverse of Nekrasov matrices. Appl. Math. Comput. 219, 5020–5024 (2013)

    MathSciNet  Google Scholar 

  3. Cvetković, L., Kostić, V., Doroslovačkic, K.: Max-norm bounds for the inverse of \(S\)-Nekrasov matrices. Appl. Math. Comput. 218, 9498–9503 (2012)

    MathSciNet  Google Scholar 

  4. Cottle, R.W., Pang, J.S., Stone, R.E.: The linear complementarity problem. SIAM, Philadelphia, PA (2009)

  5. Chen, X.J., Xiang, S.H.: Computation of error bounds for \(P\)-matrix linear complementarity problems. Math. Program. Ser. A 106, 513–525 (2006)

    Article  MathSciNet  Google Scholar 

  6. Chen, X.J., Xiang, S.H.: Perturbation bounds of \(P\)-matrix linear complementarity problems. SIAM J. Optim. 18, 1250–1265 (2007)

    Article  MathSciNet  Google Scholar 

  7. Dai, P.F., Li, J.C., Li, Y.T., Zhang, C.Y.: Error bounds for linear complementarity problems of \(QN\)-matrices. Calcolo 53, 647–657 (2016)

    Article  MathSciNet  Google Scholar 

  8. Dai, P.F., Li, J.C., Bai, J., Dong, L.: Notes on new error bounds for linear complementarity problems of Nekrasov matrices, \(B\)-Nekrasov matrices and \(QN\)-matrices. Numer. Math. Theor. Meth. Appl. 12(4), 1191–1212 (2019)

    Article  MathSciNet  Google Scholar 

  9. Demmel, J., Koev, P.: Accurate SVDs of weakly diagonally dominant \(M\)-matrices. Numer. Math. 98, 99–104 (2004)

    Article  MathSciNet  Google Scholar 

  10. Demmel, J., Dumitriu, I., Holtz, O., Koev, P.: Accurate and efficient expression evaluation and linear algebra. Acta Numer. 17, 87–145 (2008)

    Article  MathSciNet  Google Scholar 

  11. Gudkov, V.V.: On a certain test for nonsingularity of matrices. Latv. Mut. Ezhegodnik 1965, Zinatne, Riga, 385–390, 1966. (MR 33, 1967, No. 1323)

  12. García-Esnaola, M., Peña, J.M.: A comparison of error bounds for linear complementarity problems of \(H\)-matrices. Linear Algebra Appl. 433, 956–964 (2010)

    Article  MathSciNet  Google Scholar 

  13. García-Esnaola, M., Peña, J.M.: Error bounds for linear complementarity problems of Nekrasov matrices. Numer. Algor. 67, 655–667 (2014)

    Article  MathSciNet  Google Scholar 

  14. García-Esnaola, M., Peña, J.M.: \(B\)-Nekrasov matrices and error bounds for linear complementarity problems. Numer. Algor. 72, 435–445 (2016)

    Article  MathSciNet  Google Scholar 

  15. Gao, L., Liu, Q.L.: New upper bounds for the infinity norm of Nekrasov matrices. J. Math. Inequal. 14(3), 723–733 (2020)

    Article  MathSciNet  Google Scholar 

  16. Gu, X.M., Wu, S.L.: A parallel-in-time iterative algorithm for Volterra partial integro-differential problems with weakly singular kernel. J. Comput. Phys. 417, 109576 (2020)

    Article  MathSciNet  Google Scholar 

  17. Kolotilina, L.Y.: On bounding inverse to Nekrasov matrices in the infinity norm. J. Math. Sci. 199, 432–437 (2014)

    Article  MathSciNet  Google Scholar 

  18. Liu, J.Z., Xiong, Y., Liu, Y.: The closure property of the Schur complement for Nekrasove matrices and its applications in solving large linear systems with Schur-based method. Comput. Appl. Math. 39, 290 (2020)

    Article  MathSciNet  Google Scholar 

  19. Liu, J.Z., Zhang, J., Zhou, L., Tu, G.: The Nekrasov diagonally dominant degree on the Schur complement of Nekrasov matrices and its applications. Appl. Math. Comput. 320, 251–263 (2018)

    MathSciNet  Google Scholar 

  20. Lyu, Z.H., Wang, X., Wen, L.: \(K\)-subdirect sums of Nekrasov matrices. Electron. J. Linear Algebra. 38, 339–346 (2022)

    Article  MathSciNet  Google Scholar 

  21. Li, C.Q., Li, Y.T.: Note on error bounds for linear complementarity problems for \(B\)-matrices. Appl. Math. Lett. 57, 108–113 (2016)

    Article  MathSciNet  Google Scholar 

  22. Li, C.Q., Pei, H., Gao, A.N., Li, Y.T.: Improvements on the infinity norm bound for the inverse of Nekrasov matrices. Numer. Algor. 71, 613–630 (2016)

    Article  MathSciNet  Google Scholar 

  23. Li, C.Q., Dai, P.F., Li, Y.T.: New error bounds for linear complementarity problems of Nekrasov matrices and \(B\)-Nekrasov matrices. Numer. Algor. 74, 997–1009 (2017)

    Article  MathSciNet  Google Scholar 

  24. Nedovič, M., Cvetković, L.: Norm bounds for the inverse and error bounds for linear complementarity problems for \(\{P_1\), \(P_2\}\)-Nekrasov matrices. Filomat 35, 239–250 (2021)

    Article  MathSciNet  Google Scholar 

  25. Orera, H., Peña, J.M.: Infinity norm bounds for the inverse of Nekrasov matrices using scaling matrices. Appl. Math. Comput. 358, 119–127 (2019)

    MathSciNet  Google Scholar 

  26. Robert, F.: Blocs-\(H\)-matrices et convergence des methodes iteratives classiques par blocs. Linear Algebra Appl. 2, 223–265 (1969)

    Article  MathSciNet  Google Scholar 

  27. Szulc, T.: Some remarks on a theorem of Gudkov. Linear Algebra Appl. 225, 221–235 (1995)

    Article  MathSciNet  Google Scholar 

  28. Schäfer, U.: An enclosure method for free boundary problems based on a linear complementarity problem with interval data. Numer. Func. Anal. Optim. 22, 991–1011 (2001)

    Article  MathSciNet  Google Scholar 

  29. Stewart, G.: Matrix algorithms Vol. I: Basic Decompositions. SIAM, Philadelphia, PA (1998)

  30. Varah, J.M.: A lower bound for the smallest singular value of a matrix. Linear Algebra Appl. 11, 3–5 (1975)

    Article  MathSciNet  Google Scholar 

  31. Wang, S.Y., Liang, X.N., Zhou, Y.M., Lyu, Z.H.: Two infinity norm bounds for the inverse of Nekrasov matrices. Linear Multilinear A., (2023). https://doi.org/10.1080/03081087.2023.2195150

  32. Xue, J., Li, C.Q., Li, Y.T.: On subdirect sums of Nekrasov matrices. Linear Multilinear A., (2023). https://doi.org/10.1080/03081087.2023.2172378

  33. Zhao, Y.L., Gu, X.M., Ostermann, A.: A preconditioning technique for an all-at-once system from Volterra subdiffusion equations with graded time steps. J. Sci. Comput. 88, 11 (2021)

    Article  MathSciNet  Google Scholar 

Download references

Funding

This work was supported by the National Natural Science Foundations of China (12061087, 61962059, and 31600299), the Young Science and Technology Nova Program of Shaanxi Province (2022KJXX-01), the Scientific Research Fund of Yunnan Department of Education (2022J0949), the Sichuan Science and Technology Program (2022ZYD0006), and Guanghua Talent Project of Southwestern University of Finance and Economics.

Author information

Authors and Affiliations

  1. College of Mathematics and Computer Science, Yan’an University, Yan’an, 716000, People’s Republic of China

    Lei Gao

  2. School of Mathematics, Southwestern University of Finance and Economics, Chengdu, 611130, People’s Republic of China

    Xian-Ming Gu

  3. School of Mathematics and Information Science, Baoji University of Arts and Sciences, Baoji, 721013, People’s Republic of China

    Xiudan Jia

  4. School of Mathematics and Statistics, Yunnan University, Kunming, 650091, People’s Republic of China

    Chaoqian Li

Authors
  1. Lei Gao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xian-Ming Gu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xiudan Jia
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Chaoqian Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

LG (first author): conceptualization, methodology, writing—original draft. X-MG (second author): methodology, writing—original draft. XJ (third author): data curation, visualization, investigation, writing—original draft. CL (fourth author, corresponding author): conceptualization, writing—review and editing. All authors reviewed the manuscript.

Corresponding author

Correspondence to Chaoqian Li.

Ethics declarations

Ethical approval

Not applicable

Conflict of interest

The authors declare no competing interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gao, L., Gu, XM., Jia, X. et al. Upper triangulation-based infinity norm bounds for the inverse of Nekrasov matrices with applications. Numer Algor 97, 1453–1479 (2024). https://doi.org/10.1007/s11075-024-01758-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-024-01758-3

Keywords