Документ взят из кэша поисковой машины. Адрес оригинального документа : http://mailybaev.imec.msu.ru/papers/Mailybaev2001b.pdf
Дата изменения: Thu Jun 30 14:11:07 2005
Дата индексирования: Mon Oct 1 19:39:10 2012
Кодировка:

Doklady Mathematics, Vol. 64, No. 1, 2001, pp. 3640. Translated from Doklady Akademii Nauk, Vol. 379, No. 2, 2001, pp. 165169. Original Russian Text Copyright © 2001 by Mailybaev. English Translation Copyright © 2001 by MAIK "Nauka / Interperiodica" (Russia).

MATHEMATICS

Evaluation of Multiple Eigenvalues and Jordan Chains of Vectors for Matrices Depending on Parameters
A. A. Mailybaev
Presented by Academician N.S. Bakhvalov April 5, 2001 Received April 6, 2001

The reduction of a matrix to the Jordan form is an unstable operation if the matrix has multiple eigenvalues. We can make all eigenvalues simple by an arbitrarily small variation of the matrix. However, multiple eigenvalues are unremovable when we consider families of matrices smoothly depending on parameters, and they play an important role in problems of stability and optimization of eigenvalues [13]. Arnol'd [4, 5] obtained local normal forms of families of complex matrices (versal deformations) and applied them to a qualitative study of bifurcation diagrams (sets of parameter values corresponding to matrices with multiple eigenvalues). In this paper, we apply the theory of versal deformations to obtain explicit formulas that make it possible to find multiple eigenvalues and the corresponding Jordan chains of vectors for complex and real families of matrices under the conditions of precise calculations. In numerical calculations with the use of standard procedures, it is necessary to take into account that round-off errors can sometimes lead to large errors in evaluation of simple eigenvalues used in formulas. In this paper, we consider the case of multiple eigenvalues that correspond to a single Jordan chain of vectors (one Jordan block). The eigenvalues of this form are most typical [4, 5]. Many authors considered the problem of evaluating multiple eigenvalues of matrices (see, e.g., [69]). However, the methods described in the literature do not apply to matrices depending on parameters; in addition, the formulas of this paper give more complete information about multiple eigenvalues. 1. Consider a complex m в m matrix A analytically depending on a vector p = (p1, p2 , ..., pn ) of complex parameters. By d, we denote the set of values of the parameter vector p such that the matrix A(p) has an eigenvalue of algebraic multiplicity d corresponding to a single Jordan chain of vectors (single Jordan block)

and the other eigenvalues are simple. In the case of general position, the set d (stratum) is a smooth manifold of codimension d 1 [4]. Let p' d be a point in this manifold. By ', we denote a multiple eigenvalue of the matrix A' = A(p'), and by u '1 , u '2 , ..., u 'd , the corresponding Jordan chain of vectors satisfying the equations A ' u '1 = ' u '1 , A ' u '2 = ' u '2 + u '1 ,
1

' ' ... , A ' u d = ' u d + u 'd

.

(1)

For convenience, we represent the Jordan chain as the m в d matrix U' = [ u '1 , u '2 , ..., u 'd ]. Let p0 be a point in the parameter space lying in the vicinity of the set d. In the case of general position, the matrix A0 = A(p0 ) has only simple eigenvalues. By 1, 2, ..., d, we denote the eigenvalues of A0 transforming into the multiple eigenvalue ' as p0 p' d. Let ui and vi be the right and left eigenvectors corresponding to i, i.e., satisfying the equations A0 ui = i ui , the last the m в ..., vd ] defined vi A0 = i vi ,
T T

v i u i = 1;

T

(2)

relation is a normalization condition. Consider d matrices U = [u1, u2 , ..., ud ] and V = [v1, v2 , and the row-vectors ni and n of dimension n as

T A T A T A n i = v i ------- u i, v i ------- u i, ..., v i ------- u i , p1 p2 pn

i = 1, 2, ..., d ,

n=

i=1

d

n ---i , d

(3)

Institute of Mechanics, Moscow State University, Michurinskii pr. 1, Moscow, 117192 Russia e-mail: mailybaev@imec.msu.ru 36

where the derivatives are evaluated at the point p0 . Let us also introduce the d в d matrices K = diag (k1, k2 , ..., kd ), R, S = R1, and Y with components ki , rij , sij , and yij , where

EVALUATION OF MULTIPLE EIGENVALUES AND JORDAN CHAINS OF VECTORS

37

u1 u1 k i = --------------- , T ( ui u1 ) µ j = j 0 ,
0

T

r ij = µ

i1 j

,

y ij = s id µ j ,
d

p0

d

1 + 2 + ... + d 0 = ---------------------------------------d

(4)

p'min
Fig. 1.

(here, µ j = 1 if µj is zero). Note that determining the vectors and matrices defined by (3) and (4) only requires an information on the family A(p) at the point p0 . Having this information, we can evaluate in the first approximation [accurate to O(||p0 p'||2 )] the set d near the point p0 , the multiple eigenvalue, and the corresponding Jordan chain at the points of the stratum d with the use of the formulas given by the following theorem. Theorem 1. Let 1, 2 , ..., d be simple eigenvalues of the matrix A0. Then, the first approximation of the stratum d for which 1, 2 , ..., d form a multiple eigenvalue ' is determined by the following system of d 1 linear equations in p: q j + q j ( p p0 ) = 0 ,
0 T

be obtained from a family A'(q) of special form (versal deformation) by a smooth change of the basis and a smooth change q = q(p) of the parameters. The stratum d is determined by the equations q1 = q2 = ... = qd 1 = 0, where qi are the parameters of the versal deformation selected in a special way. Using linear approximations of the functions qi (p) at the point p0 , we obtain system of equations (5), where q i = qi (p0 ) and qi is the gradient (row-vector) evaluated at p = p0 . Equations (5) specify a plane in the parameter space; this plane is the first approximation of the stratum d in a neighbor0 hood of the point p0 (Fig. 1). The values of q i and qi , as well as the values of ' and U', are determined by analyzing the relations between the family A(p) and the versal deformation at the point p0 . Let us write system (5) in the matrix form
0

j = 1, 2, ..., d 1,

qj =

0

i=1

d

s ij µ i ,
d

q j =

i=1

d

s ij ( n i n ) ----------------------- . s id

(5)

The first approximations of the multiple eigenvalue ' and of the corresponding Jordan chain U' = [ u '1 , u '2 , ..., u 'd ] at the points of stratum (5) are determined by the relations ' = 0 + , = n ( p p 0 ) ,
T

q q x= q
0 1

···
d1

Q ( p p0 ) = x ,
T

q Q=

1

, (8)

(6)

U ' = ( U ( K + K ' ) + [ w 1, w 2, ..., w d ] ) S , w i = ( A 0 i I v i v i ) ( UKY + UK AUK ) , K ' = diag ( k '1, k '2, ..., k 'd ) , S T k 'i = v i [ w 1, w 2, ..., w d ] -------- , s id A =
d T 1 i

(7)

where Q is a (d 1) в n matrix and x is dimension d 1. Corollary 1. Under the conditions of ' the value of the vector p min d nearest respect to the Euclidean norm) in the first tion has the form
T T p 'min = p 0 + x ( QQ ) Q . d d d 1

···
0 d1

,

a vector of Theorem 1, to p0 (with approxima(9)

i=1

n

A ------ ( p i p 0 i ) , pi Sd

where all derivatives are evaluated at p = p0 , denotes the dth column of the matrix S and I is the identity matrix. Theorem 1 makes it possible to examine the structure of the stratum d and determine multiple eigenvalues and Jordan chains at the points of the stratum based on the information at the point p0 , where the matrix has only simple eigenvalues. To derive relations (5)(7), we have used the theory of versal deformations [4], according to which a family of matrices A(p) in a neighborhood of the point p' can
DOKLADY MATHEMATICS Vol. 64 No. 1 2001

Consider the stratum 1 1 2 2 ... s s consisting of the values of p at which the matrix A(p) has s different multiple eigenvalues '1 , '2 , ... 's , and each eigenvalue 'i corresponds to a single Jordan chain of length di . The stratum 1 1 2 2 ... s s is the transversal intersection of the strata i with i = 1, 2, ..., s [4]. Corollary 2. Let p0 be a point in the parameter space at which the matrix A0 has only simple eigenvalues. Then the first approximation of the stratum
d d d d

38 p 8 2 4 0 4 3 0 4 2 8 p1
2

MAILYBAEV

K ' = diag ( k '1, k '2, ..., k 'd ) , S T k 'i = v i [ w 1, w 2, ..., w d ] -------- . s id Corollary 3. Under the conditions of Theorem 2, the matrix A 'min d nearest to A0 (with respect to the Euclidean norm ||·||E) in the first approximation has the form
d1 d

Fig. 2.

A 'min = A 0 +

Q j y j,

y = P x,

1

(14)

j=1

1 1 2 2 ... s s in a neighborhood of p0 is the intersection of planes (5) for all multiple eigenvalues. The multiple eigenvalues and the corresponding Jordan chains at the points of stratum are defined by relations (6), (7) for every i' . 2. Consider the stratum d in the space of all complex m в m matrices. Every matrix element can be treated as an independent parameter. Replacing the parameter vector p by a matrix A and taking into account that the derivative of a matrix with respect to a parameter contains only one nonzero element, which equals 1, we obtain the following assertion from Theorem 1 and Corollary 1. Theorem 2. Let 1, 2 , ..., d be simple eigenvalues of the matrix A0 . Then, in the space of complex matrices, the first approximation of the stratum d for which 1, 2 , ..., d form a multiple eigenvalue ' is determined by the following system of d 1 linear equations in A: q j + tr ( Q j ( A A 0 ) ) = 0 ,
0 T

d

d

d

where P is the (d 1) в (d 1) matrix with the elements T pij = tr( Q i Q j ), and x and y are vectors-columns of dimension d 1 with the components xj = q j and yj, respectively. Note that, according to Theorem 2, determining the stratum d in a neighborhood of the matrix A0 , the multiple eigenvalue, and the corresponding Jordan chain only involves the simple eigenvalues and eigenvectors of the matrix A0 . 3. Consider a real matrix A smoothly depending on a vector p of real parameters. In this case, we should distinguish between real and complex multiple eigenvalues '. The corresponding strata in the parameter space are denoted by d and ( ± i)d and have codimensions d 1 and 2(d 1), respectively [4]. Theorems 1 and 2 can be extended to the case of the stratum ( ± i)d. In this case, relations (5) and (10) determine systems of 2(d 1) linear equations (each equality determines two equations for the real and imaginary parts). The eigenvalues 1, 2 , ..., d of the matrix A0, which transform into a multiple complex eigenvalue ' as p0 p' ( ± i)d, should have imaginary parts of the same sign [this is so at the points p0 sufficiently close to ( ± i)d]. In the case of the stratum d, Theorems 1 and 2 are valid if the constants ki that determine the diagonal elements of matrix K have the form 1 k i = --------------- , T ( ui u ' ) u1 u ' = Re --------------- . u T u 1 1 (15)
0

j = 1, 2, ..., d 1,

qj =

0

i=1

d

s ij µ i ,
d

Qj =

i=1 d

d

s ij ( N i N ) ------------------------- , s id

(10)

where tr (A) is the trace of the matrix A, and Ni and N are the following m в m matrices: Ni = vi u ,
T i

N=

i=1

N ----i . d

(11)

The first approximation of the multiple eigenvalue ' and the corresponding Jordan chain U' are determined at the points of stratum (10) by the relations ' = 0 + , = tr ( N ( A A 0 ) ) ,
T

(12)

U ' = ( U ( K + K ' ) + [ w 1, w 2, ..., w d ] ) S , wi = ( A0 i I vi vi )
T 1 i

в ( UKY + UK ( A A 0 ) UK ) ,

(13)

Relations (5) and (10) with conditions (15) taken into account determine systems of d 1 real linear equations, and relations (6), (7), (11), and (12) determine the real values ' and U'. The eigenvalues 1, 2, ..., d of the matrix A0 , which transform into a multiple real eigenvalue ' as p0 p' d, must be real or complex conjugate. 4. As an example, consider the two-parameter family of real matrices
DOKLADY MATHEMATICS Vol. 64 No. 1 2001

EVALUATION OF MULTIPLE EIGENVALUES AND JORDAN CHAINS OF VECTORS

39

130 A ( p ) = p1 1 p2 231

,

p 'min = ( 0, 9 ) , p = ( p 1, p 2 ) . (16)

' = 2 , (20)

By Theorem 1, the equation of the stratum 2 in the first approximation has the form q1 + q1 ( p p0 ) = 0 ,
0 T

0.7044 0.1494 [ u '1, u '2 ] = 0.7044 0.0854 . 0.2348 0.1067

(17)

2 0 where q 1 = µ2, q1 = µ(n2 n1 ), and µ = ---------------1 . The 2 vector p 'min 2 nearest to p0 is determined by Corollary 1 in the form q1 p 'min = p 0 ------------------- q 1 . T q1 q1
0

Comparing (19) and (20), we see that the approximate values obtained with the use of Theorem 1 differ from the exact values only by the fourth digit. 5. Consider the stratum 4 in the space of real matrices. Take a 10 в 10 Jordan matrix Ad 4 with simple eigenvalues = 4, 3, 2, 1, 0, 4 and the Jordan 4 в 4 block with eigenvalue = 2. Consider the following perturbations of the matrix Ad: A0 = Ad + D , where D is a real 10 в 10 matrix whose elements are independent random variables with zero expectation and variance 2 = 4 в 104 (||D||E ~ 0.2). Taking as 1, 2, 3, 4 the simple eigenvalues of the matrix A0 nearest to = 2, we find the nearest real matrix A 'min 4 ' and the distance || A min A0 ||E from A0 to the stratum 4 by (10), (14). The mean value of the square of this distance obtained by numerical computations over 1000 random matrices D is 1.193 в 103. Since the stra2 tum 4 has codimension 3, the expectation of ||Dn || E , where Dn is the component of the perturbation matrix D normal to 4, equals 32 = 1.2 в 103; this agrees well with the numerical calculations. Thus, the approximate formulas given by Theorems 1 and 2 make it possible to effectively analyze multiple eigenvalues corresponding to a single Jordan chain in the case of complex and real families of matrices. These formulas only involve the derivatives of the matrix A(p) with respect to the parameters at the point p0 and the simple eigenvalues and the corresponding eigenvectors of the matrix A0 . This information can easily be obtained with the use of standard programs for calculating eigenvalues of matrices; this makes the approach suggested constructive and applicable to numerical computations. ACKNOWLEDGMENTS The author thanks A.P. Seiranyan, who has drawn the author's attention to this problem.

(18)

Figure 2 shows the bifurcation diagram (the strata 2 and 3) in the parameter space. The arrows denote the vectors p 'min p0 , where p0 are various values of the parameter vector and p 'min are the nearest points of the stratum 2 found approximately by (18). In calculations, 1 and 2 were set to be equal to complex conjugate eigenvalues of the matrix A0 . If the matrix A0 had three real eigenvalues, then all the three possible pairs 1, 2 were considered, and the nearest vector p 'min was selected among the three obtained vectors (every time, the value p 'min at which the given pair of eigenvalues formed a double eigenvalue ' was determined). It is seen from Fig. 2 that formula (18) gave a good approximation of the nearest vector p 'min 2 for the points p0 considered. Consider the point p0 = (0.3, 9.1) at which the matrix A0 has eigenvalues 1 = 2.624, 2 = 1.472, and 3 = 7.096. Calculations by formula (18) show that the pair 1, 2 gives the nearest value p 'min = ( 0.0008, 8.9990) 2. The multiple eigenvalue ' and the Jordan chain (the eigenvector u '1 and the associated vector u '2 ) evaluated at the point p = p 'min by approximate formulas (6) and (7) have the form ' = 2.00006 , 0.7044 0.1496 U ' = [ u '1, u '2 ] = 0.7044 0.0852 . 0.2346 0.1067 (19)

REFERENCES
1. Mailybaev, A.A. and Seyranian, A.P., SIAM J. Matrix Anal. Appl., 2000, vol. 21, no. 1, pp. 106128. 2. Mailybaev, A.A. and Seiranyan, A.P., Prikl. Mat. Mekh., no. 6, pp. 947962.

' For comparison, we give the exact values of p min , ', and U':
DOKLADY MATHEMATICS Vol. 64 No. 1 2001

40

MAILYBAEV
° 7. K agstrЖm, B. and Ruhe, A., ACM Trans. Math. Software, 1980, vol. 6, pp. 398419.

3. Lewis, A.S. and Overton, M.L., Acta Numerica, 1996, vol. 5, pp. 149190. 4. Arnol'd, V.I., Usp. Mat. Nauk, 1971, vol. 26, no. 2, pp. 101114. 5. Arnol'd, V.I., Dopolnitel'nye glavy teorii obyknovennykh differentsial'nykh uravnenii (Additional Chapters of the Theory of Ordinary Differential Equations), Moscow: Nauka, 1978. 6. Voevodin, V.V. and Kuznetsov, Yu.A., Matritsy i vychisleniya (Matrices and Calculations), Moscow: Nauka, 1984.

8. Fairgrieve, T.F., The Application of Singularity Theory to the Computation of Jordan Canonical Form, M.Sc. Thesis, Toronto: Department of Computer Science, Univ. of Toronto, 1986. 9. Lippert, R. and Edelman, A., Advances in Computational Mathematics, Lect. Notes Pure Appl. Math., vol. 202, New York: Marcel Dekker, 1999.

DOKLADY MATHEMATICS

Vol. 64

No. 1

2001