Study Guides / Lineare Algebra / Übungsstunde 5
ÜBUNGSSTUNDE 5 · ETH ZURICH · HS19 · linalg

LR-Zerlegung, Vektorräume, Injektivität und Surjektivität

LR-Zerlegung, Körper, abelsche Gruppe, Vektorräume, Untervektorraum, Injektivität, Surjektivität, Bijektivität

SB
Steven Battilana Quant · ex-ETH

LR-Zerlegung (engl. LU decomposition)

Bemerkung Idee

Bei grossen Gleichungssystemen Ax=bAx=b mit A∈En×nA \in \mathbb{E}^{n \times n} und b,x∈Enb,x \in \mathbb{E}^n ist die Lösung xx meist nicht einfach zu finden. Daher wollen wir AA gerne in eine einfachere Form von Dreiecksmatrizen zerlegen, d.h. Wir suchen Matrizen P,L,R∈En×nP,L,R \in \mathbb{E}^{n \times n} so dass PA=LRPA = LR,

P=^ ist eine Permutationsmatrix (entha¨lt nur 1 und 0)L=^ ist eine linke Dreiecksmatrix (engl. lower triangular matrix)R (engl. U)=^ ist eine rechte Dreiecksmatrix (engl. upper triangular matrix)\begin{aligned} P &\mathrel{\hat{=}} \text{ ist eine \emph{Permutationsmatrix} (enthält nur $1$ und $0$)}\\ L &\mathrel{\hat{=}} \text{ ist eine \emph{linke Dreiecksmatrix} (engl. lower triangular matrix)}\\ R \text{ (engl. $U$)} &\mathrel{\hat{=}} \text{ ist eine \emph{rechte Dreiecksmatrix} (engl. upper triangular matrix)} \end{aligned}L=(10⋯0∗⋱⋱⋮⋮⋱⋱0∗⋯∗1)R=(∗⋯⋯∗0⋱⋱⋮⋮⋱⋱0⋯0∗)L = \begin{pmatrix} 1 & 0 & \cdots & 0\\ * & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ * & \cdots & * & 1 \end{pmatrix} \quad\quad\quad\quad R = \begin{pmatrix} * & \cdots & \cdots & *\\ 0 & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & \\ 0 & \cdots & 0 & * \end{pmatrix}
Bemerkung

Seien A,P,L,R∈En×nA,P,L,R \in \mathbb{E}^{n \times n}. PP speichert die Zeilenvertauschungen, die man für die Pivotisierung braucht, LL speichert die Umformungsschritte, um AA in eine Zeilenstufenform zu verwandeln, RR ist die Zeilenstufenform von AA.

Bemerkung

Seien A,P,L,R∈En×nA,P,L,R \in \mathbb{E}^{n \times n} und b,c,x∈Enb,c,x \in \mathbb{E}^n. Das anfängliche System Ax=bAx=b lässt sich nun einfacher lösen:

  1. Löse Lc=PbLc = Pb nach cc durch Vorwärtseinsetzen, d.h. (L∣Pb)(L|Pb) von oben nach unten "Gaussen".
  2. Löse Rx=cRx=c nach xx durch Rückwärtseinsetzen, d.h. (R∣c)(R|c) von unten nach oben "Gaussen".
Bemerkung

Dass die Beziehung aus der obigen Bemerkung für A,P,P−1,L,R∈En×nA,P,P^{-1},L,R \in \mathbb{E}^{n \times n} die richtige Lösung x∈En\boldsymbol{x} \in \mathbb{E}^n liefert, sieht man auch daraus, dass

Ax=P−1PAx=P−1LRx=P−1Lc=P−1Pb=b.A \boldsymbol{x} = P^{-1}PA\boldsymbol{x} = P^{-1}LR\boldsymbol{x} = P^{-1}L\boldsymbol{c} = P^{-1}P\boldsymbol{b} = \boldsymbol{b}.
Satz

Für eine reguläre, quadratische Matrix A∈En×nA \in \mathbb{E}^{n \times n} existiert eine LR-Zerlegung, d.h.

∃P,L,R∈En×n:PA=LR.\exists P,L,R \in \mathbb{E}^{n \times n}: \quad PA = LR.
Bemerkung LR-Zerlegung light (d.h. ohne Pivotisierung)

Annahme: keine Zeilenvertauschungen nötig und AA hat keine Nullspalte
Gegeben: A∈En×nA \in \mathbb{E}^{n \times n}
Gesucht: L∈En×n, R∈En×nL \in \mathbb{E}^{n \times n},\, R \in \mathbb{E}^{n \times n} so dass gilt: A=LRA = LR

  1. Schreibe das Schema (A∣𝟙)(A|\text{𝟙})

  2. Forme AA mit Hilfe von Gauss-Elimination (OHNE Zeilenvertauschungen!) um bis ihr die Zeilenstufenform erreicht habt. Dies tut ihr alles nur auf der linken Seite der erweiterten Koeffizientenmatrix.

  3. Auf der rechten Seite schreibt ihr die Verhältnisse auf:

    lij:=aijajj,L=(10⋯0l21⋱⋱⋮⋮⋱⋱0ln1⋯lnn−11)l_{ij} := \frac{a_{ij}}{a_{jj}}, \quad\quad L = \begin{pmatrix} 1 & 0 & \cdots & 0\\ l_{21} & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ l_{n1} & \cdots & l_{nn-1} & 1 \end{pmatrix}

Diese Schritte sehen wie folgt aus:

(A∣𝟙)⇝⋯⇝(R∣L)(A|\text{𝟙}) \leadsto \cdots \leadsto (R|L)

mit mehr Details:

(a11a12a13100a21a22a23010a31a32a33001)\left(\begin{array}{ccc|ccc} a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ a_{21} & a_{22} & a_{23} & 0 & 1 & 0\\ a_{31} & a_{32} & a_{33} & 0 & 0 & 1 \end{array}\right)⇝(ii)−l21⋅(i)  (a11a12a13100a21−l21a11a22−l21a12a23−l21a13l2110a31a32a33001)⇝(iii)−l31⋅(i)  (a11a12a131000a22~a23~l2110a31−l31a11a32−l31a12a33−l31a13l3101)⇝  (a11a12a131000a22~a23~l21100a32~a33~l3101)⇝  ⋯  ⇝  (a11a12a131000a22~a23~l211000a33^l31l321)\begin{aligned} \stackrel{(ii) - l_{21} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|ccc} a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ a_{21} - l_{21}a_{11} & a_{22} - l_{21}a_{12} & a_{23} - l_{21}a_{13} & l_{21} & 1 & 0\\ a_{31} & a_{32} & a_{33} & 0 & 0 & 1 \end{array}\right)\\[1.5ex] \stackrel{(iii) - l_{31} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|ccc} a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & \widetilde{a_{22}} & \widetilde{a_{23}} & l_{21} & 1 & 0\\ a_{31} - l_{31}a_{11} & a_{32} - l_{31}a_{12} & a_{33} - l_{31}a_{13} & l_{31} & 0 & 1 \end{array}\right)\\[1.5ex] \leadsto \; & \left(\begin{array}{ccc|ccc} a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & \widetilde{a_{22}} & \widetilde{a_{23}} & l_{21} & 1 & 0\\ 0 & \widetilde{a_{32}} & \widetilde{a_{33}} & l_{31} & 0 & 1 \end{array}\right)\\[1.5ex] \leadsto \; \cdots \; \leadsto \; & \left(\begin{array}{ccc|ccc} a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & \widetilde{a_{22}} & \widetilde{a_{23}} & l_{21} & 1 & 0\\ 0 & 0 & \widehat{a_{33}} & l_{31} & l_{32} & 1 \end{array}\right) \end{aligned}⟹R=(a11a12a130a22~a23~00a33^),L=(100l2110l31l321)\quad \Longrightarrow \quad R = \begin{pmatrix} a_{11} & a_{12} & a_{13}\\ 0 & \widetilde{a_{22}} & \widetilde{a_{23}}\\ 0 & 0 & \widehat{a_{33}} \end{pmatrix}, \quad\quad L = \begin{pmatrix} 1 & 0 & 0\\ l_{21} & 1 & 0\\ l_{31} & l_{32} & 1 \end{pmatrix}

Nun gilt:

A=(a11a12a13a21a22a23a31a32a33)=(100l2110l31l321)(a11a12a130a22~a23~00a33^)=LRA = \begin{pmatrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33} \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0\\ l_{21} & 1 & 0\\ l_{31} & l_{32} & 1 \end{pmatrix} \begin{pmatrix} a_{11} & a_{12} & a_{13}\\ 0 & \widetilde{a_{22}} & \widetilde{a_{23}}\\ 0 & 0 & \widehat{a_{33}} \end{pmatrix} = LR
Beispiel 1

Sei A∈R3×3A \in \mathbb{R}^{3 \times 3} und b∈Rnb \in \mathbb{R}^n gegeben.

A=(12438142613),b=(35129109)A = \begin{pmatrix} 1 & 2 & 4\\ 3 & 8 & 14\\ 2 & 6 & 13 \end{pmatrix}, \quad\quad \boldsymbol{b} = \begin{pmatrix} 35\\ 129\\ 109 \end{pmatrix}

(i) Gesucht: L,R∈R3×3:A=LR.L,R \in \mathbb{R}^{3 \times 3}:\quad A = LR.

Lösung anzeigenLösung ausblenden (12410038140102613001)\left(\begin{array}{ccc|ccc} 1 & 2 & 4 & 1 & 0 & 0\\ 3 & 8 & 14 & 0 & 1 & 0\\ 2 & 6 & 13 & 0 & 0 & 1 \end{array}\right)⇝(ii)−l21⋅(i)  (1241000223102613001)⇝(iii)−l31⋅(i)  (124100022310025201)⇝(iii)−l32⋅(ii)  (124100022310003211)\begin{aligned} \stackrel{(ii) - l_{21} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|ccc} 1 & 2 & 4 & 1 & 0 & 0\\ 0 & 2 & 2 & 3 & 1 & 0\\ 2 & 6 & 13 & 0 & 0 & 1 \end{array}\right)\\[1.5ex] \stackrel{(iii) - l_{31} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|ccc} 1 & 2 & 4 & 1 & 0 & 0\\ 0 & 2 & 2 & 3 & 1 & 0\\ 0 & 2 & 5 & 2 & 0 & 1 \end{array}\right)\\[1.5ex] \stackrel{(iii) - l_{32} \cdot (ii)}{\leadsto} \; & \left(\begin{array}{ccc|ccc} 1 & 2 & 4 & 1 & 0 & 0\\ 0 & 2 & 2 & 3 & 1 & 0\\ 0 & 0 & 3 & 2 & 1 & 1 \end{array}\right) \end{aligned}⟹A=(12438142613)=(100310211)(124022003)=LR.\Longrightarrow \quad A = \begin{pmatrix} 1 & 2 & 4\\ 3 & 8 & 14\\ 2 & 6 & 13 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0\\ 3 & 1 & 0\\ 2 & 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 & 4\\ 0 & 2 & 2\\ 0 & 0 & 3 \end{pmatrix} =LR.

(ii) Gesucht: x∈Rn:Ax=b\boldsymbol{x} \in \mathbb{R}^n: \quad A\boldsymbol{x}=\boldsymbol{b}.

Lösung anzeigenLösung ausblenden

Wir gehen vor, wie in der Bemerkung oben (Vorwärts- und Rückwärtseinsetzen) vorgeschlagen:

  1. Löse Lc=bL\boldsymbol{c} = \boldsymbol{b}:

    (10035310129211109)\left(\begin{array}{ccc|c} 1 & 0 & 0 & 35\\ 3 & 1 & 0 & 129\\ 2 & 1 & 1 & 109 \end{array}\right) ⇝(ii)−31⋅(i)  (1003501024211109)⇝(iii)−21⋅(i)  (100350102401139)⇝(iii)−11⋅(ii)  (100350102400115)⇒c=(352415)\begin{aligned} \stackrel{(ii) - \frac{3}{1} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 35\\ 0 & 1 & 0 & 24\\ 2 & 1 & 1 & 109 \end{array}\right)\\[1.5ex] \stackrel{(iii) - \frac{2}{1} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 35\\ 0 & 1 & 0 & 24\\ 0 & 1 & 1 & 39 \end{array}\right)\\[1.5ex] \stackrel{(iii) - \frac{1}{1} \cdot (ii)}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 35\\ 0 & 1 & 0 & 24\\ 0 & 0 & 1 & 15 \end{array}\right) \quad\quad \Rightarrow \quad\quad \boldsymbol{c} = \begin{pmatrix} 35\\ 24\\ 15 \end{pmatrix} \end{aligned}
  2. Löse Rx=cR\boldsymbol{x} = \boldsymbol{c}:

    (124350222400315)\left(\begin{array}{ccc|c} 1 & 2 & 4 & 35\\ 0 & 2 & 2 & 24\\ 0 & 0 & 3 & 15 \end{array}\right) ⇝(ii)−23⋅(iii)  (124350201400315)⇝(i)−43⋅(iii)  (120150201400315)⇝(i)−22⋅(ii)  (10010201400315)⇝(ii)⋅12  (1001010700315)⇝(iii)⋅13  (100101070015)\begin{aligned} \stackrel{(ii) - \frac{2}{3} \cdot (iii)}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 2 & 4 & 35\\ 0 & 2 & 0 & 14\\ 0 & 0 & 3 & 15 \end{array}\right)\\[1.5ex] \stackrel{(i) - \frac{4}{3} \cdot (iii)}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 2 & 0 & 15\\ 0 & 2 & 0 & 14\\ 0 & 0 & 3 & 15 \end{array}\right)\\[1.5ex] \stackrel{(i) - \frac{2}{2} \cdot (ii)}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 1\\ 0 & 2 & 0 & 14\\ 0 & 0 & 3 & 15 \end{array}\right)\\[1.5ex] \stackrel{(ii) \cdot \frac{1}{2}}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 7\\ 0 & 0 & 3 & 15 \end{array}\right)\\[1.5ex] \stackrel{(iii) \cdot \frac{1}{3}}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 7\\ 0 & 0 & 1 & 5 \end{array}\right) \end{aligned} ⇒x=(175)⟹L={(x1x2x3)∣(175)}\Rightarrow \quad\quad \boldsymbol{x} = \begin{pmatrix} 1\\ 7\\ 5 \end{pmatrix} \quad\quad \Longrightarrow \quad\quad \mathbb{L} = \left\{ \left. \begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix} \right| \begin{pmatrix} 1\\ 7\\ 5 \end{pmatrix}\right\}
Bemerkung LR-Zerlegung full (d.h. mit Pivotisierung)

Gegeben: A∈En×nA \in \mathbb{E}^{n \times n}
Gesucht: P∈Rn×n, L∈En×n, R∈En×nP \in \mathbb{R}^{n \times n},\, L \in \mathbb{E}^{n \times n},\, R \in \mathbb{E}^{n \times n} so dass gilt: PA=LRPA = LR

  1. Schreibe das Schema (𝟙∣A∣𝟙)(\text{𝟙}|A|\text{𝟙}). Links merkt ihr euch die Zeilenvertauschungen, in der Mitte "Gausst" ihr und rechts merkt ihr euch die Verhältnisse.

  2. Pivotisiere in der aktuellen Spalte jj, d.h. bestimme den Index ip∈{j,j+1,...,n}i_p \in \{j,j+1, ..., n\} mit ∣aipj∣=max⁡i∈{j,j+1,...,n}∣aij∣|a_{i_pj}| =\max \limits _{i \in \{j,j+1, ..., n\}} |a_{ij}|. Falls ∣aipj∣=0|a_{i_pj}| = 0 breche ab, es existiert keine LR-Zerlegung. Sonst berechne PijA=A~P_{ij}A=\widetilde{A} in der Mitte, wobei Pij∈Rn×nP_{ij} \in \mathbb{R}^{n \times n} von links an die Matrix links im Schema multipliziert wird und auf der rechten Seite müsst ihr entsprechend die Verhältnisse vertauschen (ausser im ersten Schritt).

    • Falls ihr zu Beginn pivotisieren müsst, sieht das Resultat vom Schritt wie folgt aus:
      (𝟙∣A∣𝟙)⇝(Pij∣A~∣𝟙)(\text{𝟙}|A|\text{𝟙}) \leadsto (P_{ij}|\widetilde{A}|\text{𝟙})

    • Sonst, sieht das Resultat vom Schritt wie folgt aus:

      (010a11a12a1310010000a23~l21100010a32~a33~l3101)\left(\begin{array}{ccc|ccc|ccc} 0 & 1 & 0 & a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & \widetilde{a_{23}} & l_{21} & 1 & 0\\ 0 & 0 & 1 & 0 & \widetilde{a_{32}} & \widetilde{a_{33}} & l_{31} & 0 & 1 \end{array}\right) ⇝pivotisiere(010a11a12a131000010a32~a33~l311010000a23~l2101)\stackrel{\text{pivotisiere}}{\leadsto} \left(\begin{array}{ccc|ccc|ccc} 0 & 1 & 0 & a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & \widetilde{a_{32}} & \widetilde{a_{33}} & l_{31} & 1 & 0\\ 1 & 0 & 0 & 0 & 0 & \widetilde{a_{23}} & l_{21} & 0 & 1 \end{array}\right)
  3. Forme AA mit Hilfe von Gauss-Elimination (OHNE Zeilenvertauschungen!) um bis ihr die Zeilenstufenform erreicht habt. Dies tut ihr alles nur auf der linken Seite der erweiterten Koeffizientenmatrix.
    Taucht bei der Berechnung wieder ein Nulleintrag auf in der Hauptdiagonale, dann müsst ihr wieder pivotisieren, also wiederholt den zweiten Schritt. Dann weiter "Gaussen".

  4. Auf der rechten Seite schreibt ihr die Verhältnisse auf:

    lij:=aijajj,L=(10⋯0l21⋱⋱⋮⋮⋱⋱0ln1⋯lnn−11)l_{ij} := \frac{a_{ij}}{a_{jj}}, \quad\quad L = \begin{pmatrix} 1 & 0 & \cdots & 0\\ l_{21} & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ l_{n1} & \cdots & l_{nn-1} & 1 \end{pmatrix}

Die Schritte sehen wie folgt aus:

(𝟙∣A∣𝟙)⇝⋯⇝(P∣R∣L)(\text{𝟙}|A|\text{𝟙}) \leadsto \cdots \leadsto (P|R|L)

mit mehr Details:

(100a11a12a13100010a21a22a23010001a31a32a33001)\left(\begin{array}{ccc|ccc|ccc} 1 & 0 & 0 & a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & 1 & 0 & a_{21} & a_{22} & a_{23} & 0 & 1 & 0\\ 0 & 0 & 1 & a_{31} & a_{32} & a_{33} & 0 & 0 & 1 \end{array}\right)⇝(ii)−l21⋅(i)  (100a11a12a13100010a21−l21a11a22−l21a12a23−l21a13l2110001a31a32a33001)⇝(iii)−l31⋅(i)  (100a11a12a1310001000a23~l2110001a31−l31a11a32−l31a12a33−l31a13l3101)\begin{aligned} \stackrel{(ii) - l_{21} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|ccc|ccc} 1 & 0 & 0 & a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & 1 & 0 & a_{21} - l_{21}a_{11} & a_{22} - l_{21}a_{12} & a_{23} - l_{21}a_{13} & l_{21} & 1 & 0\\ 0 & 0 & 1 & a_{31} & a_{32} & a_{33} & 0 & 0 & 1 \end{array}\right)\\[1.5ex] \stackrel{(iii) - l_{31} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|ccc|ccc} 1 & 0 & 0 & a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & \widetilde{a_{23}} & l_{21} & 1 & 0\\ 0 & 0 & 1 & a_{31} - l_{31}a_{11} & a_{32} - l_{31}a_{12} & a_{33} - l_{31}a_{13} & l_{31} & 0 & 1 \end{array}\right) \end{aligned}⇝(100a11a12a1310001000a23~l21100010a32~a33~l3101)\leadsto \left(\begin{array}{ccc|ccc|ccc} 1 & 0 & 0 & a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & \widetilde{a_{23}} & l_{21} & 1 & 0\\ 0 & 0 & 1 & 0 & \widetilde{a_{32}} & \widetilde{a_{33}} & l_{31} & 0 & 1 \end{array}\right)⇝pivotisiere(100a11a12a131000010a32~a33~l311001000a23~l2101)\stackrel{\text{pivotisiere}}{\leadsto} \left(\begin{array}{ccc|ccc|ccc} 1 & 0 & 0 & a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & \widetilde{a_{32}} & \widetilde{a_{33}} & l_{31} & 1 & 0\\ 0 & 1 & 0 & 0 & 0 & \widetilde{a_{23}} & l_{21} & 0 & 1 \end{array}\right)PA=(100001010)(a11a12a13a21a22a23a31a32a33)=(100l3110l2101)(a11a12a130a32~a33~00a23~)=LRPA = \begin{pmatrix} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33} \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0\\ l_{31} & 1 & 0\\ l_{21} & 0 & 1 \end{pmatrix} \begin{pmatrix} a_{11} & a_{12} & a_{13}\\ 0 & \widetilde{a_{32}} & \widetilde{a_{33}}\\ 0 & 0 & \widetilde{a_{23}} \end{pmatrix} = LR
Beispiel 2

Sei A∈R3×3A \in \mathbb{R}^{3 \times 3} und b∈Rnb \in \mathbb{R}^n gegeben.

A=(316−60−1608−17),b=(40−86−29)A = \begin{pmatrix} 3 & 1 & 6\\ -6 & 0 & -16\\ 0 & 8 & -17 \end{pmatrix}, \quad\quad \boldsymbol{b} = \begin{pmatrix} 40\\ -86\\ -29 \end{pmatrix}

(i) Gesucht: L,P,R∈R3×3:PA=LR.L,P,R \in \mathbb{R}^{3 \times 3}:\quad PA = LR.

Lösung anzeigenLösung ausblenden (100316100010−60−1601000108−17001)\left(\begin{array}{ccc|ccc|ccc} 1 & 0 & 0 & 3 & 1 & 6 & 1 & 0 & 0\\ 0 & 1 & 0 & -6 & 0 & -16 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 8 & -17 & 0 & 0 & 1 \end{array}\right)⇝pivotisiere:P21  (010−60−1610010031601000108−17001)⇝(ii)−l21⋅(i)  (010−60−1610010001−2−121000108−17001)⇝pivotisiere:P32  (010−60−1610000108−1701010001−2−1201)\begin{aligned} \stackrel{\text{pivotisiere:} P_{21}}{\leadsto} \; & \left(\begin{array}{ccc|ccc|ccc} 0 & 1 & 0 & -6 & 0 & -16 & 1 & 0 & 0\\ 1 & 0 & 0 & 3 & 1 & 6 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 8 & -17 & 0 & 0 & 1 \end{array}\right)\\[1.5ex] \stackrel{(ii) - l_{21} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|ccc|ccc} 0 & 1 & 0 & -6 & 0 & -16 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & -2 & -\frac{1}{2} & 1 & 0\\ 0 & 0 & 1 & 0 & 8 & -17 & 0 & 0 & 1 \end{array}\right)\\[1.5ex] \stackrel{\text{pivotisiere:} P_{32}}{\leadsto} \; & \left(\begin{array}{ccc|ccc|ccc} 0 & 1 & 0 & -6 & 0 & -16 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 8 & -17 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 & 1 & -2 & -\frac{1}{2} & 0 & 1 \end{array}\right) \end{aligned}⇝(iii)−l32⋅(ii)(010−60−1610000108−170101000018−12181)\stackrel{(iii) - l_{32} \cdot (ii)}{\leadsto} \left(\begin{array}{ccc|ccc|ccc} 0 & 1 & 0 & -6 & 0 & -16 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 8 & -17 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 & 0 & \frac{1}{8} & -\frac{1}{2} & \frac{1}{8} & 1 \end{array}\right)PA=(010001100)(316−60−1608−17)=(100010−12181)(−60−1608−170018)=LRPA = \begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} 3 & 1 & 6\\ -6 & 0 & -16\\ 0 & 8 & -17 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ -\frac{1}{2} & \frac{1}{8} & 1 \end{pmatrix} \begin{pmatrix} -6 & 0 & -16\\ 0 & 8 & -17\\ 0 & 0 & \frac{1}{8} \end{pmatrix} = LR

(ii) Gesucht: x∈Rn:Ax=b\boldsymbol{x} \in \mathbb{R}^n: \quad A\boldsymbol{x}=\boldsymbol{b}.

Lösung anzeigenLösung ausblenden

Wir gehen vor, wie in der Bemerkung oben (Vorwärts- und Rückwärtseinsetzen) vorgeschlagen:

  1. Löse Lc=PbL\boldsymbol{c} = P\boldsymbol{b}:

    Pb=(010001100)(40−86−29)=(−86−2940)P\boldsymbol{b} = \begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} 40\\ -86\\ -29 \end{pmatrix} = \begin{pmatrix} -86\\ -29\\ 40 \end{pmatrix} (100−86010−29−1218140)⇝(iii)−−1/21⋅(i)(100−86010−290181−3)⇝(iii)−1/81⋅(ii)(100−86010−2900158)\left(\begin{array}{ccc|c} 1 & 0 & 0 & -86\\ 0 & 1 & 0 & -29\\ -\frac{1}{2} & \frac{1}{8} & 1 & 40 \end{array}\right) \stackrel{(iii) - \frac{-1/2}{1} \cdot (i)}{\leadsto} \left(\begin{array}{ccc|c} 1 & 0 & 0 & -86\\ 0 & 1 & 0 & -29\\ 0 & \frac{1}{8} & 1 & -3 \end{array}\right) \stackrel{(iii) - \frac{1/8}{1} \cdot (ii)}{\leadsto} \left(\begin{array}{ccc|c} 1 & 0 & 0 & -86\\ 0 & 1 & 0 & -29\\ 0 & 0 & 1 & \frac{5}{8} \end{array}\right) ⇒c=(−86−2958)\Rightarrow \quad\quad \boldsymbol{c} = \begin{pmatrix} -86\\ -29\\ \frac{5}{8} \end{pmatrix}
  2. Löse Rx=cR\boldsymbol{x} = \boldsymbol{c}:

    (−60−16−8608−17−29001858)\left(\begin{array}{ccc|c} -6 & 0 & -16 & -86\\ 0 & 8 & -17 & -29\\ 0 & 0 & \frac{1}{8} & \frac{5}{8} \end{array}\right) ⇝(ii)−−171/8⋅(iii)  (−60−16−8608056001858)⇝(i)−−161/8⋅(iii)  (−600−608056001858)⇝(i)⋅(−16)  (100108056001858)⇝(ii)⋅18  (10010107001858)⇝(iii)⋅8  (100101070015)\begin{aligned} \stackrel{(ii) - \frac{-17}{1/8} \cdot (iii)}{\leadsto} \; & \left(\begin{array}{ccc|c} -6 & 0 & -16 & -86\\ 0 & 8 & 0 & 56\\ 0 & 0 & \frac{1}{8} & \frac{5}{8} \end{array}\right)\\[1.5ex] \stackrel{(i) - \frac{-16}{1/8} \cdot (iii)}{\leadsto} \; & \left(\begin{array}{ccc|c} -6 & 0 & 0 & -6\\ 0 & 8 & 0 & 56\\ 0 & 0 & \frac{1}{8} & \frac{5}{8} \end{array}\right)\\[1.5ex] \stackrel{(i) \cdot (-\frac{1}{6})}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 1\\ 0 & 8 & 0 & 56\\ 0 & 0 & \frac{1}{8} & \frac{5}{8} \end{array}\right)\\[1.5ex] \stackrel{(ii) \cdot \frac{1}{8}}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 7\\ 0 & 0 & \frac{1}{8} & \frac{5}{8} \end{array}\right)\\[1.5ex] \stackrel{(iii) \cdot 8}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 7\\ 0 & 0 & 1 & 5 \end{array}\right) \end{aligned} ⇒x=(175)⟹L={(x1x2x3)∣(175)}\Rightarrow \quad\quad \boldsymbol{x} = \begin{pmatrix} 1\\ 7\\ 5 \end{pmatrix} \quad\quad \Longrightarrow \quad\quad \mathbb{L} = \left\{ \left. \begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix} \right| \begin{pmatrix} 1\\ 7\\ 5 \end{pmatrix}\right\}

Vektorräume

Definition

Eine Menge E\mathbb{E} zusammen mit zwei Verknüpfungen

+:E×E→E,(x,y)↦x+y(Addition)⋅:E×E→E,(x,y)↦x⋅y(Multiplikation)\begin{aligned} +:& \quad \mathbb{E} \times \mathbb{E} \to \mathbb{E}, \quad (x,y) \mapsto x + y \quad\quad &\text{(Addition)}\\ \cdot:& \quad \mathbb{E} \times \mathbb{E} \to \mathbb{E}, \quad (x,y) \mapsto x \cdot y \quad\quad &\text{(Multiplikation)} \end{aligned}

heisst Körper, wenn ∀x,y,z∈E\forall x,y,z \in \mathbb{E} folgendes gilt:

K1 E\mathbb{E} zusammen mit der Addition ++ ist eine abelsche Gruppe.
(Ihr neutrales Element wird mit 00, das zu a∈Ea \in \mathbb{E} inverse Element mit −a-a bezeichnet; vgl. Diskrete Mathematik, 5. Algebra, Definition 5.7 und 5.8: ⟨E;+⟩\langle \mathbb{E}; + \rangle is an abelian group):

  • (i) (Assoziativität) (x+y)+z=x+(y+z)\quad (x+y)+z = x+(y+z)
  • (ii) (Neutrales Element) ∃e∈E:x+e=e+x=x\quad \exists e \in \mathbb{E}: \quad x + e = e + x = x
  • (iii) (Inverses Element) ∃x′∈E:x+x′=x′+x=e\quad \exists x' \in \mathbb{E}: \quad x+x'=x'+x= e
  • (iv) (Abelsch ⇔\Leftrightarrow Kommutativität) x+y=y+x\quad x+y = y+x

K2 Bezeichnet E∗:=E∖{0}\mathbb{E}^* := \mathbb{E} \setminus \{0\}, so gilt für x,y∈E∗x,y \in \mathbb{E}^* auch x⋅y∈E∗x\cdot y \in \mathbb{E}^*, und E∗\mathbb{E}^* zusammen mit der so erhaltenen Multiplikation ist eine abelsche Gruppe.
(Ihr neutrales Element wird mit 11, das zu x∈E∗x \in \mathbb{E}^* inverse Element mit x−1x^{-1} oder 1/x1/x bezeichnet. Man schreibt y/x=x−1y=yx−1y/x =x^{-1}y=yx^{-1}.
Vgl. Diskrete Mathematik, 5. Algebra, Definition 5.7 und 5.8: ⟨E;⋅⟩\langle \mathbb{E}; \cdot \rangle is an abelian group)

(vgl. Diskrete Mathematik, 5. Algebra: Definition 5.26 und Theorem 5.23)

Bemerkung

Meistens werden wir mit den Körpern R\mathbb{R} oder C\mathbb{C} arbeiten. Ein weiterer Körper der für uns Informatiker bekannt ist, ist der kleinste endliche Körper Z2\mathbb{Z}_2, der nur {0,1}\{0,1\} enthält.

Definition

Ein Vektorraum VV über E\mathbb{E} (oder auch E\mathbb{E}-Vektorraum; VR) ist eine nichtleere Menge VV zusammen mit zwei Operationen:

+:V×V→V,(x,y)↦x+y(Addition)⋅:E×V→V,(α,x)↦αx(Skalarmultiplikation)\begin{aligned} +:& \quad V \times V \to V, \quad (x,y) \mapsto x + y \quad\quad &\text{(Addition)}\\ \cdot:& \quad \mathbb{E} \times V \to V, \quad (\alpha,x) \mapsto \alpha x \quad\quad &\text{(Skalarmultiplikation)} \end{aligned}

so dass ∀x,y,z∈V\forall x,y,z \in V und ∀α,β∈E\forall \alpha, \beta \in \mathbb{E} gilt:

V1 VV zusammen mit der Addition ist eine abelsche (kommutative) Gruppe (das neutrale Element heißt Nullvektor, es wird mit 0\boldsymbol{0}, und das Negative wird mit −x-x bezeichnet; vgl. Diskrete Mathematik, 5. Algebra: ⟨V;+⟩\langle V; + \rangle is an abelian group):

  • (i) (Assoziativität) (x+y)+z=x+(y+z)\quad (x+y)+z = x+(y+z)
  • (ii) (Neutrales Element) ∃e∈V:x+e=e+x=x\quad \exists e \in V: \quad x + e = e + x = x
  • (iii) (Inverses Element) ∃x′∈V:x+x′=x′+x=e\quad \exists x' \in V: \quad x+x'=x'+x= e
  • (iv) (Abelsch ⇔\Leftrightarrow Kommutativität) x+y=y+x\quad x+y = y+x

V2 Die Multiplikation mit Skalaren muss in folgender Weise mit den anderen Verknüpfungen verträglich sein:

  • (i) (Distributivität I) (α+β)x=αx+βx\quad (\alpha + \beta) x = \alpha x + \beta x
  • (ii) (Distributivität II) α(x+y)=αx+αy\quad \alpha (x+y) = \alpha x + \alpha y
  • (iii) (Assoziativität) (αβ)x=α(βx)\quad (\alpha \beta) x = \alpha (\beta x)
  • (iv) (Verträglichkeit mit 11) 1x=x\quad 1x = x
Beispiel 3
  1. nn-dimensionale Vektoren bilden über E\mathbb{E} einen Vektorraum.
  2. m×nm \times n-Matrizen bilden über E\mathbb{E} einen Vektorraum.
  3. Pn:={\mathcal{P}_n := \{Polynome in einer Variablen mit Koeffizienten in E\mathbb{E} von max. Grad n}n \} bilden über E\mathbb{E} einen Vektorraum.
Definition

Sei VV ein Vektorraum, U⊆V, U≠{}U \subseteq V, \, U \neq \{\}. UU heisst Untervektorraum, Unterraum, linearer Teilraum (UVR), falls sie bezüglich Addition und skalarer Multiplikation abgeschlossen ist, d.h. wenn ∀x,y∈U\forall x,y \in U und ∀α∈E\forall \alpha \in \mathbb{E} gilt:

U1 x+y∈Ux + y \in U

U2 αx∈U\alpha x \in U.

Bemerkung

Jeder Untervektorraum UU enthält den Nullvektor, d.h.

U0 0∈U\boldsymbol{0} \in U.

Satz

Jeder Untervektorraum ist ein Vektorraum.

Beispiel 4

Zu zeigen: W={(x1x2x3)∈R3∣x1+x2+x3=0}W = \left\{ \left. \begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix} \in \mathbb{R}^3 \right| x_1+x_2+x_3 = 0 \right\} ist ein Vektorraum.

Bemerkung
Wir haben zwei Optionen:

  1. Überprüfe ob V1 und V2 von der Vektorraum Definition erfüllt sind
  2. Verwende den Satz von oben und zeige nur U1 und U2
Lösung anzeigenLösung ausblenden

Beweis:
Wir führen den Beweis mit der zweiten Option durch. Also genügt es nach dem Satz zu zeigen, dass WW ein Untervektorraum ist.
Seien x=(x1x2x3),y=(y1y2y3)∈W,λ∈Ex = \begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix}, y = \begin{pmatrix} y_1\\ y_2\\ y_3 \end{pmatrix} \in W, \lambda \in \mathbb{E}

U0 (000)∈W\begin{pmatrix} 0\\ 0\\ 0 \end{pmatrix} \in W, da 0+0+0=00+0+0=0, (U0 folgt trivialerweise)

U1 x+y=(x1+y1x2+y2x3+y3)∈Wx+y = \begin{pmatrix} x_1+y_1\\ x_2+y_2\\ x_3+y_3 \end{pmatrix} \in W,
da (x1+y1)+(x2+y2)+(x3+y3)=(x1+x2+x3)⏟x1+x2+x3=0+(y1+y2+y3)⏟y1+y2+y3=0=0(x_1+y_1)+(x_2+y_2)+(x_3+y_3) = \underbrace{(x_1+x_2+x_3)}_{x_1+x_2+x_3=0} + \underbrace{(y_1+y_2+y_3)}_{y_1+y_2+y_3 = 0} = 0

U2 λx=(λx1λx2λx3)∈W\lambda x = \begin{pmatrix} \lambda x_1\\ \lambda x_2\\ \lambda x_3 \end{pmatrix} \in W, da λx1+λx2+λx3=λ(x1+x2+x3)⏟x1+x2+x3=0=0\lambda x_1 + \lambda x_2 + \lambda x_3 = \lambda \underbrace{(x_1+x_2+x_3)}_{x_1+x_2+x_3=0} = 0

Oder statt, dass ihr U1 und U2 separat zeigt könnt ihr auch die "all in one" Variante zeigen:

U1/U2 x−λy=(x1−λy1x2−λy2x3−λy3)∈Wx-\lambda y = \begin{pmatrix} x_1 - \lambda y_1\\ x_2 - \lambda y_2\\ x_3 - \lambda y_3 \end{pmatrix} \in W,
da (x1−λy1)+(x2−λy2)+(x3−λy3)=(x1+x2+x3)⏟x1+x2+x3=0−λ(y1+y2+y3)⏟y1+y2+y3=0=0□(x_1 - \lambda y_1) + (x_2 - \lambda y_2) + (x_3 - \lambda y_3) = \underbrace{(x_1+x_2+x_3)}_{x_1+x_2+x_3=0} - \lambda \underbrace{(y_1+y_2+y_3)}_{y_1+y_2+y_3 = 0} = 0 \quad\quad\quad\quad \square

Injektivität, Surjektivität, Bijektivität

Definition

Eine Abbildung f:X→Yf: X \to Y heisst injektiv, falls

∀x1,x2∈X:x1≠x2⇒f(x1)≠f(x2).\forall x_1,x_2 \in X: \quad x_1 \neq x_2 \quad \Rightarrow \quad f(x_1) \neq f(x_2).

(In Worten: Verschiedene Elemente aus XX werden auf verschiedene Bilder in YY abgebildet.)

Definition

Eine Abbildung f:X→Yf: X \to Y heisst surjektiv, falls

∀y∈Y ∃x∈X:f(x)=y.\forall y \in Y \, \exists x \in X: \quad f(x) = y.

(In Worten: Jedes Element aus YY wird von ff "getroffen".)

Definition

Eine Abbildung f:X→Yf: X \to Y heisst bijektiv, falls

∀y∈Y ∃!x∈X:f(x)=y.\forall y \in Y \, \exists \boldsymbol{!} x \in X: \quad f(x) = y.

(In Worten: Jedes Element aus YY wird von ff genau einmal "getroffen".)