Weighted least squares solutions to general coupled Sylvester matrix equations

This paper is concerned with weighted least squares solutions to general coupled Sylvester matrix equations. Gradient based iterative algorithms are proposed to solve this problem. This type of iterative algorithm includes a wide class of iterative algorithms, and two special cases of them are studied in detail in this paper. Necessary and sufficient conditions guaranteeing the convergence of the proposed algorithms are presented. Sufficient conditions that are easy to compute are also given. The optimal step sizes such that the convergence rates of the algorithms, which are properly defined in this paper, are maximized and established. Several special cases of the weighted least squares problem, such as a least squares solution to the coupled Sylvester matrix equations problem, solutions to the general coupled Sylvester matrix equations problem, and a weighted least squares solution to the linear matrix equation problem are simultaneously solved. Several numerical examples are given to illustrate the effectiveness of the proposed algorithms.     

LSQR iterative method for generalized coupled Sylvester matrix equations

An iterative method is proposed to solve generalized coupled Sylvester matrix equations, based on a matrix form of the least-squares QR-factorization (LSQR) algorithm. By this iterative method on the selection of special initial matrices, we can obtain the minimum Frobenius norm solutions or the minimum Frobenius norm least-squares solutions over some constrained matrices, such as symmetric, generalized bisymmetric and (R, S)-symmetric matrices. Meanwhile, the optimal approximate solutions to the given matrices can be derived by solving the corresponding new generalized coupled Sylvester matrix equations. Finally, numerical examples are given to illustrate the effectiveness of the present method.     

Singularity, Wielandt’s lemma and singular values

In this study, some upper and lower bounds for singular values of a general complex matrix are investigated, according to singularity and Wielandt’s lemma of matrices. Especially, some relationships between the singular values of the matrix A and its block norm matrix are established. Based on these relationships, one may obtain the effective estimates for the singular values of large matrices by using the lower dimension norm matrices. In addition, a small error in Piazza (2002) [G. Piazza, T. Politi, An upper bound for the condition number of a matrix in spectral norm, J. Comput. Appl. Math. 143 (1) (2002) 141-144] is also corrected. Some numerical experiments on saddle point problems show that these results are simple and sharp under suitable conditions.     

Cauchy-type determinants and integrable systems

It is well known that the Sylvester matrix equation AX + XB = C has a unique solution X if and only if 0 ∉ spec(A) + spec(B). The main result of the present article are explicit formulas for the determinant of X in the case that C is one-dimensional. For diagonal matrices A, B, we reobtain a classical result by Cauchy as a special case.The formulas we obtain are a cornerstone in the asymptotic classification of multiple pole solutions to integrable systems like the sine-Gordon equation and the Toda lattice. We will provide a concise introduction to the background from soliton theory, an operator theoretic approach originating from work of Marchenko and Carl, and discuss examples for the application of the main results.     

Weighted and deflated global GMRES algorithms for solving large Sylvester matrix equations

The solution of a large-scale Sylvester matrix equation plays an important role in control and large scientific computations. In this paper, we are interested in the large Sylvester matrix equation with large dimensionA and small dimension B, and a popular approach is to use the global Krylov subspace method. In this paper, we propose three new algorithms for this problem. We first consider the global GMRES algorithm with weighting strategy, which can be viewed as a precondition method. We present three new schemes to update the weighting matrix during iterations. Due to the growth of memory requirements and computational cost, it is necessary to restart the algorithm effectively. The deflation strategy is efficient for the solution of large linear systems and large eigenvalue problems; to the best of our knowledge, little work is done on applying deflation to the (weighted) global GMRES algorithm for large Sylvester matrix equations. We then consider how to combine the weighting strategy with deflated restarting, and propose a weighted global GMRES algorithm with deflation for solving large Sylvester matrix equations. In particular, we are interested in the global GMRES algorithm with deflation, which can be viewed as a special case when the weighted matrix is chosen as the identity. Theoretical analysis is given to show rationality of the new algorithms. Numerical experiments illustrate the numerical behavior of the proposed algorithms.

     

一类广义Sylvester方程的反对称最小二乘解及其最佳逼近

本文利用矩阵的奇异值分解(SVD),给出了广义Sylvester矩阵方程AX YA=C反对称解存在的充分必要条件,导出了其反对称解和反对称最小二乘解的表达式,同时在解集合中得到了对给定矩阵的最佳逼近解.     

Simultaneous solutions of Sylvester equations and idempotent matrices separating the joint spectrum

We investigate simultaneous solutions of the matrix Sylvester equations A_iX-XB_i=C_i,i=1,2,…,k, where {A₁,…,A_k} and {B₁,…,B_k} are k-tuples of commuting matrices of order m×m and p×p, respectively. We show that the matrix Sylvester equations have a unique solution X for every compatible k-tuple of m×p matrices {C₁,…,C_k} if and only if the joint spectra σ(A₁,…,A_k) and σ(B₁,…,B_k) are disjoint. We discuss the connection between the simultaneous solutions of Sylvester equations and related questions about idempotent matrices separating disjoint subsets of the joint spectrum, spectral mapping for the differences of commuting k-tuples, and a characterization of the joint spectrum via simultaneous solutions of systems of linear equations.     

On some iterations for optimal control of jump linear equations

We consider different iterative methods for computing Hermitian solutions of the coupled Riccati equations of the optimal control problem for jump linear systems. We have constructed a sequence of perturbed Lyapunov algebraic equations whose solutions define matrix sequences with special properties proved under proper initial conditions. Several numerical examples are included to illustrate the effectiveness of the considered iterations.     

Schröder matrix as inverse of Delannoy matrix

Using Riordan arrays, we introduce a generalized Delannoy matrix by weighted Delannoy numbers. It turns out that Delannoy matrix, Pascal matrix, and Fibonacci matrix are all special cases of the generalized Delannoy matrices, meanwhile Schröder matrix and Catalan matrix also arise in involving inverses of the generalized Delannoy matrices. These connections are the focus of our paper. The half of generalized Delannoy matrix is also considered. In addition, we obtain a combinatorial interpretation for the generalized Fibonacci numbers.     

Convergence of block iterative methods applied to sparse least-squares problems

Recently, special attention has been given, in the mathematical literature, to the problems of accurately computing the least-squares solutions of very large-scale overdetermined systems of linear equations, such as those arising in geodetical network problems. In particular, it has been suggested that one solve such problems, iteratively by applying the block-SOR (successive overrelaxation) iterative method to a consistently ordered block-Jacobi matrix that is weakly cyclic of index 3. Here, we obtain new results (Theorem 1), giving the exact convergence and divergence domains for such iterative applications. It is then shown how these results extend, and correct, the literature on such applications. In addition, analogous results (Theorem 2) are given for the case when the eigenvalues of the associated block-Jacobi matrix are nonnegative.     

Three positive solutions of singular nonlocal boundary value problems for systems of nonlinear second-order ordinary differential equations

In this paper, we consider the existence of at least three positive solutions of singular nonlocal boundary value problems for systems of nonlinear second-order ordinary differential equations. The associated Green’s function for the boundary value problems is first given. The proofs of our main results are based upon the Leggett–Williams fixed point theorem. Finally, we give an example to demonstrate our result.     

A note on the iterative solutions of general coupled matrix equation

Recently, Ding and Chen [F. Ding, T. Chen, On iterative solutions of general coupled matrix equations, SIAM J. Control Optim. 44 (2006) 2269-2284] developed a gradient-based iterative method for solving a class of coupled Sylvester matrix equations. The basic idea is to regard the unknown matrices to be solved as parameters of a system to be identified, so that the iterative solutions are obtained by applying hierarchical identification principle. In this note, by considering the coupled Sylvester matrix equation as a linear operator equation we give a natural way to derive this algorithm. We also propose some faster algorithms and present some numerical results.     

Expansion of weighted pseudoinverse matrices with singular weights into matrix power products and iteration methods

We obtain expansions of weighted pseudoinverse matrices with singular weights into matrix power products with negative exponents and arbitrary positive parameters. We show that the rate of convergence of these expansions depends on a parameter. On the basis of the proposed expansions, we construct and investigate iteration methods with quadratic rate of convergence for the calculation of weighted pseudoinverse matrices and weighted normal pseudosolutions. Iteration methods for the calculation of weighted normal pseudosolutions are adapted to the solution of least-squares problems with constraints. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 9, pp. 1269–1289, September, 2007.     

Bounds for norms of the matrix inverse and the smallest singular value

In the first part, we obtain two easily calculable lower bounds for ‖A^-1‖, where ‖·‖ is an arbitrary matrix norm, in the case when A is an M-matrix, using first row sums and then column sums. Using those results, we obtain the characterization of M-matrices whose inverses are stochastic matrices. With different approach, we give another easily calculable lower bounds for ‖A^-1‖_∞ and ‖A^-1‖₁ in the case when A is an M-matrix. In the second part, using the results from the first part, we obtain our main result, an easily calculable upper bound for ‖A^-1‖₁ in the case when A is an SDD matrix, thus improving the known bound. All mentioned norm bounds can be used for bounding the smallest singular value of a matrix.     

Relative perturbation bounds for the unitary polar factor

LetB be anm×n (m≥n) complex (or real) matrix. It is known that there is a uniquepolar decomposition B=QH, whereQ*Q=I, then×n identity matrix, andH is positive definite, providedB has full column rank. Existing perturbation bounds suggest that in the worst case, for complex matrices the change inQ be proportional to the reciprocal ofB's least singular value, or the reciprocal of the sum ofB's least and second least singular values if matrices are real. However, there are situations where this unitary polar factor is much more accurately determined by the data than the existing perturbation bounds would indicate. In this paper the following question is addressed: how much mayQ change ifB is perturbed to $\tilde B = D_1^* BD_2 $ , whereD ₁ andD ₂ are nonsingular and close to the identity matrices of suitable dimensions? It is shown that for a such kind of perturbation, the change inQ is bounded only by the distances fromD ₁ andD ₂ to identity matrices and thus is independent ofB's singular values. Such perturbation is restrictive, but not unrealistic. We show how a frequently used scaling technique yields such a perturbation and thus scaling may result in better-conditioned polar decompositions.     

An analysis of the matrix equation <Emphasis Type="Italic">AX + X̄B = C</Emphasis>

The matrix equation AX + X?B = C, where X?B is obtained by the entry-wise conjugation of X, is examined. On the basis of analogy with the Sylvester matrix equation, special cases are distinguished where the former equation corresponds to normal and self-adjoint Sylvester equations. Efficient numerical algorithms are proposed for these special cases.     

Alexandroff-Bakelman-Pucci estimate and Harnack inequality for degenerate/singular fully non-linear elliptic equations

In this paper, we study fully non-linear elliptic equations in non-divergence form which can be degenerate or singular when “the gradient is small”. Typical examples are either equations involving the m-Laplace operator or Bellman-Isaacs equations from stochastic control problems. We establish an Alexandroff-Bakelman-Pucci estimate and we prove a Harnack inequality for viscosity solutions of such non-linear elliptic equations.     

Finite iterative method for solving coupled Sylvester-transpose matrix equations

This paper is concerned with solutions to the so-called coupled Sylvester-transpose matrix equations, which include the generalized Sylvester matrix equation and Lyapunov matrix equation as special cases. By extending the idea of conjugate gradient method, an iterative algorithm is constructed to solve this kind of coupled matrix equations. When the considered matrix equations are consistent, for any initial matrix group, a solution group can be obtained within finite iteration steps in the absence of roundoff errors. The least Frobenius norm solution group of the coupled Sylvester-transpose matrix equations can be derived when a suitable initial matrix group is chosen. By applying the proposed algorithm, the optimal approximation solution group to a given matrix group can be obtained by finding the least Frobenius norm solution group of new general coupled matrix equations. Finally, a numerical example is given to illustrate that the algorithm is effective.     

A functional approach to the Stein equation

This paper applies the theory of tensor products of functional models to the study of the Stein equation. We analyse the connections between the Sylvester and Stein equations, as well as those between the Anderson-Jury Bezoutian associated with the polynomial Sylvester equation and the T-Bezoutian associated with the homogeneous polynomial Stein equation. The functional setting allows us to extend the theory of finite section Toeplitz matrices and their inversion.     

Matrix polynomials satisfying first order differential equations and three term recurrence relations

We describe families of matrix valued polynomials satisfying simultaneously a first order differential equation and a three term recurrence relation. Our goal is to address the classification of the matrix valued polynomials satisfying first order differential equations through the solutions of the so-called bispectral problem. At the heart of this lies the need to solve some complicated nonlinear equations with matrix coefficients called ad-conditions. The solutions of these equations are studied under a variety of sufficient conditions on its coefficients.