Perturbation theory and backward error for AX-XB=C

Because of the special structure of the equations AX-XB=C the usual relation for linear equations "backward error = relative residual" does not hold, and application of the standard perturbation result for Ax=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 solution Y; 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. © 1993 BIT Foundations.