Abstract
A number of theoretical and computational problems for matrix polynomials are solved by passing to linearizations. Therefore a perturbation theory, that relates perturbations in the linearization to equivalent perturbations in the corresponding matrix polynomial, is needed. In this paper we develop an algorithm that finds which perturbation of matrix coefficients of a matrix polynomial corresponds to a given perturbation of the entire linearization pencil. Moreover we find transformation matrices that, via strict equivalence, transform a perturbation of the linearization to the linearization of a perturbed polynomial. For simplicity, we present the results for the first companion linearization but they can be generalized to a broader class of linearizations.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Nonlinear eigenvalue problems play an important role in mathematics and its applications, see e.g., the surveys [21, 26, 30]. In particular, polynomial eigenvalue problems have been receiving much attention [3, 14, 15, 22, 24, 25]. Recall that
is a matrix polynomial and that the number d is called the grade of \(P(\lambda )\). If \(A_d \ne 0\) then the grade coincides with the degree of the polynomial. Frequently, complete eigenstructures, i.e. elementary divisors and minimal indices of matrix polynomials (for the definitions, see e.g., [6, 14]) provide an understanding of the properties and behaviour of the underlying physical system and thus are the actual objects of interest. The complete eigenstructure is usually computed by passing to a (strong) linearization which replaces a matrix polynomial by a matrix pencil, i.e. matrix polynomials of degree \(d = 1\), with the same finite (and infinite) elementary divisors and with the known changes in the minimal indices, see [26] for more details. For example, a classical linearization of (1.1), used in this paper, is the first companion form
where \(I_n\) is the \(n\times n\) identity matrix and all nonspecified blocks are zeros.
In this paper, we find which perturbation of the matrix coefficients of a given matrix polynomial corresponds to a given perturbation of the entire linearization pencil. To be exact, we find such a perturbation of the matrix polynomial coefficients that the linearization of this perturbed polynomial (2.2) has the same complete eigenstructure as a given perturbed linearization (2.1). We also note that the existence of such a perturbation (2.2) was proven before for Fiedler-type linearizations [8, 14, 32], and even for a larger class of block-Kronecker linearizations [15]. Nevertheless, the problem of finding this perturbation explicitly has been open until now. The main contribution of this paper is an algorithm for finding this perturbation explicitly. Moreover, now the existence of such perturbation also follows from the convergence of the algorithm developed in this paper.
The results of this paper can be applied to a number of problems in numerical linear algebra. One example is solving various distance problems for matrix polynomials if the corresponding problems are solved for matrix pencils, e.g., finding a singular matrix polynomial nearby a given matrix polynomial [4, 18, 20]. Another application lies in the stratification theory [8, 14]: constructing an explicit perturbation of a matrix polynomial when a perturbation of its linearization is known. This will allow to say which perturbation does a certain change to the complete eigenstructure of a given polynomial. (In [11, 16, 17] the explicit perturbations for investigating such changes for matrix pencils, bi- and sesquilinear forms are derived.) Moreover, our result may also be useful for investigating the backward stability of the polynomial eigenvalue problems solved by using the backward stable methods on the linearizations, see e.g., [29].
2 Perturbations of matrix polynomials and their linearizations
Recall that for every matrix \(X = [x_{ij}]\) its Frobenius norm is given by \(\Vert X \Vert := \Vert X \Vert _F= \left( \sum _{i,j} |x_{ij}|^2 \right) ^{\frac{1}{2}}\). Hereafter, unless otherwise stated, we use the Frobenius norm for matrices. Let \(P(\lambda )\) be an \(m \times n\) matrix polynomial of grade d and define a norm of \(P(\lambda )\) as follows
Definition 2.1
Let \(P(\lambda )\) and \(E(\lambda )\) be two \(m \times n\) matrix polynomials, with \({{\,\mathrm{grade}\,}}P(\lambda ) \ge {{\,\mathrm{grade}\,}}E(\lambda )\). The matrix polynomial \(P(\lambda ) + E(\lambda )\) is a perturbation of the \(m \times n\) matrix polynomial \(P(\lambda )\).
In this paper \(\Vert E(\lambda ) \Vert \) is typically small. Definition 2.1 is also applicable to matrix pencils as a particular case of matrix polynomials.
The first companion form \({{\mathscr {C}}}^1_{P(\lambda )}\) of \(P(\lambda )\) is defined in (1.2) and is a well-known way to linearize matrix polynomials, i.e. to substitute an investigation of a matrix polynomial by an investigation of a certain matrix pencil with the same characteristics of interest. Namely, \(P(\lambda )\) and \({{\mathscr {C}}}_{P(\lambda )}^1\) have the same finite and infinite elementary divisors (the same finite and infinite eigenvalues and their multiplicities), the same left minimal indices, and there is a simple relation between their right minimal indices (those of \({{\mathscr {C}}}_{P(\lambda )}^1\) are greater by \(d-1\) than those of \(P(\lambda )\)), see [6] for the definitions and more details. Define a (full) perturbation of the linearization of an \(m \times n\) matrix polynomial of grade d as follows
and define a structured perturbation of the linearization, i.e. a perturbation in which only the blocks \(A_i, \ i=0,1, \dots , d\) are perturbed
We also refer to (2.2) as the linearization of a perturbed matrix polynomial.
Recall that an \(m \times n\) matrix pencil \(\lambda A_1 + A_0\) is called strictly equivalent to \(\lambda B_1 + B_0\) if there are non-singular matrices Q and R such that \(Q^{-1}A_1R =B_1\) and \(Q^{-1}A_0R=B_0\). Note that two \(m \times n\) matrix pencils have the same complete eigenstructure if and only if they are strictly equivalent. Moreover, two \(m \times n\) matrix polynomials of degree d, \(P(\lambda )\) and \(Q(\lambda )\), have the same complete eigenstructure if and only if \({{\mathscr {C}}}^1_{P(\lambda )}\) and \({{\mathscr {C}}}^1_{Q(\lambda )}\) are strictly equivalent. Now we can state one of our goals as finding a perturbation \(E(\lambda )\) such that \({{\mathscr {C}}}^1_{P(\lambda )} + {{\mathscr {E}}}\) and \({{\mathscr {C}}}^1_{P(\lambda )+ E(\lambda )}\) are strictly equivalent. The existence of such a perturbation \(E(\lambda )\) is known and stated in Theorem 2.1, which is a slightly adapted formulation of Theorem 2.5 in [10], see also Theorem 5.21 in [15] and [14, 23, 32].
Theorem 2.1
Let \(P(\lambda )\) be an \(m\times n\) matrix polynomial of degree d and let \({{\mathscr {C}}}^1_{P(\lambda )}\) be its first companion form. If \(\mathcal{C}^1_{P(\lambda )} + {{\mathscr {E}}}\) is a perturbation of \({{\mathscr {C}}}^1_{P(\lambda )}\) such that
then there is some perturbation polynomial \(E(\lambda )\) such that \({{\mathscr {C}}}^1_{P(\lambda )} + {{\mathscr {E}}}\) is strictly equivalent to the linearization of the perturbed polynomial \({{\mathscr {C}}}^1_{P(\lambda )+ E(\lambda )}\), i.e. there exist two nonsingular matrices U and V (they are small perturbations of the identity matrices) such that
moreover,
Theorem 2.1 guarantees the existence of the structured perturbation (2.2) and the transformation matrices U and V but says nothing about how to find them. In the following section we present an algorithm that, for a given perturbation (2.1), finds such a structured perturbation (2.2) and transformation matrices explicitly.
3 Reduction algorithm
In this section we describe our iterative algorithm (Algorithm 3.1) that, by strict equivalence transformation, reduces a full perturbation of a linearization pencil (2.1) to a structured perturbation of this pencil (2.2), i.e. a perturbation where only the blocks that correspond to the matrix coefficients of a matrix polynomial are perturbed. The corresponding transformation matrices are derived too. We also analyze important characteristics of the proposed algorithm and its outputs.
Define an unstructured perturbation \({{\mathscr {E}}}^u=\lambda E^u + \widetilde{E}^u\) of the linearization \({{\mathscr {C}}}^1_{P(\lambda )}\) as a perturbation (2.1) where the blocks \(E_{11}, \widetilde{E}_{11}, \widetilde{E}_{12}, \dots , \widetilde{E}_{1d}\) are replaced by the zero blocks of the corresponding sizes, namely:
\({{\mathscr {E}}}^u\) consists of all the perturbation blocks that are not included in the structured perturbation (2.2), i.e. \({{\mathscr {E}}}^u\) consists of all the perturbations of the identity and zero blocks of the linearization \({{\mathscr {C}}}^1_{P(\lambda )}\). In turn, the structured perturbation \({{\mathscr {E}}}^s\) is as follows
In Sect. 3.1 we show that the unstructured part of the perturbation tends to zero (entrywise) as the number of iterations of our algorithm grows; in Sect. 3.2 we derive a bound on the norm of the resulting structured perturbation; in Sect. 3.3 we explain how to construct the corresponding transformation matrices, i.e. matrices that reduce a full perturbation to a structured one.
We note that the construction of the corresponding transformation matrices in this paper is similar to the construction of the transformation matrices for the reduction to miniversal deformations of matrices in [12, 13], and that the evaluation of the norm of the structured part has some similarities with the evaluation of the norm of the miniversal deformation of (skew-)symmetric matrix pencils in [7, 9], see also [12, 13]. These similarities are due to the fact that our structured perturbation is a versal deformation (but not miniversal), see the mentioned papers for the definitions and details.
Algorithm 3.1
Let \({{\mathscr {C}}}^1_{P(\lambda )}\) be a first companion linearization of a matrix polynomial \(P(\lambda )\) and \({{\mathscr {E}}}_1\) be a full perturbation of \({{\mathscr {C}}}^1_{P(\lambda )}\).
-
Input: Matrix polynomial \(P(\lambda )\), perturbed matrix pencil \({{\mathscr {C}}}^1_{P(\lambda )}+{{\mathscr {E}}}_1\), and the tolerance parameter \(\mathrm{tol}\);
-
Initialization: \(U_1:=I\) and \(V_1:=I\)
-
Computation: While \(\Vert {{\mathscr {E}}}^u_i \Vert > \mathrm{tol}\)
-
find the minimum norm least-squares solution to the coupled Sylvester equations: \(\left( ({{\mathscr {C}}}^1_{P(\lambda )} + {{\mathscr {E}}}_{i}^{{s}})X_i + Y_i({{\mathscr {C}}}^1_{P(\lambda )} + {{\mathscr {E}}}_{i}^{{s}})\right) ^u = - {{\mathscr {E}}}^u_i;\)
-
update the perturbation of the linearization (the updated perturbed linearization remains strictly equivalent to the original one): \(({{\mathscr {C}}}^1_{P(\lambda )} + {{\mathscr {E}}}_{i+1}):=(I+Y_i) ({{\mathscr {C}}}^1_{P(\lambda )} + {{\mathscr {E}}}_{i}) (I+X_i);\)
-
update the transformation matrices: \(U_{i+1} := (I+Y_i)U_{i}\) and \(V_{i+1} := V_{i}(I+X_i);\)
-
extract the new unstructured perturbation \({{\mathscr {E}}}^u_{i+1} \) to be eliminated;
-
increase the counter: \(i:=i+1\);
-
-
Output: A structurally perturbed linearization pencil \({{\mathscr {C}}}^1_{P(\lambda )+E(\lambda )}:={{\mathscr {C}}}^1_{P(\lambda )} + {{\mathscr {E}}}_{k}\), where \({{\mathscr {E}}}_{k}\) is a structured perturbation (since \(\Vert {{\mathscr {E}}}^u_{k}\Vert < \mathrm{tol}\)), and the transformation matrices U and V.
The system \(\left( ({{\mathscr {C}}}^1_{P(\lambda )} + {{\mathscr {E}}}^s_{i})X_i + Y_i({{\mathscr {C}}}^1_{P(\lambda )} + {{\mathscr {E}}}^s_{i})\right) ^u = - {{\mathscr {E}}}^u_i\), appearing at the computation step of Algorithm 3.1, has a solution since the space
is transversal to the space of the first companion linearizations
i.e., these spaces add up to the whole space of matrix pencils of the corresponding size, see e.g., [14, 23, 32].
Following Algorithm 3.1 we can explicitly write how the resulting perturbation of the linearization \({{\mathscr {C}}}^1_{P(\lambda )} + {{\mathscr {E}}}_{k}\) is constructed:
where
In the rest of the paper we investigate properties of this algorithm and perform numerical experiments.
3.1 Elimination of the unstructured perturbation
We start by deriving an auxiliary lemma that will be used to prove that in Algorithm 3.1 the unstructured perturbation converges to zero.
For a given matrix T, define \(\kappa (T):= \kappa _F(T) = \Vert T\Vert \cdot \Vert T^{\dagger }\Vert \) to be a Frobenius condition number of T, e.g., see references [2, 5, 28]. We recall that the matrix \(T^{\dagger }\) denotes the pseudoinverse (the Moore–Penrose inverse) of T, see e.g., [19].
Lemma 3.1
Let A, B, C, D, M, and N be \(m\times n\) matrices and let the \(n \times n\) matrix X and the \(m \times m\) matrix Y be the minimum norm least-squares solution to the system of coupled Sylvester equations
Then
where \(T=\begin{bmatrix} I_n \otimes A &{} B^T \otimes I_m \\ I _n\otimes C &{} D^T \otimes I_m \end{bmatrix}\) is the Kronecker product matrix associated with the system (3.2).
Proof
Using the Kronecker product we can rewrite the system of coupled Sylvester equations as a system of linear equations \(Tx=b\), or explicitly
The minimum norm least-squares solution to such system can be written as \(x = T^{\dagger } b\), implying \(\Vert x\Vert \le \Vert T^{\dagger }\Vert \cdot \Vert b\Vert \) or more explicitly, and taking into account \(\Vert x\Vert ^2 = \Vert X\Vert ^2 + \Vert Y\Vert ^2\):
where \(\kappa (T)\) is the Frobenius condition number of T. Taking into account that
we obtain
\(\square \)
The bounding expression in (3.3) depends on the conditioning of the problem (3.4) as well as on how small (normwise) the right-hand side of (3.4) (or, equivalently, (3.2)) is, compared to the matrix coefficients in the left-hand side. The conditioning of (3.2) may actually be better than the conditioning of (3.4). Thus for very ill-conditioned problems and large perturbations, it may be reasonable to use a solver for (3.2) instead of passing to the Kronecker product matrices.
In the following theorem we prove that Algorithm 3.1 eliminates the unstructured perturbation, i.e. we show that the norm of the unstructured part of the perturbation tends to zero as the number of iterations grows.
Theorem 3.1
Let \({{\mathscr {C}}}^1_{P(\lambda )} + {{\mathscr {E}}}_{1}\) be a perturbation of the linearization and let \(\alpha \Vert {{\mathscr {E}}}_{1}\Vert <~1\), where
with the pencils \({{\mathscr {C}}}^1_{P(\lambda )} + {{\mathscr {E}}}_{i} = \lambda (W+E_i) + (\widetilde{W} + \widetilde{E_i})\) from Algorithm 3.1, and the Kronecker product matrices
Then \({{\mathscr {E}}}_{i}^u = \lambda E^u_i + \widetilde{E}^u_i\) in Algorithm 3.1 satisfies \(\Vert {{\mathscr {E}}}_{i}^u\Vert \rightarrow 0\) when \(i \rightarrow \infty \).
Proof
We start by proving a bound for the norm of the unstructured part of a perturbation at the \((i+1)\)-st step of the algorithm, using the norm of the unstructured part of a perturbation at the i-th step of the algorithm. Define \({{\mathscr {C}}}^1_{P(\lambda )} = \lambda W + \widetilde{W}\).
Following Algorithm 3.1 we obtain matrices \(X_i\) and \(Y_i\) by solving the system of coupled Sylvester matrix equations:
Using the solution \(X_i\) and \(Y_i\) to the system (3.8) we compute
or equivalently,
Since \(X_i\) and \(Y_i\) are a solution to (3.8) we have
Splitting the perturbation into the structured and unstructured parts we obtain
In general, \(E_{i+1}^u\) and \(\widetilde{E}_{i+1}^u\) are not zero matrices but we show that they tend to zero (entrywise) when \(i \rightarrow \infty \). In (3.9)–(3.12) below \(T_i\) is the Kronecker product matrix defined in (3.7) and associated with the system of coupled Sylvester equations (3.8). Using the bound (3.5) we have:
respectively, using the bound (3.3) we have:
Combining (3.9) and (3.10) we obtain the following bound on the Frobenious norm of \(\Vert E_{i+1}^u\Vert \):
similarly, for the matrix \(\Vert \widetilde{E}_{i+1}^u\Vert \),
Using \(\alpha \), defined in (3.6), we can write the bounds on the unstructured part of the perturbation for both coefficients of the matrix pencil at the step \(i+1\) as follows
Note that the supremum in the definition of \(\alpha \) is finite since \(\kappa (T_i)\) and the norms of the corresponding matrices are finite. This results into the bound for the whole pencil:
Using the bounds (3.13) and (3.14) at each step we get
If \(\alpha \Vert {{\mathscr {E}}}_{1}\Vert < 1\) then the norm of the unstructured part of the perturbation tends to zero as the number of iterations grows. \(\square \)
Remark 3.1
In our case we should exclude some rows from (3.7), since we want to eliminate only the unstructured part of the perturbation \({{\mathscr {E}}}_i\). Therefore, the norm of the solution of such least-squares problem will be less than or equal to \(\Vert x\Vert \), where \(x= T^{\dagger } b\). Clearly, the bounds from Lemma 3.1 remain valid.
The sharpness of the bounds (3.15) depends on the value of \(\alpha \) and on the size of the initial perturbation: the better conditioned the problem is and the smaller initial perturbation is, the better the bounds (3.15) are. Even if the problem is ill-conditioned we can still guarantee the convergence for small enough perturbations. Note that a proper scaling of a matrix polynomial improves the conditioning of the problem, see e.g., [15]. Moreover, in practice, Algorithm 3.1 converges to a structured perturbation very well and requires only a small number of iterations, see the numerical experiments in Sect. 4. The numerical experiments also suggest that we have the quadratic order of convergence, and this can indeed be verified using (3.15).
3.2 Bound on the norm of the structured perturbation
In this section we find a bound on the resulting structured perturbation. Similarly to the analysis in Sect. 3.1 we have a dependence on the conditioning of the problem as well as on the norm of an original perturbation. Therefore, we need to make an assumption that these quantities are small enough.
Theorem 3.2
Let \({{\mathscr {C}}}^1_{P(\lambda )} + {{\mathscr {E}}}_{1}\) be a perturbation of the linearization \({{\mathscr {C}}}^1_{P(\lambda )}\), \(\Vert {{\mathscr {E}}}_1\Vert = \varepsilon \), and \(\alpha \varepsilon < 1\), where \(\alpha = \alpha ({{\mathscr {C}}}^1_{P(\lambda )},{{\mathscr {E}}}_{1})\) is defined in (3.6). Define also \( \beta := \ \sup _{i} \ \sqrt{\frac{2}{\left( n+m\right) }} \kappa (T_i)\) and
with the pencils \({{\mathscr {C}}}^1_{P(\lambda )} + {{\mathscr {E}}}_{i} = \lambda (W+E_i) + (\widetilde{W} + \widetilde{E_i})\) from Algorithm 3.1, and the Kronecker product matrix \(T_i\) in (3.7). Then \(\Vert {{\mathscr {E}}}^s\Vert \le \varepsilon (1+ \beta ) / (1 - \gamma \varepsilon )\).
Proof
For the input \({{\mathscr {C}}}^1_{P(\lambda )}+{{\mathscr {E}}}_1\), following Algorithm 3.1 step by step, we can build the resulting perturbation as explained in (3.1). Skipping writing the eliminated unstructured parts of (3.1) we have:
We start by evaluating the structured part of the perturbation coming from the coupled Sylvester equations using the bounds (3.5):
Recall that \(\kappa (T_i)\) and the norms of the corresponding perturbations are finite and thus the supremum in the definition of \(\beta \) is finite. We use the bounds in (3.10), see also (3.12), for \(\left\| \left( {Y_i}({{\mathscr {C}}}^1_{P(\lambda )}+{{\mathscr {E}}}_{i}){X_i}\right) ^s\right\| \) since \(\left\| \left( {Y_i}({{\mathscr {C}}}^1_{P(\lambda )}+{{\mathscr {E}}}_{i}){X_i}\right) ^s\right\| \le \Vert {Y_i}({{\mathscr {C}}}^1_{P(\lambda )}+{{\mathscr {E}}}_{i}){X_i}\Vert \). Thus we can evaluate the norm of \(\Vert {{\mathscr {E}}}^s_i\Vert \) using (3.15) and (3.17) as well as noting that \(\Vert {{\mathscr {E}}}^s_i\Vert \) and \(\Vert {{\mathscr {E}}}^u_i\Vert \) are less than or equal to \(\Vert {{\mathscr {E}}}_i\Vert \):
In (3.18) we used that \(\gamma \varepsilon <1\) which is true since by the assumption of the theorem \(\alpha \varepsilon < 1\), and \(\gamma < \alpha \). \(\square \)
The bound in Theorem 3.2 is not very tight if \(\gamma \varepsilon \) is close to 1 but it is better for small \(\gamma \varepsilon \). For example, Theorem 3.2 says that for \(\gamma \varepsilon < 1/n\) we get \(\Vert {{\mathscr {E}}}^s\Vert \le n \varepsilon (1 + {\beta }) / (n-1)\), and in particular, for \(\gamma \varepsilon <~1/2\) we get \(\Vert {{\mathscr {E}}}^s\Vert \le 2 (1 + {\beta }) \varepsilon \).
3.3 Construction of the transformation matrices
In this section we investigate the transformation matrices that bring a full perturbation of the linearization to a structured perturbation of the linearization. Following Algorithm 3.1, we observe that the transformation matrices are constructed as the following infinite products:
The convergence of these infinite products to nonsingular matrices is proven in Theorem 3.3. Note that, for small initial perturbations, such transformation matrices are small perturbations of the identity matrices.
Theorem 3.3
Let \({{\mathscr {C}}}^1_{P(\lambda )} + {{\mathscr {E}}}_{1}\) be a perturbation of the linearization \({{\mathscr {C}}}^1_{P(\lambda )}\), and \(\alpha \Vert {{\mathscr {E}}}_1\Vert <~1\), where \(\alpha = \alpha ({{\mathscr {C}}}^1_{P(\lambda )},{{\mathscr {E}}}_{1})\) is defined in (3.6). Let also \(X_i\) and \(Y_i\) be a solution to (3.8) for the corresponding index i, and \(I_m\) and \(I_n\) be the \(m \times m\) and \(n \times n\) identity matrices. Then
exist and are nonsingular matrices.
Proof
By [31, Theorem 4] the limits in (3.19) exist and are nonsingular matrices if the sums
respectively, absolutely converge.
Using the bound (3.5) for a solution of coupled Sylvester equations and noting that \(\Vert X\Vert ^2 \le \Vert X\Vert ^2 + \Vert Y\Vert ^2\), we have the following bound for both \(\Vert X_{i}\Vert ^2\) and \(\Vert Y_{i}\Vert ^2\):
Bounds (3.21) together with our assumption \(\alpha \Vert {{\mathscr {E}}}_1\Vert < 1 \ (\Vert {{\mathscr {E}}}_1^u\Vert \le \Vert {{\mathscr {E}}}_1\Vert )\) allow us to conclude that the sums in (3.20) absolutely converge. \(\square \)
4 Numerical experiments
All the numerical experiments are performed on a MacBook Pro (processor: 2.6 GHz Intel Core i7, memory: 32 GB 2400 MHz DDR4), using Matlab R2019a (64-bit). We consider a large number of randomly generated matrix polynomials, matrix polynomials coming from real world applications, and matrix polynomials crafted specially for testing the limits of the proposed algorithm.
Example 4.1
Consider 1000 random polynomials of size \(8 \times 8\) and degree 4. The entries of the matrix coefficients of these polynomials are generated from the normal distribution with mean \(\mu = 0\) and standard deviation \(\sigma =10\) (variance \(\sigma ^2=100\)). The polynomials are normalized to have the Frobenius norm equal to 1. Each polynomial is perturbed by adding a matrix polynomial whose matrix coefficients have entries that are uniformly distributed numbers on the interval (0, 0.01). At most 6 iterations are needed for the norm of the unstructured part of a perturbation to be of order \(10^{-16}\) (\(10^{-16}\) is the tolerance we require). In Fig. 1 we present the results in whisker plots (box plots).
In the following two examples we consider two quadratic matrix polynomials coming from applications. Both matrix polynomials belong to the NLEVP collection [3].
Example 4.2
Consider the \(5 \times 5\) quadratic matrix polynomial \(Q(\lambda ) = \lambda ^2 M + \lambda D + K\) arising from modelling a two-dimensional three-link mobile manipulator [3]. The \(5 \times 5\) coefficient matrices are
with
In Fig. 2 we present the decay of the norm of the unstructured part of the perturbation in Algorithm 3.1. The changes in the norm of the structured part of the perturbation and in the norms of the transformation matrices are presented in Figs. 3 and 4 , respectively.
Example 4.3
Consider a \(21 \times 16\) quadratic matrix polynomial arising from calibration of a surveillance camera using a human body as a calibration target [3, 27]. Note that the polynomial is rectangular. In Fig. 5 we present the decay of the norm of the unstructured part of the perturbation. The changes in the norm of the structured part of the perturbation and in the norms of the transformation matrices are presented in Figs. 6 and 7, respectively.
In the following example we tune the conditioning of the problem and the value of the initial perturbation to test the limits of Algorithm 3.1.
Example 4.4
Consider the \(5 \times 5\) quadratic matrix polynomial from Example 4.2. We scale the matrix coefficients of this polynomial and increase the initial perturbation to achieve the following goals: (a) making the structured perturbation much larger compared to the initial perturbation and (b) forcing Algorithm 3.1 to diverge. Notably, if (a) is achieved, i.e. the limit perturbation is much larger than the original one, then we may still have the convergence. We summarize the results of our experiment in Table 1. In the last column we underline the word “yes” if the convergence is also provable by Theorem 3.1, e.g., in the first and the second experiments the values of \(\alpha \Vert {{\mathscr {E}}}_1\Vert \) are 7.75e-05 and 0.98, respectively; in experiments 3,5,6, and 8 the value of \(\alpha \Vert {{\mathscr {E}}}_1\Vert \) is larger than 1 thus Theorem 3.1 is not applicable, nevertheless we still observe convergence numerically. In experiments 9 and 10 we do not have even the numerical convergence and of course the value of \(\alpha \Vert {{\mathscr {E}}}_1\Vert \) is larger than 1.
5 Future work
The method developed in this paper can be directly generalized to the other linearizations, e.g., Fiedler linearizations [1, 6, 14] or even block-Kronecker linearizations [15]. Such a generalization may also cover structure-preserving linearizations, see e.g., [8]. The existence of structured perturbations for these broader classes of linearizations follows, e.g., from [8, 14, 15]. Such a generalization will require solving the corresponding structured coupled Sylvester equations, or at least the corresponding structured least-squares problem.
Relaxing the conditions in Theorems 3.1 and 3.2, to have provable convergence and bounds for a broader class of examples, is another possible line of future research.
References
Antoniou, E., Vologiannidis, S.: A new family of companion forms of polynomial matrices. Electron. J. Linear Algebra 11, 78–87 (2004)
Avron, H., Druinsky, A., Toledo, S.: Spectral condition-number estimation of large sparse matrices. arXiv:1301.1107 (2013)
Betcke, T., Higham, N., Mehrmann, V., Schröder, C., Tisseur, F.: NLEVP: a collection of nonlinear eigenvalue problems. ACM Trans. Math. Softw. 39(2), 7:1–7:28 (2013)
Byers, R., He, C., Mehrmann, V.: Where is the nearest non-regular pencil? Linear Algebra Appl. 285(1), 81–105 (1998)
Chehab, J.-P., Raydan, M.: Geometrical properties of the Frobenius condition number for positive definite matrices. Linear Algebra Appl. 429(8), 2089–2097 (2008)
De Terán, F., Dopico, F.M., Mackey, D.S.: Fiedler companion linearizations for rectangular matrix polynomials. Linear Algebra Appl. 437(3), 957–991 (2012)
Dmytryshyn, A.: Miniversal deformations of pairs of skew-symmetric matrices under congruence. Linear Algebra Appl. 506, 506–534 (2016)
Dmytryshyn, A.: Structure preserving stratification of skew-symmetric matrix polynomials. Linear Algebra Appl. 532, 266–286 (2017)
Dmytryshyn, A.: Miniversal deformations of pairs of symmetric matrices under congruence. Linear Algebra Appl. 568, 84–105 (2019)
Dmytryshyn, A., Dopico, F.M.: Generic complete eigenstructures for sets of matrix polynomials with bounded rank and degree. Linear Algebra Appl. 535, 213–230 (2017)
Dmytryshyn, A., Futorny, V., Kågström, B., Klimenko, L., Sergeichuk, V.: Change of the congruence canonical form of 2-by-2 and 3-by-3 matrices under perturbations and bundles of matrices under congruence. Linear Algebra Appl. 469, 305–334 (2015)
Dmytryshyn, A., Futorny, V., Sergeichuk, V.: Miniversal deformations of matrices of bilinear forms. Linear Algebra Appl. 436, 2670–2700 (2012)
Dmytryshyn, A., Futorny, V., Sergeichuk, V.: Miniversal deformations of matrices under *congruence and reducing transformations. Linear Algebra Appl. 446, 388–420 (2014)
Dmytryshyn, A., Johansson, S., Kågström, B., Van Dooren, P.: Geometry of matrix polynomial spaces. Found. Comput. Math. 20, 423–450 (2020)
Dopico, F.M., Lawrence, P., Pérez, J., Van Dooren, P.: Block Kronecker linearizations of matrix polynomials and their backward errors. Numer. Math. 140, 373–426 (2018)
Futorny, V., Klimenko, V., Sergeichuk, V.: Change of the *congruence canonical form of 2-by-2 matrices under perturbations. Electron. J. Linear Algebra 27 (2014)
Futorny, V., Klymchuk, T., Klymenko, O., Sergeichuk, V.V., Shvai, N.: Perturbation theory of matrix pencils through miniversal deformations. Linear Algebra Appl. (2020)
Giesbrecht, M., Haraldson, J., Labahn, G.: Computing the nearest rank-deficient matrix polynomial. In: Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC ’17, pp. 181–188. ACM, New York (2017)
Golub, G.H., Van Loan, C.F.: Matrix Computations, 4rd edn. John Hopkins University Press, Baltimore, MD (2013)
Guglielmi, N., Lubich, C., Mehrmann, V.: On the nearest singular matrix pencil. SIAM J. Matrix Anal. Appl. 38, 776–806 (2017)
Güttel, S., Tisseur, F.: The nonlinear eigenvalue problem. Acta Numer. 26, 1–94 (2017)
Hilliges, A., Mehl, C., Mehrmann, V.: On the solution of palindromic eigenvalue problems. In: Proceedings of the 4th European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS). Jyväskylä, Finland (2004)
Johansson, S., Kågström, B., Van Dooren, P.: Stratification of full rank polynomial matrices. Linear Algebra Appl. 439, 1062–1090 (2013)
Karlsson, L., Tisseur, F.: Algorithms for Hessenberg-triangular reduction of Fiedler linearization of matrix polynomials. SIAM J. Sci. Comput. 37(3), C384–C414 (2015)
Kressner, D., Schröder, C., Watkins, D.: Implicit QR algorithms for palindromic and even eigenvalue problems. Numer. Algorithms 51(2), 209–238 (2009)
Mackey, D.S., Mackey, N., Tisseur, F.: Polynomial eigenvalue problems: theory, computation, and structure. In: Numerical Algebra, Matrix Theory, Differential-Algebraic Equations and Control Theory, pp. 319–348. Springer (2015)
Micusík, B., Pajdla, T.: Simultaneous surveillance camera calibration and foot-head homology estimation from human detections. 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 1562–1569 (2010)
Suárez, A., González, L.: Normalized Frobenius condition number of the orthogonal projections of the identity. J. Math. Anal. Appl. 400(2), 510–516 (2013)
Tisseur, F.: Backward error and condition of polynomial eigenvalue problems. Linear Algebra Appl. 309(1), 339–361 (2000)
Tisseur, F., Meerbergen, K.: The quadratic eigenvalue problem. SIAM Rev. 43(2), 235–286 (2001)
Trench, W.F.: Invertibly convergent infinite products of matrices. J. Comput. Appl. Math. 101(1), 255–263 (1999)
Van Dooren, P., Dewilde, P.: The eigenstructure of a polynomial matrix: computational aspects. Linear Algebra Appl. 50, 545–579 (1983)
Acknowledgements
The author is thankful to Zhaojun Bai, Froilán Dopico, and Massimiliano Fasi for the useful discussions on this paper. The author is also very thankful to the anonymous referees for the helpful remarks and suggestions.
Funding
Open access funding provided by Örebro University.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Marko Huhtanen.
Dedicated to the memory of my father, Roman Dmytryshyn (1959–2020).
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Dmytryshyn, A. Recovering a perturbation of a matrix polynomial from a perturbation of its first companion linearization. Bit Numer Math 62, 69–88 (2022). https://doi.org/10.1007/s10543-021-00878-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10543-021-00878-9