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