Abstract
Because of the special structure of the equationsAX−XB=C the usual relation for linear equations “backward error = relative residual” does not hold, and application of the standard perturbation result forAx=b yields a perturbation bound involving sep (A, B)−1 that is not always attainable. An expression is derived for the backward error of an approximate solutionY; it shows that the backward error can exceed the relative residual by an arbitrary factor. A sharp perturbation bound is derived and it is shown that the condition number it defines can be arbitrarily smaller than the sep(A, B)−1-based quantity that is usually used to measure sensitivity. For practical error estimation using the residual of a computed solution an “LAPACK-style” bound is shown to be efficiently computable and potentially much smaller than a sep-based bound. A Fortran 77 code has been written that solves the Sylvester equation and computes this bound, making use of LAPACK routines.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
E. Anderson, Z. Bai, C. H. Bischof, J. W. Demmel, J. J. Dongarra, J. J. Du Croz, A. Greenbaum, S. J. Hammarling, A. McKenney, S. Ostrouchov, and D. C. Sorensen,LAPACK Users' Guide, Society for Industrial and Applied Mathematics, Philadelphia, 1992.
M. Arioli, J. W. Demmel, and I. S. Duff,Solving sparse linear systems with sparse backward error, SIAM J. Matrix Anal. Appl., 10 (1989), pp. 165–190.
Z. Bai and J. W. Demmel,On a direct algorithm for computing invariant subspaces with specified eigenvalues, Technical Report CS-91-139, Department of Computer Science, University of Tennessee, Nov. 1991. (LAPACK Working Note #38).
J. B. Barlow, M. M. Monahemi, and D. P. O'Leary,Constrained matrix Sylvester equations, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 1–9.
R. H. Bartels and G. W. Stewart,Algorithm 432: Solution of the matrix equation AX+XB=C, Comm. ACM, 15 (1972), pp. 820–826.
R. Byers,A LINPACK-style condition estimator for the equation AX − XB T =C, IEEE Trans. Automat. Control, AC-29 (1984), pp. 926–928.
K. Datta,The matrix equation XA−BX=R and its applications, Linear Algebra and Appl., 109 (1988), pp. 91–105.
J. J. Du Croz and N. J. Higham,Stability of methods for matrix inversion, IMA Journal of Numerical Analysis, 12 (1992), pp. 1–19.
G. H. Golub, S. Nash, and C. F. Van Loan,A Hessenberg-Schur method for the problem AX+XB=C, IEEE Trans. Automat. Control, AC-24 (1979), pp. 909–913.
G. H. Golub and C. F. Van Loan,Matrix Computations, Johns Hopkins University Press, Baltimore, Maryland, second ed., 1989.
W. W. Hager,Condition estimates, SIAM J. Sci. Stat. Comput., 5 (1984), pp. 311–316.
J. Z. Hearon,Nonsingular solutions of TA−BT=C, Linear Algebra and Appl., 16 (1977), pp. 57–63.
H. V. Henderson and S. R. Searle,The vec-permutation matrix, the vec operator and Kronecker products: A review, Linear and Multilinear Algebra, 9 (1981), pp. 271–288.
G. Hewer and C. Kenney,The sensitivity of the stable Lyapunov equation, SIAM J. Control and Optimization, 26 (1988), pp. 321–344.
D. J. Higham and N. J. Higham,Componentwise perturbation theory for linear systems with multiple right-hand sides, Numerical Analysis Report No. 200, University of Manchester, England, July 1991. To appear in Linear Algebra and Appl.
——,Backward error and condition of structured linear systems, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 162–175.
N. J. Higham,Computing real square roots of a real matrix, Linear Algebra and Appl., 88/89 (1987), pp. 405–430.
——,FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation (Algorithm 674), ACM Trans. Math. Soft., 14 (1988), pp. 381–396.
——,Experience with a matrix norm estimator, SIAM J. Sci. Stat. Comput., 11 (1990), pp. 804–809.
A. S. Hodel,Recent applications of the Lyapunov equation in control theory, Manuscript, Dept. of Electrical Engineering, Auburn University, 1991. To appear in Proceedings of the IMACS International Symposium on Iterative Methods in Linear Algebra.
R. A. Horn and C. R. Johnson,Topics in Matrix Analysis, Cambridge University Press, 1991.
D. Y. Hu and L. Reichel,Krylov subspace methods for the Sylvester equation, Linear Algebra and Appl., 172 (1992), pp. 283–314.
B. Kågström and P. Poromaa,Distributed and shared memory block algorithms for the triangular Sylvester equation with sep−1 estimators, SIAM J. Matrix Anal., 13 (1992), pp. 90–101.
J. L. Rigal and J. Gaches,On the compatibility of a given solution with the data of a linear system, J. Assoc. Comput. Mach., 14 (1967), pp. 543–548.
R. D. Skeel,Iterative refinement implies numerical stability for Gaussian elimination, Math. Comp., 35 (1980), pp. 817–832.
G. Starke and W. Niethammer,SOR for AX−XB=C, Linear Algebra and Appl., 154–156 (1991), pp. 355–375.
G. W. Stewart,Error and perturbation bounds for subspaces associated with certain eigenvalue problems, SIAM Review, 15 (1973), pp. 727–764.
J. M. Varah,On the separation of two matrices, SIAM J. Numer. Anal., 16 (1979), pp. 216–222.
E. L. Wachspress,Iterative solution of the Lyapunov matrix equation, Appl. Math. Lett. 1 (1988), pp. 87–90.
Author information
Authors and Affiliations
Additional information
Nuffield Science Research Fellow. This work was carried out while the author was a visitor at the Institute for Mathematics and its Applications, University of Minnesota.
Rights and permissions
About this article
Cite this article
Higham, N.J. Perturbation theory and backward error forAX−XB=C . BIT 33, 124–136 (1993). https://doi.org/10.1007/BF01990348
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01990348