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 (A₀, B₀) = (A, B) wird eine Folge von äquivalenten Matrixpaaren (A_i, B_i) 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 p_i ein Polynom, R_i, S_i obere Dreiecksmatrizen und Q_i, Z_i orthogonale Matrizen sind. Das Polynom p_i ist hierbei typischerweise von der Form p_i (x) = x − μ mit μ ∈ ℝ oder \({p}_{i}(x)=(x-\nu)(x-\overline{\nu})\) ν ∈ 𝒞. Im Falle B = I hat man B_i = I, Z_i = Q_i und S_i = R_i. Der QZ-Algorithmus reduziert sich zum QR-Algorithmus.

Im allgemeinen konvergiert die Folge der (A_i, B_i) 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 n³ arithmetischen Operationen auf n² 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.