On equivalence of pencils from discrete-time and continuous-time control

We study two matrix pencils that arise, respectively, in discrete-time and continuous-time optimal and robust control. We introduce a one-to-one transformation between these two pencils. We show that for the pencils under the transformation, their regularity is preserved and their eigenvalues and deflating subspaces are equivalently related. The eigen-structures of the pencils under consideration have strong connections with the associated control problems. Our result may be applied to connect the discrete-time and continuous-time control problems and eventually lead to a unified treatment of these two types of control problems.     

Stein iterations for the coupled discrete-time Riccati equations

We consider a set of discrete-time coupled algebraic Riccati equations that arise in quadratic optimal control of Markovian jump linear systems. Two iterations for computing a symmetric (maximal) solution of this system are investigated. We construct sequences of the solutions of the decoupled Stein equations and show that these sequences converge to a solution of the considered system. Numerical experiments are given.     

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     

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.     

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.     

A numerical method for computing the Hamiltonian Schur form

We derive a new numerical method for computing the Hamiltonian Schur form of a Hamiltonian matrix that has no purely imaginary eigenvalues. We demonstrate the properties of the new method by showing its performance for the benchmark collection of continuous-time algebraic Riccati equations. Despite the fact that no complete error analysis for the method is yet available, the numerical results indicate that if no eigenvalues of are close to the imaginary axis then the method computes the exact Hamiltonian Schur form of a nearby Hamiltonian matrix and thus is numerically strongly backward stable. The new method is of complexity and hence it solves a long-standing open problem in numerical analysis. Volker Mehrmann was supported by Deutsche Forschungsgemeinschaft, Research Grant Me 790/11-3.     

Principal minors, Part II: The principal minor assignment problem

The inverse problem of finding a matrix with prescribed principal minors is considered. A condition that implies a constructive algorithm for solving this problem will always succeed is presented. The algorithm is based on reconstructing matrices from their principal submatrices and Schur complements in a recursive manner. Consequences regarding the overdeterminancy of this inverse problem are examined, leading to a faster (polynomial time) version of the algorithmic construction. Care is given in the MATLAB^® implementation of the algorithms regarding numerical stability and accuracy.     

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     

The Riccati algebraic equation in a locallyC ⋆-algebra

The stabilizability and complete stabilizability of a pair of elements and the structure of the set of selfadjoint solutions of the algebraic Riccati equation is studied inC ^*-algebras and locallyC ^*-algebras which includes certain algebras of unbounded operators. Under some mild assumptions, selfadjoint solutions are in one-to-one correspondence with a particular set of idempotents.     

Pseudospectra, critical points and multiple eigenvalues of matrix polynomials

We develop a general framework for perturbation analysis of matrix polynomials. More specifically, we show that the normed linear space L_m(C^n×n) of n-by-n matrix polynomials of degree at most m provides a natural framework for perturbation analysis of matrix polynomials in L_m(C^n×n). We present a family of natural norms on the space L_m(C^n×n) and show that the norms on the spaces C^m+1 and C^n×n play a crucial role in the perturbation analysis of matrix polynomials. We define pseudospectra of matrix polynomials in the general framework of the normed space L_m(C^n×n) and show that the pseudospectra of matrix polynomials well known in the literature follow as special cases. We analyze various properties of pseudospectra in the unified framework of the normed space L_m(C^n×n). We analyze critical points of backward errors of approximate eigenvalues of matrix polynomials and show that each critical point is a multiple eigenvalue of an appropriately perturbed polynomial. We show that common boundary points of components of pseudospectra of matrix polynomials are critical points. As a consequence, we show that a solution of Wilkinson’s problem for matrix polynomials can be read off from the pseudospectra of matrix polynomials.     

Dimensionality reduction and volume minimization—generalization of the determinant minimization criterion for reduced rank regression problems

In this article we propose a generalization of the determinant minimization criterion. The problem of minimizing the determinant of a matrix expression has implicit assumptions that the objective matrix is always nonsingular. In case of singular objective matrix the determinant would be zero and the minimization problem would be meaningless. To be able to handle all possible cases we generalize the determinant criterion to rank reduction and volume minimization of the objective matrix. The generalized minimization criterion is used to solve the following ordinary reduced rank regression problem:

min_rank(X)=kdet(B-XA)(B-XA)^T,     

An algorithm for addressing the real interval eigenvalue problem

In this paper we present an algorithm for approximating the range of the real eigenvalues of interval matrices. Such matrices could be used to model real-life problems, where data sets suffer from bounded variations such as uncertainties (e.g. tolerances on parameters, measurement errors), or to study problems for given states.The algorithm that we propose is a subdivision algorithm that exploits sophisticated techniques from interval analysis. The quality of the computed approximation and the running time of the algorithm depend on a given input accuracy. We also present an efficient C++ implementation and illustrate its efficiency on various data sets. In most of the cases we manage to compute efficiently the exact boundary points (limited by floating point representation).     

Smooth factorizations of matrix valued functions and their derivatives

Summary In this paper we study the numerical factorization of matrix valued functions in order to apply them in the numerical solution of differential algebraic equations with time varying coefficients. The main difficulty is to obtain smoothness of the factors and a numerically accessible form of their derivatives. We show how this can be achieved without numerical differentiation if the derivative of the given matrix valued function is known. These results are then applied in the numerical solution of differential algebraic Riccati equations. For this a numerical algorithm is given and its properties are demonstrated by a numerical example.     

First order spectral perturbation theory of square singular matrix polynomials

We develop first order eigenvalue expansions of one-parametric perturbations of square singular matrix polynomials. Although the eigenvalues of a singular matrix polynomial P(λ) are not continuous functions of the entries of the coefficients of the polynomial, we show that for most perturbations they are indeed continuous. Given an eigenvalue λ₀ of P(λ) we prove that, for generic perturbations M(λ) of degree at most the degree of P(λ), the eigenvalues of P(λ)+?M(λ) admit covergent series expansions near λ₀ and we describe the first order term of these expansions in terms of M(λ₀) and certain particular bases of the left and right null spaces of P(λ₀). In the important case of λ₀ being a semisimple eigenvalue of P(λ) any bases of the left and right null spaces of P(λ₀) can be used, and the first order term of the eigenvalue expansions takes a simple form. In this situation we also obtain the limit vector of the associated eigenvector expansions.     

AIR Tools — A MATLAB package of algebraic iterative reconstruction methods

We present a MATLAB package with implementations of several algebraic iterative reconstruction methods for discretizations of inverse problems. These so-called row action methods rely on semi-convergence for achieving the necessary regularization of the problem. Two classes of methods are implemented: Algebraic Reconstruction Techniques (ART) and Simultaneous Iterative Reconstruction Techniques (SIRT). In addition we provide a few simplified test problems from medical and seismic tomography. For each iterative method, a number of strategies are available for choosing the relaxation parameter and the stopping rule. The relaxation parameter can be fixed, or chosen adaptively in each iteration; in the former case we provide a new “training” algorithm that finds the optimal parameter for a given test problem. The stopping rules provided are the discrepancy principle, the monotone error rule, and the NCP criterion; for the first two methods “training” can be used to find the optimal discrepancy parameter.     

On the quadratic two-parameter eigenvalue problem and its linearization

We introduce the quadratic two-parameter eigenvalue problem and linearize it as a singular two-parameter eigenvalue problem. This, together with an example from model updating, shows the need for numerical methods for singular two-parameter eigenvalue problems and for a better understanding of such problems.There are various numerical methods for two-parameter eigenvalue problems, but only few for nonsingular ones. We present a method that can be applied to singular two-parameter eigenvalue problems including the linearization of the quadratic two-parameter eigenvalue problem. It is based on the staircase algorithm for the extraction of the common regular part of two singular matrix pencils.