Singular Matrix Pencils and the QZ Algorithm - Cleve Moler on Mathematics and Computing
 

This year, 2023, is the 50-th anniversary of the QZ algorithm for generalized matrix eignenvalue problems,

Ax = λBxThe algorithm computes these eigevalues without inverting either A or B. And, the QZ-algorithm can help detect and analyze exceptional situaions known as [I]singular pencils[/I].

[B]Contents[/B]
[LIST][*][URL="https://www.labfans.com/bbs/#19d0dd38-a456-4a63-bf2f-18e02689531d"]Matrix pencils[/URL][*][URL="https://www.labfans.com/bbs/#31c19b00-cfd8-493d-b712-08610ce3c5aa"]Example[/URL][*][URL="https://www.labfans.com/bbs/#0f5d9fb9-0792-4d4c-a9ac-c5fd3e1e7691"]Wilkinson example[/URL][*][URL="https://www.labfans.com/bbs/#cbe4eaf1-8a19-41e7-badd-1b8e69f74b61"]References[/URL][/LIST][B]Matrix pencils[/B]

If A and B are two square matrices, the [I]linear matrix pencil[/I] is the matrix-valued function

A - λBA pencil is [I]regular[/I] if there is at least one value of λ for which A - λB if not singular. The pencil is [I]singular[/I] if both A and B are singular and, moreover, A - λB is singular for all λ. In other words,

det(A - λB) = 0 for all λ.Singular pencils are more insiduous than migt appear at first glance.

[B]Example[/B]

A = [9 8 7; 6 5 4; 3 2 1] B = [7 9 8; 4 6 5; 1 3 2]A = 9 8 7 6 5 4 3 2 1B = 7 9 8 4 6 5 1 3 2 syms s AB = A - s*B d = det(AB) AB = [9 - 7*s, 8 - 9*s, 7 - 8*s][6 - 4*s, 5 - 6*s, 4 - 5*s][ 3 - s, 2 - 3*s, 1 - 2*s] d = 0 eig1 = eig(A,B) eig2 = 1./eig(B,A) [QAZ,QBZ,Q,Z,V,W] = qz(A,B); QAZ, QBZeig1 = -0.4071 1.0000 0.2439eig2 = -2.0000 1.0000 0.3536QAZ = -1.0298 -13.0363 7.7455 0 5.6991 -4.6389 0 0 0.0000QBZ = 2.4396 -11.4948 9.6394 0 5.6991 -4.6389 0 0 0.0000 eig3 = eig(A',B') eig4 = 1./eig(B',A') [QATZ,QBTZ,Q,Z,V,W] = qz(A',B'); QATZ, QBTZeig3 = -0.2169 Inf 1.0000eig4 = -0.0738 0 1.0000QATZ = -0.0000 -15.0218 6.8390 0 2.6729 -2.2533 0 0 0.5922QBTZ = 0.0000 -15.2578 7.1280 0 0 1.0203 0 0 0.5922[B]Wilkinson example[/B]

clear A = [4 3 2 5; 6 4 2 7; -1 -1 -2 -2; 5 3 2 6] B = [2 1 3 4; 3 3 3 5; 0 0 -3 -2; 3 1 3 5]A = 4 3 2 5 6 4 2 7 -1 -1 -2 -2 5 3 2 6B = 2 1 3 4 3 3 3 5 0 0 -3 -2 3 1 3 5 syms s AB = A - s*B d = det(AB) AB = [4 - 2*s, 3 - s, 2 - 3*s, 5 - 4*s][6 - 3*s, 4 - 3*s, 2 - 3*s, 7 - 5*s][ -1, -1, 3*s - 2, 2*s - 2][5 - 3*s, 3 - s, 2 - 3*s, 6 - 5*s] d = 0 eig1 = eig(A,B) eig2 = 1./eig(B,A) [QAZ,QBZ,Q,Z,V,W] = qz(A,B); QAZ, QBZeig1 = 1.2056 0.7055 -1.0000 -Infeig2 = 1.5097 0.6408 0 -1.0000QAZ = 0.7437 4.1769 -12.7279 -5.5000 0 0.0000 5.2328 2.1602 0 0 0.7857 0.0123 0 0 0 -0.2887QBZ = 0.5005 6.6143 -8.4853 -2.5000 0 0.0000 3.2668 2.0105 0 0 1.1525 -0.7904 0 0 0 0.2887 eig3 = eig(A',B') eig4 = 1./eig(B',A') [QATZ,QBTZ,Q,Z,V,W] = qz(A',B'); QATZ, QBTZeig3 = -0.2141 + 0.2033i -0.2141 - 0.2033i 0.7013 + 0.0000i 1.4508 + 0.0000ieig4 = 0.3168 0.9823 1.2325 0QATZ = 0.1281 - 0.2434i 0.2665 + 0.0169i 0.2663 + 1.4905i 0.3721 + 3.5350i 0.0000 + 0.0000i 0.0587 + 0.1116i 5.2603 - 1.6197i 12.7878 - 4.0110i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 4.1745 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.7572 + 0.0000iQBTZ = 0.9052 + 0.0000i 0.6130 - 0.6141i -0.2443 + 0.8738i 1.2233 + 2.5485i 0.0000 + 0.0000i 0.4150 + 0.0000i 3.5658 - 1.2114i 8.0696 - 2.2671i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 6.6127 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.5220 + 0.0000i[B]References[/B]

C. B. Moler and G. W. Stewart, "An Algorithm for Generalized Matrix Eigenvalue Problems", SIAM J.NUMER.ANAL. Vol.10, No.2, April 1973. Also available at [URL="https://blogs.mathworks.com/cleve/files/cbm_gws.pdf"]cbm_gws.pdf[/URL]

J. H. Wilkinson, Kronecker's Canonical Form and the QZ Algorithm", LINEAR ALGEBRA AND ITS APPPLICATIONS, Vol. 28, 1979. Also available at Also available at [URL="https://blogs.mathworks.com/cleve/files/wilkinson.pdf"]wilkinson.pdf[/URL]

[RIGHT][COLOR=gray][I]
[URL="javascript:grabCode_a9bf4a4405b542598f6dba1c3d53fdbd()"][I]Get the MATLAB code (requires JavaScript)[/I][/URL]

Published with MATLAB® R2023a
[/I][/COLOR][/RIGHT]