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.     

On algebraic Riccati equations associated with M-matrices

We consider the algebraic Riccati equation for which the four coefficient matrices form an M-matrix K. When K is a nonsingular M-matrix or an irreducible singular M-matrix, the Riccati equation is known to have a minimal nonnegative solution and several efficient methods are available to find this solution. In this paper we are mainly interested in the case where K is a reducible singular M-matrix. Under a regularity assumption on the M-matrix K, we show that the Riccati equation still has a minimal nonnegative solution. We also study the properties of this particular solution and explain how the solution can be found by existing methods.     

Transformations between discrete-time and continuous-time algebraic Riccati equations

We introduce a transformation between the discrete-time and continuous-time algebraic Riccati equations. We show that under mild conditions the two algebraic Riccati equations can be transformed from one to another, and both algebraic Riccati equations share common Hermitian solutions. The transformation also sets up the relations about the properties, commonly in system and control setting, that are imposed in parallel to the coefficient matrices and Hermitian solutions of two algebraic Riccati equations. The transformation is simple and all the relations can be easily derived. We also introduce a generalized transformation that requires weaker conditions. The proposed transformations may provide a unified tool to develop the theories and numerical methods for the algebraic Riccati equations and the associated system and control problems.     

Convergence rates of some iterative methods for nonsymmetric algebraic Riccati equations arising in transport theory

We determine and compare the convergence rates of various fixed-point iterations for finding the minimal positive solution of a class of nonsymmetric algebraic Riccati equations arising in transport theory.     

The general coupled matrix equations over generalized bisymmetric matrices

In the present paper, by extending the idea of conjugate gradient (CG) method, we construct an iterative method to solve the general coupled matrix equations

     

Sensitivity analysis of the algebraic Riccati equations

Summary. In this paper, some sharp perturbation bounds for the Hermitian positive semi-definite solution to an algebraic Riccati equation are developed. A further analysis for these bounds is done. This analysis shows that there is, presumably, some intrinsic relation between the sensitivity of the solution to the algebraic Riccati equation and the distance of the spectrum of the closed-loop matrix from the imaginary axis. Received December 16, 1994     

Residual bounds of approximate solutions of the discrete-time algebraic Riccati equation

Let be a Hermitian matrix which approximates the unique Hermitian positive semi-definite solution to the discrete-time algebraic Riccati equation (DARE) where , is Hermitian positive definite, , the pair is stabilizable, and the pair is detectable. Assume that is nonsingular, and is stable. Let , and let be the residual of the DARE with respect to . Define the linear operator by The main result of this paper is: If where denotes any unitarily invariant norm, and then Received June 7, 1995 / Revised version received February 28, 1996     

A posteriori error estimates for linear equations

Summary This paper describes upper and lowerp-norm error bounds for approximate solutions of the linear system of equationsAx=b. These bounds imply that the error is proportional to the quantity wherer is the residual andq is the conjugate index top. The constant of proportionality is larger than 1 and lies in a specified range. Similar results are obtained for approximations toA ^–1 and solutions of nonsingular linear equations on general spaces.Research was partially supported by NSF Grant DMS8901477     

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.     

Approximate iterations for structured matrices

Important matrix-valued functions f (A) are, e.g., the inverse A ⁻¹, the square root and the sign function. Their evaluation for large matrices arising from pdes is not an easy task and needs techniques exploiting appropriate structures of the matrices A and f (A) (often f (A) possesses this structure only approximately). However, intermediate matrices arising during the evaluation may lose the structure of the initial matrix. This would make the computations inefficient and even infeasible. However, the main result of this paper is that an iterative fixed-point like process for the evaluation of f (A) can be transformed, under certain general assumptions, into another process which preserves the convergence rate and benefits from the underlying structure. It is shown how this result applies to matrices in a tensor format with a bounded tensor rank and to the structure of the hierarchical matrix technique. We demonstrate our results by verifying all requirements in the case of the iterative computation of A ⁻¹ and . This work was performed during the stay of the third author at the Max-Planck-Institute for Mathematics in the Sciences (Leipzig) and also supported by the Russian Fund of Basic Research (grants 05-01-00721, 04-07-90336) and a Priority Research Grant of the Department of Mathematical Sciences of the Russian Academy of Sciences.     

Matrix commutators: their asymptotic metric properties and relation to approximate joint diagonalization

We analyze the properties of the norm of the commutator of two Hermitian matrices, showing that asymptotically it behaves like a metric, and establish its relation to joint approximate diagonalization of matrices, showing that almost-commuting matrices are almost jointly diagonalizable, and vice versa. We show an application of our results in the field of 3D shape analysis.     

Vector least-squares solutions for coupled singular matrix equations

The weighted least-squares solutions of coupled singular matrix equations are too difficult to obtain by applying matrices decomposition. In this paper, a family of algorithms are applied to solve these problems based on the Kronecker structures. Subsequently, we construct a computationally efficient solutions of coupled restricted singular matrix equations. Furthermore, the need to compute the weighted Drazin and weighted Moore–Penrose inverses; and the use of Tian's work and Lev-Ari's results are due to appearance in the solutions of these problems. The several special cases of these problems are also considered which includes the well-known coupled Sylvester matrix equations. Finally, we recover the iterative methods to the weighted case in order to obtain the minimum D-norm G-vector least-squares solutions for the coupled Sylvester matrix equations and the results lead to the least-squares solutions and invertible solutions, as a special case.     

Accelerated Landweber iterations for the solution of ill-posed equations

Summary In this paper, the potentials of so-calledlinear semiiterative methods are considered for the approximate solution of linear ill-posed problems and ill conditioned matrix equations. Several efficient two-step methods are presented, most of which have been introduced earlier in the literature. Stipulating certain conditions concerning the smoothness of the solution, a notion of optimal speed of convergence may be formulated. Various direct and converse results are derived to illustrate the properties of this concept.If the problem's right hand side data are contaminated by noise, semiiterative methods may be used asregularization methods. Assuming optimal rate of convergence of the iteration for the unperturbed problem, the regularized approximations will be of order optimal accuracy.To derive these results, specific properties of polynomials are used in connection with the basic theory of solving ill-posed problems. Rather recent results onfast decreasing polynomials are applied to answer an open question of Brakhage.Numerical examples are given including a comparison to the method of conjugate gradients.This research was sponsored by the Deutsche Forschungsgemeinschaft (DFG).     

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.     

Structured eigenvalue condition numbers and linearizations for matrix polynomials

This work is concerned with eigenvalue problems for structured matrix polynomials, including complex symmetric, Hermitian, even, odd, palindromic, and anti-palindromic matrix polynomials. Most numerical approaches to solving such eigenvalue problems proceed by linearizing the matrix polynomial into a matrix pencil of larger size. Recently, linearizations have been classified for which the pencil reflects the structure of the original polynomial. A question of practical importance is whether this process of linearization significantly increases the eigenvalue sensitivity with respect to structured perturbations. For all structures under consideration, we show that this cannot happen if the matrix polynomial is well scaled: there is always a structured linearization for which the structured eigenvalue condition number does not differ much. This implies, for example, that a structure-preserving algorithm applied to the linearization fully benefits from a potentially low structured eigenvalue condition number of the original matrix polynomial.     

Characterizations of the polynomial numerical hull of degree k

Six characterizations of the polynomial numerical hull of degree k are established for bounded linear operators on a Hilbert space. It is shown how these characterizations provide a natural distinction between interior and boundary points. One of the characterizations is used to prove that the polynomial numerical hull of any fixed degree k for a Toeplitz matrix whose symbol is piecewise continuous approaches all or most of that of the infinite-dimensional Toeplitz operator, as the matrix size goes to infinity.     

Spline collocation for strongly elliptic equations on the torus

Summary We prove convergence and error estimates in Sobolev spaces for the collocation method with tensor product splines for strongly elliptic pseudodifferential equations on the torus. Examples of applications include elliptic partial differential equations with periodic boundary conditions but also the classical boundary integral operators of potential theory on torus-shaped domains in three or more dimensions. For odd-degree splines, we prove convergence of nodal collocation for any strongly elliptic operator. For even-degree splines and midpoint collocation, we find an additional condition for the convergence which is satisfied for the classical boundary integral operators. Our analysis is a generalization to higher dimensions of the corresponding analysis of Arnold and Wendland [4].     

Fast Fourier-Galerkin methods for solving singular boundary integral equations: Numerical integration and precondition

We develop a fast fully discrete Fourier-Galerkin method for solving a class of singular boundary integral equations. We prove that the number of multiplications used in generating the compressed matrix is O(nlog³n), and the solution of the proposed method preserves the optimal convergence order O(n^−t), where n is the order of the Fourier basis functions used in the method and t denotes the degree of regularity of the exact solution. Moreover, we propose a preconditioning which ensures the numerical stability when solving the preconditioned linear system. Numerical examples are presented to confirm the theoretical estimates and to demonstrate the approximation accuracy and computational efficiency of the proposed algorithm.     

Perturbation bounds for polynomials

Using two different elementary approaches we derive a global and a local perturbation theorem on polynomial zeros that significantly improve the results of Ostrowski (Acta Math 72:99–257, 1940), Elsner et al. (Linear Algebra Appl 142:195–209, 1990). A comparison of different perturbation bounds shows that our results are better in many cases than the similar local result of Beauzamy (Can Math Bull 42(1):3–12, 1999). Using the matrix theoretical approach we also improve the backward stability result of Edelman and Murakami (Proceedings of the Fifth SIAM Conference on Applied Linear Algebra, SIAM, Philapdelphia, 1994; Math Comput 64:210–763, 1995).