Direkt zum Inhalt

Lexikon der Mathematik: QMR-Verfahren

iteratives Krylow-Raum-Verfahren zur Lösung eines linearen Gleichungssystems Ax = b, wobei A ∈ ℝn×n eine beliebige (insbesondere auch unsymmetrische) Matrix ist.

Da im Laufe der Berechnungen lediglich Matrix-Vektor-Multiplikationen benötigt werden, ist das Verfahren besonders für große sparse Matrizen A geeignet.

Das QMR-Verfahren ist eine Verallgemeinerung des konjugierten Gradientenverfahrens für Gleichungssysteme mit symmetrisch positiv definiten Koeffizientenmatrizen. Es wird, ausgehend von einem (beliebigen) Startvektor x(0), eine Folge von Näherungsvektoren x(k) an die gesuchte Lösung x gebildet.

Im k-ten Schritt des QMR-Verfahrens minimiert man nun \begin{eqnarray}{(b-A{x}^{(k)})}^{T}(b-A{x}^{(k)})\end{eqnarray}

unter der Nebenbedingung, daß x(k) die Form \({x}^{(k)}={x}^{(0)}+{Q}_{k}{y}^{(k)}\) für ein y(k) ∈ ℝk hat. Dabei wird Qk ∈ ℝn×k gerade als die Matrix gewählt, welche man nach k Schritten des Lanczos-Verfahrens erhält, d. h. \begin{eqnarray}A{Q}_{k}={Q}_{k+1}{T}_{k+1}\end{eqnarray}

mit \begin{eqnarray}{T}_{k+1,k}=\left[\begin{array}{lllll}{\alpha }_{1} & {\beta }_{1} & & & \\ {\beta }_{1} & {\alpha }_{2} & {\beta }_{2} & & \\ & \ddots & \ddots & \ddots & \\ & & \ddots & \ddots & {\beta }_{k-1}\\ & & & {\beta }_{k-1} & {\alpha }_{k}\\ & & & & {\beta }_{k}\end{array}\right]\in {{\mathbb{R}}}^{k+1,k}.\end{eqnarray}

Es folgt, daß y(k) als die Lösung des linearen Ausgleichsproblems \begin{eqnarray}\mathop{\min }\limits_{y\in {{\mathbb{R}}}^{k}}||\frac{{e}_{1}}{||{r}^{(0)}|{|}_{2}}-{T}_{k+1,k}y|{|}_{2}\end{eqnarray}

zu wählen ist, wobei e1 = [1, 0, …, 0]T ∈ ℝk. Das Ausgleichsproblem kann effizient mittels der Methode der kleinsten Quadrate gelöst werden.

Aufgrund des zugrundeliegenden Lanczos-Verfahrens kann das QMR-Verfahren vorzeitig zusammenbrechen, ohne eine Lösung des Problems zu berechnen. Mithilfe von sogenannten lookahead Techniken ist es jedoch möglich, diese Probleme zu umgehen.

Die dem QMR-Verfahren zugrundeliegende Idee ist ähnlich der des GMRES-Verfahrens. Dort wird statt des Lanczos-Verfahrens das Arnoldi-Verfahren verwendet.

[1] Hartung, J.; Elpelt, B.: Multivariate Statistik. Lehr- und Handbuch der angewandten Statistik, Oldenbourg Verlag, München, 1989.

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