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

Structured backward error analysis for generalized saddle point problems

  • Published:
Advances in Computational Mathematics Aims and scope Submit manuscript

Abstract

Recently, the structured backward errors for the generalized saddle point problems with some different structures have been studied by some authors, but their results involve some Kronecker products, the vec-permutation matrices, and the orthogonal projection of a large block matrix which make them very expensive to compute when utilized for testing the stability of a practical algorithm or as an effective stopping criteria. In this paper, adopting a new technique, we present the explicit and computable formulae of the normwise structured backward errors for the generalized saddle point problems with five different structures. Our analysis can be viewed as a unified or general treatment for the structured backward errors for all kinds of saddle point problems and the derived results also can be seen as the generalizations of the existing ones for standard saddle point problems, including some Karush-Kuhn-Tucker systems. Some numerical experiments are performed to illustrate that our results can be easily used to test the stability of practical algorithms when applied some physical problems. We also show that the normwise structured and unstructured backward errors can be arbitrarily far apart in some certain cases.

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

Similar content being viewed by others

References

  1. Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numer. 14, 1–137 (2005)

    Article  MathSciNet  Google Scholar 

  2. Björck, Å.: Numerical Methods for Least Squares Problems. SIAM, Philadelphia (1996)

  3. Bunch, J.R.: The weak and strong stability of algorithms in numerical linear algebra. Linear Algebra Appl. 88/89, 49–66 (1987)

    Article  MathSciNet  Google Scholar 

  4. Bunch, J.R., Demmel, W.J., Van Loan, C.F.: The strong stability of algorithms for solving symmetric linear systems. SIAM J. Matrix Anal. Appl. 10(4), 494–499 (1989)

    Article  MathSciNet  Google Scholar 

  5. Chen, X. S., Li, W., Chen, X.J., Liu, J.: Structured backward errors for generalized saddle point systems. Linear Algebra Appl. 436(9), 3109–3119 (2012)

    Article  MathSciNet  Google Scholar 

  6. Eisenstat, S.C., Gratton, S., Titley-peloquin, D.: On the symmetric componentwise relative backward error for linear systems of equations. SIAM J. Matrix Anal. Appl. 38(4), 1100–1115 (2017)

    Article  MathSciNet  Google Scholar 

  7. Elman, H.C., Ramage, A., Silvester, D.J.: Algorithm 866: IFISS, a Matlab toolbox for modelling incompressible flow. ACM Trans. Math. Software 33(2), Article 14 (2007)

  8. Elman, H.C., Silvester, D.J., Wathen, A.J.: Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics, 2nd edn. Oxford University Press, Oxford (2014)

    Book  Google Scholar 

  9. Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. The Johns Hopkins University Press, Baltimore (2013)

    MATH  Google Scholar 

  10. Higham, D.J., Higham, N.J.: Backward error and condition of structured linear systems. SIAM J. Matrix Anal. Appl. 13(1), 162–175 (1992)

    Article  MathSciNet  Google Scholar 

  11. Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. SIAM, Philadelphia (2002)

    Book  Google Scholar 

  12. Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge (1991)

    Book  Google Scholar 

  13. Li, X.X., Liu, X.G.: Structured backward errors for structured KKT systems. J. Comput. Math. 22(4), 605–610 (2004)

    Article  MathSciNet  Google Scholar 

  14. Liu, X.G., Chen, C.X.: A note on backward errors for Toeplitz systems. Numer. Linear Algebra Appl. 14(7), 547–562 (2007)

    Article  MathSciNet  Google Scholar 

  15. Ma, W.: On normwise structured backward errors for the generalized saddle point systems. Calcolo 54(2), 503–514 (2017)

    Article  MathSciNet  Google Scholar 

  16. Meng, L.S., Li, J.: Condition numbers of generalized saddle point systems. Calcolo 56(2), Article 18 (2019)

  17. Oettli, W., Prager, W.: Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides. Numer. Math. 6(1), 405–409 (1964)

    Article  MathSciNet  Google Scholar 

  18. Rigal, J.L., Gaches, J.: On the compatibility of a given solution with the data of a linear system. J. Assoc. Comput. Mach. 14(3), 543–548 (1967)

    Article  MathSciNet  Google Scholar 

  19. Rump, S.M.: The componentwise structured and unstructured backward errors can be arbitrarily far apart. SIAM J. Matrix Anal. Appl. 36(2), 385–392 (2015)

    Article  MathSciNet  Google Scholar 

  20. Stewart, G.W., Sun, J.G.: Matrix Perturbation Theory. Academic Press, Boston (1990)

    MATH  Google Scholar 

  21. Sun, J.G.: Backward perturbation analysis of certain characteristic subspaces. Numer. Math. 65(1), 357–382 (1993)

    Article  MathSciNet  Google Scholar 

  22. Sun, J.G.: Optimal backward perturbation bounds for linear systems and linear least squares problems. Tech. rep., UMINF 96.15, ISSN-0348-0542, Department of Computing Science, Umeå University (1996)

  23. Sun, J.G.: Bounds for the structured backward errors of Vandermonde systems. SIAM J. Matrix Anal. Appl. 20(1), 45–59 (1998)

    Article  MathSciNet  Google Scholar 

  24. Sun, J.G.: Structured backward errors for KKT systems. Linear Algebra Appl. 288, 75–88 (1999)

    Article  MathSciNet  Google Scholar 

  25. Sun, J.G.: A note on backward errors for structured linear systems. Numer. Linear Algebra Appl. 12(7), 585–603 (2005)

    Article  MathSciNet  Google Scholar 

  26. Varah, J.M.: Backward error estimates for Toeplitz systems. SIAM J. Matrix Anal. Appl. 15(2), 408–417 (1994)

    Article  MathSciNet  Google Scholar 

  27. Wilkinson, J.H.: The Algebraic Eigenvalue Problem. Oxford University Press , Oxford (1965)

    MATH  Google Scholar 

  28. Xiang, H., Wei, Y.M.: On normwise structured backward errors for saddle point systems. SIAM J. Matrix Anal. Appl. 29(3), 838–849 (2007)

    Article  MathSciNet  Google Scholar 

  29. Xiang, H., Wei, Y.M., Diao, H.A.: Perturbation analysis of generalized saddle point systems. Linear Algebra Appl. 419, 8–23 (2006)

    Article  MathSciNet  Google Scholar 

  30. Xu, W.W., Li, W.: New perturbation analysis for generalized saddle point systems. Calcolo 46, 25–36 (2009)

    Article  MathSciNet  Google Scholar 

  31. Xu, W.W., Liu, M.M., Zhu, L., Zuo, H.F.: New perturbation bounds analysis of a kind of generalized saddle point systems. East Asian J. Appl. Math. 7 (1), 116–124 (2017)

    Article  MathSciNet  Google Scholar 

  32. Yang, X.D., Dai, H., He, Q.Q.: Condition numbers and backward perturbation bound for linear matrix equations. Numer. Linear Algebra Appl. 18(1), 155–165 (2011)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

The authors would like to express their gratitude to the anonymous referees for their detailed and helpful suggestions that substantially improved the manuscript.

Funding

The work is supported by the National Natural Science Foundation of China (11571004)

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Lanzhou University, Lanzhou, 730000, People’s Republic of China

    Bing Zheng & Peng Lv

Authors
  1. Bing Zheng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peng Lv
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bing Zheng.

Additional information

Communicated by: Raymond H. Chan

Publisher’s note

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

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zheng, B., Lv, P. Structured backward error analysis for generalized saddle point problems. Adv Comput Math 46, 34 (2020). https://doi.org/10.1007/s10444-020-09787-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10444-020-09787-x

Keywords

Mathematics subject classification (2010)

Search

Navigation