We present the perturbation and backward error analyses of the partitioned LU factorization for block tridiagonal matrices. In addition, we consider the bounds of perturbations for the partitioned LU factorization for block-tridiagonal linear systems. Finally, numerical examples are given to verify the obtained results.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. Barrland, “Perturbation bounds for the LDL H and the LU factorizations,” BIT, 31, 358–363 (1991).
G. W. Stewart, “Perturbation bounds for the QR factorization of a matrix,” SIAM J. Numer. Anal., 14, 509–518 (1977).
G. W. Stewart, “On the perturbation of LU, Cholesky, and QR factorizations,” SIAM J. Numer. Anal., 14, 1141–1145 (1993).
G. W. Stewart, “On the perturbation of LU and Cholesky factors,” SIAM J. Numer. Anal., 17, 1–6 (1997).
X.-W. Chang and C. C. Paige, “On the sensitivity of the LU factorization,” BIT, 38, 486–501 (1998).
F. M. Dopico and J. M. Molera, “Perturbation theory of factorizations of LUF type through series expansions,” SIAM J. Matrix Anal. Appl., 27, 561–581 (2005).
X.-W. Chang, C. C. Paige, and G. W. Stewart, “Perturbation analyses for the QR factorization,” SIAM J. Matrix Anal. Appl., 18, 775–791 (1997).
N. J. Higham, Accuracy and Stability of Numerical Algorithm, SIAM, Philadelphia (1996).
N. J. Higham, “Accuracy and stability of algorithms in numerical linear algebra,” Manchester Center Comput. Math. Numer. Anal. Rept., No. 333 (1998).
N. J. Higham, “The accuracy of solutions to triangular systems,” SIAM J. Numer. Anal., 26, 1252–1256 (1989).
P. Amodio and F. Mazzia, “A new approach to the backward error analysis in the LU factorization algorithm,” BIT, 39, 385–402 (1999).
J. W. Demmel, N. J. Higham, and R. S. Shreiber, “Stability of block LU factorization,” Numer. Linear Algebra Appl., 2, 173–190 (1995).
J. Zhao, W. Wang, and W. Ren, “Stability of the matrix factorization for solving block tridiagonal symmetric indefinite linear systems,” BIT Numer. Math., 44, 181–188 (2004).
R. M. M. Mattheij, “The stability of LU-decompositions of block tridiagonal matrices,” Bull. Aust. Math. Soc., 29, 177–205 (1984).
A. Forsgren, P. E. Gill, and J. R. Shinnerl, “Stability of symmetric ill-conditioned systems arising in interior methods for constrained optimization,” SIAM J. Matrix Anal. Appl., 17, 187–211 (1996).
M. I. Bueno and F. M. Dopico, “Stability and sensitivity of tridiagonal LU factorization without pivoting,” BIT Numer. Math., 44, 651–673 (2004).
J. W. Demmel and N. J. Higham, “Stability of block algorithms with fast level-3 BLAS,” ACM Trans. Math. Software, 18, 274–291 (1992).
J. Stoer and R. Bulirsch, Introduction to Numerical Analysis, 2nd ed, Springer-Verlag, New York (1993).
Author information
Authors and Affiliations
Additional information
Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 68, No. 12, pp. 1683–1695, December, 2016.
Rights and permissions
About this article
Cite this article
Wu, CY., Huang, TZ. Perturbation and Error Analyses of the Partitioned LU Factorization for Block Tridiagonal Linear Systems. Ukr Math J 68, 1949–1964 (2017). https://doi.org/10.1007/s11253-017-1340-8
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11253-017-1340-8