1 Introduction

The main purpose of this work is to provide perturbation results in a way appropriate to the particular structure in the coefficient matrices of the generalized Sylvester matrix equation

$$\begin{aligned} AXB+CXD=E, \end{aligned}$$
(1.1)

where A, B, C, D, E are infinite size matrices of the form \(S=T(s)+E_s\), where T(s) is a semi-infinite Toeplitz matrix associated with a function \(s(z)=\sum _{i=-\infty }^{\infty }s_iz^i\) and \(E_s=(e_{ij})\) is a compact operator on the space \(\ell ^{\infty }\), the usual Banach space of sequences \(x=(x_i)_{i\in \mathbb N}\) with \(\Vert x\Vert _{\infty }:=\sup _i |x_i|<\infty \). Here the function s(z) is defined on the unit circle \(\mathbb {T}\) and satisfies \(\sum _{i\in \mathbb {Z}}|s_i|<\infty \). Matrices of this kind are called quasi Toeplitz (QT) matrices and have been widely studied in [2,3,4,5,6].

Matrix equations with quasi Toeplitz coefficient matrices have been drawing attentions recently [2, 4, 7, 17]. Among those equations, the most widely studied is the quadratic matrix equation \(A_1X^2+A_0X+A_{-1}=X\), which is encountered in a 2-dimensional Quasi-Birth-Death (QDB) stochastic process and the coefficients are infinite tridiagonal matrices with a QT structure. In [7] when applying Newton’s method to this quadratic equation, a generalized Sylvester equation, which has coefficients with QT structure, is involved at each step. Numerical algorithms, which fully exploit the QT structure, for the solution of the Sylvester equation was proposed in [17].

The generalized Sylvester Eq. (1.1) in a matrix setting (finite dimensional) has been widely investigated, see [1, 9, 10, 13, 18, 20] and the references therein. When the coefficients are bounded linear operators on a Hilbert space, sufficient conditions for the existence of solutions were derived in [15]. Equations of type (1.1) with infinite size Toeplitz like coefficients were first studied in [17], where the Stein, Lyapunov and Sylvester type equations were proved to have the same structure as in the coefficient matrices and efficient iteration methods, such as ADI iteration and rational Krylov methods, were proposed. Our goal here is to provide perturbation analysis to equations of type (1.1) with the emphasis on respecting structure in the coefficient matrices.

For matrix equations with QT coefficients, the Toeplitz part of the solution can be computed at a low cost by algorithms based on evaluation and interpolation. An efficient efficient way for computing the solution, when it is an infinite size quasi Toeplitz matrix, is to separate the computation into two parts, that is, the computation of the Toeplitz part and the computation of the correction part, see [7, 17]. Accordingly, we investigate the perturbation analysis on the Toeplitz part and on the correction part separately. The existing results on perturbation analysis as in [11, 12, 19], where the analysis is restricted to equations with finite coefficients and ignores the structures of the matrices, are not appropriate for Eq. (1.1). Motivated by this, we provide perturbation results in a way appropriate to the infinite size QT matrices.

This paper is organized as follows: in Sect. 2 we recall some properties concerning semi-infinite quasi Toeplitz matrices and show that Eq. (1.1) has a unique solution with QT structure under certain conditions; in Sect. 3, we carry out a structure-preserving perturbation analysis and provide sharp perturbation bounds, while in Sect. 4 we extend the perturbation results to an equation with a more general form; in Sect. 5, we apply the perturbation results to equations encountered in solving a quadratic matrix equation arising in a Markov process and in the study of a 2D Poisson problem.

2 Existence of QT solutions

2.1 Preliminaries

We start with a review of some properties of the quasi Toeplitz (QT) matrices. Let \(\ell ^{\infty }\) stand for the usual Banach space of sequences \(x=(x_i)_{i\in \mathbb N}\) with \(\Vert x\Vert _{\infty }:=\sup _i |x_i|<\infty \). Denote by \(\mathcal {L}_{\infty }\) the set of matrices \(A=(a_{i,j})\) such that \(y\rightarrow Ax\), where \(y=\sum _{j=1}^{\infty }a_{i,j}x_j\), defines a bounded linear operator from \(\ell ^{\infty }\) to \(\ell ^{\infty }\) [7]. Recall that \(\mathcal L_{\infty }\) is a Banach space with the induced norm \(\Vert A\Vert _{\infty }:=\sup _{\Vert x\Vert _{\infty }=1}\Vert Ax\Vert _{\infty }\), which is verified to be \(\Vert A\Vert _{\infty }=\sup _{i}\sum _{j=1}^{\infty }|a_{i,j}|\).

Consider the complex valued functions \(a(z)=\sum _{i\in \mathbb {Z}}a_iz^i\), where a(z) is defined on the unit circle \(\mathbb {T}\), the Wiener algebra \(\mathcal {W}\) is defined as the set \(\mathcal {W}=\{a(z)=\sum _{i\in \mathbb {Z}}a_iz^i: \Vert a\Vert _w=\sum _{i\in \mathbb {Z}}|a_i|<\infty \}\). It is known that \(\mathcal {W}\) is a Banach algebra, then \(\Vert ab\Vert _w\le \Vert a\Vert _w\Vert b\Vert _w\) for any \(a,b\in \mathcal {W}\) and the normed space is complete [8].

For \(a\in \mathcal {W}\), we denote by T(a) the semi-infinite Toeplitz matrix associated with the function a(z), that is, \((T(a))_{i,j}=a_{j-i}\) for \(i,j\in \mathbb {Z}^+\). Denote by \(\mathcal {K}\mathcal {L}_{\infty }\) the set of matrices \(E=(e_{i,j})\in \mathcal L_{\infty }\) such that \(\lim _i v_i=0\), where \(v_i=\sum _{j=1}^{\infty }|e_{i,j}|\). It was proved in [5, Lemma 2.9 and Theorem 2.11] that \(\mathcal {KL}_{\infty }\) is a closed subset of \(\mathcal {K}(\ell ^{\infty })\), which is the set of compact operators from \(\ell ^{\infty }\) to \(\ell ^{\infty }\), so that \(\mathcal {KL}_{\infty }\) is a Banach space with the induced norm \(\Vert \cdot \Vert _{\infty }\). Consider the class

$$\begin{aligned} \mathcal {QT}_{\infty }=\{A=T(a)+E_a: a\in \mathcal W,\ E_a\in \mathcal {K}\mathcal {L}_{\infty }\}. \end{aligned}$$

If \(A\in \mathcal {QT}_{\infty }\), we call A a quasi Toeplitz (QT) matrix with a Toeplitz part T(a) and a compact correction part \(E_a\). The function a(z) is called the symbol of A and it is invertible if and only if \(a(z)\ne 0\) for all \(z\in \mathbb {T}\). It follows from [8, Proposition 1.1] that \(T(a)\in \mathcal {L}_{\infty }\), which implies that \(A\in \mathcal {L}_{\infty }\) if \(A\in \mathcal {QT}_{\infty }\).

For \(A\in \mathcal {QT}_{\infty }\), there exist a unique \(a\in \mathcal W\) and \(E_a\in \mathcal {KL}_{\infty }\) such that \(A=T(a)+E_a\). Indeed, suppose there is \(a_1\in \mathcal W\) and \(E_{a_1}\in \mathcal {KL}_{\infty }\) such that \(A=T(a_1)+E_{a_1}\), then we have \(T(a-a_1)+(E_a-E_{a_1})=0\), which yields \(T(a-a_1)=E_{a_1}-E_a\in \mathcal {KL}_{\infty }\). It follows from [8, Corollary 1.13] that \(T(a-a_1)=0\) so that \(a=a_1\) and hence \(E_{a}=E_{a_1}\).

Observe that the quasi Toeplitz matrices can be defined as \(A=T(a)+E_a\), where \(a\in \mathcal W\) and \(E_a\) is a compact operator on \(\ell ^p\) for \(1\le p\le \infty \), see [17] for example. In this paper, we only consider the case where \(p=\infty \).

We refer the readers to [2,3,4, 6] for more details about the QT matrices.

The following properties of matrices in \(\mathcal {QT}_{\infty }\) can be found in [8].

Lemma 2.1

[8, Proposition 1.3] Let T(a) and T(b) be two semi-infinite Toeplitz matrices with \(a,b\in \mathcal {W}\). Then

$$\begin{aligned} T(a)T(b)=T(ab)-H(a^-)H(b^+), \end{aligned}$$

where \(H(a^-)\) and \(H(b^+)\) are Hankel matrices such that \((H(a^-))_{i,j}=(a_{-(i+j)+1})_{i,j\in \mathbb {Z}^+}\) and \((H(b^+))_{i,j}=(b_{i+j-1})_{i,j\in \mathbb {Z^+}}\). Moreover, \(H(a^-)H(b^+)\) is a compact operator on \(\ell ^p\) for any \(p\in [1,\infty ]\).

Lemma 2.2

[8, Theorem 1.14] If \(a\in \mathcal W\), then \(\Vert T(a)\Vert _{1}=\Vert T(a)\Vert _{\infty }=\Vert a\Vert _{w}\).

It can be seen from [8, Page 27] that if \(a\in \mathcal {W}\) and \(E_a\in \mathcal {L}_{\infty }\) is a compact operator, then \(\Vert T(a)\Vert _{\infty }\le \Vert T(a)+E_a\Vert _{\infty }\). Together with Lemma 2.2, we have

Lemma 2.3

If \(A=T(a)+E_a\in \mathcal {QT}\), then \(\Vert a\Vert _{w}\le \Vert A\Vert _{\infty }\).

Denote by \(\mathcal B(\ell ^{\infty })\) the set of all bounded linear operators from \(\ell ^{\infty }\) to itself. Recall that the spectrum of \(A\in \mathcal {B}(\ell ^{\infty })\) is the set \( \sigma (A) =\{\lambda \in \mathbb {C} : A-\lambda I \mathbf{\ is\ not\ invertible}\}. \) The essential spectrum of \(A\in \mathcal {B}(\ell ^{\infty })\) is the set \( \sigma _{ess}(A)= \{\lambda \in \mathbb {C} : A-\lambda I \text { is not Fredholm}\}\), where \(A\in \mathcal B(\ell ^{\infty })\) is said to be Fredholm if it is an invertible operator modulo compact operators. We know from [8] that \(\mathrm{\sigma _{ess}}(A)\subset \sigma (A)\) and \(\mathrm{\sigma _{ess}}(A)\) is invariant under compact perturbations.

In what follows, we denote by \(\sigma (A)\) and \(\sigma _{ess}(A)\), respectively, the spectrum and the essential spectrum of an operator A in the space \(\mathcal L_{\infty }\) unless otherwise specified.

2.2 Existence of solutions

Note that if \(X\in \mathcal {QT}_{\infty }\) then \(X\in \mathcal {L}_{\infty }\), we show that under certain conditions Eq. (1.1) has a unique solution in \(\mathcal L_{\infty }\) and then prove that the solution is a QT matrix if the coefficients \(A,B,C,D,E\in \mathcal {QT}_{\infty }\).

Observe that Eq. (1.1) is solvable in \(\mathcal {L}_{\infty }\) if and only if the operator \(\mathcal {G}: \mathcal L_{\infty }\rightarrow \mathcal {L}_{\infty }\) defined by \(\mathcal {G}(X)=AXB+CXD\) is invertible in \(\mathcal {L}_{\infty }\). It follows from [14, Theorem 4] that \(\sigma (\mathcal G)\subset \sigma (A)\sigma (B)+\sigma (C)\sigma (D)\) if \(AC=CA\) and \(BD=DB\). Here we denote by \(\sigma (A)\sigma (B)\) the set \(\{\lambda _A\lambda _B: \lambda _A\in \sigma (A), \lambda _B\in \sigma (B)\}\) and by \(\sigma (A)\sigma (B)+\sigma (C)\sigma (D)\) we denote the set \(\{\lambda _A\lambda _B+\lambda _C\lambda _D: \lambda _A\lambda _B\in \sigma (A)\sigma (B), \lambda _C\lambda _D\in \sigma (C)\sigma (D)\}\). Hence, \(\mathcal {G}\) is invertible if \(AC=CA,\ BD=DB, \ \mathrm{and}\ \sigma (A)\sigma (B)\cap \sigma (-C)\sigma (D)=\emptyset \). We have

Theorem 2.1

Suppose \(A,B,C,D,E\in \mathcal {L}_{\infty }\) are such that \(AC=CA\), \(BD=DB\) and \(\sigma (A)\sigma (B)\cap \sigma (-C)\sigma (D)=\emptyset \), then Eq. (1.1) has a unique solution \(X\in \mathcal L_{\infty }\).

If \(\sigma (A)\sigma (B)\cap \sigma (-C)\sigma (D)=\emptyset \) holds, then \(0\notin \sigma (A)\sigma (B)\cap \sigma (-C)\sigma (D)\), which implies \(0\notin \sigma (A)\sigma (B)\) or \(0\notin \sigma (-C)\sigma (D)\). If \(0\notin \sigma (A)\sigma (B)\), then both A and B are invertible, so are C and D if \(0\notin \sigma (-C)\sigma (D)\). In what follows, without loss of generality, A and B are assumed to be invertible. We show that the commutativity property \(AC=CA, BD=DB\) can be removed under a stronger condition and the solution of Eq. (1.1) can be described in an explicit way.

Theorem 2.2

Suppose A and B are invertible, let \(\alpha =\Vert A^{-1}\Vert _{\infty }\Vert B^{-1}\Vert _{\infty }\) and \(\beta =\Vert C\Vert _{\infty }\Vert D\Vert _{\infty }\). If \(\alpha \beta <1\), then Eq. (1.1) has a unique solution \(X\in \mathcal {L}_{\infty }\) and

$$\begin{aligned} X=\sum _{k=0}^{\infty }(-1)^{k}\check{A}^k\check{E}\check{B}^k, \end{aligned}$$
(2.1)

where \(\check{A}=A^{-1}C\), \(\check{B}=DB^{-1}\) and \(\check{E}=A^{-1}EB^{-1}\).

Proof

Set \(\check{A}=A^{-1}C\), \(\check{B}=DB^{-1}\) and \(\check{E}=A^{-1}EB^{-1}\), observe that X solves Eq. (1.1) if and only if X is a solution of equation

$$\begin{aligned} X+\check{A}X\check{B}=\check{E}. \end{aligned}$$
(2.2)

It suffices to prove that Eq. (2.2) has a unique solution in \(\mathcal {L}_{\infty }\).

Note that \(\Vert \check{A}\Vert _{\infty }\Vert \check{B}\Vert _{\infty }\le \alpha \beta <1\), then for any \(\lambda \in \sigma (-\check{A})\sigma (\check{B})\), we have \(|\lambda |<1\), which implies \(1\notin \sigma (-\check{A})\sigma (\check{B})\). According to Theorem 2.1, the map \(\mathcal {F}: X\rightarrow X+\check{A}X\check{B}\) is invertible in \(\mathcal {L}_{\infty }\), this implies that Eq. (2.2) has a unique solution \(X\in \mathcal {L}_{\infty }\).

We prove that the series in (2.1) is convergent in \(\mathcal {L}_{\infty }\), it is then easy to check that X in (2.1) solves Eq. (2.2) and hence is a solution of Eq. (1.1). Indeed, we have

$$\begin{aligned} \Big \Vert \sum _{k=0}^{\infty }(-1)^{k}\check{A}^{k}\check{E}\check{B}^k\Big \Vert _{\infty }\le & {} \sum _{k=0}^{\infty }(\alpha \beta )^k\Vert A^{-1}\Vert _{\infty }\Vert B^{-1}\Vert _{\infty }\Vert E\Vert _{\infty }\nonumber \\\le & {} \frac{\alpha \Vert E\Vert _{\infty }}{1-\alpha \beta }<\infty . \end{aligned}$$
(2.3)

The proof is completed. \(\square \)

In what follows, we use \(\alpha \) and \(\beta \) to denote \(\Vert A^{-1}\Vert _{\infty }\Vert B^{-1}\Vert _{\infty }\) and \(\Vert C\Vert _{\infty }\Vert D\Vert _{\infty }\), respectively. Observe that the assumption \(\alpha \beta <1\) can be relaxed to be \(\Vert \check{A}\Vert _{\infty }\Vert \check{B}\Vert _{\infty }<1\). Under the latter one it is easy to prove that Eq. (2.2) has a unique solution in \(\mathcal {L}_{\infty }\) by applying the same technique as in the proof of Theorem 2.2.

Remark 2.1

Since \(\alpha \beta <1\), there is \(\epsilon >0\) such that \(\epsilon \) is sufficiently small and \(\beta \le \alpha ^{-1}-\epsilon \). This implies that \(\sigma (-C)\sigma (D)\) is contained in the disk \(\{z:|z|\le \alpha ^{-1}-\epsilon \}\). On the other hand, it follows from \(\Vert A^{-1}\Vert _{\infty }\Vert B^{-1}\Vert _{\infty }=\alpha \) that \(\sigma (A^{-1})\sigma (B^{-1})\) is inside the disk \(\{z: |z|\le \alpha \}\). Then \(\sigma (A)\sigma (B)\) is outside the disk \(\{z:|z|\le \alpha ^{-1}\}\). This way, we have \(\sigma (A)\sigma (B)\cap \sigma (-C)\sigma (D)=\emptyset \).

Concerning the case where the coefficients are QT matrices, if there is a disc of radius \(r<1\) such that \(\sigma (\check{A}),\sigma (\check{B})\subseteq B(0,r)\), it can be seen from [17] that Eq. (2.2) has a unique solution \(X\in \mathcal {QT}_{\infty }\) so that Eq. (1.1) has a unique solution in the \(\mathcal {QT}_{\infty }\) class. Here with the condition \(\alpha \beta <1\) and a slightly different technique, we prove that the unique solution of Eq. (1.1) belongs to the \(\mathcal {QT}_{\infty }\) class.

Theorem 2.3

For \(A,B,C,D,E\in \mathcal {QT}_{\infty }\), under the assumptions in Theorem 2.2, Eq. (1.1) has a unique solution \(X\in \mathcal {QT}_{\infty }\).

Proof

For \(A,B,C,D,E\in \mathcal {QT}_{\infty }\) such that the conditions of Theorem 2.2 are satisfied, by relying on Lemma 2.1 and (2.1) we will prove that X can be written as \(X = T(x) + E_x\), where

$$\begin{aligned} x(z)=\sum _{k=0}^{\infty }(-1)^kc(z)^ka(z)^{-k-1}e(z)b(z)^{-k-1}d(z)^k, \end{aligned}$$
(2.4)

and \(x(z) \in \mathcal W\), \(E_x \in \mathcal {KL}_{\infty }\) so that \(X\in \mathcal {QT}_{\infty }\). To show \(x\in \mathcal {W}\), we have

$$\begin{aligned} \Vert x\Vert _w\le \sum _{k=0}^{\infty }(\Vert a^{-1}\Vert _w\Vert b^{-1}\Vert _w\Vert c\Vert _w\Vert d\Vert _w)^k\Vert a^{-1}\Vert _w\Vert b^{-1}\Vert _w\Vert e\Vert _w. \end{aligned}$$
(2.5)

In view of Lemma 2.3, we have

$$\begin{aligned} \Vert a^{-1}\Vert _{w}\Vert b^{-1}\Vert _{w}\Vert c\Vert _w\Vert d\Vert _w\le \alpha \beta <1 \ \mathrm{and}\ \Vert a^{-1}\Vert _{w}\Vert b^{-1}\Vert _{w}\le \alpha , \end{aligned}$$

it follows from (2.5) that

$$\begin{aligned} \Vert x\Vert _w\le \frac{\alpha \Vert e\Vert _w}{1-\alpha \beta }, \end{aligned}$$
(2.6)

from which we obtain \(x\in \mathcal W\). It remains for us to prove that \(E_x\in \mathcal {KL}_{\infty }\). To this end, set \(X_n=\sum _{k=0}^{n}(-1)^{k}\check{A}^{k}\check{E}\check{B}^k\), we have

$$\begin{aligned} \Vert X_n-X\Vert _{\infty }\le & {} \sum _{k=n+1}^{\infty }(\Vert A^{-1}\Vert _{\infty }\Vert B^{-1}\Vert _{\infty }\Vert C\Vert _{\infty }\Vert D\Vert _{\infty })^k\Vert A^{-1}\Vert _{\infty }\Vert B^{-1}\Vert _{\infty }\Vert E\Vert _{\infty }\\\le & {} \frac{(\alpha \beta )^{n+1}\alpha \Vert E\Vert _{\infty }}{1-\alpha \beta }, \end{aligned}$$

which implies \(\lim _n\Vert X_n-X\Vert _{\infty }=0\) as \(\alpha \beta <1\) and hence \((\alpha \beta )^{n+1}\rightarrow 0\) as \(n\rightarrow \infty \).

It is clear that \(X_n\in \mathcal {QT}_{\infty }\) and \(X_n=T(x_n)+E_{n}\), where

$$\begin{aligned} x_n(z)=\sum _{k=0}^n(-1)^kc(z)^ka(z)^{-k-1}e(z)b(z)^{-k-1}d(z)^k\in \mathcal {W} \end{aligned}$$

and \(E_n\in \mathcal {K}\mathcal {L}_{\infty }\). We prove that \(\lim _{n\rightarrow \infty }\Vert E_n-E_x\Vert _{\infty }=0\) so that \(E_x\in \mathcal {KL}_{\infty }\) since \(\mathcal {K}\mathcal {L}_{\infty }\) is a Banach space. Note that

$$\begin{aligned} \Vert x-x_n\Vert _{w}= & {} \sum _{k=n+1}^{\infty }\Vert c^ka^{-k-1}eb^{-k-1}d^k\Vert _w\nonumber \\\le & {} \sum _{k=n+1}^{\infty }(\Vert a^{-1}\Vert _w\Vert b^{-1}\Vert _w\Vert c\Vert _w\Vert d\Vert _w)^k\Vert a^{-1}\Vert _w\Vert b^{-1}\Vert _w\Vert e\Vert _w\nonumber \\\le & {} \frac{(\alpha \beta )^{n+1}\alpha \Vert e\Vert _w}{1-\alpha \beta }, \end{aligned}$$
(2.7)

which implies \(\lim _{n\rightarrow \infty }\Vert T(x_n-x)\Vert _{\infty }=\lim _{n\rightarrow \infty }\Vert x_n-x\Vert _w=0\).

From \(E_n-E_x=X_n-X-T(x_n-x)\), we have \(\Vert E_n-E_x\Vert _{\infty }\le \Vert X_n-X\Vert _{\infty }+\Vert T(x_n-x)\Vert _{\infty }\), which yields \(\lim _k\Vert E_n-E_x\Vert _{\infty }=0\) since \(\lim _n\Vert X_n-X\Vert _{\infty }=0\) and \(\lim _{n\rightarrow \infty }\Vert T(x_n-x)\Vert _{\infty }=0\). \(\square \)

The next theorem shows that the symbol of the solution \(X\in \mathcal {QT}_{\infty }\) has an explicit expression.

Theorem 2.4

For \(A=T(a)+E_a,B=T(b)+E_b,C=T(c)+E_c,D=T(d)+E_d,E=T(e)+E_e\in \mathcal {QT}_{\infty }\), under the assumptions in Theorem 2.2, let \(X=T(x)+E_x\) be the unique solution of Eq. (1.1), then \(x(z)=(a(z)b(z)+c(z)d(z))^{-1}e(z)\).

Proof

In view of Lemma 2.1, we know

$$\begin{aligned} AXB+CXD-E=T(x(ab+cd)-e)+F, \end{aligned}$$

where \(F\in \mathcal {KL}_{\infty }\) is a compact correction. Since \(AXB+CXD-E=0\), we must have

$$\begin{aligned} x(z)(a(z)b(z)+c(z)d(z))=e(z). \end{aligned}$$
(2.8)

We prove that \(a(z)b(z)+c(z)d(z)\) is invertible, that is, \(a(z)b(z)+c(z)d(z)\ne 0\) for all \(z\in \mathbb {T}\). It follows from [8, Corollary 1.10] that \(a(\mathbb {T})=\sigma _{ess}(T(a))\) and since the essential spectrum is invariant under compact perturbations, we have \(a(\mathbb {T})=\sigma _{ess}(T(a))=\sigma _{ess}(A)\subseteq \sigma (A)\). The same results hold for matrices B, C and D, that is, \(b(\mathbb {T})\subseteq \sigma (B)\), \(c(\mathbb {T})\subseteq \sigma (C)\) and \(d(\mathbb {T})\subseteq \sigma (D)\). Suppose \(a(z)b(z)+c(z)d(z)=0\) for some \(z\in \mathbb {T}\), that is, \(a(z)b(z)=-c(z)d(z)\), this shows that \(\sigma (A)\sigma (B)\cap \sigma (-C)\sigma (D)\ne \emptyset \), which is impossible since \(\sigma (A)\sigma (B)\cap \sigma (-C)\sigma (D)= \emptyset \) in view of Remark 2.1. Hence, \(a(z)b(z)+c(z)d(z)\ne 0\) for all \(z\in \mathbb {T}\) so that \(x(z)=(a(z)b(z)+c(z)d(z))^{-1}e(z)\). \(\square \)

Remark 2.2

Since the decomposition of a QT matrix into the sum of a Toepltiz part and a correction part is unique, we know from Theorem 2.4 and (2.4) that \((a(z)b(z)+c(z)d(z))^{-1}e(z)=\sum _{k=0}^{\infty }(-1)^kc(z)^ka(z)^{-k-1}e(z)b(z)^{-k-1}d(z)^k\).

3 Structured perturbation analysis

Consider the perturbed equation

$$\begin{aligned} (A+\varDelta _A)(X+\varDelta _X)(B+\varDelta _B)+(C+\varDelta _C)(X+\varDelta _X)(D+\varDelta _D)=E+\varDelta _E, \end{aligned}$$
(3.1)

where \(\varDelta _A, \varDelta _B, \varDelta _C, \varDelta _D, \varDelta _E\in \mathcal {QT}_{\infty }\) are such that \(\varDelta _A=T(\delta _a)+E_{\delta _a}\), \( \varDelta _B=T(\delta _b)+E_{\delta _b}\), \( \varDelta _C=T(\delta _c)+E_{\delta _c}\), \(\varDelta _D=T(\delta _d)+E_{\delta _d}\), \(\varDelta _E=T(\delta _e)+E_{\delta _e}\), and \(X + \varDelta _X\) is the perturbed solution.

Suppose the assumptions in Theorem are satisfied by the perturbed Eq. (3.1), it follows from Theorem 2.3 that \(\varDelta _X\in \mathcal {QT}_{\infty }\).

Taking the difference of Eq. (3.1) with (1.1) and omitting the second and higher order terms in the perturbations, it yields

$$\begin{aligned} A\varDelta _XB+C\varDelta _XD\doteq \varDelta _W, \end{aligned}$$
(3.2)

where \(\varDelta _W=\varDelta _E-\varDelta _AXB-AX\varDelta _B-\varDelta _CXD-CX\varDelta _D\). Then (3.2) can be written as

$$\begin{aligned} \mathcal {G}(\varDelta _X)\doteq \varDelta _W, \end{aligned}$$

where \(\doteq \) means equality up to higher order terms with respect to the perturbations and \(\mathcal {G}: \mathcal {L}_{\infty }\rightarrow \mathcal {L}_{\infty }\) is defined by \( \mathcal {G}(Y)= AYB+CYD. \) Under the assumptions in Theorem 2.2, \(\mathcal {G}\) is invertible and

$$\begin{aligned} \varDelta _X\doteq \mathcal {G}^{-1}(\varDelta _W)=\sum _{k=0}^{\infty }(-1)^{k}{\check{A}}^{k}\varDelta _{\check{W}}{\check{B}}^{k}, \end{aligned}$$
(3.3)

where \(\check{A}=A^{-1}C\), \(\check{B}=DB^{-1}\) and \(\varDelta _{\check{W}}=A^{-1}\varDelta _WB^{-1}\). It follows from (3.3) that

$$\begin{aligned} \Vert \varDelta _X\Vert _{\infty }&\dot{\le } \sum _{k=0}^{\infty }(\Vert A^{-1}\Vert _{\infty }\Vert B^{-1}\Vert _{\infty }\Vert C\Vert _{\infty }\Vert D\Vert _{\infty })^k\Vert A^{-1}\Vert _{\infty }\Vert B^{-1}\Vert _{\infty }\Vert \varDelta _W\Vert _{\infty }\\&\le \frac{\alpha \Vert \varDelta _W\Vert _{\infty }}{1-\alpha \beta }. \end{aligned}$$

On the other hand, we have from (2.3) that \(\Vert X\Vert _{\infty }\le \frac{\alpha \Vert E\Vert _{\infty }}{1-\alpha \beta }\). Set

$$\begin{aligned} \omega =\max \{\Vert A\Vert _{\infty }, \Vert B\Vert _{\infty }, \Vert C\Vert _{\infty }, \Vert D\Vert _{\infty }\}, \quad \gamma =\mathrm{max}\left\{ 1, \frac{\alpha \omega \Vert E\Vert _{\infty }}{1-\alpha \beta }\right\} , \end{aligned}$$
(3.4)

we have

$$\begin{aligned} \Vert \varDelta _W\Vert _{\infty }\le \gamma (\Vert \varDelta _A\Vert _{\infty }+\Vert \varDelta _B\Vert _{\infty }+\Vert \varDelta _C\Vert _{\infty }+\Vert \varDelta _D\Vert _{\infty }+\Vert \varDelta _E\Vert _{\infty }), \end{aligned}$$

and

$$\begin{aligned} \Vert \varDelta _X\Vert _{\infty }\dot{\le } \frac{\alpha \gamma }{1-\alpha \beta } (\Vert \varDelta _A\Vert _{\infty }+\Vert \varDelta _B \Vert _{\infty }+\Vert \varDelta _C\Vert _{\infty }+\Vert \varDelta _D\Vert _{\infty }+\Vert \varDelta _E\Vert _{\infty }). \end{aligned}$$
(3.5)

Inequality (3.5) provides a perturbation bound to the whole solution without taking the QT structure into account and \(\frac{\alpha \gamma }{1-\alpha \beta }\) provides an upper bound to the conditioning of the whole problem. In real applications, when the solution of an equation with QT coefficients is also a QT matrix, in some implementation issues, it is feasible to approximate the Toeplitz part and the correction part of the solution separately. For example, in [17] the Toeplitz part is computed by algorithms based on evaluation and interpolation while the correction part is computed separately by Krylov or ADI methods. Accordingly, it is convenient to separate the perturbation analysis into two parts, that is, the analysis of the Toeplitz part and the analysis of the correction part.

3.1 Toeplitz part

Write \(\varDelta _X=T(\delta _x)+E_{\delta _x}\), in view of Theorem 2.4, \(x+\delta _x\) is the unique solution of the equation

$$\begin{aligned} ((a+\delta _a)(b+\delta _b)+(c+\delta _c)(d+\delta _d))(x+\delta _x)=e+\delta _e. \end{aligned}$$
(3.6)

Taking the difference of Eq. (3.6) with (2.8) yields

$$\begin{aligned} (ab+cd)\delta _x\doteq \delta _e-xb\delta _a-ax\delta _b-xd\delta _c-cx\delta _d. \end{aligned}$$

According to Theorem 2.4, \(a(z)b(z)+c(z)d(z)\) is invertible, we have

$$\begin{aligned} \delta _x\doteq \frac{\delta _e-xb\delta _a-ax\delta _b-xd\delta _c-cx\delta _d}{ab+cd}, \end{aligned}$$
(3.7)

from which we obtain

$$\begin{aligned} \Vert \delta _x\Vert _w\dot{}\le & {} \Vert (ab+cd)^{-1}\Vert _w \big (\Vert \delta _e\Vert _w+(\Vert \delta _a\Vert _w\Vert b\Vert _w\nonumber \\&+\Vert \delta _b\Vert _w\Vert a\Vert _w+\Vert \delta _c\Vert _w\Vert d\Vert _w+\Vert \delta _d\Vert _w\Vert c\Vert _w)\Vert x\Vert _w\big ). \end{aligned}$$
(3.8)

Observe that \(\Vert x\Vert _w=\Vert (ab+cd)^{-1}e\Vert _w\) in view of Theorem 2.4. Together with (3.8), we have

$$\begin{aligned} \Vert \delta _x\Vert _w&\dot{\le } \mu \Vert (ab+cd)^{-1}\Vert _w(\Vert \delta _a\Vert _w+ \Vert \delta _b\Vert _w+\Vert \delta _c\Vert _w+\Vert \delta _d\Vert _w+\Vert \delta _e\Vert _w), \end{aligned}$$
(3.9)

where

$$\begin{aligned} \mu =\max \{1, \nu \Vert (ab+cd)^{-1}e\Vert _w\}, \ \nu =\max \{\Vert a\Vert _{w}, \Vert b\Vert _{w}, \Vert c\Vert _{w}, \Vert d\Vert _w\}. \end{aligned}$$
(3.10)

It turns out from (3.9) that \(\mu \Vert (ab+cd)^{-1}\Vert _w\) provides an upper bound to the conditioning of the Toeplitz part. In view of Remark 2.2, we have \(\Vert (ab+cd)^{-1}e\Vert _w\le \frac{\alpha \Vert e\Vert _w}{1-\alpha \beta }\). Then, according to Lemma 2.3, (3.4) and (3.10), we deduce that \(\mu \le \gamma \). On the other hand, it can be easily checked that \((ab+cd)^{-1}=\sum _{k=0}^{\infty }(ab)^{-k-1}(cd)^k\) so that \(\Vert (ab+cd)^{-1}\Vert _w\le \frac{\alpha }{1-\alpha \beta }\), from which we have \(\mu \Vert (ab+cd)^{-1}\Vert _w\le \frac{\alpha \mu }{1-\alpha \beta }\le \frac{\alpha \gamma }{1-\alpha \beta }\). Recall that \(\frac{\alpha \gamma }{1-\alpha \beta }\) is an upper bound to the conditioning of the whole problem, it is interesting to observe that if \(\frac{\alpha \gamma }{1-\alpha \beta }\) is a small number, that is, the whole problem is well-conditioned, then the Toeplitz part is well-conditioned.

3.2 Correction part

Concerning the perturbation bound of the correction part, it follows from \(E_{\delta _x}=\varDelta _X-T(\delta _x)\) and Lemma 2.2 that \(\Vert E_{\delta _x}\Vert _{\infty }\le \Vert \varDelta _X\Vert _{\infty }+\Vert \delta _x\Vert _{w}\). Moreover, in view of Lemma 2.3 and (3.9), we have

$$\begin{aligned} \Vert \delta _x\Vert _w\dot{\le } \mu \Vert (ab+cd)^{-1}\Vert _w(\Vert \varDelta _A\Vert _{\infty }+\Vert \varDelta _B\Vert _{\infty }+\Vert \varDelta _C\Vert _{\infty }+\Vert \varDelta _D\Vert _{\infty }+\Vert \varDelta _E\Vert _{\infty }). \end{aligned}$$

Together with (3.5), we derive an upper bound for \(E_{\delta _x}\)

$$\begin{aligned} \Vert E_{\delta _x}\Vert _{\infty }\dot{}\le & {} \frac{\alpha \gamma }{1-\alpha \beta } (\Vert \varDelta _A\Vert _{\infty }+\Vert \varDelta _B\Vert _{\infty }+\Vert \varDelta _C\Vert _{\infty }+\Vert \varDelta _D\Vert _{\infty }+\Vert \varDelta _E\Vert _{\infty })+\Vert \delta _x\Vert _{w}\nonumber \\\le & {} \kappa (\Vert \varDelta _A\Vert _{\infty }+\Vert \varDelta _B\Vert _{\infty }+\Vert \varDelta _C\Vert _{\infty }+\Vert \varDelta _D\Vert _{\infty }+\Vert \varDelta _E\Vert _{\infty }), \end{aligned}$$
(3.11)

where \(\kappa =\frac{\alpha \gamma }{1-\alpha \beta }+\mu \Vert (ab+cd)^{-1}\Vert _w\), \(\mu \) and \(\gamma \) are defined in (3.10) and (3.4) respectively.

Inequality (3.11) provides an upper perturbation bound to the correction part. It is interesting to observe from (3.11) that the perturbations on the Toeplitz part of the coefficients may make a difference to the perturbation results on the correction part. This coincides with the fact that, when the computations are separated, the Toeplitz part that has been previously computed appears in the computation of the correction part, see [17] for example.

Set

$$\begin{aligned} \delta =\max \left\{ \frac{\Vert \delta _a\Vert _w}{\Vert E_{\delta _a}\Vert _{\infty }}, \frac{\Vert \delta _b\Vert _w}{\Vert E_{\delta _b}\Vert _{\infty }}, \frac{\Vert \delta _c\Vert _w}{\Vert E_{\delta _c}\Vert _{\infty }}, \frac{\Vert \delta _d\Vert _w}{\Vert E_{\delta _d}\Vert _{\infty }}, \frac{\Vert \delta _e\Vert _w}{\Vert E_{\delta _e}\Vert _{\infty }}\right\} . \end{aligned}$$
(3.12)

If \(\delta <\infty \), it follows from (3.11) that

$$\begin{aligned} \Vert E_{\delta _x}\Vert _{\infty } \dot{}\le & {} \kappa (1+\delta ) (\Vert E_{\delta _a}\Vert _{\infty }+\Vert E_{\delta _b}\Vert _{\infty }+\Vert E_{\delta _c}\Vert _{\infty }+\Vert E_{\delta _d}\Vert _{\infty }+\Vert E_{\delta _e}\Vert _{\infty })\nonumber \\\le & {} \frac{2\alpha \gamma (1+\delta )}{1-\alpha \beta }(\Vert E_{\delta _a}\Vert _{\infty }+\Vert E_{\delta _b}\Vert _{\infty }+\Vert E_{\delta _c}\Vert _{\infty }+\Vert E_{\delta _d}\Vert _{\infty }+\Vert E_{\delta _e}\Vert _{\infty }),\nonumber \\ \end{aligned}$$
(3.13)

where the last inequality follows from \(\Vert (ab+cd)^{-1}\Vert _w\le \frac{\alpha }{1-\alpha \beta }\) and \(\mu \le \gamma \) so that \(\kappa \le \frac{\alpha (\mu +\gamma )}{1-\alpha \beta }\le \frac{2\alpha \gamma }{1-\alpha \beta }\).

If \(\delta <\infty \), we can see from (3.13) that \(\frac{2\alpha \gamma (1+\delta )}{1-\alpha \beta }\) may provide some insights to the conditioning of the correction part. When \(\delta \) is a small number, the perturbations on the Toeplitz part make a very small difference to the perturbations on the correction part and in this case the correction part is well-conditioned if the whole problem is well-conditioned.

3.3 A special case

We consider a special case of Eq. (1.1), which is

$$\begin{aligned} AX+XA=E, \end{aligned}$$
(3.14)

where \(A=T(a)+E_a\in \mathcal {QT}_{\infty }\) and \(E=T(e)+E_e\in \mathcal {QT}_{\infty }\). An equation of this type arises in the study of 2D Poisson problem on an unbounded domain, see [17, Example 5.1]. The assumptions in Theorem 2.2 are not satisfied by Eq. (3.14) since \(\Vert A^{-1}\Vert _{\infty }\Vert A\Vert _{\infty }\ge 1\) for all invertible A. Hence, the structured perturbation results may not apply.

Let

$$\begin{aligned} \mathcal {S}=\{\lambda \in \mathbb {C}: \Vert (A+\lambda I)^{-1}\Vert _{\infty }\Vert A-\lambda I\Vert _{\infty }<1\}. \end{aligned}$$

If \(\mathcal S\ne \emptyset \), then Eq. (3.14) has a unique solution X which satisfies \(X\in \mathcal {L}_{\infty }\cap \mathcal {QT}_{\infty }\). Indeed, consider the equation

$$\begin{aligned} (A+\lambda I)X+X(A-\lambda I)=E. \end{aligned}$$
(3.15)

Suppose \(\mathcal {S}\) is nonempty, that is, there is \(\lambda \in \mathcal {S}\) such that \(\Vert (A+\lambda I)^{-1}\Vert _{\infty }\Vert A-\lambda I\Vert _{\infty }<1\), by Remark 2.1, we have \(\sigma (A+\lambda I)\cap \sigma (\lambda I-A)=\emptyset \), which implies \(\sigma (A)\cap \sigma (-A)=\emptyset \), so that Eq. (3.14) has a unique solution \(X\in \mathcal L_{\infty }\) in view of Theorem 2.1. On the other hand, observe that X also solves Eq. (3.15) so that \(X\in \mathcal {QT}_{\infty }\), since it follows from Theorem 2.3 that Eq. (3.15) has a unique solution \(X_{\lambda }\in \mathcal {QT}_{\infty }\).

We have the following properties for the set \(\mathcal {S}\).

Lemma 3.1

If \(\mathcal {S}\) is nonempty, then \(a(z)\ne 0\) for all \(z\in \mathbb {T}\), where a(z) is the symbol of matrix A.

Proof

Suppose by contradiction that \(a(z_0)=0\) for some \(z_0\in \mathbb {T}\). Let \(\lambda \in \mathcal {S}\) be such that \(\Vert (A+\lambda I)^{-1}\Vert _{\infty }\Vert A-\lambda I\Vert _{\infty }<1\). Observe that \(a(z)+\lambda \) is invertible on the unit circle \(\mathbb {T}\) since \(a(\mathbb {T})+\lambda =\sigma _{ess}(A+\lambda I)\subset \sigma (A+\lambda I)\) and \(0\notin \sigma (A+\lambda I)\) so that \(a(z)+\lambda \ne 0\) for all \(z\in \mathbb {T}\). In view of Lemma 2.3, we have \(\Vert (a+\lambda )^{-1}\Vert _w\Vert a-\lambda \Vert _w\le \Vert (A+\lambda I)^{-1}\Vert _{\infty }\Vert A-\lambda I\Vert _{\infty } <1\), which is impossible since \(\Vert (a+\lambda )^{-1}\Vert _w\Vert a-\lambda \Vert _w\ge \Vert (a+\lambda )^{-1}\Vert _{\infty }\Vert a-\lambda \Vert _{\infty }\ge |(a(z_0)+\lambda )^{-1}||a(z_0)-\lambda |=1\). \(\square \)

In what follows, we suppose that the set \(\mathcal {S}\) is nonempty so that Eq. (3.14) has a unique solution in the \(\mathcal {QT}_{\infty }\) class. Concerning the perturbed Eq. of (3.14), we have

$$\begin{aligned} (A+\varDelta _A)(X+\varDelta _X)+(X+ \varDelta _X)(A+\varDelta _A)=E+\varDelta _E, \end{aligned}$$
(3.16)

where \(\varDelta _A=T(\delta _a)+E_{\delta _a}\in \mathcal {QT}_{\infty }\) and \(\varDelta _E=T(\delta _e)+E_{\delta _e}\in \mathcal {QT}_{\infty }\).

Suppose

$$\begin{aligned} \Vert (A+\varDelta _A+\lambda I)^{-1}\Vert _{\infty }\Vert A+\varDelta _A-\lambda I\Vert _{\infty }<1 \end{aligned}$$
(3.17)

for some \(\lambda \in \mathcal {S}\). This assumption is shown to be feasible by numerical experiment. Then, the perturbed Eq. (3.16) has a unique solution \(X+\varDelta _X\in \mathcal {QT}_{\infty }\).

Taking difference of Eq. (3.16) with (3.14) and omitting the second and higher order terms in perturbations, we have

$$\begin{aligned} A\varDelta _X+\varDelta _XA\doteq \varDelta _E-X\varDelta _A-\varDelta _AX. \end{aligned}$$
(3.18)

Now we apply the perturbation results to Eq. (3.14). For the Toeplitz part, since a(z) is invertible in view of Lemma 3.1, we have

$$\begin{aligned} \delta _x=\frac{1}{2}a^{-1}(\delta _e-2x\delta _a), \end{aligned}$$

from which we obtain

$$\begin{aligned} \Vert \delta _x\Vert _{w}\le \frac{1}{2}\Vert a^{-1}\Vert _w(\Vert \delta _e\Vert _w+2\Vert x\Vert _w\Vert \delta _a\Vert _w). \end{aligned}$$
(3.19)

On the other hand, it is easy to get \(x(z)=\frac{1}{2}a(z)^{-1}e(z)\) so that \(\Vert x\Vert _w\le \frac{1}{2}\Vert a^{-1}e\Vert _w\). Let \(\xi =\max \{1, \Vert a^{-1}e\Vert _w\}\), it follows from (3.19) that

$$\begin{aligned} \Vert \delta _x\Vert _{w}\le \frac{\xi \Vert a^{-1}\Vert _w}{2}(\Vert \delta _e\Vert _w+\Vert \delta _a\Vert _w). \end{aligned}$$
(3.20)

Concerning the correction part, observe that Eq. (3.18) is equivalent to

$$\begin{aligned} (A+\lambda I)\varDelta _X+\varDelta _X(A-\lambda I)\doteq \varDelta _E-X\varDelta _A-\varDelta _AX \end{aligned}$$
(3.21)

for some \(\lambda \in \mathcal {S}\) such that (3.17) is satisfied. Set \(\tilde{\alpha }=\Vert (A+\lambda I)^{-1}\Vert _{\infty }\) and \(\tilde{\beta }=\Vert A-\lambda I\Vert _{\infty }\), then \(\tilde{\alpha }\tilde{\beta }<1\). We obtain from (3.21) that

$$\begin{aligned} \varDelta _X=\sum _{k=0}^{\infty }(-1)^k(A+\lambda I)^{-k-1}(\varDelta _E-X\varDelta _A-\varDelta _A X)(A-\lambda I)^k, \end{aligned}$$

which yields

$$\begin{aligned} \Vert \varDelta _X\Vert _{\infty }\le & {} \frac{\tilde{\alpha }}{1-\tilde{a}\tilde{\beta }}(\Vert \varDelta _E\Vert _{\infty }+2\Vert X\Vert _{\infty }\Vert \varDelta _A\Vert _{\infty })\nonumber \\\le & {} \frac{\tilde{\alpha }\tilde{\tau }}{1-\tilde{a}\tilde{\beta }}(\Vert \varDelta _E\Vert _{\infty }+\Vert \varDelta _A\Vert _{\infty }), \end{aligned}$$
(3.22)

where \(\tilde{\tau }= \max \{1, 2\Vert X\Vert _{\infty }\}\). It follows

$$\begin{aligned} \Vert E_{\delta _x}\Vert _{\infty }\le & {} \frac{\tilde{\alpha }\tilde{\tau }}{1-\tilde{a}\tilde{\beta }}(\Vert \varDelta _E\Vert _{\infty }+\Vert \varDelta _A\Vert _{\infty })+\Vert \delta _x\Vert _{w}\nonumber \\\le & {} \left( \frac{\tilde{\alpha }\tilde{\tau }}{1-\tilde{a}\tilde{\beta }}+\frac{\xi \Vert a^{-1}\Vert _w}{2}\right) (\Vert \varDelta _E\Vert _{\infty }+ \Vert \varDelta _A\Vert _{\infty }), \end{aligned}$$
(3.23)

where the last inequality follows from (3.20) and Lemma 2.3.

Observe that the perturbation bounds (3.22) and (3.23) shed light on how the whole solution and the correction part behave when the coefficients are perturbed by small perturbations. However they can be inaccurate since they are quite related to the value of some \(\lambda \in \mathcal {S}\).

Here we provide some insight on how to choose \(\lambda \) if \(A=T(a)\), where \(a(z)=\sum _{i\in \mathbb {Z}}a_iz^i\in \mathcal W\). This is a special case but has practical interest, see Example 5.2. Observe that we may choose \(\lambda \) such that the value \(\Vert (A+\lambda I)^{-1}\Vert _{\infty }\Vert A-\lambda I\Vert _{\infty }\) is far away from 1. For any \(\theta \in \mathbb {C}\) such that \(A+\theta I\) is invertible, we have \(\Vert (A+\theta I)^{-1}\Vert _{\infty }\Vert A-\theta I\Vert _{\infty }\ge \Vert (a+\theta )^{-1}\Vert _{w}\Vert a-\theta \Vert _w\ge \frac{\Vert a-\theta \Vert _w}{\Vert a+\theta \Vert _w}\). This inequality provides a good way to choose \(\lambda \), that is, we may choose \(\lambda \) such that \(\lambda =\arg \min _{\theta }\frac{\Vert a-\theta \Vert _w}{\Vert a+\theta \Vert _w}\), and one can see that \(\lambda =a_0\). Now let \(\lambda =a_0\) and \(B=A-\lambda I\), suppose \(|a_0|>\sum _{i\ne 0}|a_i|\), we have \(|\lambda |>\Vert B\Vert _{\infty }\) and

$$\begin{aligned} \Vert (A+\lambda I)^{-1}\Vert _{\infty }\Vert A-\lambda I\Vert _{\infty }&=\Vert (2\lambda I+B)^{-1}\Vert _{\infty }\Vert B\Vert _{\infty }\\&\le \frac{1}{2|\lambda |}\sum _{i=0}^{\infty }\frac{\Vert B\Vert ^i_{\infty }}{(2|\lambda |)^i}\Vert B\Vert _{\infty }\\&=\frac{\Vert B\Vert _{\infty }}{2|\lambda |-\Vert B\Vert _{\infty }}<1. \end{aligned}$$

From the above analysis, we can see that \(\lambda =a_0\) can be used in practice if \(A=T(a)\) and the symbol a satisfies \(|a_0|>\sum _{i\ne 0}|a_i|\).

4 A generalization

The perturbation results for the generalized Sylvester Eq. (1.1) are here applied to a more general type equation

$$\begin{aligned} \sum _{k=1}^nA_kXB_k=C, \end{aligned}$$
(4.1)

where \(A_k, B_k\), \(k=1,\ldots ,n\ (n\ge 3)\), and C belong to the \(\mathcal {QT}_{\infty }\) class. Observer that Eq. (4.1) has a unique solution \(X\in \mathcal {L}_{\infty }\) if the elementary operator \(\mathcal {T}: X\rightarrow \sum _{k=1}^nA_kXB_k\) is invertible in \(\mathcal {L}_{\infty }\). It was proved in [14, Theorem 4] that if \(A_iA_j=A_jA_i\) and \(B_iB_j=B_jB_i\) for \(\forall i,j\in \{1,\ldots ,n\}\), then the spectrum of \(\mathcal {T}\) satisfies

$$\begin{aligned} \sigma ({\mathcal T})\subset \Big \{\sum _{k=1}^n\alpha _k\beta _k: \alpha _k\in \sigma (A_k), \beta _k\in \sigma (B_k), 1\le k\le n\Big \}, \end{aligned}$$

which implies that \(\mathcal T\) is invertible in \(\mathcal {L}_{\infty }\) if \(0\notin \sum _{k=1}^n\sigma (A_k)\sigma (B_k)\).

Concerning matrices in the \(\mathcal {QT}_{\infty }\) class, it would be natural to ask if the set of commutative QT matrices is nonempty. We show by an interesting example that there are cases where the QT matrices are commutative. Consider the set \(\mathcal {C}=\{A_k=T(a_k)-H(a_k^{+})\): \(a_k(z)=\sum _{i\in \mathbb {Z}}a_i^{(k)}z^i\in \mathcal W\) and \(a_i^{(k)}\in \mathbb {R}\) satisfies \(a_i^{(k)}=a_{-i}^{(k)}\) for all \(i\in \mathbb {Z}\), \(H(a_k^{+})\) is a Hankel matrix such that \(H(a_k^{+})_{i,j}=(a^{(k)}_{i+j-1})_{i,j\in \mathbb {Z}^+}\)}. Observe that both \(T(a_k)\) and \(H(a_k^{+})\) are real symmetric and \(H(a_k^{+})=H(a_k^-)\), where \(H(a_k^-)\) is a Hankel matrix such that \(H(a_k^-)_{i,j}=(a^{(k)}_{-i-j+1})_{i,j\in \mathbb {Z}^+}\). For any \(A_k, A_{\ell }\in \mathcal C\), in view of Lemma 2.1, we have

$$\begin{aligned} A_kA_{\ell }=T(a_ka_{\ell })-T(a_k)H(a_{\ell }^+)-H(a_k^+)T(a_{\ell }),\\ \end{aligned}$$

and

$$\begin{aligned} A_{\ell }A_k=T(a_ka_{\ell })-T(a_{\ell })H(a_{k}^+)-H(a_{\ell }^+)T(a_{k}). \end{aligned}$$

A direct computation yields that \(T(a_k)H(a_{\ell }^+)+H(a_k^+)T(a_{\ell })=T(a_{\ell })H(a_{k}^+)+H(a_{\ell }^+)T(a_{k})\) so that \(A_kA_{\ell }=A_{\ell }A_k\).

4.1 Existence of QT solutions

Suppose there is at least a pair \((A_i, B_i)\), \(i=1,\ldots ,n\), such that both \(A_i\) and \(B_i\) are invertible in \(\mathcal {L}_{\infty }\). We provide an easy-to-check condition under which \(\mathcal T\) is invertible in \(\mathcal L_{\infty }\). In what follows, without loss of generality, we assume \(A_1\) and \(B_1\) are invertible.

Theorem 4.1

Assume \(A_1\) and \(B_1\) are invertible in \(\mathcal {L}_{\infty }\), \(A_iA_j=A_jA_i\) and \(B_iB_j=B_jB_i\), \(\forall i,j\in \{1,\ldots ,n\}\), and

$$\begin{aligned} \eta :=\Vert A_1^{-1}\Vert _{\infty }\Vert B_1^{-1}\Vert _{\infty }\left( \sum _{k=2}^n\Vert A_k\Vert _{\infty }\Vert B_k\Vert _{\infty }\right) <1, \end{aligned}$$

Then Eq. (4.1) has a unique solution in \(\mathcal {L}_{\infty }\) and

$$\begin{aligned} X=A_1^{-1}C B_1^{-1}+\sum _{k=1}^{\infty }\sum _{i_1,\ldots ,i_k=2}^n (-1)^kA_1^{-k-1} A_{i_1}\cdots A_{i_k} CB_{i_1}\cdots B_{i_k}B_1^{-k-1}. \end{aligned}$$
(4.2)

Moreover, if \(A_k, B_k, C\in \mathcal {QT}_{\infty }\) for \(k=1,\ldots , n\), then \(X\in \mathcal {QT}_{\infty }.\)

Proof

Set \(\eta _1=\Vert A_1^{-1}\Vert _{\infty }\Vert B_1^{-1}\Vert _{\infty }\), we have \(\sigma (A_1)\sigma (B_1)\subseteq \{z:|z|\ge \eta _1^{-1}\}\). Observe that \(\sum _{k=2}^n\Vert A_k\Vert _{\infty }\Vert B_k\Vert _{\infty }<\eta _1^{-1}\), we have \(\sum _{k=2}^n\sigma (A_k)\sigma (B_k)\subseteq \{z:|z|<\eta _1^{-1}\}\). It follows that \(0\notin \sum _{k=1}^n\sigma (A_k)\sigma (B_k)\). Hence the elementary operator \(\mathcal T: X\rightarrow \sum _{k=1}^nA_kXB_k\) is invertible and Eq. (4.1) has a unique solution in \(\mathcal {L}_{\infty }\). It is easy to check that X in (4.2) solves Eq. (4.1). We prove that the series in (4.2) converges in \(\mathcal {L}_{\infty }\).

Set \(\check{A}_{i_k}=A_1^{-1}A_{i_k}\) and \(\check{B}_{i_k}=B_{i_k}B_1^{-1}\) for \(k=1,\ldots , \infty \) and \(i_k=2,\ldots ,n\), concerning the commutativity of the coefficients, (4.2) is equivalent to

$$\begin{aligned} X=A_1^{-1}C B_1^{-1}+\sum _{k=1}^{\infty }\sum _{i_1,\ldots ,i_k=2}^n (-1)^k \check{A}_{i_1}\cdots \check{A}_{i_k} A_1^{-1}CB_1^{-1}\check{B}_{i_1}\cdots \check{B}_{i_k}. \end{aligned}$$
(4.3)

Write \(Q=A_1^{-1}CB_1^{-1}\), then \(Q\in \mathcal {L}_{\infty }.\) Observe that for \(j=1,\ldots ,k\), we have

$$\begin{aligned} \sum _{i_j=2}^n\Vert {\check{A}}_{i_j}\Vert _{\infty }\Vert {\check{B}}_{i_j}\Vert _{\infty }\le \Vert A_1^{-1}\Vert _{\infty }\Vert B_1^{-1}\Vert _{\infty }\Big (\sum _{i_j=2}^n\Vert A_{i_j}\Vert _{\infty }\Vert B_{i_j}\Vert _{\infty }\Big )=\eta <1. \end{aligned}$$

It follows from (4.3) that

$$\begin{aligned} \Vert X\Vert _{\infty }\le & {} \Vert Q\Vert _{\infty }+\Big \Vert \sum _{k=1}^{\infty }\sum _{i_1,\ldots ,i_k=2}^n{\check{A}}_{i_1}\cdots {\check{A}}_{i_k}Q {\check{B}}_{i_1}\cdots {\check{B}}_{i_k}\Big \Vert _{\infty }\nonumber \\\le & {} \Vert Q\Vert _{\infty }+\sum _{k=1}^{\infty } \Big (\sum _{{i_1}=2}^n \Vert {\check{A}}_{i_1}\Vert _{\infty }\Vert {\check{B}}_{i_1}\Vert _{\infty }\Big )\ldots \Big (\sum _{i_k=2}^n\Vert {\check{A}}_{i_k}\Vert _{\infty }\Vert {\check{B}}_{i_k}\Vert _{\infty }\Big )\Vert Q\Vert _{\infty }\nonumber \\\le & {} \sum _{k=0}^{\infty } \eta ^k\Vert Q\Vert _{\infty }=\frac{\Vert Q\Vert _{\infty }}{1-\eta }, \end{aligned}$$
(4.4)

from which we obtain \(X\in \mathcal {L}_{\infty }\).

Concerning the case where the coefficients \(A_k, B_k\), \(k=1,\ldots ,n\), and C are QT matrices, the proof to show \(X\in \mathcal {QT}_{\infty }\) is analogous to that of Theorem 2.3 and is omitted here. \(\square \)

Theorem 4.2

Assume that the assumptions in Theorem 4.1 hold true. For \(A_k=T(a_k)+E_k, B_k=T(b_k)+E_k, C=T(c)+E_c\in \mathcal {QT}_{\infty }\), \(k=1,\ldots ,n\), let \(X=T(x)+E_x\in \mathcal {QT}_{\infty }\) be the unique solution of Eq. (4.1), then

$$\begin{aligned} x(z)=\Big (\sum _{k=1}^na_k(z)b_k(z)\Big )^{-1}c(z). \end{aligned}$$

Proof

We have from

$$\begin{aligned} \sum _{k=1}^nA_kXB_k-C=T\Big (\Big (\sum _{k=1}^na_kb_k\Big )x-c\Big )+F=0 \end{aligned}$$

that \(\Big (\sum _{k=1}^na_k(z)b_k(z)\Big )x(z)=c(z)\). Since, for any \(z\in \mathbb {T}\), it holds \(a_k(z)\in \sigma (A_k)\) and \(b_k(z)\in \sigma (B_k)\) for \(k=1,\ldots ,n\), we have

$$\begin{aligned} \sum _{k=1}^n a_k(z)b_k(z)\in \sum _{k=1}^n \sigma (A_k)\sigma (B_k) \end{aligned}$$

for any \(z\in \mathbb {T}\). Note that \(0\notin \sum _{k=1}^n \sigma (A_k)\sigma (B_k)\) in view of the proof of Theorem 4.1, then \(\sum _{k=1}^n a_k(z)b_k(z)\ne 0\) for all \(z\in \mathbb {T}\), from which we have \(x(z)=\Big (\sum _{k=1}^na_k(z)b_k(z)\Big )^{-1}x(z)\). \(\square \)

4.2 Perturbation results

We are ready to extend the perturbation results to Eq. (4.1). Consider the perturbed matrix equation obtained from (4.1) by replacing the coefficients \(A_k\), \(B_k\) and C by \(A_k+\varDelta _{A_k}\), \(B_k+ \varDelta _{B_k}\) and \(C+\varDelta _C\), respectively, where \(\varDelta _{A_k}=T(\delta _{a_k})+E_{\delta _{a_k}}\in \mathcal {QT}_{\infty }\), \(\varDelta _{B_k}=T(\delta _{b_k})+E_{\delta _{b_k}}\in \mathcal {QT}_{\infty }\), \(k=1,\ldots ,n\), and \(\varDelta _C=T(\delta _c)+E_{\delta _c}\in \mathcal {QT}_{\infty }\). Denote by \(X+\varDelta _X\) the solution of the perturbed equation, we have

$$\begin{aligned} \sum _{k=1}^n(A_k+\varDelta _{A_k})(X+\varDelta _X)(B_k+\varDelta _{B_k})=C+\varDelta _C. \end{aligned}$$
(4.5)

In what follows, we suppose the assumptions in Theorem 4.1 are satisfied for the perturbed equation, then there is a unique \(X+\varDelta _X\in \mathcal {QT}_{\infty }\) solving Eq. (4.5). Write \(\varDelta _X=T(\delta _x)+E_{\delta _x}\), we have for the Toeplitz part

$$\begin{aligned} \Big (\sum _{k=1}^n a_kb_k\Big )\delta _x \doteq \delta _{c}-\sum _{k=1}^n(\delta _{a_k}xb_k+a_kx\delta _{b_k}). \end{aligned}$$

In view of the proof of Theorem 4.2, we know \(\sum _{k=1}^n a_k(z)b_k(z)\) is invertible, it follows

$$\begin{aligned} \delta _x \doteq \Big (\sum _{k=1}^n a_kb_k\Big )^{-1} \Big (\delta _{c}-\sum _{k=1}^n\Big (\delta _{a_k}b_k+a_k\delta _{b_k}\Big )x\Big ), \end{aligned}$$

which yields

$$\begin{aligned} \delta _x \dot{\le }\Big \Vert \Big (\sum _{k=1}^n a_kb_k\Big )^{-1}\Big \Vert _w\big (\Vert \delta _c\Vert _w+\sum _{k=1}^n(\Vert \delta _{a_k}\Vert _w\Vert b_k\Vert _w+\Vert \delta _{b_k}\Vert _w\Vert a_k\Vert _w)\Vert x\Vert _w\big ). \end{aligned}$$

Let

$$\begin{aligned} v_1=\max _k\{\Vert a_k\Vert _w\},\quad v_2=\max _k\{\Vert b_k\Vert _w\}, \quad \theta = \Big \Vert \Big (\sum _{k=1}^n a_kb_k\Big )^{-1}\Big \Vert _w\Vert c\Vert _w, \end{aligned}$$

and

$$\begin{aligned} \hat{\mu }=\max \{1, v_1\theta , v_2\theta \}. \end{aligned}$$
(4.6)

Note that \(\Vert x\Vert _w\le \Vert (\sum _{k=1}^n a_kb_k)^{-1}\Vert _w\Vert c\Vert _w\) in view of Theorem 4.2, we obtain

$$\begin{aligned} \Vert \delta _x\Vert _w\dot{\le } \hat{\mu } \Big \Vert \Big (\sum _{k=1}^n a_kb_k\Big )^{-1}\Big \Vert _w \Big (\sum _{k=1}^n \Big (\Vert \delta _{a_k}\Vert _w+\Vert \delta _{b_k}\Vert _w\Big )+\Vert \delta _c\Vert _w\Big ). \end{aligned}$$
(4.7)

Concerning the correction part, write \(\varDelta _V =\varDelta _C-\sum _{k=1}^n(\varDelta _{A_k}XB_k+A_kX\varDelta _{B_k})\), we have \({\mathcal T}(\varDelta _X) \doteq \varDelta _V\), where \(\mathcal {T}:X\rightarrow \sum _{k=1}^nA_kXB_k\) is the elementary operator. Since \(\mathcal {T}\) is invertible in view of the proof of Theorem 4.1, we have \(\varDelta _X\doteq \mathcal {T}^{-1}(\varDelta _V)\), which is

$$\begin{aligned} \varDelta _X \doteq A_1^{-1}\varDelta _VB_1^{-1}+\sum _{k=1}^{\infty }\sum _{i_1,\ldots ,i_k=2}^n(-1)^kA_1^{-k-1} A_{i_1}\cdots A_{i_k} \varDelta _V B_{i_1}\cdots B_{i_k}B_1^{-k-1}. \end{aligned}$$
(4.8)

Set \(\eta _1=\Vert A_1^{-1}\Vert _{\infty }\Vert B_1^{-1}\Vert _{\infty }\), \(\eta _2=\max \{\max _k \Vert A_k\Vert _{\infty }, \max _k\Vert B_k\Vert _{\infty }\}\) and \(\eta _3=\max \Big \{1, \frac{\eta _1\eta _2}{1-\eta }\Vert C\Vert _{\infty }\Big \}\), we obtain from (4.8) that

$$\begin{aligned}&\Vert \varDelta _X\Vert _{\infty }\dot{\le } \Vert A_1^{-1}\Vert _{\infty }\Vert B_1^{-1}\Vert _{\infty }\Big (\sum _{k=0}^{\infty }\eta ^k\Big )\Vert \varDelta _V\Vert _{\infty }\\&\quad =\frac{\eta _1}{1-\eta } \Big (\Vert \varDelta _C\Vert _{\infty }+\sum _{k=1}^n \Big (\Vert \varDelta _{A_k}\Vert _{\infty }\Vert B_k\Vert _{\infty }+\Vert \varDelta _{B_k}\Vert _{\infty }\Vert A_k\Vert _{\infty }\Big )\Vert X\Vert _{\infty }\Big )\\&\quad \le \frac{\eta _1\eta _3}{1-\eta }\Big (\Vert \varDelta _C\Vert _{\infty }+\sum _{k=1}^n\Big (\Vert \varDelta _{A_k}\Vert _{\infty }+\Vert \varDelta _{B_k}\Vert _{\infty }\Big )\Big ), \end{aligned}$$

where the last inequality follows from \(\Vert X\Vert _{\infty }\le \frac{\eta _1\Vert C\Vert _{\infty }}{1-\eta }\), which is obtained by (4.4).

Set

$$\begin{aligned} \hat{\delta }=\max \Big \{\max _k\Big \{\frac{\Vert \delta _{a_k}\Vert _w}{\Vert E_{\delta _{a_k}}\Vert _{\infty }}\Big \}, \max _k\Big \{\frac{\Vert \delta _{b_k}\Vert _w}{\Vert E_{\delta _{b_k}}\Vert _{\infty }}\Big \}, \frac{\Vert \delta _{c}\Vert _w}{\Vert E_{\delta _{c}}\Vert _{\infty }}\Big \}, \end{aligned}$$

if \(\hat{\delta }<\infty \), we obtain a bound for \(E_{\delta _x}\)

$$\begin{aligned} \Vert E_{\delta _x}\Vert _{\infty }\dot{\le } \hat{\kappa }(1+\hat{\delta })\Big (\sum _{k=1}^n (\Vert E_{\delta _{a_k}}\Vert _{\infty }+\Vert E_{\delta _{b_k}}\Vert _{\infty })+\Vert E_{\delta _{c}}\Vert _{\infty }\Big ), \end{aligned}$$

where \(\hat{\kappa }=\frac{\eta _1\eta _3}{1-\eta }+\hat{\mu }\Vert (\sum _{k=1}^na_kb_k)^{-1}\Vert _w\) and \(\hat{u}\) is defined in (4.6).

We may observe that the results we obtained can be used as a basis to solve equation of the form

$$\begin{aligned} \sum _{k=1}^nf_k(A)Xg_k(B)=C, \end{aligned}$$

where \(f_k(\cdot )\) and \(g_k(\cdot )\), \(k=1,\ldots , n\), are holomorphic functions in domains containing \(\sigma (A)\) and \(\sigma (B)\), respectively. An equation of this type in the (finite dimensional) matrix setting was studied in [21]. Concerning the case where \(A,B,C\in \mathcal {L}_{\infty }\) ( or \(A,B,C\in \mathcal {QT}_{\infty }\)), according to [14, Theorem 5], the spectrum of the operator \(\mathcal {R}: \mathcal {L}_{\infty }\rightarrow \mathcal {L}_{\infty }\) defined by \(\mathcal {R}(X)= \sum _{k=1}^{\infty }f_k(A)Xg_k(B)\) satisfies

$$\begin{aligned} \sigma (\mathcal {R})\subset \Big \{\sum _{k=1}^nf_k(\lambda _a)g_k(\lambda _b): \lambda _a\in \sigma (A)\ \mathrm{and}\ \lambda _b\in \sigma (B)\Big \}. \end{aligned}$$

Under certain conditions, it may be feasible to extend the results we have obtained to this equation. We leave this as a future consideration.

5 Numerical experiments

In this section, we apply the perturbation analysis to the generalized Sylvester Eq. (1.1). All the computations are performed in QT arithmetic relying on the operations implemented in cqt-toolbox [6]. The threshold used in the computations is set to \(10^{-12}\).

Example 5.1

This example is taken from Example 5.2 in [17], where a generalized Sylvester equation arising in solving a quadratic matrix equation \(A_1X^2+A_0X+A_{-1}=0\) by Newton’s method [7] is considered. The involved quadratic matrix equation arises in the analysis of a Markov process modeling a two-node Jackson network [16] and the matrices \(A_1,A_0, A_{-1}\) are nonnegative matrices with QT structure. When applying Newton’s method to the quadratic matrix equation, the computation of the Newton increment \(H_k\) at each step is reduced to solve an equation of the form

$$\begin{aligned} (A_1X_k+A_0-I)H+A_1HX_k=L(X_k), \end{aligned}$$
(5.1)

with \(L(X_k)=A_1X_k^2 + (A_0- I)X_k + A_{-1}\).

We consider the generalized Sylvester equation arising in the computation of the second Newton iterates \(X_2\), that is, we consider the equation

$$\begin{aligned} (A_1X_1+A_0-I)H+A_1HX_1=L(X_1), \end{aligned}$$
(5.2)

where \(X_1\) is obtained by using the Newton iteration in [7] and the solution H of the generalized Sylvester equation is computed using the Galerkin approach in [17]. We choose the coefficients \(A_1, A_0, A_{-1}\) from the 10 problems as in [7], Example 6.2] and perturb the coefficients by using the same technique as in [7].

It can be seen from [7] that \(A_1X_1+A_0-I\) is invertible in \(\mathcal {L}_{\infty }\). Moreover, \(\Vert (I-A_0-A_1X)^{-1}A_1\Vert _{\infty }<1\) and \(\Vert X_1\Vert _{\infty }\le 1\), according to Theorem 2.3, Eq. (5.2) has a unique solution \(H=T(h)+E_h\in \mathcal {QT}_{\infty }\). Moreover, the perturbed equation has a unique solution \(H+\varDelta _H\in \mathcal {QT}_{\infty }\) with \(\varDelta H=T(\delta _h)+E_{\delta _h}\).

Table 1 reports the value \(\delta \) defined in (3.12), the upper bound of the conditioning of the whole solution, which is cond\(_{H}=\frac{\alpha \gamma }{1-\alpha \beta }\). Recall that cond\(_{H}\) implies that the Toeplitz part is well-conditioned if it is a small number. In this experiment, we observe that \(\frac{\alpha \gamma }{1-\alpha \beta }\) provides a good estimate to the conditioning of the whole problem so that the Toeplitz part is well-conditioned, and together with \(\delta \), it implies that the correction part is also well-conditioned.

Denote by \(\delta _h\)-bound the bound (3.9) for the Toeplitz part and \(E_{\delta _h}\)-bound the bound (3.11) for the correction part. In Table 1, we compare these two perturbation bounds with the actual perturbation errors \(\Vert \delta _h\Vert _{w}\) and \(\Vert E_{\delta _h}\Vert _{\infty }\). It can be seen that, with respect to small perturbations on the coefficients, inequalities (3.9) and (3.11) provide sharp and revealing perturbation bounds to the Toeplitz part and to the correction part, respectively.

Table 1 Conditioning of the the whole solution of Eq. (5.2) and perturbation bounds: actual perturbations in the Toeplitz part and in the correction part and the related upper bounds
Full size table

Example 5.2

This example is taken from Example 5.1 in [17], where, in the solution of a 2D Poisson problem on the positive orthant, equation of the form

$$\begin{aligned} MX+XM=Q, \end{aligned}$$
(5.3)

is encountered, where \(M=(\varDelta t A-\frac{\varDelta x^2}{2}I)\) and \(Q=\varDelta x^2U_t-\varDelta x^2\varDelta t F\). Here, \(\varDelta x\) is the discretization step, \(\varDelta t\) is the time step, \(U_t\) is the solution of the Poisson problem at time t. Both A and F are QT matrices so that the coefficients M and Q are also QT matrices.

We perturb the matrix F by \(\varDelta _F\), where \(\varDelta _F=\texttt {cqt('hankel', dfm)}+\texttt {0.1*cqt(dfm,dfm)}\) with \(\texttt {dfm=rand*10}\hat{\,}{} \texttt {\{-8\}*fm}\), the construction of \(\texttt {fm}\) can be found in [17]. Matrix A is perturbed by \(\varDelta _A\), where \(\varDelta _A=\texttt {cqt}([-c1, c2],[-c1, c2])\) with \(c1=\texttt {rand}*10^{-8}\) and \(c2=\texttt {rand}*10^{-8}\). It can be examined that \(M+\lambda I\) is invertible for \(\lambda =1\). Moreover, it holds \(\Vert (M+\lambda I)^{-1}\Vert _{\infty }\Vert M-\lambda I\Vert _{\infty }<1\) and \(\Vert (M+\varDelta _M+\lambda I)^{-1}\Vert _{\infty }\Vert M+\varDelta _M-\lambda I\Vert _{\infty }<1\). Hence, there is unique \(X=T(x)+E_x\in \mathcal {QT}_{\infty }\) and \(X+\varDelta _X\) with \(\varDelta _X=T(\delta x)+E_{\delta _x}\) solving Eq. (5.3) and the corresponding perturbed equation, respectively.

As in [17], we consider the solution of Eq. (5.3) in \([0,2] \times [0,2]\) with timesteps \(\varDelta t=0.05, 0.10, 0.15, 0.20\), respectively. Table 2 reports two perturbation bounds (3.20) and (3.23), denoted by \(\delta _x\)-bound for the Toeplitz part and \(E_{\delta _x}\)-bound for the correction part, respectively. Comparison with the corresponding actual perturbation errors \(\Vert \delta _x\Vert _{w}\) and \(\Vert E_{\delta _x}\Vert _{\infty }\) indicates that these two bounds are sharp.

Table 2 Perturbation bounds for Eq. (5.3): actual perturbations in the Toeplitz part and in the correction part and the related upper bounds
Full size table

Example 5.3

Consider the equation \(X+A_1XA_2=A_3\), where \(A_1=T(a_1)\) with \(a_1(z)=\frac{1}{2}-\epsilon +\frac{1}{4}(z+z^{-1})\), where \(\epsilon >0\) is a small number, \(A_2=T(a_2)\) with \(a_2(z)=\frac{3}{5}+\frac{1}{5}z+\frac{1}{5}z^{-1}\) and \(A_3=\texttt {cqt(1,1)}\).

Observe that matrix \(A_1\) is nearly singular if \(\epsilon \) is close to 0, so that the computations involving matrix \(A_1\) are usually very sensitive to numerical errors. Choose \(\epsilon =0.006\), we perturbed \(A_i\), \(i=1,2,3\), by \(\varDelta _{A_i}=\texttt {cqt}(c_i,c_i)\), where \(c_i=\texttt {rand}*10^{-8}\). In this special case, the numerical results show that the perturbation bound for the Toeplitz part is 2.7493e-08 and the actual error is 1.4297e-08. For the perturbation bound of the whole problem, the upper bound of the conditioning is shown to be 1.0000e+02, and the perturbation bound is 2.3465e-06, compared with the actual error 1.4297e-08, we can see that the perturbation bound (3.5) is also descriptive of the errors when the problem is not well-conditioned.

6 Conclusion

We have analysed a generalized Sylvester equation with infinite size matrix coefficients in the \(\mathcal {QT}_{\infty }\) class of quasi Toeplitz matrices. Under sufficient conditions, we showed that an equation of this type has a unique solution in the \(\mathcal {QT}_{\infty }\) class. By separating the perturbation analysis of the Toeplitz part from the correction part, we provided perturbation results that cater to the particular QT structure. The perturbation results were also extended to an equation with a more general form.