nach oben

2011 | Buch

Kapitel lesen Erstes Kapitel lesen

Algorithms for Quadratic Matrix and Vector Equations

verfasst von: Federico Poloni

Verlag: Scuola Normale Superiore

Buchreihe : CRM Series

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book is devoted to studying algorithms for the solution of a class of quadratic matrix and vector equations. These equations appear, in different forms, in several practical applications, especially in applied probability and control theory. The equations are first presented using a novel unifying approach; then, specific numerical methods are presented for the cases most relevant for applications, and new algorithms and theoretical results developed by the author are presented. The book focuses on “matrix multiplication-rich” iterations such as cyclic reduction and the structured doubling algorithm (SDA) and contains a variety of new research results which, as of today, are only available in articles or preprints.

Inhaltsverzeichnis

Frontmatter

Linear algebra preliminaries

Chapter 1. Linear algebra preliminaries

Abstract

With the notations R ⁿ and R ^m×n we denote respectively the space of n-vectors and m × n matrices with coefficients in a ring R — or a semi-ring, as in the case of

$${\mathbb{R}_ + }: = \left\{ {x \in \mathbb{R}:x \geqslant 0} \right\}.$$

The notation I_n, with n often omitted when it is clear from the context, denotes the identity matrix; the zero matrix of any dimension is denoted simply by 0. With e we denote the vector of suitable dimension all of whose entries are 1. The expression ρ (A) stands for the spectral radius of the matrix A.

Federico Poloni

Quadratic vector and matrix equations

Frontmatter

Chapter 2. Quadratic vector equations

Abstract

In this chapter, we aim to study in an unified fashion several quadratic vector and matrix equations with nonnegativity hypotheses. Specific cases of these problems have been studied extensively in the past by several authors. For references to the single equations and results, we refer the reader to the following sections, in particular Section 2.3. Many of the results appearing here have already been proved for one or more of the single instances of the problems, resorting to specific characteristics of the problem. In some cases the proofs we present here are mere rewritings of the original proofs with a little change of notation to adapt them to our framework, but in some cases we are effectively able to remove some hypotheses and generalize the results by abstracting the specific aspects of each problem.

Federico Poloni

Chapter 3. A Perron vector iteration for QVEs

Abstract

Equation (1), with the additional conditions

$$M = I, a + b\left( {e,e} \right) = e$$

(3.1.1)

(i.e., the vector e is a solution, though not necessarily the minimal one), arises from the study of a class of branching processes known as Markovian binary trees. These processes model a population composed of a number of individuals, each of which may be in a state φ ∈ {1,2, ..., n}. The individuals evolve independently and have state-dependent probabilities of reproducing or dying. Here reproducing means that an individual in state i splits into two individuals in state j and k respectively; the probability of this event is represented by the term b_ijk in the equation, while the probability of an individual in state i dying is a _i.

Federico Poloni

Chapter 4. Unilateral quadratic matrix equations

Abstract

In this chapter, we introduce the unilateral quadratic equations (2) and present several known results on the properties of their solutions and on numerical algorithms, taken mainly from [31]. Moreover, we describe several attempts to generalize the logarithmic reduction algorithm to a generic quadratic vector equation in the framework of Chapter 2, that lead to an unexpected connection with Newton’s algorithm. While the original results contained in this chapter are modest, most of the background material exposed here is needed later in Chapter 6.

Federico Poloni

Chapter 5. Nonsymmetric algebraic Riccati equations

Abstract

The research activity concerning the analysis of nonsymmetric algebraic Riccati equations associated with M-matrices and the design of numerical algorithms for their solution has had a strong acceleration in the last decade. Important progresses have been obtained concerning theoretical properties of this class of matrix equations and new effective algorithms relying on the properties of M-matrices have been designed and analyzed [15, 39, 33, 32, 56, 70, 71, 74, 72, 77, 69, 94, 100, 115, 116, 117].

Federico Poloni

Chapter 6. Transforming NAREs into UQMEs

Abstract

The problem of reducing an algebraic Riccati equation (5) to a unilateral quadratic matrix equation (2) has been considered in [32, 73, 95, 109, 138].

Federico Poloni

Rank-structured NAREs

Frontmatter

Chapter 7. Storage-optimal algorithms for Cauchy-like matrices

Abstract

Several classes of algorithms for the numerical solution of Toeplitz-like and Cauchy-like linear systems exist in the literature. We refer the reader to [153] for an extended introduction on this topic, with descriptions of each method and plenty of citations to the relevant papers, and only summarize them in Table 7.1.

Federico Poloni

Chapter 8. Newton method for rank-structured algebraic Riccati equations

Abstract

Equation (5) with coefficients given by (10) arises from the discretization of an integrodifferential equation appearing in a neutron transport model [100]. The solution of interest is the minimal positive one, whose existence is proved in [100]. Note that for this equation $\mathcal{M}$ is an M-matrix [70]: in fact,

$$\mathcal{M} = \left[ {\begin{array}{*{20}{c}} \Gamma &0 \\ 0&\Delta \end{array}} \right] - \left[ {\begin{array}{*{20}{c}} q \\ e \end{array}} \right]\left[ {{e^T} {q^T}} \right];$$

by Lemma 1.2.2 this is an M-matrix if and only if

$$0 \leqslant 1 - \left[ {{e^T} {q^T}} \right]\left[ {\begin{array}{*{20}{c}} {{\Gamma ^{ - 1}}}&0 \\ 0&{{\Delta ^{ - 1}}} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} q \\ e \end{array}} \right],$$

which reduces to

$$1 \geqslant {e^T}{\Gamma ^{ - 1}}q + {q^T}{\Delta ^{ - 1}}e = \sum\limits_{i = 1}^n {\frac{{c\left( {1 - \alpha } \right)}}{2}} {w_i} + \sum\limits_{i = 1}^n {\frac{{c\left( {1 + \alpha } \right)}}{2}} {w_i} = c,$$

(8.1.1)

in view of (11). According to the terminology in (5.2.2), the equation is nonsingular whenever c ≠ 1, transient when α ≠ 0, c = 1, and null recurrent when α = 0, c = 1.

Federico Poloni

Matrix equations from control theory

Frontmatter

Chapter 9. Lur’e equations

Abstract

For given matrices A, Q ∈ ℂ ^n×n with Q = Q* and B, C ∈ ℂ^n×m, R ∈ ℂ^m×m, we consider the Lur’e equations

$$\begin{gathered} A*X + XA + Q = K*K, \hfill \\ XB + C = K*L, \hfill \\ R = L*L, \hfill \\ \end{gathered} $$

(9.1.1)

that have to be solved for (X, K, L) ∈ ℂ^n×n × ℂ^p×n × ℂ^p×m with X = X* and p as small as possible. Equations of type (9.1.1) were first introduced by A.I. Lur’e [119] in 1951 (see [13] for an historical overview) and play a fundamental role in systems theory, since properties like dissipativity of linear systems can be characterized via their solvability [2, 3, 4, 157]. This type of equations moreover appears in the infinite time horizon linear-quadratic optimal control problem [45, 46, 47, 160, 161], spectral factorization [48, 49] as well as in balancing-related model reduction [42, 68, 130, 133, 141]. In the case where R is invertible, the matrices K and L can be eliminated by obtaining the algebraic Riccati equation

$$A*X + XA - \left( {XB + C} \right){R^{ - 1}}\left( {XB + C} \right)* + Q = 0.$$

(9.1.2)

Whereas this type is well explored both from an analytical and numerical point of view [110, 156, 17], the case of singular R has received comparatively little attention. However, the singularity of R is often a structural property of the system to be analyzed [140] and can therefore not be avoided by arguments of genericity.

Federico Poloni

Chapter 10. Generalized SDA

Abstract

The traditional hypotheses needed for the implementation of SDA are that the two Riccati equations

$$\begin{gathered} Q + {A^T}X + XA - XGX = 0 \hfill \\ YQY + Y{A^T} + AY - G = 0 \hfill \\ \end{gathered} $$

have respectively a stabilizing and anti-stabilizing solution. This is equivalent to saying that the Hamiltonian

$$\mathcal{H} = \left[ {\begin{array}{*{20}{c}} A&{ - G} \\ { - Q}&{ - {A^T}} \end{array}} \right]$$

has stable and unstable invariant subspaces in the form

$$U = \left[ {\begin{array}{*{20}{c}} {{U^{\left( 1 \right)}}} \\ {{U^{\left( 2 \right)}}} \end{array}} \right], V = \left[ {\begin{array}{*{20}{c}} {{V^{\left( 1 \right)}}} \\ {{V^{\left( 2 \right)}}} \end{array}} \right],$$

with U⁽¹⁾ and V⁽²⁾ nonsingular. If this property is true, we can form the desired solutions to the two Riccati equations as X = U₍₂₎U₍₁₎ ⁽⁻¹⁾, Y =V₍₁₎V₍₂₎ ⁽⁻¹⁾.

Federico Poloni

Matrix geometric means

Frontmatter

Chapter 11. An effective matrix geometric mean

Abstract

In several contexts, it is natural to generalize the geometric mean of two positive real numbers $a\# b: = \sqrt {ab} $ to real symmetric positive definite n × n matrices using (15) Several papers, e.g. [24, 25, 127], and a chapter of the book [26], are devoted to studying the geometry of the cone of positive definite matrices ℙⁿ endowed with the Riemannian metric defined by

$$ds = \left\| {{A^{ - {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2}}}dA{A^{ - {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2}}}} \right\|,$$

where $\left\| B \right\| = \sqrt {\sum\nolimits_{i,j} {{{\left| {{b_{i,j}}} \right|}^2}} } $ denotes the Frobenius norm. The distance induced by this metric is

$$d\left( {A,B} \right) = \left\| {\log \left( {{A^{ - {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2}}}B{A^{ - {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2}}}} \right)} \right\|$$

(11.1.1)

It turns out that on this manifold the geodesic joining X and Y has equation

$$\gamma \left( t \right) = {X^{{{ - 1} \mathord{\left/ {\vphantom {{ - 1} 2}} \right. \kern-\nulldelimiterspace} 2}}}{\left( {{X^{{{ - 1} \mathord{\left/ {\vphantom {{ - 1} 2}} \right. \kern-\nulldelimiterspace} 2}}}Y{X^{{{ - 1} \mathord{\left/ {\vphantom {{ - 1} 2}} \right. \kern-\nulldelimiterspace} 2}}}} \right)^t}{X^{{{ - 1} \mathord{\left/ {\vphantom {{ - 1} 2}} \right. \kern-\nulldelimiterspace} 2}}} = X{\left( {{X^{ - 1}}Y} \right)^t} = :X{\# _t}Y, t \in \left[ {0,1} \right],$$

and thus A # B is the midpoint of the geodesic joining A and B. An analysis of numerical methods for computing the geometric mean of two matrices is carried out in [96].

Federico Poloni

Chapter 12. Constructing other matrix geometric means

Abstract

In the last few years, several papers have been devoted to defining a proper way to generalize the concept of geometric mean to n ≥ 3 Hermitian, positive definite m × m matrices. Chapter 11 mention the desirable properties listed by Ando, Li and Mathias [6]; however, these properties do not uniquely define a multivariate matrix geometric mean; thus several different definitions appeared in literature.

Federico Poloni

Chapter 13. Conclusions

Abstract

We have presented a unified introduction to a number of matrix equations appearing in applications and in mathematical literature, and some old and new algorithms for their solution. The relationships between the different quadratic vector and matrix equations are partially exploited to give better algorithms and unified proofs. However, some details still cannot be embedded elegantly in the theory, and many algorithms for one equation of the class have no counterpart for the others.

Federico Poloni

Backmatter

Titel: Algorithms for Quadratic Matrix and Vector Equations
verfasst von: Federico Poloni
Verlag: Scuola Normale Superiore
Electronic ISBN: 978-88-7642-384-0
Print ISBN: 978-88-7642-383-3
DOI: https://doi.org/10.1007/978-88-7642-384-0