Lernen Einführung in die Matrixzerlegung | Grundlagen der Linearen Algebra

Das Lösen von Gleichungssystemen wie $A \vec{x} = \vec{b}$ kann rechnerisch aufwendig sein, insbesondere bei großen Systemen.

Die Matrixzerlegung vereinfacht diesen Prozess, indem sie die Matrix $A$ in einfachere Teile zerlegt, die dann schrittweise gelöst werden können.

LU vs QR

Die Matrix $A$ wird in andere strukturierte Matrizen zerlegt.

LU-Zerlegung

Zerlegung von $A$ in eine untere und eine obere Dreiecksmatrix:

Erstellt mittels Gaußscher Eliminierung;
Am besten geeignet für quadratische Matrizen.

A = LU

QR-Zerlegung

Zerlegung von $A$ in eine orthogonale und eine obere Matrix:

Häufig verwendet für nicht-quadratische Matrizen;
Ideal für Ausgleichsrechnungen oder wenn LU versagt.

A = QR

LU-Zerlegung

Ausgangspunkt ist eine quadratische Matrix:

A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Das Ziel ist, dies wie folgt darzustellen:

A = LU

Wobei gilt:

L = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix},\ \ U = \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}

Diese Zerlegung ist möglich, wenn A quadratisch und invertierbar ist.

Wichtige Punkte:

Untere Dreiecksmatrizen haben alle Einträge oberhalb der Diagonalen gleich null, was die Vorwärtssubstitution vereinfacht;
Obere Dreiecksmatrizen haben Nullen unterhalb der Diagonalen, wodurch die Rückwärtssubstitution unkompliziert wird;
Eine orthogonale Matrix besitzt Spalten, die orthonormale Vektoren sind (Vektoren der Länge 1, die senkrecht zueinander stehen);
Diese Eigenschaft erhält Vektorlängen und Winkel, was beim Lösen von Ausgleichsproblemen und zur Verbesserung der numerischen Stabilität nützlich ist.

Gaußsches Eliminationsverfahren

Anwendung des gaußschen Eliminationsverfahrens, um den Eintrag unterhalb des linken oberen Pivotelements zu eliminieren:

R_2 \rarr R_2 - \frac{6}{4}R_1

Dies ergibt:

R'_2 = [0, -1.5]

Die aktualisierten Matrizen lauten somit:

U = \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix}

Und aus unserer Zeilenoperation ergibt sich:

L = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix}

Wichtige Punkte:

Das gaußsche Eliminationsverfahren eliminiert systematisch die Einträge unterhalb des Pivotelements in jeder Spalte, indem skalierte Versionen der Pivotzeile von den darunterliegenden Zeilen subtrahiert werden;
Dieser Prozess transformiert A in eine obere Dreiecksmatrix U;
Die zum Eliminieren verwendeten Multiplikatoren werden in L gespeichert, sodass A als Produkt LU dargestellt werden kann.

Ergebnis der LU-Zerlegung

Wir überprüfen:

A = LU = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix} = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Nun kann das System $A \vec{x} = \vec{b}$ in zwei Schritten gelöst werden:

Lösung von $L \vec{y} = \vec{b}$ durch Vorwärtssubstitution;
Lösung von $U \vec{x} = \vec{y}$ durch Rückwärtssubstitution.

QR-Zerlegung

Eine Matrix $A$ soll als Produkt zweier Matrizen dargestellt werden:

A = QR

Dabei gilt:

$A$ ist die Eingabematrix (z. B. Daten, Koeffizienten usw.);
$Q$ ist eine orthogonale Matrix (ihre Spalten sind orthonormale Vektoren);
$R$ ist eine obere Dreiecksmatrix.

Beispiel für die Zerlegung der Form:

A = \begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} = \begin{bmatrix} q_1 & q_2 \\ q_3 & q_4 \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Diese Zerlegung wird häufig verwendet, wenn:

Matrix A nicht quadratisch ist;
Kleinste-Quadrate-Probleme gelöst werden;
Die LU-Zerlegung nicht stabil ist.

Was sind Orthonormalvektoren?

Orthogonale Vektoren

Zwei Vektoren $u, v$ sind orthogonal, wenn ihr Skalarprodukt null ist:

u \cdot v = 0

Normalisierter Vektor

Ein Vektor $u$ ist normalisiert, wenn $|u| = 1$ gilt.

Orthonormale Menge

Eine Menge von Vektoren $\{q_1, q_2, ..., q_k\}$ ist orthonormal, wenn jeder Vektor die Einheitslänge besitzt und sie zueinander orthogonal sind:

q_i \cdot q_j = \begin{cases} 1,\ \text{falls}\ \ i = j,\\ 0,\ \text{falls}\ \ i \neq j. \end{cases}

Bedeutung: Orthonormale Spalten in $Q$ erhalten die Geometrie, vereinfachen Projektionen und verbessern die numerische Stabilität.

Definition der Matrix A

Wir beginnen mit folgendem Beispiel:

A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Wir verwenden das Gram-Schmidt-Verfahren, um Matrizen $Q$ und $R$ zu finden, sodass $A=QR$ gilt. Das Gram-Schmidt-Verfahren erzeugt aus den Spalten von $A$ eine orthonormale Vektormenge.

Das bedeutet, die Vektoren in $Q$ sind alle zueinander senkrecht (orthogonal) und besitzen die Einheitslänge (normalisiert). Diese Eigenschaft vereinfacht viele Berechnungen und verbessert die numerische Stabilität beim Lösen von Gleichungssystemen.

Das Ziel ist hier:

Die Spalten von $Q$ orthonormal machen;
Die Matrix $R$ erstellen, die die Projektionen kodiert.

Ermittlung des ersten Basisvektors

Wir entnehmen die erste Spalte von $A$ :

a_1 = \begin{bmatrix} 4 \\ 6 \end{bmatrix}

Zur Normalisierung berechnen wir die Norm:

|a_1| = \sqrt{4^2 + 6^2} = \sqrt{16 + 36} = \sqrt{52}

Dann:

q_1 = \frac{1}{\sqrt{52}} \begin{bmatrix} 4 \\ 6 \end{bmatrix} = \begin{bmatrix} \frac{4}{\sqrt{52}} \\ \frac{6}{\sqrt{52}} \end{bmatrix}

Dies ist der erste orthonormale Vektor für $Q$ .

Wie wird ein Vektor normalisiert?

Gegeben sei ein Vektor:

v = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}

Wir berechnen seine Norm:

|v| = \sqrt{v_1^2 + v_2^2 + ... + v^2_n}

Dann normalisieren wir:

\hat{v} = \frac{1}{|v|}v

Beispiel:

v = \begin{bmatrix} 3 \\ 4 \end{bmatrix},\ \ |v| = \sqrt{3^2 + 4^2} = 5

Unser normalisierter Vektor ist somit:

\hat{v} = \frac{1}{5}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}

Sobald die Normalisierung und Orthogonalisierung von Vektoren bekannt ist, kann das Gram-Schmidt-Verfahren angewendet werden, um die $Q$ -Matrix zu bilden und damit $R$ in der QR-Zerlegung zu berechnen.

Berechnung von q₂ mit dem Gram-Schmidt-Verfahren

Um $q_2$ zu berechnen, beginnt man mit der zweiten Spalte von $A$ :

a_2 = \begin{bmatrix} 3 \\ 3 \end{bmatrix}

Als Nächstes projiziert man $a_2$ auf $q_1$ :

r_{12} = q_1^Ta_2 = \frac{1}{\sqrt{52}}(4 \cdot 3 + 6 \cdot 3) = \frac{1}{\sqrt{52}} \cdot 30

Die Projektion wird von $a_2$ abgezogen:

u_2 = a_2 - r_{12}q_1

Anschließend wird normalisiert (wie oben gezeigt):

q_2 = \frac{u_2}{|u_2|}

Nun bilden sowohl $q_1$ als auch $q_2$ die orthonormale Basis für $Q$ . Das Endergebnis wird nun zusammengesetzt:

Q = \begin{bmatrix} q_1 & q_2 \end{bmatrix},\ \ R = \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Diese erfüllen:

A = QR

War alles klar?

Danke für Ihr Feedback!

Abschnitt 4. Kapitel 8

Fragen Sie AI

Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen

Awesome!

Completion rate improved to 1.96

Swipe um das Menü anzuzeigen

Das Lösen von Gleichungssystemen wie $A \vec{x} = \vec{b}$ kann rechnerisch aufwendig sein, insbesondere bei großen Systemen.

Die Matrixzerlegung vereinfacht diesen Prozess, indem sie die Matrix $A$ in einfachere Teile zerlegt, die dann schrittweise gelöst werden können.

LU vs QR

Die Matrix $A$ wird in andere strukturierte Matrizen zerlegt.

LU-Zerlegung

Zerlegung von $A$ in eine untere und eine obere Dreiecksmatrix:

Erstellt mittels Gaußscher Eliminierung;
Am besten geeignet für quadratische Matrizen.

A = LU

QR-Zerlegung

Zerlegung von $A$ in eine orthogonale und eine obere Matrix:

Häufig verwendet für nicht-quadratische Matrizen;
Ideal für Ausgleichsrechnungen oder wenn LU versagt.

A = QR

LU-Zerlegung

Ausgangspunkt ist eine quadratische Matrix:

A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Das Ziel ist, dies wie folgt darzustellen:

A = LU

Wobei gilt:

L = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix},\ \ U = \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}

Diese Zerlegung ist möglich, wenn A quadratisch und invertierbar ist.

Wichtige Punkte:

Untere Dreiecksmatrizen haben alle Einträge oberhalb der Diagonalen gleich null, was die Vorwärtssubstitution vereinfacht;
Obere Dreiecksmatrizen haben Nullen unterhalb der Diagonalen, wodurch die Rückwärtssubstitution unkompliziert wird;
Eine orthogonale Matrix besitzt Spalten, die orthonormale Vektoren sind (Vektoren der Länge 1, die senkrecht zueinander stehen);
Diese Eigenschaft erhält Vektorlängen und Winkel, was beim Lösen von Ausgleichsproblemen und zur Verbesserung der numerischen Stabilität nützlich ist.

Gaußsches Eliminationsverfahren

Anwendung des gaußschen Eliminationsverfahrens, um den Eintrag unterhalb des linken oberen Pivotelements zu eliminieren:

R_2 \rarr R_2 - \frac{6}{4}R_1

Dies ergibt:

R'_2 = [0, -1.5]

Die aktualisierten Matrizen lauten somit:

U = \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix}

Und aus unserer Zeilenoperation ergibt sich:

L = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix}

Wichtige Punkte:

Das gaußsche Eliminationsverfahren eliminiert systematisch die Einträge unterhalb des Pivotelements in jeder Spalte, indem skalierte Versionen der Pivotzeile von den darunterliegenden Zeilen subtrahiert werden;
Dieser Prozess transformiert A in eine obere Dreiecksmatrix U;
Die zum Eliminieren verwendeten Multiplikatoren werden in L gespeichert, sodass A als Produkt LU dargestellt werden kann.

Ergebnis der LU-Zerlegung

Wir überprüfen:

A = LU = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix} = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Nun kann das System $A \vec{x} = \vec{b}$ in zwei Schritten gelöst werden:

Lösung von $L \vec{y} = \vec{b}$ durch Vorwärtssubstitution;
Lösung von $U \vec{x} = \vec{y}$ durch Rückwärtssubstitution.

QR-Zerlegung

Eine Matrix $A$ soll als Produkt zweier Matrizen dargestellt werden:

A = QR

Dabei gilt:

$A$ ist die Eingabematrix (z. B. Daten, Koeffizienten usw.);
$Q$ ist eine orthogonale Matrix (ihre Spalten sind orthonormale Vektoren);
$R$ ist eine obere Dreiecksmatrix.

Beispiel für die Zerlegung der Form:

A = \begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} = \begin{bmatrix} q_1 & q_2 \\ q_3 & q_4 \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Diese Zerlegung wird häufig verwendet, wenn:

Matrix A nicht quadratisch ist;
Kleinste-Quadrate-Probleme gelöst werden;
Die LU-Zerlegung nicht stabil ist.

Was sind Orthonormalvektoren?

Orthogonale Vektoren

Zwei Vektoren $u, v$ sind orthogonal, wenn ihr Skalarprodukt null ist:

u \cdot v = 0

Normalisierter Vektor

Ein Vektor $u$ ist normalisiert, wenn $|u| = 1$ gilt.

Orthonormale Menge

Eine Menge von Vektoren $\{q_1, q_2, ..., q_k\}$ ist orthonormal, wenn jeder Vektor die Einheitslänge besitzt und sie zueinander orthogonal sind:

q_i \cdot q_j = \begin{cases} 1,\ \text{falls}\ \ i = j,\\ 0,\ \text{falls}\ \ i \neq j. \end{cases}

Bedeutung: Orthonormale Spalten in $Q$ erhalten die Geometrie, vereinfachen Projektionen und verbessern die numerische Stabilität.

Definition der Matrix A

Wir beginnen mit folgendem Beispiel:

A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Wir verwenden das Gram-Schmidt-Verfahren, um Matrizen $Q$ und $R$ zu finden, sodass $A=QR$ gilt. Das Gram-Schmidt-Verfahren erzeugt aus den Spalten von $A$ eine orthonormale Vektormenge.

Das Ziel ist hier:

Die Spalten von $Q$ orthonormal machen;
Die Matrix $R$ erstellen, die die Projektionen kodiert.

Ermittlung des ersten Basisvektors

Wir entnehmen die erste Spalte von $A$ :

a_1 = \begin{bmatrix} 4 \\ 6 \end{bmatrix}

Zur Normalisierung berechnen wir die Norm:

|a_1| = \sqrt{4^2 + 6^2} = \sqrt{16 + 36} = \sqrt{52}

Dann:

q_1 = \frac{1}{\sqrt{52}} \begin{bmatrix} 4 \\ 6 \end{bmatrix} = \begin{bmatrix} \frac{4}{\sqrt{52}} \\ \frac{6}{\sqrt{52}} \end{bmatrix}

Dies ist der erste orthonormale Vektor für $Q$ .

Wie wird ein Vektor normalisiert?

Gegeben sei ein Vektor:

v = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}

Wir berechnen seine Norm:

|v| = \sqrt{v_1^2 + v_2^2 + ... + v^2_n}

Dann normalisieren wir:

\hat{v} = \frac{1}{|v|}v

Beispiel:

v = \begin{bmatrix} 3 \\ 4 \end{bmatrix},\ \ |v| = \sqrt{3^2 + 4^2} = 5

Unser normalisierter Vektor ist somit:

\hat{v} = \frac{1}{5}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}

Berechnung von q₂ mit dem Gram-Schmidt-Verfahren

Um $q_2$ zu berechnen, beginnt man mit der zweiten Spalte von $A$ :

a_2 = \begin{bmatrix} 3 \\ 3 \end{bmatrix}

Als Nächstes projiziert man $a_2$ auf $q_1$ :

r_{12} = q_1^Ta_2 = \frac{1}{\sqrt{52}}(4 \cdot 3 + 6 \cdot 3) = \frac{1}{\sqrt{52}} \cdot 30

Die Projektion wird von $a_2$ abgezogen:

u_2 = a_2 - r_{12}q_1

Anschließend wird normalisiert (wie oben gezeigt):

q_2 = \frac{u_2}{|u_2|}

Nun bilden sowohl $q_1$ als auch $q_2$ die orthonormale Basis für $Q$ . Das Endergebnis wird nun zusammengesetzt:

Q = \begin{bmatrix} q_1 & q_2 \end{bmatrix},\ \ R = \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Diese erfüllen:

A = QR

War alles klar?

Danke für Ihr Feedback!

Abschnitt 4. Kapitel 8