A Note on the Inversion of Sylvester Matrices in Control Systems

Abstract

We give a sufficient condition (the solvability of two standard equations) of Sylvester matrix by using the displacement structure of the Sylvester matrix, and, according to the sufficient condition, we derive a new fast algorithm for the inversion of a Sylvester matrix, which can be denoted as a sum of products of two triangular Toeplitz matrices. The stability of the inversion formula for a Sylvester matrix is also considered. The Sylvester matrix is numerically forward stable if it is nonsingular and well conditioned.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Recommended by Gradimir V. Milovanovic

College of Science, Shandong University of Technology, Shandong 255049, China

Received 21 November 2010; Revised 28 February 2011; Accepted 31 March 2011

1. Introduction

Let R[x] be the space of polynomials over the real numbers. Given univariate polynomials f(x),g(x)∈R[x] , _a1 ≠0 , where [figure omitted; refer to PDF]

Let S denote the Sylvester matrix of f(x) and g(x): [figure omitted; refer to PDF]

Sylvester matrix is applied in many science and technology fields. The solutions of Sylvester matrix equations and matrix inequations play an important role in the analysis and design of control systems. In determining the greatest common divisor of two polynomials, the Sylvester matrix plays a vital role, and the magnitude of the inverse of the Sylvester matrix is important in determining the distance to the closest polynomials which have a common root. Assuming that all principal submatrices of the matrix are nonsingular, in [1], Jing Yang et al. have given a fast algorithm for the inverse of Sylvester matrix by using the displacement structure of m+n -order Sylvester matrix.

By using the displacement structure of the Sylvester matrix, in this paper, we give a sufficient condition (the solvability of two standard equations) of Toeplitz matrix, and, according to the sufficient condition, we derive a new fast algorithm for the inversion of a Sylvester matrix, which can be denoted as a sum of products of two triangular Toeplitz matrices. At last, the stability of the inversion formula for a Sylvester matrix is also considered. The Sylvester matrix is numerically forward stable if it is nonsingular and well conditioned.

In this paper, _||·||2 always denotes the Euclidean or spectral norm and _||·||F the Frobenius norm.

2. Preliminary Notes

In this section, we present a lemma that is important to our main results.

Lemma 2.1 (see [2, Section 2.4.8 ]).

Let A,B∈^...n,n and α∈... . Then for any floating-point arithmetic with machine precision [straight epsilon] , one has that [figure omitted; refer to PDF] As usual, one neglects the errors of O(^{[straight epsilon]2} ) , O(^{[straight epsilon]...2} ) , and O([straight epsilon][straight epsilon]...) .

3. Sylvester Inversion Formula

In this section, we present our main results.

Theorem 3.1.

Let matrix S be a Sylvester matrix; then it satisfies the formula [figure omitted; refer to PDF] where K=(0 _{e1 e2} ... _em+n-1 ) is a (m+n)×(m+n) shift matrix, [figure omitted; refer to PDF]

Proof.

We have that [figure omitted; refer to PDF] So KS-SK=_em^fT -_em+n^gT .

Theorem 3.2.

Let matrix S be a Sylvester matrix and x=^{(_{x1 x2} ... _xm+n )T} , y= ^{(_{y1 y2} ... _ym+n )T} , μ=^{(_{μ1 μ2} ... _μm+n )T} , and V=^{(_{V1 V2} ... _Vm+n )T} the solutions of the systems of equations Sx=_em , Sy=_em+n , ^ST μ=f , and ^ST V=g , respectively, where _em and _em+n are both (m+n)×1 vectors; then

(a) S is invertible, and the column vector _wj (j=1,2,...,m+n) of ^S-1 satisfies the recurrence relation

[figure omitted; refer to PDF]

(b)

[figure omitted; refer to PDF]

Proof.

By Theorem 3.1 Sx=_em and Sy=_em+n , we have that [figure omitted; refer to PDF] so [figure omitted; refer to PDF] Hence, we have that [figure omitted; refer to PDF] Let [figure omitted; refer to PDF] It is easy to see that ^Ki_em+n =_em+n-i , and by (3.8) [figure omitted; refer to PDF] From Sy=_em+n , we have that _wm+n =y . Let X=(_{w1 w2} ... _wm+n ) ; then [figure omitted; refer to PDF] so the matrix S is invertible and the inverse of S is the matrix X .

From (3.1), we have that [figure omitted; refer to PDF] and thus [figure omitted; refer to PDF]

So [figure omitted; refer to PDF]

Since K_ei =_ei-1 , we have that [figure omitted; refer to PDF] and hence [figure omitted; refer to PDF]

For (b), by (3.4) [figure omitted; refer to PDF] So [figure omitted; refer to PDF] This completes the proof.

4. Stability Analysis

In this section, we will show that the Sylvester inversion formula presented in this paper is evaluation forward stable.

If, for all well conditioned problems, the computed solution x... is close to the true solution x , in the sense that the relative error _||x-x...||2 /_||x||2 is small, then we call the algorithm forward stable (the author called this weakly in [3]). Round-off errors will occur in the matrix computation.

Theorem 4.1.

Let matrix S be a nonsingular Sylvester matrix and well conditioned; then the formula in Theorem 3.2 is forward stable.

Proof.

Assume that we have computed the solutions x..., y..., μ... , and V... of Sx=_em , Sy=_em+n , ^ST μ=f , and ^ST V=g in Theorem 3.2 which are perturbed by the normwise relative errors bounded by [straight epsilon]... , [figure omitted; refer to PDF]

Thus, we have that [figure omitted; refer to PDF]

The inversion formula in Theorem 3.2, using the perturbed solutions x... , y... , μ... , and V... , can be expressed as [figure omitted; refer to PDF] Here, and in the sequel, E is the matrix containing the error which results from computing the matrix products and F contains the error from subtracting the matrices. For the error matrices Δ_S1 , Δ_U1 , Δ_S2 , and Δ_U2 , we have that [figure omitted; refer to PDF]

By Lemma 2.1, we have the following bounds on E and F : [figure omitted; refer to PDF]

Consequently, adding all these error bounds, by (4.3), we have that [figure omitted; refer to PDF]

From the equations Sx=_em , Sy=_em+n ^ST μ=f , and ^ST V=g in Theorem 3.2, we have that [figure omitted; refer to PDF]

Thus, the relative error is [figure omitted; refer to PDF]

Since S is well conditioned, _{||^S-1 ||2} is finite. It is easy to see that ^||g||2 ,^||f||2 are finite. Therefore, the formula presented in Theorem 3.2 is forward stable.

This completes the proof.

5. Numerical Example

This section gives an example to illustrate our results. All the following tests are performed by MATLAB 7.0.

Example 5.1.

Given f(x)=x+1, g(x)=^x2 +x+1 , that is, _a1 =1 , _a2 =1 , _b1 =1 , _b2 =1 , _b3 =1 , n=1 , m=2 , f=^(1,1,0)T , g=^(0,1,1)T , and S=(110011111) .

So [figure omitted; refer to PDF] [figure omitted; refer to PDF] Therefore, KS-SK=_em^fT -_em+n^gT .

By the condition of Theorem 3.2, we can get [figure omitted; refer to PDF] Obviously, S is invertible and ^S-1 =(0-1111-1-101). And it is easy to see that _w3 =y , [figure omitted; refer to PDF]

Acknowledgments

This work was supported financially by the Youth Foundation of Shandong Province, China (ZR2010EQ014), Shandong Province Natural Science Foundation (ZR2010AQ026), and National Natural Science Foundation of China (11026047).

References

[1] J. Yang, Z. Xu, Q. Lu, "A fast algorithm for the inverse of Sylvester matrices," Journal on Numerical Methods and Computer Applications , vol. 31, no. 2, pp. 92-98, 2010.

[2] G. H. Golub, C. F. Van Loan Matrix Computations , vol. 3, of Johns Hopkins Series in the Mathematical Sciences, pp. xxii+642, Johns Hopkins University Press, Baltimore, Md, USA, 1989., 2nd.

[3] J. R. Bunch, "The weak and strong stability of algorithms in numerical linear algebra," Linear Algebra and Its Applications , vol. 88/89, pp. 49-66, 1987.