Die Matrix A∈En×n ist orthogonal/unitär genau dann, wenn die Zeilen von A paarweise orthonormal (bezüglich dem Standardskalarprodukt) zueinander stehen und die Spalten von A paarweise orthonormal (bezüglich dem Standardskalarprodukt) zueinander stehen.
Definition
Eine komplexe n×n - Matrix A heisst unitär, falls AHA=AAH=𝟙.
Eine reelle n×n - Matrix A heisst orthogonal, falls ATA=AAT=𝟙.
Bemerkung
Der Begriff der orthogonalen/unitären Matrizen A∈En×n ist unabhängig vom Skalarprodukt (per Definition vom euklidischen Skalarprodukt, d.h. AAH=AHA=𝟙). Der Begriff der orthogonalen Vektoren ist hingegen abhängig vom betrachteten Skalarprodukt ⟨⋅,⋅⟩V.
Bemerkung
Warnung: Diese Bemerkung ist ein Gedankenspiel und dient zur Vertiefung des bereits erworbenen Verständnisses.
Würde man die Definition von der orthogonalen/unitären Matrix auf ein allgemeines Skalarprodukt ⟨⋅,⋅⟩M erweitern, würde man folgendes erhalten:
AMAH=AHMA=𝟙
Die Matrix M des M-Skalarprodukts wird wie folgt berechnet, falls das Skalarprodukt bereits gegeben ist:
Für das Standard-Skalarprodukt würde man dann folgendes erhalten:
A𝟙AH=AH𝟙A=𝟙⇔AAH=AHA=𝟙
Beispiel 1
Betrachte das M-Skalarprodukt für symmetrisch positiv definites M∈Rn×n:
⟨v,w⟩M:=vTMw
Dann steht v senkrecht auf w bezüglich ⟨⋅,⋅⟩M⇔vTMw=0.
Beispiel 2
Gegeben: ONB (bezüglich dem Standardskalarprodukt) A,B mit
A={(10),(01)},B={(5354),(−5453)}.
Gesucht: TBA und TAB
Lösung anzeigenLösung ausblendenTAB=(5354−5453) ist orthogonal mit (TAB)−1=(TAB)TTBA=(TAB)−1=(TAB)T=(53−545453)
⇒ Bei orthogonalen/unitären Matrizen ist es einfach die Inverse zu bestimmen, d.h. hat man TAB erhält man sofort TBA.
Methode der kleinsten Quadrate
BemerkungIdee
Wir betrachten für A∈Em×n,m>n das überbestimmte LGS Ax=y. Oftmals haben solche LGS keine (exakten) Lösungen, daher löst man sie mit Hilfe von Näherungsverfahren, wobei ein Fehler entsteht.
Die Methode der kleinsten Quadrate (manchmal auch als lineare Ausgleichsrechnung bezeichnet) versucht den Fehler zu minimieren. Der Residuenvektor (das Residuum, der Fehler) r:=y−Ax soll minimale euklidische Norm haben, d.h. wir suchen x∈Rn, so dass
∥r∥22=k=1∑m∣rk∣2=k=1∑m∣yk−l=1∑naklxl∣2
minimal ist.
Bemerkung
Die Methode der kleinsten Quadrate lässt sich auf allgemeine Normen erweitern. (Beispiel: HS17 S10A2)
Bemerkung
Betrachte für A∈Em×n,m>n das überbestimmte LGS
Ax=!y
Methode der kleinsten Quadrate: Finde x∈En, so dass Residuum r=y−Ax minimale Norm hat. Formal ausgedrückt:
x∈Enargmin∥y−Ax∥2
Lösungsansatz:
Normalengleichung
QR-Zerlegung
Normalengleichung
Lemma 7.3
Sind die Kolonnen einer A∈Em×n Matrix linear unabhängig, d.h. ist rang(A)=n(≤m), so ist AHA regulär.
Satz 7.4
Die Orthogonalprojektion PA:Em→ Im(A)⊂Em auf den Kolonnenraum Im(A) einer A∈Em×n Matrix mit Rang n(≤m) ist gegeben durch:
PA:=A(AHA)−1AH.
Satz 7.6
Für eine Orthogonalprojektion P∈En×n gilt:
∥y−Py∥2=z∈Im(P)min∥y−z∥2,∀y∈En
Bemerkung
Angenommen die Kolonnen von A∈Em×n sind linear unabhängig, also ker(A)={0} gilt und AHA gemäss Lemma 7.3 regulär ist. Auf Grund von Satz 7.6 wissen wir, dass ∥r∥ minimal ist, wenn gilt:
Es sei A∈Em×n, rang(A)=n≤m,y∈Em. Dann hat das überbestimmte Gleichungssystem Ax=y eine eindeutig bestimmte Lösung x im Sinne der kleinsten Quadrate, d.h. x mit
∥y−Ax∥22=x∈Enmin∥y−Ax∥22,x∈En(1)
x kann berechnet werden durch Lösen des regulären Systems der Normalgleichungen (Bemerkung nach Satz 7.6). Der Residuenvektor r⊥ Im(A).
Beispiel 3
Gegeben:
A=01213−2,⇒m=3>2=n,y=224
Gesucht: Bestimme mit Hilfe der Normalengleichung x=(x1,x2)T, so dass ∥r∥22=∥y−Ax∥22 minimal ist bezüglich dem Standard-Skalarprodukt ⟨x,y⟩=xHy.
AHA ist hermitesch positiv definit ⇒ kann für Cholesky-Zerlegung ausgenutzt werden
Con:
Wenn A schlecht konditioniert ist, ist AHA quadratisch schlecht konditioniert. ⇒ Cholesky liefert unbrauchbare Resultate (Rundungsfehler massiv verstärkt, Implementierung instabil)
QR-Zerlegung
Pro:
kann numerisch stabil implementiert werden (Verfahren hängt weniger von der Kondition ab)
Die Spalten von Q bilden eine ONB von Im(A) (die Orthogonalprojektion auf Im(A) ist QQH)
Con:
"hässlich", um von Hand zu rechnen (Wurzeln)
Symmetrische Gruppe
Definition
Eine Permutation ist eine bijektive Abbildung:
p:{1,...,n}→{1,...,n}
Definition
Die Menge aller Permutationen heisst symmetrische GruppeSn.
Definition
Eine Permutation, welche nur zwei Elemente vertauscht, heisst Transposition.
Satz
Jede Permutation kann als Produkt (Hintereinanderschaltung von Abbildungen) von Transpositionen geschrieben werden.
Bemerkung
Die Darstellung einer Permutation als Produkt von Transpositionen ist nicht eindeutig. Aber die Anzahl benötigter Transpositionen ist eindeutigerweise entweder gerade oder ungerade.
Definition
Ist p∈Sn, so nennt man jedes Paar i,j∈{1,...,n} mit
i<jaberp(i)>p(j),
einen Fehlstand von p.
Beispiel 5
Gegeben:
p=[122331]
Gesucht: Fehlstände von p
Definition
Das Signum einer Permutation ist definiert als
sign(p)=(−1)k={1,falls p eine gerade Anzahl k von Fehlsta¨nden hat−1,falls p eine ungerade Anzahl k von Fehlsta¨nden hat.
Definition
Man nennt p∈Sn:
gerade, falls sign(p)=+1,
ungerade, falls sign(p)=−1.
Determinanten
Definition
Die Determinante ist eine Abbildung:
det:En×nA→E↦det(A)=p∈Sn∑sign(p)⋅i=1∏naip(i)
Bemerkung
In der obigen Definition summieren wir über n! Summanden.
Es wird das folgende Muster bei der Regel von Sarrus angewendet:
+adg−+beh−+cfi−adgbeh
Bemerkung
Für eine n×n-Matrix kann man die Determinante über die Definition mit Permutationen berechnen, aber ist sehr ineffizient (Aufwand proportional zu n!).
Satz
Sei A die Zeilenstufenform von A (d.h. A ist eine obere/untere Dreiecksmatrix), welche man durch den Gauss-Algorithmus aus A berechnet hat. Sei k∈N0 die Anzahl ausgeführter Zeilenvertauschungen:
⇒det(A)=(−1)k⋅det(A)=(−1)ki=1∏nAii,wobei i=1∏nAii das Produkt der Diagonaleintra¨ge ist.
Satz
Laplace’scher Entwicklungssatz
Sei A∈En×n und Aij′∈E(n−1)×(n−1) die Streichmatrix ohne i-te Zeile und j-te Spalte.
⇒Entwicklung nach der i-ten Zeile: det(A)=j=1∑n(−1)i+j⋅aij⋅det(Aij′)⇒Entwicklung nach der j-ten Spalte: det(A)=i=1∑n(−1)i+j⋅aij⋅det(Aij′).
Beispiel 6
Gegeben:
A=1312−10005
Gesucht: det(A)
SatzAxiomatischer Zugang, Eigenschaften der Determinante
Die Abbildung
det:En×nA→E↦det(A)
heisst Determinante, falls folgende Eigenschaften gelten:
Sei A∈En×n eine quadratische Matrix, dann gilt:
(D1)det(𝟙)=1
(D2) Hat A zwei gleiche oder linear abhängige Zeilen/Spalten, so ist
det(A)=0
(D3) Linearität in jeder Zeile/Spalte (in der Literatur auch n-Linearität genannt)
Zu jedem Element akl einer n×n-Matrix A werde die (n−1)×(n−1)-Untermatrix A[k,l] definiert durch Streichen der Zeile k und der Kolonne l von A. Der Kofaktorκkl von akl ist dann die Zahl:
κkl:=(−1)k+l det(A[k,l]).
Definition
Der Graddj des Knotens j ist wie folgt definiert:
dj:=i=1∑n(A)ij.
SatzSatz von Kirchhoff
Der Satz von Kirchhoff besagt, dass die Anzahl der aufspannenden Teilbäume eines Graphen gleich dem Wert eines beliebigen Kofaktors von L ist, wobei L wie folgt definiert ist:
L:=D−Amit D=diag(d1,...,dn),di=^ Grad des Knotens iundA=^ Adjazenzmatrix mit (Aij)={1,0,falls i mit j durch eine Kante verbunden ist sonst.