Direkt zum Inhalt

Lexikon der Mathematik: QZ-Algorithmus

ein stabiles Verfahren zur Lösung des verallgemeinerten Eigenwertproblems

\begin{eqnarray}Ax=\lambda Bx\end{eqnarray}

für A, B ∈ ℝn×n.

Das Matrixpaar (A, B) wird dabei iterativ mittels Äquivalenztransformationen in ein Paar \((\widehat{A},\widehat{B})\) überführt, wobei \(\widehat{A}\) und \(\widehat{B}\) obere Dreiecksmatrizen sind. Von den Diagonalen lassen sich dann die Eigenwerte λj ablesen:

\begin{eqnarray}\begin{array}{ccc}{\lambda }_{j}=\displaystyle \frac{{\widehat{a}}_{jj}}{{\widehat{b}}_{jj}}, & \text{falls} & {\widehat{b}}_{jj}\ne 0.\end{array}\end{eqnarray}

Falls B nichtsingulär ist, kann der QZ-Algorithmus wie folgt interpretiert werden: Ausgehend von (A0, B0) = (A, B) wird eine Folge von äquivalenten Matrixpaaren (Ai, Bi) berechnet, welche alle dieselben Eigenwerte und zugehörigen invarianten Unterräume haben.

Die Transformationsmatrizen für die Äquivalenztransformationen

\begin{eqnarray}\begin{array}{ccc}{A}_{i}={Q}_{i}^{T}{A}_{i-1}{Z}_{i} & \text{und} & {B}_{i}={Q}_{i}^{T}{B}_{i-1}{Z}_{i}\end{array}\end{eqnarray}

erhält man aus den QR-Zerlegungen

\begin{eqnarray}\begin{array}{ccc}{p}_{i}({A}_{i-1}{B}_{i-1}^{-1})={Q}_{i}{R}_{i} & \text{und} & {p}_{i}({B}_{i-1}^{-1}{A}_{i-1})={Z}_{i}{S}_{i},\end{array}\end{eqnarray}

wobei pi ein Polynom, Ri, Si obere Dreiecksmatrizen und Qi, Zi orthogonale Matrizen sind. Das Polynom pi ist hierbei typischerweise von der Form pi (x) = xμ mit μ ∈ ℝ oder \({p}_{i}(x)=(x-\nu)(x-\overline{\nu})\) ν ∈ 𝒞. Im Falle B = I hat man Bi = I, Zi = Qi und Si = Ri. Der QZ-Algorithmus reduziert sich zum QR-Algorithmus.

Im allgemeinen konvergiert die Folge der (Ai, Bi) gegen ein Matrixpaar \((\tilde{A},\tilde{B})\), wobei \(\tilde{B}\) eine obere Dreiecksmatrix und \(\tilde{A}\) eine obere Quasi-Dreiecksmatrix ist, d. h. von der Form

\begin{eqnarray}\left(\begin{array}{ccccc}{\tilde{A}}_{11} & {\tilde{A}}_{12} & {\tilde{A}}_{13} & \ldots & {\tilde{A}}_{1m}\\ & {\tilde{A}}_{22} & {\tilde{A}}_{23} & \ldots & {\tilde{A}}_{2m}\\ & & \ddots & & \vdots \\ & & & {\tilde{A}}_{m-1,m-1} & {\tilde{A}}_{m-1,m}\\ & & & & {\tilde{A}}_{mm}\end{array}\right),\end{eqnarray}

wobei die Matrizen \({\tilde{A}}_{ii}\) entweder (1 × 1)-Matrizen oder (2 × 2)-Matrizen sind. Jedes \({\tilde{A}}_{jj}\in {{\mathbb{R}}}^{2\times 2}\) signalisiert ein Paar konjugiert komplexer Eigenwerte, jedes \({\tilde{A}}_{jj}\in {{\mathbb{R}}}^{1\times 1}\) einen reellen Eigenwert.

Numerisch ist das beschriebene Vorgehen problematisch, da in jedem Schritt die Inverse \({B}_{i}^{-1}\) und anschließend die Produkte \({A}_{i}{B}_{i}^{-1},{B}_{i}^{-1}{A}_{i}\) explizit gebildet werden müssen. Der QZ-Algorithmus umgeht diese numerische Schwierigkeit, indem direkt mit dem Matrixpaar (A, B) gearbeitet wird. Ist B nichtsingulär, so entspricht der QZ-Algorithmus dem impliziten Ausführen des obigen Vorgehens. Der QZ-Algorithmus ist aber auch für singuläres B durchführbar.

Wie beim QR-Algorithmus wird zunächst das gegebene Matrixpaar (A, B) auf eine einfachere Gestalt transformiert, welche im Laufe der nachfolgenden Iteration erhalten bleibt und den Aufwand eines Iterationsschritts um eine Größenordnung von n3 arithmetischen Operationen auf n2 reduziert. A wird in eine obere Hessenbergmatrix H und B in eine obere Dreiecksmatrix R transformiert. Anschließend wird durch eine Folge von Äquivalenztransformationen die Matrix H in eine obere Quasi-Dreiecksmatrix so transformiert, daß R seine obere Dreiecksgestalt behält.

Der QZ-Algorithmus ist auch für komplexe Matrixpaare durchführbar. In diesem Falle werden unitäre anstelle der orthogonalen Äquivalenztransformationen verwendet. Die Iterierten konvergieren dann im allgemeinen gegen obere Dreiecksmatrizen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos