Bei grossen Gleichungssystemen Ax=b mit A∈En×n und b,x∈En ist die Lösung x meist nicht einfach zu finden. Daher wollen wir A gerne in eine einfachere Form von Dreiecksmatrizen zerlegen, d.h.
Wir suchen Matrizen P,L,R∈En×n so dass PA=LR,
PLR (engl. U)=^ ist eine Permutationsmatrix (entha¨lt nur 1 und 0)=^ ist eine linke Dreiecksmatrix (engl. lower triangular matrix)=^ ist eine rechte Dreiecksmatrix (engl. upper triangular matrix)L=1∗⋮∗0⋱⋱⋯⋯⋱⋱∗0⋮01R=∗0⋮0⋯⋱⋱⋯⋯⋱⋱0∗⋮∗
Bemerkung
Seien A,P,L,R∈En×n. P speichert die Zeilenvertauschungen, die man für die Pivotisierung braucht, L speichert die Umformungsschritte, um A in eine Zeilenstufenform zu verwandeln, R ist die Zeilenstufenform von A.
Bemerkung
Seien A,P,L,R∈En×n und b,c,x∈En.
Das anfängliche System Ax=b lässt sich nun einfacher lösen:
Löse Lc=Pb nach c durch Vorwärtseinsetzen, d.h. (L∣Pb) von oben nach unten "Gaussen".
Löse Rx=c nach x durch Rückwärtseinsetzen, d.h. (R∣c) von unten nach oben "Gaussen".
Bemerkung
Dass die Beziehung aus der obigen Bemerkung für A,P,P−1,L,R∈En×n die richtige Lösung x∈En liefert, sieht man auch daraus, dass
Ax=P−1PAx=P−1LRx=P−1Lc=P−1Pb=b.
Satz
Für eine reguläre, quadratische Matrix A∈En×n existiert eine LR-Zerlegung, d.h.
∃P,L,R∈En×n:PA=LR.
BemerkungLR-Zerlegung light (d.h. ohne Pivotisierung)
Annahme: keine Zeilenvertauschungen nötig und A hat keine Nullspalte
Gegeben: A∈En×n
Gesucht: L∈En×n,R∈En×n so dass gilt: A=LR
Schreibe das Schema (A∣𝟙)
Forme A 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.
Auf der rechten Seite schreibt ihr die Verhältnisse auf:
BemerkungLR-Zerlegung full (d.h. mit Pivotisierung)
Gegeben: A∈En×n
Gesucht: P∈Rn×n,L∈En×n,R∈En×n so dass gilt: PA=LR
Schreibe das Schema (𝟙∣A∣𝟙). Links merkt ihr euch die Zeilenvertauschungen, in der Mitte "Gausst" ihr und rechts merkt ihr euch die Verhältnisse.
Pivotisiere in der aktuellen Spalte j, d.h. bestimme den Index ip∈{j,j+1,...,n} mit ∣aipj∣=i∈{j,j+1,...,n}max∣aij∣. Falls ∣aipj∣=0 breche ab, es existiert keine LR-Zerlegung. Sonst berechne PijA=A in der Mitte, wobei Pij∈Rn×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∣𝟙)
Sonst, sieht das Resultat vom Schritt wie folgt aus:
Forme A 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".
Auf der rechten Seite schreibt ihr die Verhältnisse auf:
K1E zusammen mit der Addition + ist eine abelsche Gruppe.
(Ihr neutrales Element wird mit 0, das zu a∈E inverse Element mit −a bezeichnet; vgl. Diskrete Mathematik, 5. Algebra, Definition 5.7 und 5.8: ⟨E;+⟩ is an abelian group):
(i) (Assoziativität) (x+y)+z=x+(y+z)
(ii) (Neutrales Element) ∃e∈E:x+e=e+x=x
(iii) (Inverses Element) ∃x′∈E:x+x′=x′+x=e
(iv) (Abelsch ⇔ Kommutativität) x+y=y+x
K2 Bezeichnet E∗:=E∖{0}, so gilt für x,y∈E∗ auch x⋅y∈E∗, und E∗ zusammen mit der so erhaltenen Multiplikation ist eine abelsche Gruppe.
(Ihr neutrales Element wird mit 1, das zu x∈E∗ inverse Element mit x−1 oder 1/x bezeichnet. Man schreibt y/x=x−1y=yx−1.
Vgl. Diskrete Mathematik, 5. Algebra, Definition 5.7 und 5.8: ⟨E;⋅⟩ 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 oder C arbeiten. Ein weiterer Körper der für uns Informatiker bekannt ist, ist der kleinste endliche Körper Z2, der nur {0,1} enthält.
Definition
Ein VektorraumV über E (oder auch E-Vektorraum; VR) ist eine nichtleere Menge V zusammen mit zwei Operationen:
V1V zusammen mit der Addition ist eine abelsche (kommutative) Gruppe (das neutrale Element heißt Nullvektor, es wird mit 0, und das Negative wird mit −x bezeichnet; vgl. Diskrete Mathematik, 5. Algebra: ⟨V;+⟩ is an abelian group):
(i) (Assoziativität) (x+y)+z=x+(y+z)
(ii) (Neutrales Element) ∃e∈V:x+e=e+x=x
(iii) (Inverses Element) ∃x′∈V:x+x′=x′+x=e
(iv) (Abelsch ⇔ Kommutativität) 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
(ii) (Distributivität II) α(x+y)=αx+αy
(iii) (Assoziativität) (αβ)x=α(βx)
(iv) (Verträglichkeit mit 1) 1x=x
Beispiel 3
n-dimensionale Vektoren bilden über E einen Vektorraum.
m×n-Matrizen bilden über E einen Vektorraum.
Pn:={Polynome in einer Variablen mit Koeffizienten in E von max. Grad n} bilden über E einen Vektorraum.
Definition
Sei V ein Vektorraum, U⊆V,U={}. U heisst Untervektorraum, Unterraum, linearer Teilraum (UVR), falls sie bezüglich Addition und skalarer Multiplikation abgeschlossen ist, d.h. wenn ∀x,y∈U und ∀α∈E gilt:
U1x+y∈U
U2αx∈U.
Bemerkung
Jeder Untervektorraum U enthält den Nullvektor, d.h.
U00∈U.
Satz
Jeder Untervektorraum ist ein Vektorraum.
Beispiel 4
Zu zeigen:W=⎩⎨⎧x1x2x3∈R3x1+x2+x3=0⎭⎬⎫ ist ein Vektorraum.
Bemerkung
Wir haben zwei Optionen:
Überprüfe ob V1 und V2 von der Vektorraum Definition erfüllt sind
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 W ein Untervektorraum ist.
Seien x=x1x2x3,y=y1y2y3∈W,λ∈E
U0000∈W, da 0+0+0=0, (U0 folgt trivialerweise)
U1x+y=x1+y1x2+y2x3+y3∈W,
da (x1+y1)+(x2+y2)+(x3+y3)=x1+x2+x3=0(x1+x2+x3)+y1+y2+y3=0(y1+y2+y3)=0
U2λx=λx1λx2λx3∈W, da λx1+λx2+λx3=λx1+x2+x3=0(x1+x2+x3)=0
Oder statt, dass ihr U1 und U2 separat zeigt könnt ihr auch die "all in one" Variante zeigen:
U1/U2x−λy=x1−λy1x2−λy2x3−λy3∈W,
da (x1−λy1)+(x2−λy2)+(x3−λy3)=x1+x2+x3=0(x1+x2+x3)−λy1+y2+y3=0(y1+y2+y3)=0□
Injektivität, Surjektivität, Bijektivität
Definition
Eine Abbildung f:X→Y heisst injektiv, falls
∀x1,x2∈X:x1=x2⇒f(x1)=f(x2).
(In Worten: Verschiedene Elemente aus X werden auf verschiedene Bilder in Y abgebildet.)
Definition
Eine Abbildung f:X→Y heisst surjektiv, falls
∀y∈Y∃x∈X:f(x)=y.
(In Worten: Jedes Element aus Y wird von f "getroffen".)
Definition
Eine Abbildung f:X→Y heisst bijektiv, falls
∀y∈Y∃!x∈X:f(x)=y.
(In Worten: Jedes Element aus Y wird von fgenau einmal "getroffen".)