Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] Englische Flagge
Mathematik-Online-Lexikon:

Householder-Transformation bei einem linearen Gleichungssystem

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht

Ein lineares Gleichungssystem

$\displaystyle Ax=b $

mit einer $ m\times n$-Matrix $ A$ kann mit Hilfe der QR-Zerlegung $ A(:,I)=QR$ gelöst werden. Nach Multiplikation mit $ Q^t$, bzw. Durchführung der entsprechenden Householder-Transformationen, hat das System $ A(:,I) x(I) = b$ die Form

$\displaystyle Ry = \left(\begin{array}{cc} \tilde R & S \\ 0 & 0 \end{array}\right) y = \left(\begin{array}{c} c \\ d \end{array}\right) = Q^t b $

mit $ y = x(I)$ und einer quadratischen invertierbaren Matrix $ \tilde R$. Die Dimension $ k$ von $ \tilde R$ ist der Rang von $ A$.

Eine Lösung existiert genau dann wenn $ d=0$ ist und kann durch Rückwärtseinsetzen aus den ersten $ k$ Gleichungen,

$\displaystyle \tilde R\, y(1:k) = c - S\, y(k+1:n) \,, $

berechnet werden. Die Lösung ist eindeutig für $ k=n$, andernfalls sind die Komponenten $ y_i$, $ i>k$, frei wählbar.

Für $ d\ne0$ ist das lineare Gleichungssystem nicht lösbar. Da orthogonale Transformationen die $ 2$-Norm invariant lassen. minimiert jedoch die obige Lösung den Fehler $ e = \vert Ax-b\vert$ und $ e_{\min} = \vert d\vert$.

Beispiel:

[Erläuterungen] [Downloads] [Verweise]
  automatisch erstellt am 19.  8. 2013