Eigenvalue Problems

Abstract

In natural sciences and engineering, are often used differential equations and systems of differential equations. Their solution leads to the problem of eigenvalues. Because of that, problem of eigenvalues occupies an important place in linear algebra. In this caption we will consider the problem of eigenvalues, and to linear and quadratic problems of eigenvalues. During the studying of linear problem of eigenvalues, we put emphasis on QR algorithm for unsymmetrical case and on minmax characterization of symmetric case. During the studying of quadratic problems of eingenvalue, we consider the linearization and variational characterization. We illustrate all with practical examples.

1. Introduction

Every mechanical system has the property of vibration. Analog phenomenon can be observed in the electrical systems in the form of oscillation circuits. Neglecting terms of vibration can lead to resonance, which on one hand can have catastrophic consequences as the demolition of the bridge, on the other hand can be used positively. Mathematical description of vibratory condition leads to a differential equation or a system of differential equations. This problem is further transformed to the eigenvalue problem. This is the motivation for considering the eigenvalue problems.

This chapter is organized as follows: The Linear eigenvalue problem and the quadratic eigenvalue problem.

2. The linear eigenvalue problem

This section considers the linear eigenvalue problem of finding parameter λ such that the linear system

$\mathit{A}\mathbf{x}\mathbf{=}\lambda \mathbf{x}$E1

has nontrivial solution x, where A ∈ C^(n,n). The scalar λ is called an eigenvalue of A, and x is an eigenvector of A corresponding to λ. The set of all eigenvalues of matrix A is called the spectrum of A, and is denoted as σ(A)_.

The literature discusses the right and left eigenvectors. In our deliberations, we have been limited to the right eigenvectors, which are earlier defined.

This section is organized as follows:

1. Basis properties (characteristic polynomial, bases for eigenspaces, eigenvalues and invertibility, diagonalization)

2. QR Algorithm (The QR algorithm is used for determining all the eigenvalues of a matrix. Today, it is the best method for solving the unsymmetrical eigenvalue problems.)

3. Mathematical background for Hermitian (symmetric) case (Rayleigh quotient, min max principle of Poincare, minmax principle of Courant-Fischer)

4. Physical Background

5. General linear eigenvalue problem

$\mathit{A}\mathbf{x}=\lambda \mathit{B}\mathbf{x}$E2

2.1. Basic properties

In this section we outline the basic concepts and theorems, which will allow us to understand further elaboration. The eigenvalue problem is related to the homogeneous system of linear equations, as we will see in the following discussion.

To find the eigenvalues of n × n matrix A we rewrite (1) as

$\mathit{A}\mathbf{x}=\lambda \mathit{I}\mathbf{x}$E3

or by inserting an identity matrix I equivalently

$\left(\mathit{A}-\lambda \mathit{I}\right)\mathbf{x}=\mathbf{0}\text{.}$E4

Such system is homogeneous system and the system (3) has a nontrivial solution if and only if

$\mathit{det}\left(\mathit{A}-\lambda \mathit{I}\right)=0\text{.}$E5

This is called the characteristic equation of A; the scalars satisfying this equation are the eigenvalues of A. When is expanded, the determinant det(A − λI) is polynomial p in λ, and it is called the characteristic polynomial of A.

The following theorem gives the link between the characteristic polynomial of the matrix A and its eigenvalues.

Theorem 2.1.1. Equivalent Statements

If A is an n × n matrix and λ is a complex number, then the following are equivalent

1. λ is an eigenvalue of A.

2. The system of equations (A − λI)x = 0 has nontrivial solutions.

3. There is a nonzero vector x in ℂⁿ such that Ax = λx.

4. λ is a solution of the characteristic equation det(A − λI).

Some coefficients of the characteristic polynomial of A have a specific shape. The following theorem gives the information about it.

Theorem 2.1.2.

If A is an n × n matrix, then the characteristic polynomial p(λ) of A has degree n, the coefficient of λⁿ is (−1)ⁿ, the coefficient of λ^n − 1 is (−1)^n − 1 trace(A) and the constant term is det(A), where trace(A) := a₁₁ + a₂₂ + ⋯ + a_nn.

In some structured matrices, eigenvalues can be read as shown in Theorem 2.1.3.

Theorem 2.1.3.

If A is an n × n triangular matrix (upper triangular, lower triangular, or diagonal), then the eigenvalues of A are entries of the main diagonal of A.

Cayley-Hamilton’s theorem is one of the most important statements in linear algebra. The theorem states:

Theorem 2.1.4.

Substituting the matrix A for λ in characteristic polynomial of A, we get the result of zero matrix i.e., p(A) = 0.

There are a number of methods for determining eigenvalue. Some methods allow finding all the eigenvalues and the other just a few of the eigenvalues. Methods based on first determining the coefficients of the characteristic polynomial, and later to determining the eigenvalue solving algebraic equations are rarely implemented, because they are numerically unstable. In fact, for the coefficients of the characteristic polynomial burdened with rounding errors, and due to numerical instability cause large errors in the eigenvalue. Because of that, the characteristic polynomial has mainly theoretical significance. The methods, which are based on the direct application characteristic polynomial, are applied in practice only when the characteristic polynomial is well conditioned. Also for some structured matrices, we can apply the method for the characteristic polynomial, but we don’t calculate directly characteristic polynomial coefficients. The following example describes a class of such matrices.

Example 2.1.1 The Example of structured matrix which achieve the characteristic polynomial for determining the eigenvalue are Toeplitz matrix. Toeplitz matrix marked as T_n, are matrices with constant diagonals. If the Toeplitz matrix is symmetric and positive definite, recursive relation is p_n(λ) = p_n − 1(λ)β_n − 1(λ), where are p_n i p_n − 1 characteristic polynomial matrix T_n i T_n − 1 respectively a β_n − 1 Schur-Szegö parameter for Yule-Walker system. The above recursive relation enables work with characteristic polynomial without individual accounts of his odds. More information can be found at [1]

The following definitions are introducing two important terms: the geometric multiplicity of λ₀ and the algebraic multiplicity of A.

The eigenvectors corresponding to λ are the nonzero vectors in the solutions space of (A − λI)x = 0. We call this solution space the eigenspace of A corresponding to λ.

Definition 2.1.1.

If λ₀ is an eigenvalue of an n × n matrix A, then the dimension of the eigenspace corresponding to λ₀ is called the geometric multiplicity of λ₀, and the number of times that λ − λ₀ appears as a factor in the characteristic polynomial of A is called the algebraic multiplicity of A.

Eigenvalue and eigenvector have some specific features, which are easy to prove.

The following are some of the obvious features of eigenvalues of matrix A and corresponding eigenvector:

Theorem 2.1.5.

1. If μ ≠ 0 complex number, λ is an eigenvalue of matrix A, and x ≠ 0 corresponding eigenvector, then μx is a corresponding eigenvector.

2. If k is a positive integer, λ is an eigenvalue of matrix A, and x ≠ 0 corresponding eigenvector, then λ^k is an eigenvalue of A^k and x is a corresponding eigenvector.

3. Matrix A and A^T have the same eigenvalues.

In linear algebra invertible matrix are important. From the problem of eigenvalues we can easily conclude If the matrix A is invertible or not. What more can be, the eigenvalues of the matrix A invertible can be immediately read from the eigenvalues of the matrix A^− 1. Because of that, in the following theorems we summarize some properties of invertible matrix.

Theorem 2.1.6.

If A is an n × n matrix, then the following are equivalent.

1. A is invertible.

2. λ = 0 is not an eigenvalue of A

3. If λ is an eigenvalue of matrix invertible A, and x ≠ 0 corresponding eigenvector, then $\frac{1}{\lambda }$ is an eigenvalue of A^− 1 and x is a corresponding eigenvector.

4. det(A) ≠ 0.

5. A has rank n.

6. Ax = 0 has only the trivial solution.

7. Ax = b has exactly one solution for every n × 1 matrix B

8. The column vectors of A form a basis for ℝⁿ.

9. The row vectors of A form a basis for ℝⁿ.

10. A^TA is invertible.

The problem of finding a base ℝⁿ consisting of eigenvectors is very important in linear algebra. Because of that, in this section we will consider the following two equivalent problems:

The Eigenvector Problem. Given an n × n matrix A, does there exist a basis for ℝⁿ consisting of eigenvectors of A?

The Diagonalization Problem (Matrix Form). Given an n × n matrix A, does there exist an invertible matrix P such that P^− 1AP is a diagonal matrix?

The latter problem suggests the following terminology.

Definition 2.1.3. Two square matrices A and B are similarly called, if there is invertible matrix P, so that B = P^− 1AP. The transition from A to the matrix of the matrix B is called the similarity transformations .

The importance of similar matrices can be seen in the following theorem:

Theorem 2.1.7. Similar matrices A and B have the same characteristic polynomial. They have the same eigenvalues including their geometric multiplicity of the geometric multiplicity of λ₀ and the algebraic multiplicity of λ₀.

Based on previous definitions, we can define the term diagonalizable as follows:

Definition 2.1.4. A square matrix A is called diagonalizable if the transformation of similarity may be translated into a diagonal form.

To the above two problems are obviously equivalent to the following theorem.

Theorem 2.1.8.

If A is an n × n matrix, then the following are equivalent.

1. A is diagonalizable.

2. A has n linearly independent eigenvectors.

The following algorithm is for diagonalizing a matrix

Algorithm for Diagonalizing a Matrix

Find n linearly independent eigenvectors of A, marked as x¹, x², ⋯, xⁿ.

Form the matrix P having x¹, x², ⋯, xⁿ., at its column vectors.

The matrix P^− 1AP then will be diagonal with λ₁, λ₂, ⋯, λ_n successive diagonal entries, where λ_i is eigenvalue corresponding to xⁱ , for i = 1, 2, ⋯, n.

Theorem 2.1.9.

If x¹, x², ⋯, x^k are eigenvectors of A corresponding to distinct eigenvalues λ₁, λ₂, ⋯, λ_k, then {x¹, x², ⋯, x^k } is a linearly independent set.

As consequence of Theorem 2.1.8. and Theorem 2.1.9 ., we obtain the following important result

Theorem 2.1.10.

If an n × n matrix A has n distinct eigenvalues, then A is diagonalizable.

There are matrices that can have the same eigenvalues and yet can be diagonalizable. Broadest such class of such matrices are normal matrix, which we will introduce the following definition.

Definition 2.1.5 . Matrix A ∈ ℂ^(n,n) is called normal, if holds A^HA = AA^H.

More general characterization of diagonalizable matrix A is given in the following theorem .

Theorem 2.1.11.

If A is a square matrix, then:

1. For every eigenvalue of A the geometric multiplicity is less than or equal to the algebraic multiplicity.

2. A is diagonalizable if and if the geometric multiplicity is equal to the algebraic multiplicity for every eigenvalue.

2.2. QR algorithm

In this section we will present the QR algorithm. In numerical linear algebra, the QR algorithm is an eigenvalue algorithm : that is, a procedure to calculate the eigenvalues and eigenvectors of a matrix. QR algorithm represent factorization method, because it is based on the matrix decomposition. First factorization method labeled as LR algorithm is developed by H. Rutishauser in 1958. LR algorithm is due to the many shortcomings, today is rarely used, (Wilkinson monograph). Better factorization method, is designated as the QR algorithm. The basic form have developed independently from each other, in 1962 G. F. Francis (England) and by Vera N. Kublanskoovskaya (USSR). Today, it is the best method for solving the unsymmetrical eigenvalue problems, when you want to determine all the eigenvalues of the matrix. It is particularly effective when it is brought into the so-called matrix "Condensed form". Condensed form is for the unsymmetrical problem Hessenberg form. About Hessenberg form will be discussed more later. The basic idea is to perform a QR decomposition, writing the matrix as a product of an orthogonal matrix and an upper triangular matrix, multiply the factors in the reverse order, and iterate.

For understanding of the QR algorithm we will need the following terms:

Definition 2.2.1. Matrix Q ∈ P^(n,n) called orthogonal if worth Q^TQ = I.

Remark 2.2.1.Orthogonal matrix represent special case of unitary matrices. The Matrix U ∈ ℂ^(n,n) called unitary if applies U^HU = I. It is now clear that the orthogonal matrix of a unitary matrix in which all elements of real numbers. In practice, of course, is easier to work with the orthogonal than unitary matrices.

Remark 2.2.2 Orthogonal and unitary matrices are normal matrices.

Let A and B are similar matrices. If the similarity transformations performed by the orthogonal or unitary matrix Q i.e. if applies B = Q^TAQ or B = U^HAU we will say that the matrices A and B are unitary similar. Since the unitary similar matrices are special special case of similar matrix, the eigenvalues of unitary similar matrices are the same.

In addition to the unitary similar matrices and their properties for the introduction of the QR algorithm, we will need the following theorem.

Theorem 2.2.1. Let’s A ∈ ℝ^(n,n) regular matrix, then there is a decomposition A = QR, where is Q orthogonal matrix and R upper triangular matrix. If the diagonal elements of the matrix R are positive, decomposition is unique.

The decomposition of the matrix A from Theorem 2.2.1 is called the QR decomposition of the matrix A.

The following is a basic form of the QR algorithm.

Let A₀ := A. The basic forms of the QR algorithm is given by

Algorithm 2.2.1 . (QR algorithm-basic forms)

For i = 0, 1, ⋯ until convergence

Decompose A_i = Q_iR_i (QR decomposition)

${\mathit{A}}_{\mathit{i}+\mathbf{1}}={\mathit{R}}_{\mathit{i}}{\mathit{Q}}_{\mathit{i}}$E60000

End

Theorem 2.2.1 All matrices A_i resulting in algorithms 2.2.1 are unitary similar.

Proof

Since applies ${\mathit{Q}}_i^T{\mathit{A}}_{\mathit{i}}={\mathit{R}}_{\mathit{i}}$ we have ${\mathit{A}}_{\mathit{i}+\mathbf{1}}={\mathit{R}}_{\mathit{i}}{\mathit{Q}}_{\mathit{i}}={\mathit{Q}}_{\mathit{i}}^{\mathit{T}}{\mathit{A}}_{\mathit{i}}{\mathit{Q}}_{\mathit{i}}$. Based on past relationships, it is clear that it is true ${\mathit{A}}_{\mathit{i}+\mathbf{1}}={\mathit{Q}}_{\mathit{i}}^{\mathit{T}}{\mathit{Q}}_{\mathit{i}-\mathbf{1}}^{\mathit{T}}\cdot \cdots \cdot {\mathit{Q}}_{\mathbf{0}}^{\mathit{T}}{\mathit{A}}_{\mathbf{0}}{\mathit{Q}}_{\mathbf{0}}\cdot \cdots \cdot {\mathit{Q}}_{\mathit{i}-\mathbf{1}}{\mathit{Q}}_{\mathit{i}}$. It is obvious that the matrix Q := Q₀ ⋅ ⋯ ⋅ Q_i orthogonal matrix and the theorem is proved.

Let’s look briefly at some properties QR algorithm:

1. For QR factorization full matrix it is necessary O(n³) flops by factorization. Total QR iteration needs O(n⁴) flops, which means that it is objectively very slow. But the problem of the slowness of the basic forms of the algorithm can be overcome with the two strategies, namely: translation matrix in Hessenberg form and the introduction of shift.

Let A ∈ ℝ^(n,n) then for each and Q_i, R_i ∈ ℝ^(n,n) and the whole algorithm is performed in real area. If all eigenvalues of matrix A modulo different, then they are all real and the algorithm converges. However, if there is at least one, and so it is worth $\left|\frac{{\lambda }_{i+1}}{{\lambda }_i}\right|\approx 1$ QR algorithm is very slow. If the matrix A has complex eigenvalues then a basic form of the QR algorithm does not converge. We have already seen the need for the introduction of Hessenberg form of a matrix and it will introduce the following definition.

Definition 2.2.2. For the matrix A will say that in the upper Hessenberg form if holds

$a_{ij}=0\mathrm{f}\mathrm{o}\mathrm{r}i-j>2$E70000

i.e. the upper triangular matrix has a side below the main diagonal.

The process of reducing the Hessenberg form can be performed using Househelder reflectors and Givens rotation. Let’s look at bringing in Hessenberg form using Househelder spotlight.

Let $\mathit{A}=\left(\begin{array}{cc}\hfill a_{11}\hfill & \hfill {\mathbf{c}}^T\hfill \\ \hfill \mathbf{b}\hfill & \hfill \mathit{B}\hfill \end{array}\right)\mathrm{with}\mathbf{b}\ne \mathbf{0}$

Our goal is to determine ω ∈ ℂ^n − 1 with features a‖ω‖₂ = 1 and

$${\mathit{Q}}_1\mathbf{b}:=\left({\mathit{I}}_{\mathit{n}-\mathbf{1}}-2\mathbf{\omega }{\mathbf{\omega }}^H\right)\mathbf{b}=\mathrm{k}{\mathbf{e}}^1$$E80000

where I_n − 1 is identity matrix row n-1 a e¹ the first column of the matrix I_n − 1.

We define Householder reflector as follows

${\mathbf{P}}_{\mathbf{1}}:=\left(\begin{array}{ll}1\hfill & {\mathbf{0}}^{\mathit{T}}\hfill \\ \mathbf{0}\hfill & {\mathit{Q}}_{\mathbf{1}}\hfill \end{array}\right)$E90000

Now applies

${\mathit{A}}_{\mathbf{1}}:={\mathit{P}}_{\mathbf{1}}\mathit{A}{\mathit{P}}_{\mathbf{1}}=\left(\begin{array}{cc}\hfill a_{11}\hfill & \hfill {\mathbf{c}}^{\mathit{T}}{\mathit{Q}}_{\mathbf{1}}\hfill \\ \hfill k\hfill & \hfill \hfill \\ \hfill 0\hfill & \hfill \hfill \\ \hfill ⋮\hfill & \hfill {\mathit{Q}}_{\mathbf{1}}\mathit{B}{\mathit{Q}}_{\mathbf{1}}\hfill \\ \hfill 0\hfill & \hfill \hfill \end{array}\right)\text{.}$E100000

Obviously, the first column of the matrix A₁ have a look what is required in the upper Hessenberg form. In this way, we showed that the first column is converted into a suitable form. An analogous procedure can be performed on 2,3,…,n-1 column.

For the implementation of QR algorithm is important that in each iteration in implementing QR algorithm preserves the structure of the matrix. For a matrix form in the upper Hessenberg applies following theorem.

Theorem 2.2.2 If A is upper Hessenberg matrix, then the Q in its QR factorization A=QR also upper Hessenberg matrix.

The above theorem that QR and also upper Hessenberg matrix is the product of the upper triangular matrix and upper Hessenberg matrix.

Preserving the structure of the matrix is very important to stop the efficiency of the algorithm. Namely, if the upper Hessenberg matrix A matrix of its QR factorization is only O(n²) instead of O(n³) as is necessary for QR factorization (decomposition) of full matrix.

Let’s look at one more advantage of the transformation matrix in Hessenberg form. Namely, A_i → R (i → ∞), where R is an upper triangular matrix. Because the matrix A_i is always upper Hessenberg matrix proves that elements of the second diagonal tend to zero and it’s worth $a_{j+1,j}^{\left(i\right)}\to 0\left(i\to \infty \right),j=1,2,\cdots ,n-1$ wherein $a_{j+1,j}^{\left(i\right)}$ elements of the matrix A_i. It is now clear that for sufficiently large and can be read eigenvalues initial value of A on the basis of theorem 2.1.3. as the diagonal elements of the matrix A_i

For a further improve of the algorithm, shift is used . The idea of improving the QR algorithm is based on the simple fact that if the eigenvalues of A are equal λ_i that the eigenvalues of the matrix A − σI equal λ_i − σ. If we shift σ chosen close eigenvalues, there is a strong acceleration of the algorithm.

Let A₀ := A.

Algorithm 2.2.2. . (QR algorithm with shift)

For i = 0, 1, ⋯ until convergence

Choose shift σ_i near the eigenvalues value

Decompose A_i − σ_iI = Q_iR_i (QR decomposition)

${\mathit{A}}_{\mathit{i}+\mathbf{1}}={\mathit{R}}_{\mathit{i}}{\mathit{Q}}_{\mathit{i}}+{\sigma }_i\mathit{I}$E110000

End

It is easy to prove that all matrices in the algorithm 2.2.1. are unitary similar. From the above it is clear that in the case of real matrices with real eigenvalues is best to shift the parameters taken ${\sigma }_i=a_{n.n}^{\left(i\right)}$.

For a further analysis of the parameter shifts we will need the concept of reduced upper Hessenberg matrix as well as the implicit Q theorem.

Definition 2.2.3 The upper Hessenberg matrix H is unreduced upper Hessenberg matrix if the first second diagonal not a single zero.

Theorem 2.2.3. Let Q^TAQ = H unreduced upper Hessenberg matrix with positive subdiagonal elements h_k + 1,k a Q unitary matrix. The columns of the matrix Q and matrix H starting from the second to n-th, are uniquely determined first column of the matrix Q.

Proof

Let Q = (q¹, q², ⋯, qⁿ) some prior q¹, q², ⋯, q^k and the first k − 1 column of the matrix H is determined. The proof will be carried out by mathematical induction by k. For k = 1 is determined q¹ and the process can start. Because QH = AQ and H = (h_ij) the upper Hessenberg matrix applies

$h_{k+1,k}{\mathit{q}}^{k+1}+h_{kk}{\mathit{q}}^k+\cdots +h_{1k}{\mathit{q}}^1=\mathit{A}{\mathit{q}}^k\text{.}$E120000

If you multiply the last equality with (qⁱ)^H we get

$h_{ik}={\left({\mathit{q}}^i\right)}^H\mathit{A}{\mathit{q}}^k\left(i=1,2,\cdots ,k\right)$E130000

From here it’s k-th column of H except element h_k + 1,k specified.

Because h_k + 1,k ≠ 0 we have

${\mathit{q}}^{k+1}=\frac{1}{h_{k+1,k}}\left(\mathit{A}{\mathit{q}}^k-{\displaystyle \sum _{i=1}^k{h}_{ik\mathit{q}i}}\right)\text{.}$E140000

From (q^k + 1)^Hq^k + 1 = 1 and positivity h_k + 1,k we get h_k + 1,k in a unitary way.

Theorem is proved.

Remark 2.2.3 Condition h_k + 1,k > 0 in the previous theorem was we only need to ensure uniformity of matrices Q i H.

With the help of implicit Q theorem we discuss the selection of shift A = A₀ real matrix has complex eigenvalues. Then you have to make a double shift for $\sigma \mathrm{i}\overline{\sigma }$. Namely,

$\begin{array}{ll}{\mathit{A}}_0-\sigma \mathit{I}={\mathit{Q}}_1{\mathit{R}}_1,\hfill & {\mathit{A}}_1={\mathit{R}}_1{\mathit{Q}}_1+\sigma \mathit{I}\hfill \\ {\mathit{A}}_0-\overline{\sigma }\mathit{I}={\mathit{Q}}_1{\mathit{R}}_1,\hfill & {\mathit{A}}_1={\mathit{R}}_1{\mathit{Q}}_1+\overline{\sigma }\mathit{I}\text{.}\hfill \end{array}$E150000

From there, easy to get ${\mathit{A}}_2={\mathit{Q}}_2^T{\mathit{Q}}_1^T{\mathit{A}}_0{\mathit{Q}}_1{\mathit{Q}}_2$. Matrices Q₁i Q₂ can be chosen so that Q₁Q₂ real matrices and therefore the matrix A₂ is real matrix. Applying

$\begin{array}{c}\hfill {\mathit{Q}}_1{\mathit{Q}}_2{\mathit{R}}_2{\mathit{R}}_1={\mathit{Q}}_1\left({\mathit{A}}_1-\overline{\sigma }\mathit{I}\right){\mathit{R}}_1={\mathit{Q}}_1\left({\mathit{R}}_1{\mathit{Q}}_1+\left(\sigma -\overline{\sigma }\right)\mathit{I}\right){\mathit{R}}_1={\mathit{Q}}_1{\mathit{R}}_1{\mathit{Q}}_1{\mathit{R}}_1+\left(\sigma -\overline{\sigma }\right){\mathit{Q}}_1{\mathit{R}}_1\hfill \\ \hfill ={\left({\mathit{A}}_0-\sigma \mathit{I}\right)}^2+\left(\sigma -\overline{\sigma }\right)\left({\mathit{A}}_0-\sigma \mathit{I}\right)=A_0^2+\left(\sigma +\overline{\sigma }\right){\mathit{A}}_0+{\left|\sigma \right|}^2\mathit{I}=:\mathit{M}\text{.}\hfill \end{array}$E160000

Because of $\sigma +\overline{\sigma }\in P$, matrix M is real. Then Q₁Q₂R₂R₁ QR factorization real matrix and that means Q₁Q₂ i R₂R₁ we can choose a real matrix. The first column of the matrix Q₁Q₂ is proportional to the first column of the matrix M, and the other columns are calculated by applying implicit Q theorem.

2.3. Mathematical background for Hermitian (symmetric) case

In this section we look at the problem of eigenvalues in the case of a symmetric or Hermitian matrix.

Definition 2.3.1. Matrix A ∈ ℝ^(n,n) is called symmetric if applies A = A^T.

Definition 2.3.2 Matrix A ∈ ℂ^(n,n) is called Hermitian if applies A = A^H.

Remark 2.3.1 Symmetric Matrices are only a special case of Hermitian matrices in the case that the elements matrices are real numbers. Therefore, we will formulate a theorem for Hermitian matrices.

Remark 2.3.2 Hermitian and symmetric matrices are normal matrices, which means that they can diagonalize.

The following theorem gives important information on the reality of eigenvalues Hermitian (symmetric) matrices. This feature greatly facilitates consideration of the problem of eigenvalues for this class of matrices, which makes this class of matrices applicable in practice.

Theorem 2.3.1 . If A is Hermitian (symmetric) matrix, then:

1. The eigenvalues of A are all real numbers.

2. Eigenvectors from different eigenspace are orthogonal.

Since all the eigenvalues of real ones can be compared. Therefore, we assume that the eigenvalues in order of size, i.e. It applies λ₁ ≤ λ₂ ≤ ⋯ ≤ λ_n and that the corresponding orthonormal eigenvectors.

If the matrix A is symmetrical due to symmetry feature, it comes to the significant acceleration algorithms for the unsymmetrical case. We will demonstrate the QR algorithm which is presented in section 2.2. for the unsymmetrical case. In symmetric case is important to note that the upper Hessenberg form of symmetric matrix tridiagonal matrix whose QR decomposition is only necessary O(n) operation. It is also important that during the QR algorithm preserves the structure of the matrix or all tridiagonal matrices A_i. For a shift in this case is usually taken Wilkins shift which is defined as an eigenvalue of matrix

$\left(\begin{array}{cc}\hfill a_{n-1,n-1}\hfill & \hfill a_{n-1,n}\hfill \\ \hfill a_{n-1,n}\hfill & \hfill a_{n,n}\hfill \end{array}\right)$ , that is closest a_n,n.

For a QR algorithm Wilkinson shifts apply following theorem, whose proof is given in [2]

Theorem 2.3.2 (Wilkinson) QR algorithm with Wilkinson shifts for symmetric tridiagonal matrix converges globally and at least linearly. For a almost all of the matrices are on asymptotically cubic converging.

Now we introduce the very important concept of the Rayleigh quotient, because it gives the best estimate of the eigenvalues for a given vector x ∈ ℂⁿ, x ≠ 0

Definition 2.3.3 Let A be a Hermitian (symmetric) matrix. For a given vector x ∈ ℂⁿ, x ≠ 0 Rayleigh quotient is defined $R\left(\mathit{x}\right):=\frac{{\mathbf{x}}^{\mathbf{H}}\mathit{A}\mathbf{x}}{{\mathbf{x}}^{\mathbf{H}}\mathbf{x}}$.

The importance of the Rayleigh quotient is seen in the following theorems

Theorem 2.3.3. (Features Rayleigh quotient)

1. For all x ∈ ℂⁿ, x ≠ 0 worth λ₁ ≤ R(x) ≤ λ_n.

2. ${\lambda }_1={min}_{\mathit{x}\ne \mathbf{0}}R\left(\mathbf{x}\right),{\lambda }_n={max}_{\mathit{x}\ne \mathbf{0}}R\left(\mathbf{x}\right)$

3. If x ≠ 0 with λ₁ = R(x) respectively λ_n = R(x) x is then x is the eigenvector corresponding to λ₁ respectively λ_n.

4. $\begin{array}{l}{\lambda }_i=min\left\{R\left(\mathbf{x}\right):{\mathbf{x}}^{\mathrm{H}}{\mathbf{x}}^{\mathit{j}}=0,j=1,\cdots ,i-1,\mathbf{x}\ne \mathbf{0}\right\}=\hfill \\ max\left\{R\left(\mathbf{x}\right):{\mathit{x}}^{\mathrm{H}}{\mathbf{x}}^{\mathit{j}}=0,j=i+1,\cdots n,\mathbf{x}\ne \mathbf{0}\right\}\hfill \end{array}$

Paragraph (d) in the previous theorem is known as Rayleigh principle. However it is numerically worthless, because for the determination example, we need eigenvector or x¹ corresponding to the eigenvalue λ₁. In order to overcome this disadvantage is introduced min max principle of Poincaré that is listed in the following theorems.

Theorem 2.3.4 . (min max principle of Poincaré )

${\lambda }_i=\underset{\mathit{dimV}=i}{min}\underset{\mathbf{x}\in \mathit{V}\backslash \left\{\mathbf{0}\right\}}{max}R\left(\mathbf{x}\right)=\underset{\mathit{dimV}=n-i+1}{max}\underset{\mathbf{x}\in \mathit{V}\backslash \left\{\mathbf{0}\right\}}{min}R\left(\mathbf{x}\right)$E190000

The following formulation is known as min max principle of Courant-Fischer and often favorable to use.

Theorem 2.3.5. (min max principle of Courant-Fischer )

$\begin{array}{c}\hfill {\lambda }_i=\underset{\left\{p^1,\cdots ,p^{i-1}\right\}}{min}max\left\{R\left(\mathbf{x}\right):{\mathbf{x}}^{\mathrm{H}}{\mathbf{p}}^{\mathit{j}}=0,j=i+1,\cdots n,\mathbf{x}\ne \mathbf{0}\right\}\hfill \\ \hfill \underset{\left\{p^1,\cdots ,p^{n-i}\right\}}{max}min\left\{R\left(\mathbf{x}\right):{\mathbf{x}}^{\mathrm{H}}{\mathbf{p}}^{\mathit{j}}=0,j=i+1,\cdots n,\mathbf{x}\ne \mathbf{0}\right\}\text{.}\hfill \end{array}$E200000

From the above it is clear that these theorems are important for the localization of eigenvalues.

The following is an algorithm that is in linear algebra known as Rayleigh quotient iteration and it reads as follows

Let A ∈ ℝ^(n,n) symmetric matrix and x⁰ initial vector, which is the standardized. For which applies ‖x⁰‖₂ = 1.

Algorithm 2.3.1 . (Rayleigh quotient iteration)

${\sigma }_0={\left({\mathbf{x}}^0\right)}^T\mathbf{A}{\mathbf{x}}^0$E210000

For i = 1, 2 ⋯ until convergence

Solve (A_i − σ_iI)yⁱ = x^i − 1

${\mathbf{x}}^i=\frac{{\mathbf{y}}^i}{{‖{\mathbf{y}}^{\mathrm{i}}‖}_2}$E220000

${\sigma }_0={\left({\mathbf{x}}^i\right)}^T\mathbf{A}{\mathbf{x}}^i\text{.}$E230000

End

Theorem 2.3.6. Rayleigh quotient iteration converges cubic.

Finally point out that the most effective for symmetric matrices Divide-and-Conquer method. This method was introduced by Cupen [3] and the first effective implementation is the work of Cu and Eisenstat [4]. About this method, more information can be found in [4].

2.4. Physical background

We have already mentioned that the problem of eigenvalues has numerous applications in engineering. Even more motivation to consider problems of eigenvalues, comes from their large application in technical disciplines. On a simple example of a mass-spring system illustrated with application of eigenvalues in engineering. We are assuming, that each spring has the same natural length l and the same spring constant k. Finally, we can assume that the displacement of each spring in measured to its own local coordinate system with an origin at the spring’s equilibrium position.

Applying Newton’s second law we get the following system

$\begin{array}{c}\hfill m_1\frac{d^2{x}_1}{d{t}^2}-k\left(-2x_1+x_2\right)=0\hfill \\ \hfill m_2\frac{d^2{x}_2}{d{t}^2}-k\left(x_1-2x_2\right)=0\text{.}\hfill \end{array}$E240000

We are aware of vibration theory that

$x_i=a_{i}sin\omega t\text{,}$E250000

where a_i is the amplitude of the vibration of mass i and ω is the frequency of the vibration.

If the last equation twice differentiate by t, we get

$\frac{d^2{x}_2}{d{t}^2}=-a_i{\mathrm{\omega }}^{2}sin\omega t\text{.}$E260000

If the last two equations obtained expressions for $x_i\mathrm{i}\frac{d^2{x}_i}{d{t}^2}\left(i=1,2\right)$ replace the initial system and write the system in matrix form, then we get

$A\left(\begin{array}{c}\hfill a_1\hfill \\ \hfill a_2\hfill \end{array}\right)={\omega }^2\left(\begin{array}{c}\hfill a_1\hfill \\ \hfill a_2\hfill \end{array}\right)\text{,}$E6

where

$A=\left(\begin{array}{cc}\hfill \frac{2k}{m_1}\hfill & \hfill -\frac{k}{m_1}\hfill \\ \hfill -\frac{k}{m_2}\hfill & \hfill \frac{2k}{m_2}\hfill \end{array}\right)$E280000

Equation (6) represents unsymmetrical eigenvalue problem.

More information on this case can be found in [5]

2.5. General Linear Eigenvalue Problem

In this section we will deal with general linear eigenvalue problem or the problem

$\begin{array}{cc}\hfill \mathbf{A}\mathbf{x}\mathbf{=}\mathbf{B}\mathbf{x},\hfill & \hfill \mathbf{x}\ne \mathbf{0}\hfill \end{array}\text{,}$E7

where A, B ∈ C^(n,n)

The scalar λ is called an eigenvalue of the problem (7), and x said to be an eigenvector of (7) corresponding to λ.

A common acronym for general linear eigenvalue problem is GEP. Now eigenvalue problems previously discussed is called the standard eigenvalue problem and tagging with SEP. In practice, the more often we meet with GEP than SEP. Now let’s consider some features of GEP and establish its relationship with SEP.

It is obvious that the eigenvalues of (7) zero of the characteristic polynomial, which is defined as p_n(λ) := det(A − λB). In the case of GES degree polynomial p_n is less than or equal to n. The characteristic polynomial of degree n has pn if and only if B is regular matrix. In case B=I we get SEP and in this case SEP has n eigenvalues. GEP and can be less than n eigenvalues. It can also happen that at GEP is p_n(λ)≡0 and it that case GEP has infinitely many eigenvalues.

The following two examples illustrate this situation with GEP

Example 4.5.1 Let in GEP $\mathit{A}=\left(\begin{array}{cc}\hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill \end{array}\right),\mathit{B}=\left(\begin{array}{cc}\hfill 0\hfill & \hfill 6\hfill \\ \hfill 0\hfill & \hfill 0\hfill \end{array}\right)$. Then worth p_n(λ)≡0 and every λ ∈ ℂ is eigenvalue i $\mathbf{x}=\left(\begin{array}{c}\hfill 1\hfill \\ \hfill 0\hfill \end{array}\right)$ is the corresponding eigenvector.

Example 4.5.2 Let in GEP $\mathit{A}=\left(\begin{array}{cc}\hfill 1\hfill & \hfill 2\hfill \\ \hfill 3\hfill & \hfill 4\hfill \end{array}\right),\mathit{B}=\left(\begin{array}{cc}\hfill 1\hfill & \hfill -1\hfill \\ \hfill -1\hfill & \hfill 1\hfill \end{array}\right)$. When we get to the characteristic polynomial p_n(λ) = (1 − λ)(4 − λ) − (3 + λ)(2 + λ) = − 2 − 10λ and the only eigenvalue value is $\lambda =-\frac{1}{5}$.

Atypical nature of we met in the last two examples are the result of the fact that in their matrix B was not regular. Therefore, it is usual in the GEP taken that A and B are Hermitian matrix and B is positive definite, that is, all the eigenvalues of the matrix B are positive.

Our goal is to find a connection between this taken GEP and symmetric SEP. As we said B is positive definite, B has a Cholesky decomposition, i.e., B = CC^H. Then is

$\begin{array}{cc}\hfill \mathit{A}\mathbf{x}\mathbf{=}\lambda \mathit{B}\mathbf{x}\iff \mathbf{F}\mathbf{y}:={\mathit{C}}^{-\mathbf{1}}\mathit{A}{\mathit{C}}^{-\mathit{H}}\mathbf{y}\mathit{,}\hfill & \hfill \mathbf{y}:={\mathbf{C}}^{\mathbf{H}}\hfill \end{array}\mathbf{x}$E8

Since matrix F has n eigenvalues and it belongs to the GEP also has n real eigenvalues. Namely on the basis of (7) are the same eigenvalues.

Let yⁱ i y^j orthonormal eigenvectors of F then for xⁱ = C^− Hyⁱ i x^j = C^− Hy^j apply

${\delta }_{ij}={\left({\mathbf{y}}^i\right)}^H{\mathbf{y}}^j={\left({\mathbf{C}}^H{\mathbf{x}}^i\right)}^H{\mathbf{C}}^{\mathrm{H}}{\mathbf{x}}^j={\left({\mathbf{x}}^{\mathit{i}}\right)}^H\mathit{C}{\mathit{C}}^{\mathrm{H}}{\mathbf{x}}^j={\left({\mathbf{x}}^{\mathit{i}}\right)}^H\mathbf{B}{\mathbf{x}}^j$E9

From equation (8) it is clear that the eigenvectors GEP (6) are an orthonormal vectors in relation to the new inner product is defined as ⟨x, y⟩_B := x^HBy. Now we’re going to GEP (7) redefine Rayleigh quotient as follows $R_{\left(A,B\right)}\left(x\right):=\frac{x^{H}Ax}{x^{H}Bx}$. With this predefined inneren product and Rayleigh quotient applies to all theorems of section 2.3 with appropriate modification of the definition changes required. This gives self-generation Hermitian (symmetrical) SEP.

3. The quadratic eigenvalue problems

In practice, nonlinear eigenproblems commonly arise in dynamic/stability analysis of structures and in fluid mechanics, electronic behavior of semiconductor hetero-structures, vibration of fluid–solid structures, vibration of sandwich plates, accelerator design, vibro-acoustics of piezoelectric/poroelestic structures, nonlinear integrated optics, regularization on total least squares problems and stability of delay differential equations. In practice, the most important is the quadratic problem Q(λ)x = 0 where

$$\begin{array}{ccc}\hfill \mathbf{Q}\left(\mathrm{\lambda }\right):={\mathrm{\lambda }}^{\mathbf{2}}\mathit{A}+\mathrm{\lambda }\mathit{B}+\mathit{C},\hfill & \hfill \mathit{A},\mathit{B},\mathit{C}\in {\mathrm{ℂ}}^{\mathit{n}\times \mathit{n}},\hfill & \hfill \mathit{A}\ne \mathbf{0},\mathbf{x}\ne \mathbf{0}\hfill \end{array}$$E10

This section is organized as follows:

1. Basic Properties

   We consider Rayleigh functional and Minmax Characterization

2. Linearization

   A standard approach for investigating or numerically solving quadratic eigenvalue linearization problems, where the original problem is transformed into a generalized linear eigenvalues problem with the same spectrum.

3. Physical Background

   We study vibration analysis of structural systems

3.1. Basic Properties

Variational characterization is important for finding eigenvalues. In this section we give a brief review of variational characterization of nonlinear eigenvalue problems. Since the quadratic eigenproblems are a special case of nonlinear eigenvalue problems, results for nonlinear eigenvalue problems can be specially applied for the quadratic eigenvalue problems. Variational characterization is generalization of well known minmax characterization for the linear eigenvalue problems.

We consider nonlinear eigenvalue problems

$\mathit{T}\left(\mathrm{\lambda }\right)x=\mathbf{0}\text{,}$E11

where T(λ) ∈ ℂ^n × n, λ ∈ J is a family of the Hermitian matrices depending continuously on the parameter λ ∈ J and J is a real open interval which may be unbounded.

Problems of this type arise in damped vibrations of structures, conservative gyroscopic systems, lateral buckling problems, problems with retarded arguments, fluid–solid vibrations, and quantum dot heterostructures.

To generalize the variational characterization of eigenvalues we need a generalization of the Rayleigh quotient. To this end we assume that

(A) for every fixed x ∈ ℂⁿ, x ≠ 0 the scalar real equation

$f\left(\lambda ;\mathbf{x}\right):={\mathbf{x}}^{\mathbf{H}}\mathit{T}\left(\lambda \right)\mathbf{x}$E12

has at most one solution p(x) ∈ J. Then f(λ; x) = 0 implicitly defines a functional p on some subset D ⊂ ℂⁿ which is called the Rayleigh functional of (11).

(B) for every x ∈ D and every λ ∈ J with λ ≠ p(x) it holds that (λ − p(x))f(λ; x) > 0.

If p is defined on D = ℂⁿ\{0} then the problem (1) is called overdamped, otherwise it is called nonoverdamped.

Generalizations of the minmax and the maxmin characterizations of the eigenvalues were proved by Duffin [6] for the quadratic case and by Rogers [7] for the general overdamped problems. For the nonoverdamped eigenproblems the natural ordering to call the smallest eigenvalue the first one, the second smallest the second one, etc., is not appropriate. The next theorem is proved in [8], which gives more information about the following minmax characterization for eigenvalues.

Theorem 3.1.1.

Let J be an open interval in ℝ, and let λ) ∈ ℂ^nxn, λ ∈ J, be a family of Hermitian matrices depending continuously on the parameter λ ∈ J, such that the conditions (A) and (B) are satisfied. Then the following statements hold.

1. For every l ∈ ℕ there is at most one lth eigenvalue of T(⋅) which can be characterized by

   $\begin{array}{ll}{\lambda }_l=\underset{V\in H_l,V\cap D_{}\ne \varnothing }{min}\hfill & \underset{v\in V\cap D}{sup}p\left(v\right)\hfill \end{array}$E13

2. If

   $\begin{array}{ll}{\lambda }_l:=\underset{V\in H_l,V\cap D_{}\ne \varnothing }{inf}\hfill & \underset{v\in V\cap D}{sup}p\left(v\right)\in J\text{.}\hfill \end{array}$E360000

   For some l ∈ ℕ then λ _l is the lth eigenvalue of ,T(⋅) in J, and (13) holds.

3. If there exists the kth and lth eigenvalue λ _k and λ _l in J(k < l), then J contains the jth eigenvalue λ _j(k ≤ j ≤ l) as well, and λ _k ≤ λ _j ≤ λ _l.

4. Let λ ₁ = inf_x ∈ Dp(x) ∈ J and λ _l ∈ J. If the minimum in (13) is attained for an l dimensional subspace V, then V ⊃ D ∪ {0}, and (3) can be replaced with

   $\begin{array}{ll}{\lambda }_l=\underset{V\in H_l,V\supset D\cup \left\{0\right\}}{min}\hfill & \underset{v\in V,v\ne 0}{sup}p\left(v\right)\text{.}\hfill \end{array}$E370000

5. $\tilde{\lambda }$ is an lth eigenvalue if and only if μ = 0 is the lth eigenvalue of the linear eigenproblem T(λ)x = μx.

6. The minimum in (3) is attained for the invariant subspace of T(λ_l) corresponding to its lth largest eigenvalues.

Sylvester’s law of inertia has an important role in the nonlinear eigenvalue problems. We will briefly look back to the Sylvester’s law of inertia. With this purpose we define the inertia of the Hermitian matrix T as follows [9].

Definition 3.1.1. The inertia of a Hermitian matrix T is the triplet of nonnegative integers In(T) = (n_p, n_n, n_z) where n_p, n_n and n_z are the number of positive, negative, and zero eigenvalues of T (counting multiplicities).

Next, we consider a case that an extreme eigenvalue λ₁ := inf_x ∈ Dp(x)orλ_n := sup_x ∈ Dp(x) is contained in J.

Theorem 3.1.2 Assume that T : J → ℂ^nxn satisfies the conditions of the minmax characterization, and let (n_p, n_n, n_z) be the inertia of T(σ) for some σ ∈ J.

1. If λ₁ := inf_x ∈ Dp(x) ∈ J, then the nonlinear eigenproblem T(λ)x = 0 has exactly n_p eigenvalues ${\lambda }_1\le \cdots \le {\lambda }_{n_p}$ in J which are less than σ.

2. If sup_x ∈ Dp(x) ∈ J, then the nonlinear eigenproblem T(λ)x = 0 has exactly n_n eigenvalues ${\lambda }_{n-n_n+1}\le \cdots \le {\lambda }_n\text{in}J$ exceeding σ.

We consider the quadratic eigenvalue problem in the label QEP .That is why we adapt to the real scalar equation (11) QEPu. In this way, we get

$$\begin{array}{ll}\mathbf{f}\left(\mathrm{\lambda };\mathbf{x};\mathbf{:=}\right){\mathrm{\lambda }}^2{\mathbf{x}}^H\mathit{A}\mathbf{x}+\mathrm{\lambda }{\mathbf{x}}^H\mathit{B}\mathbf{x}+{\mathbf{x}}^H\mathbf{C}\mathbf{x}=\mathbf{0}\hfill & \mathrm{f}\mathrm{o}\mathrm{r}\mathrm{every}\mathrm{fixed}\mathbf{x}\in {\mathrm{ℂ}}^n,\mathbf{x}\ne \mathbf{0}\hfill \end{array}$$E14

Natural candidates for the Rayleigh functionals of QEPa (Eq. 10) are

$\begin{array}{ll}{p}_{+}\left(\mathbf{x}\right):=-\frac{{\mathbf{x}}^H\mathit{B}\mathbf{x}}{2{\mathbf{x}}^H\mathit{A}\mathbf{x}}+\sqrt{{\left(\frac{{\mathbf{x}}^H\mathit{B}\mathbf{x}}{2{\mathbf{x}}^H\mathit{A}\mathbf{x}}\right)}^2-\frac{{\mathbf{x}}^H\mathit{C}\mathbf{x}}{{\mathbf{x}}^H\mathit{A}\mathbf{x}}}\hfill & \mathrm{and}\hfill \end{array}$E15

$p_{-}\left(\mathbf{x}\right):=-\frac{{\mathbf{x}}^H\mathit{B}\mathbf{x}}{2{\mathbf{x}}^H\mathit{A}\mathbf{x}}-\sqrt{{\left(\frac{{\mathbf{x}}^H\mathit{B}\mathbf{x}}{2{\mathbf{x}}^H\mathit{A}\mathbf{x}}\right)}^2-\frac{{\mathbf{x}}^H\mathit{C}\mathbf{x}}{{\mathbf{x}}^H\mathit{A}\mathbf{x}}}$E16

The Rayleigh functionals are the generalization of the Rayleigh quotient.

In this section we deal with the hyperbolic quadratic pencil as an example overdamped problems and gyroscopically stabilized pencil as an example of the changes that are not.

Now, let us look briefly the hyperbolic quadratic pencil. It is overdamped square pencil given by (10) in which the A = A^H > 0, B = B^H, C = C^H. For hyperbolic quadratic pencil, the following interesting features

The ranges J₊ := p₊(ℂⁿ\{0}) and J₋ := p₋(ℂⁿ\{0}) are disjoint real intervals with max J₋ < min J₊. Q(λ) is the positive definite for λ < min J₋ and λ > max J₊, and it is the negative definite for λ ∈ (max J₋, min J₊).

(Q, J₊) and (−Q, J₋) satisfy the conditions of the variational characterization of the eigenvalues, i.e. there exist 2n eigenvalues[1].

${\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n<{\lambda }_{n+1}\le \cdots \le {\lambda }_{2n}$E17

and

$\begin{array}{lll}{\lambda }_j=\underset{dimV=j}{min}\underset{x\in V,x\ne 0}{max}{p}_{-}\left(\mathbf{x}\right),\hfill & {\lambda }_{n+j}=\underset{dimV=j}{min}\underset{x\in V,x\ne 0}{max}{p}_{+}\left(\mathbf{x}\right),\hfill & j=1,2,\cdots ,n\text{.}\hfill \end{array}$E18

Now we will look at gyroscopically stabilized system in the label GSS. A quadratic polynomial matrix

$\begin{array}{llll}\mathit{Q}\left(\mathit{\lambda }\right)={\lambda }^2\mathit{I}+\lambda \mathit{B}+\mathit{C},\hfill & \mathit{B}={\mathit{B}}^{\mathit{H}},\hfill & det\left(B\right)\ne 0,\hfill & \mathit{C}={\mathit{C}}^{\mathrm{H}}\hfill \end{array}$E19

is gyroscopically stabilized if for some k>0 it holds that

$\left|\mathit{B}\right|>k\mathit{I}+k^{-1}\mathit{C}\text{,}$E20

where denotes the positive square root of B².

Definition 3.1.2. A eigenvalue λ is positive type if applies $\begin{array}{lll}{\mathbf{x}}^{\mathbf{H}}{\mathit{Q}}^{\mathit{\prime }}\left(\mathit{\lambda }\right)\mathbf{x}>0\hfill & \mathbf{x}\in {\mathrm{ℂ}}^n,\hfill & \mathbf{x}\ne \mathbf{0}\hfill \end{array}$

A eigenvalue λ is positive type if applies $\begin{array}{lll}{\mathbf{x}}^{\mathbf{H}}{\mathit{Q}}^{\mathit{\prime }}\left(\mathit{\lambda }\right)\mathbf{x}<0\hfill & \mathbf{x}\in {\mathrm{ℂ}}^n,\hfill & \mathbf{x}\ne \mathbf{0}\hfill \end{array}$

Theorem (Barkwell, Lancaster, Markus 1992)

1. The spectrum of a gyroscopic stabilized pencil is real, i.e. Q is quasi-hyperbolic.

2. All eigenvalues are either of positive type or of negative type

3. If (n_p, n_n, n_z) is the inertia of B, then Q(λ)x  = 0 has 2n_p negative and 2 n_n positive eigenvalues.

4. The 2n_p negative eigenvalues lie in two disjoint intervals, eigenvalues in each; the ones in the left interval are of negative type, the ones in the right interval are of positive type.

5. The 2 n_n negative eigenvalues lie in two disjoint intervals, eigenvalues in each; the ones in the left interval are of negative type, the ones in the right interval are of positive type.

Without loss of generality we will observe only positive eigenvalues value

Let now $p_{+}\left(\mathbf{x}\right):=-\frac{{\mathbf{x}}^H\mathit{B}\mathbf{x}}{2{\mathbf{x}}^H\mathbf{x}}+\sqrt{{\left(\frac{{\mathbf{x}}^H\mathit{B}\mathbf{x}}{2{\mathbf{x}}^H\mathbf{x}}\right)}^2-\frac{{\mathbf{x}}^H\mathit{C}\mathbf{x}}{{\mathbf{x}}^H\mathbf{x}}}$ and $p_{-}\left(\mathbf{x}\right):=-\frac{{\mathbf{x}}^H\mathit{B}\mathbf{x}}{2{\mathbf{x}}^H\mathbf{x}}-\sqrt{{\left(\frac{{\mathbf{x}}^H\mathit{B}\mathbf{x}}{2{\mathbf{x}}^H\mathbf{x}}\right)}^2-\frac{{\mathbf{x}}^H\mathit{C}\mathbf{x}}{{\mathbf{x}}^H\mathbf{x}}}$ functionals appropriate for GSS. With them, we can define the Rayleigh functionals $p_{-}^{+}:=\left\{\begin{array}{c}\hfill p_{-}\left(\mathbf{x}\right)\mathrm{z}\mathrm{a}{p}_{-}\left(\mathbf{x}\right)>0\hfill \\ \hfill 0\mathrm{else}\hfill \end{array}\right.$ i $p_{+}^{+}:=\left\{\begin{array}{c}\hfill p_{+}\left(\mathbf{x}\right)\mathrm{z}\mathrm{a}{p}_{-}\left(\mathbf{x}\right)>0\hfill \\ \hfill 0\mathit{else}\hfill \end{array}\right.$

Voss and Kostić are defined for this function given interval in which the eigenvalues can minmax characterize.

In order to minmax characterized all eigenvalues, we will introduce new Rayleigh functional. It is a new strategy. With this aim we matrices B and C as well as vector x present in the following format :

$\begin{array}{c}\hfill \mathit{B}=\left(\begin{array}{cc}\hfill {\mathit{B}}_1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill -{\mathit{B}}_2\hfill \end{array}\right),{\mathit{B}}_i>0,\left(i=1,2\right)\hfill \\ \hfill \mathit{C}=\left(\begin{array}{cc}\hfill {\mathit{C}}_{11}\hfill & \hfill {\mathit{C}}_{12}\hfill \\ \hfill {\mathit{C}}_{12}^H\hfill & \hfill {\mathit{C}}_{22}\hfill \end{array}\right),{\mathit{C}}_{ii}>0,\left(i=1,2\right)\hfill \\ \hfill \mathbf{x}=\left(\begin{array}{c}\hfill \mathit{z}\hfill \\ \hfill \mathit{y}\hfill \end{array}\right)\ne 0\text{.}\hfill \end{array}$E450000

We define

$\begin{array}{c}\hfill {\mathit{Q}}_1\left(\lambda \right):={\lambda }^2\mathit{I}+\lambda {\mathit{B}}_{\mathbf{1}}+{\mathit{C}}_{\mathbf{11}}\hfill \\ \hfill {\mathit{Q}}_2\left(\lambda \right):={\lambda }^2\mathit{I}-{\lambda }_{\mathit{B}}+{\mathit{C}}_{\mathbf{22}}\hfill \\ \hfill \mathit{T}\left(\lambda \right):={\mathit{Q}}_{\mathbf{2}}\left(\lambda \right)-{\mathit{C}}_{\mathbf{12}}^{\mathit{H}}{\left({\mathit{Q}}_1\left(\lambda \right)\right)}^{-\mathbf{1}}{\mathit{C}}_{\mathbf{12}}\hfill \end{array}$E460000

Because of the conditions (20) are Q₁(λ) I Q₂(λ) are hyperbolic.

We will observe the following problem inherent value

$\mathit{T}\left(\lambda \right)\mathit{y}=0,\mathit{y}\ne 0,\mathbf{y}\in {\mathrm{ℂ}}^{n-n_p},\mathbf{y}\ne \mathbf{0}$E470000

Applies following theorem

Theorem 3.1.3 λ is eigenvalue Q(⋅) if and only if λ is eigenvalue T(⋅)

Proof

$\begin{array}{c}\hfill \mathit{Q}\left(\lambda \right)\mathbf{x}=\mathbf{0}\iff \left(\begin{array}{cc}\hfill {\mathit{Q}}_1\left(\lambda \right)\hfill & \hfill {\mathit{C}}_{12}\hfill \\ \hfill {\mathit{C}}_{12}^H\hfill & \hfill {\mathit{Q}}_2\left(\lambda \right)\hfill \end{array}\right)\mathbf{x}=\mathbf{0}\iff \left(\begin{array}{cc}\hfill {\mathit{Q}}_1\left(\lambda \right)\hfill & \hfill {\mathit{C}}_{12}\hfill \\ \hfill {\mathit{C}}_{12}^H\hfill & \hfill {\mathit{Q}}_2\left(\lambda \right)\hfill \end{array}\right)\left(\begin{array}{c}\hfill \mathbf{z}\hfill \\ \hfill \mathbf{y}\hfill \end{array}\right)=\mathbf{0}\hfill \\ \hfill \iff \left(\begin{array}{c}\hfill {\mathit{Q}}_1\left(\lambda \right)\mathit{z}+{\mathit{C}}_{12}\mathit{y}\hfill \\ \hfill {\mathit{C}}_{12}^H\mathbf{z}+{\mathit{Q}}_2\left(\lambda \right)\mathbf{y}\hfill \end{array}\right)=\left(\begin{array}{c}\hfill \mathbf{0}\hfill \\ \hfill \mathbf{0}\hfill \end{array}\right)\iff \left({\mathit{Q}}_1\left(\lambda \right)\mathit{z}+{\mathit{C}}_{12}\mathit{y}=\mathbf{0}\wedge {\mathit{C}}_{12}^H\mathbf{z}+{\mathit{Q}}_2\left(\lambda \right)\mathbf{y}=\mathbf{0}\right)\hfill \\ \hfill \iff \left(\mathit{z}=-{\left({\mathit{Q}}_1\left(\lambda \right)\right)}^{-1}\mathit{y}\wedge \left({\mathit{Q}}_2\left(\lambda \right)-{\mathit{C}}_{12}^{\mathit{H}}{\left({\mathit{Q}}_1\left(\lambda \right)\right)}^{-1}{\mathit{C}}_{12}\right)\mathbf{y}=\mathbf{0}\right)\hfill \\ \hfill \iff \left(\mathit{z}=-{\left({\mathit{Q}}_1\left(\lambda \right)\right)}^{-1}\mathit{y}\wedge \mathit{T}\left(\lambda \right)\mathbf{y}=0\right)\text{.}\hfill \end{array}$ E480000

Theorem is proved.

Analogous to the (14) we defined the following functions

$\begin{array}{lll}q\left(\lambda ;\mathbf{y}\right):={\mathbf{y}}^{\mathbf{H}}\mathit{T}\left(\lambda \right)\mathbf{y}\hfill & \mathrm{and}\hfill & f_2\left(\lambda ;\mathbf{y}\right):={\mathbf{y}}^{\mathbf{H}}{\mathit{Q}}_2\left(\lambda \right)\mathbf{y}\hfill \end{array}$E490000

In the following theorem we give information about the properties q(λ; y)

Theorem 3.1.4. Function q(λ; y) has the following characteristics

1. For each vector q(0; y) > 0

2. For λ>0 a function q(λ; y) exactly two zeros for each vector y. Minimum zero function q(λ; y) and is lower than the minimum zero function f₂(λ; y) and the largest zero function q(λ; y) is greater than the maximum zero function f₂(λ; y)

3. From $f_2^{\prime }\left(\lambda ;\mathbf{y}\right)>0i\lambda >0$ follow q′(λ; y)

Proof

1. Because C > 0 we have

   $\left(-\begin{array}{cc}\hfill {\mathbf{y}}^H{\mathit{C}}_{12}^H{\left({\mathit{C}}_{11}\right)}^{-1}\hfill & \hfill {\mathbf{y}}^H\hfill \end{array}\right)\cdot \left(\begin{array}{cc}\hfill {\mathit{C}}_{11}\hfill & \hfill {\mathit{C}}_{12}\hfill \\ \hfill {\mathit{C}}_{12}^H\hfill & \hfill {\mathit{C}}_{22}\hfill \end{array}\right)\cdot \left(\begin{array}{c}\hfill -{\left({\mathit{C}}_{11}\right)}^{-1}{\mathit{C}}_{12}\mathbf{y}\hfill \\ \hfill \mathbf{y}\hfill \end{array}\right)>0\text{.}$ E500000

   It follows

   $\left(-\begin{array}{cc}\hfill {\mathbf{y}}^H{\mathit{C}}_{12}^H{\left({\mathit{C}}_{11}\right)}^{-1}\hfill & \hfill {\mathbf{y}}^H\hfill \end{array}\right)\cdot \left(\begin{array}{c}\hfill \mathbf{0}\hfill \\ \hfill {\mathit{C}}_{22}\mathbf{y}-{\mathit{C}}_{12}^H{\left({\mathit{C}}_{11}\right)}^{-1}{\mathit{C}}_{12}\mathbf{y}\hfill \end{array}\right)>0\text{.}$E510000

   then

   $q\left(0;\mathbf{y}\right)={\mathbf{y}}^H\left({\mathit{C}}_{22}-{\mathit{C}}_{12}^H{\left({\mathit{C}}_{11}\right)}^{-1}{\mathit{C}}_{12}\right)\mathbf{y}>0$E520000

2. We have already mentioned that Q₂(λ) is hyperbolic. This means that the function f₂(λ; y) for each vector y has two different real roots. For λ > 0 ist Q₁(λ) > 0. Therefore, applies

   $q\left(\lambda ;\mathbf{y}\right)<{\mathbf{y}}^H{\mathit{Q}}_2\left(\lambda \right)\mathbf{y}-\underset{>0}{\underbrace{{\mathbf{y}}^H{\mathit{C}}_{12}^{\mathit{H}}{\left({\mathit{Q}}_1\left(\lambda \right)\right)}^{-1}{\mathit{C}}_{12}\mathit{y}}}$E530000
   $<{\mathbf{y}}^H{\mathit{Q}}_{\mathbf{2}}\left(\lambda \right)\mathbf{y}=f_2\left(\lambda ;\mathbf{y}\right)$E21

   Of further

   $\underset{\lambda \to +\infty }{lim}q\left(\lambda ;\mathbf{y}\right)=+\infty$E22

   Of (a) and because (21) and (22) follows that the function q(λ; y) for λ>0 has two zero. Minimum zero function q(λ; y) a and is lower than the minimum zero function f₂(λ; y) and the largest zero function q(λ; y) b is greater than the maximum zero function f₂(λ; y)

3. $q^{\prime }\left(\lambda ;y\right)=2\lambda y^{H}y-y^H{B}_{2}y+\underset{>0}{\underbrace{y^H{C}_{12}^H{\left(Q_1\left(\lambda \right)\right)}^{-1}{C}_{12}y}}$

   Theorem is proved.

   Define a new functional

Definition 3.1.3. Let q(a, y) = q(b, y) = 0 and 0 < a < b. We define two new functional

$\begin{array}{c}\hfill t_{-}\left(y\right)=a\hfill \\ \hfill t_{+}\left(y\right)=b\hfill \\ \hfill W_{\pm }:=t_{\pm }\left(h\right)\hfill \end{array}$E560000

Theorem 3.1.5. Applies maxW₋ < minW₊

Proof

$\begin{array}{c}\hfill p_{2\pm }\left(\mathbf{x}\right):=-\frac{{\mathbf{x}}^H{\mathit{B}}_2\mathbf{x}}{2{\mathbf{x}}^H\mathbf{x}}\pm \sqrt{{\left(\frac{{\mathbf{x}}^H{\mathit{B}}_2\mathbf{x}}{2{\mathbf{x}}^H\mathbf{x}}\right)}^2-\frac{{\mathbf{x}}^H{\mathit{C}}_2\mathbf{x}}{{\mathbf{x}}^H\mathbf{x}}}\hfill \\ \hfill J_{\pm }:=p_{2\pm }\left({\mathrm{ℂ}}^{n-n_p}\backslash \left\{\mathbf{0}\right\}\right).\hfill \\ \hfill \mathit{max}{J}_{-}<\mathit{min}{J}_{+\text{,}}\hfill \end{array}$ E570000

Because Q₂(λ) is hyperbolic.

$t_{-}\left(y\right)<\mathit{max}{J}_{-}<\mathit{min}{J}_{+}<t_{+}\left(y\right),\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{every}\mathbf{y}\in {\mathrm{ℂ}}^{n-n_p}\backslash \left\{\mathbf{0}\right\}$E580000

$\Rightarrow \mathit{max}{W}_{-}<\mathit{max}{J}_{-}<\mathit{min}{J}_{+}<\mathit{max}{W}_{+}$E590000

Theorem is proved.

Theorem 3.1.6. All the positive eigenvalues of (19) are either the value of the MinMax of t₋(y) or Maxmin of t₊(y)

3.2. Linearization

In this section we will deal with linearization. As mentioned linearization is standard procedure for reducing QEP on GEP with a view to facilitate the computation of eigenvalues. We have already seen that the problem of eigenvalues usually come as a result of solving differential equations or systems of differential equations. That is the basic idea of linearization came in the field of differential equations where the order of the differential equation of the second order can be lowered by introducing a system of two partial differential equations of the first order with two unknown functions.

The basic idea of linearization in QEPa is the introduction of shift z = λx u

$$\left({\lambda }^2\mathit{A}+\lambda \mathit{B}+\mathit{C}\right)\mathit{x}=0\text{.}$$E600000

Then we get

1. λAz + Bz + Cx = 0 or

2. λAz + λBx + Cx = 0.

The resulting equations are GEP because they can be written respectively in the form of

1. $\left(\begin{array}{cc}\hfill -\mathit{B}\hfill & \hfill -\mathit{C}\hfill \\ \hfill \mathit{I}\hfill & \hfill \mathit{O}\hfill \end{array}\right)\left(\begin{array}{c}\hfill \mathbf{z}\hfill \\ \hfill \mathbf{x}\hfill \end{array}\right)=\lambda \left(\begin{array}{cc}\hfill \mathit{A}\hfill & \hfill \mathit{O}\hfill \\ \hfill \mathit{O}\hfill & \hfill \mathit{I}\hfill \end{array}\right)\left(\begin{array}{c}\hfill \mathbf{z}\hfill \\ \hfill \mathbf{x}\hfill \end{array}\right)$

2. $\left(\begin{array}{cc}\hfill \mathit{O}\hfill & \hfill \mathit{C}\hfill \\ \hfill \mathit{I}\hfill & \hfill \mathit{O}\hfill \end{array}\right)\left(\begin{array}{c}\hfill \mathbf{z}\hfill \\ \hfill \mathbf{x}\hfill \end{array}\right)=\lambda \left(\begin{array}{cc}\hfill \mathit{A}\hfill & \hfill \mathit{B}\hfill \\ \hfill \mathit{O}\hfill & \hfill \mathit{I}\hfill \end{array}\right)\left(\begin{array}{c}\hfill \mathbf{z}\hfill \\ \hfill \mathbf{x}\hfill \end{array}\right)$.

Since the corresponding GEPs all matrices 2n × 2n to GEP has 2n eigenvalue and therefore appropriate QEP has also 2n eigenvalue. From the above it is clear that linearization is not unambiguous. However, in the choice of linearization QEP is an important factor to maintain symmetry and some spectral properties QEP if it is possible. The application of linearization will be will in the next chapter.

3.3. Physical Background

We look now at the application of eigenvalues of quadratic problems in engineering. The largest review of applications QEP is in the [10].We have already mentioned in the introduction to eigenvalue problem arises in connection with differential equations or systems of differential equations. In structural mechanics the most commonly are used differential equations and therefore the problem of eigenvalues. Note that the ultimate goal is to determine the effect of vibrations on the performance and reliability of the system, and to control these effects.

We will now demonstrate the linearization of QEP on a concrete example from the engineering. Low vibration system on n unknowns are described by the following system of differential equations

$\mathit{M}\ddot{\mathbf{y}}+\mathit{C}\stackrel{.}{\mathbf{y}}+\mathit{K}\mathbf{y}=\mathbf{0}\text{,}$E23

where M is mass matrix, C is viscous damping matrix, and K is the stiffness matrix thus Because of the conditions in physics M and K are related to the kinetic and strain energy, respectively, by a quadratic form which makes them symmetric. For most structures M and K are positive definite and space.

The introduction of shift y = xe^λ after rearrangement, we get

$\left({\mathrm{\lambda }}^2\mathit{M}+\mathrm{\lambda }\mathit{C}+\mathit{K}\right)\mathbf{x}{\mathrm{e}}^{\mathrm{\lambda }}=0$E620000

Respectively

$\left({\mathrm{\lambda }}^2\mathit{M}+\mathrm{\lambda }\mathit{C}+\mathit{K}\right)\mathbf{x}=0$E24

Therefore, the system (23) has a nontrivial solution y is selected, such that λ that QEP (24) has a nontrivial solution x.

Now we’re going to QED (24) apply linearization method presented in section 3.2. Thus we have the appropriate GEP

$\left(\begin{array}{cc}\hfill -\mathit{C}\hfill & \hfill -\mathit{K}\hfill \\ \hfill \mathit{I}\hfill & \hfill \mathit{O}\hfill \end{array}\right)\left(\begin{array}{c}\hfill \mathbf{z}\hfill \\ \hfill \mathbf{x}\hfill \end{array}\right)=\lambda \left(\begin{array}{cc}\hfill \mathit{M}\hfill & \hfill \mathit{O}\hfill \\ \hfill \mathit{O}\hfill & \hfill \mathit{I}\hfill \end{array}\right)\left(\begin{array}{c}\hfill \mathbf{z}\hfill \\ \hfill \mathbf{x}\hfill \end{array}\right)\text{.}$E640000

When the system is undamped (C=O) we get

$\mathrm{\omega }\mathit{M}\mathbf{x}:={\mathrm{\lambda }}^2\mathit{M}\mathbf{x}=\mathit{K}\mathbf{x}=0\text{.}$E650000

Because the most common matrix M and K are symmetric, positive definite and space obtained GEP is easy to solve.

4. Conclusion

Because of the great practical application eigenvalue problem occupies an important place in linear algebra. In this chapter, we discussed the linear and quadratic eigenvalues. In particular, an emphasis is on numerical methods such as the QR algorithm, Rayleigh quotient iteration for linear problems of eigenvalues and linearization and minmax characterization of quadratic problems eigenvalues. The whole chapter shows that the structure of the matrix, participating in the problem of eigenvalues, strongly influence the choice of the method itself. It is also clear that using the features of the structure matrix can do much more effectively existing algorithms. Thus, further studies are going to increase of use feature matrix involved in the problem of eigenvalues, with the aim of improving the effectiveness of the method. Finally, we point out that in this chapter we introduced new Rayleigh functionals for gyroscopically stabilized system that enables complete minmax (maxmin) characterization of eigenvalues. It’s a new strategy. We have proved all relevant features of new Rayleigh functionals.