Upload
others
View
4
Download
0
Embed Size (px)
Citation preview
Matrixzerlegungen.Überbestimmte Systeme
6. Vorlesung170 004 Numerische Methoden I
Clemens Brand und Erika Hausenblas
Montanuniversität Leoben
27. März 2014
Gliederung
1 MatrixzerlegungenLinks-Rechts-ZerlegungOrthogonale MatrizenQR-ZerlegungSingulärwertzerlegung
2 Überbestimmte SystemeKleinste QuadrateLösung durch QR-Zerlegung
3 Beispiele für überbestimmte SystemeLineare ModelleNichtlineare Systeme
Gliederung
1 MatrixzerlegungenLinks-Rechts-ZerlegungOrthogonale MatrizenQR-ZerlegungSingulärwertzerlegung
2 Überbestimmte SystemeKleinste QuadrateLösung durch QR-Zerlegung
3 Beispiele für überbestimmte SystemeLineare ModelleNichtlineare Systeme
C.B & E.H. (MUL) Matrixzerlegungen, Überbest. Systeme 20.III.2014 3 / 36
Die Matrix-Vektor-Multiplikation y = A · xGrundlegende Bedeutung einer n ×m-Matrix A
Eine Matrix definiert durch y = A · x eine lineare Abbildung Rm → R
n.
„Der Hauptberuf einer Matrix ist, aus einem Vektor einen anderen zumachen“
Im Allgemeinen ändert die Matrix dadurch Richtung, Betrag (und sogarDimension) eines Vektors. Matrixzerlegungen spalten die Aktion der Matrixin leichter zu durchblickende Einzelschritte auf.
• Links-Rechts-Zerlegung A = L · R• QR-Zerlegung A = Q · R• Singulärwertzerlegung A = U · S · V T
Die Matrix-Vektor-Multiplikation y = A · xGrundlegende Bedeutung einer n ×m-Matrix A
Eine Matrix definiert durch y = A · x eine lineare Abbildung Rm → R
n.
„Der Hauptberuf einer Matrix ist, aus einem Vektor einen anderen zumachen“
Im Allgemeinen ändert die Matrix dadurch Richtung, Betrag (und sogarDimension) eines Vektors. Matrixzerlegungen spalten die Aktion der Matrixin leichter zu durchblickende Einzelschritte auf.
• Links-Rechts-Zerlegung A = L · R• QR-Zerlegung A = Q · R• Singulärwertzerlegung A = U · S · V T
Die Matrix-Vektor-Multiplikation y = A · xGrundlegende Bedeutung einer n ×m-Matrix A
Eine Matrix definiert durch y = A · x eine lineare Abbildung Rm → R
n.
„Der Hauptberuf einer Matrix ist, aus einem Vektor einen anderen zumachen“
Im Allgemeinen ändert die Matrix dadurch Richtung, Betrag (und sogarDimension) eines Vektors. Matrixzerlegungen spalten die Aktion der Matrixin leichter zu durchblickende Einzelschritte auf.
• Links-Rechts-Zerlegung A = L · R• QR-Zerlegung A = Q · R• Singulärwertzerlegung A = U · S · V T
Wiederholung: LR-Zerlegung A = L · R
Das Gaußsche Eliminationsverfahren ohne Pivotisierung faktorisiert (wennes nicht abbricht) eine Matrix A in ein Produkt A = LR aus einer linkenunteren Dreiecksmatrix L und einer rechten oberen Dreiecksmatrix R .
5 6 710 20 2315 50 67
=
1 0 02 1 03 4 1
·
5 6 70 8 90 0 10
LR-Zerlegung allgemein
Jede quadratische oder auch rechteckige Matrix lässt sich in ein Produktder Form
A = L · Rzerlegen. Dabei ist
• L eine links-unten-Dreiecksmatrix mit 1-Diagonale (zumindest, wennman die Zeilen von L passend umordnet)
• R eine obere Dreiecksmatrix
MATLAB: [L U]=lu(A) zerlegt beispielsweise
[
1 2 34 5 6
]
=
[
1
41
1 0
]
·[
4 5 60 3
4
3
2
]
Anwendungen zur LR-Zerlegung
• lineare Gleichungssysteme
• Determinante
• Inverse
MATLAB-Hilfe: “Most of the algorithms for computing LU factorization arevariants of Gaussian elimination. The factorization is a key step inobtaining the inverse with inv and the determinant with det. It is also thebasis for the linear equation solution obtained with \”
Orthogonale MatrizenTransponierte ist zugleich Inverse
Definition
Eine quadratische Matrix Q heißt orthogonal, wenn gilt
QT · Q = I
Die Spalten von Q sind Einheitsvektoren und paarweise orthogonal. Es giltdann auch
Q · QT = I
Die Zeilen von Q sind ebenfalls Einheitsvektoren und paarweise orthogonal.
Orthogonale Matrizen: Beispiele
P =1√2
[
1 11 −1
]
, Q =13
2 −2 11 2 22 1 −2
Zwei-Drei-
}
dimensionale orthogonale Matrizen mit Determinante 1
entsprechen
{
ebenenräumlichen
}
Drehungen
Fundamentale EigenschaftMultiplikation eines Vektors mit einer orthogonalen Matrix lässt die 2-Norm desVektors unverändert
Multiplikation eines Vektors mit einer orthogonalen Matrix dreht (oderspiegelt) den Vektor, lässt aber seine Länge (2-Norm) unverändert.
‖x‖2 = ‖Q · x‖2
QR-Zerlegung
Satz
Jede reelle n×m Matrix lässt sich in ein Produkt der Form
A = Q · R
mit einer orthogonalen n × n Matrix Q und einer n ×m oberenDreiecksmatrix R zerlegen.
MATLAB: [Q R]=qr(A)
Anwendungen: Eigenwert-Berechnung, überbestimmte Systeme
Singulärwert-ZerlegungSingular Value Decomposition, SVD
Eine beliebige reelle n ×m Matrix lässt sich in ein Produkt der Form
A = U · S · V T
mit einer orthogonalen n × n Matrix U , einer n×m-Diagonalmatrix S undeiner orthogonalen m ×m Matrix V zerlegen.Die Diagonalwerte von S heißen die Singulärwerte von A.MATLAB: [U S V]=svd(A)
Anwendungen
Rang einer numerischen Matrix, Pseudoinverse, Über- und unterbestimmteSysteme etc. etc.
Singulärwert-ZerlegungAnschauliche Interpretation
Die Singulärwertzerlegung A = U · S · V T zerlegt die Multiplikation A · x indrei Einzelschritte:
• a = V T · x dreht den Vektor x
• b = S · a skaliert die Komponenten von a
• y = U · b dreht den Vektor b
Abgesehen von den beiden Drehungen beschreibt die Diagonalmatrix S ,was die die Matrix A „eigentlich“ tut.
In geeignet gedrehten Koordinaten wird aus A eine Diagonalmatrix S .Der richtige Dreh vereinfacht viele Aufgaben.
Singulärwert-ZerlegungAnschauliche Interpretation
Die Singulärwertzerlegung A = U · S · V T zerlegt die Multiplikation A · x indrei Einzelschritte:
• a = V T · x dreht den Vektor x
• b = S · a skaliert die Komponenten von a
• y = U · b dreht den Vektor b
Abgesehen von den beiden Drehungen beschreibt die Diagonalmatrix S ,was die die Matrix A „eigentlich“ tut.
In geeignet gedrehten Koordinaten wird aus A eine Diagonalmatrix S .Der richtige Dreh vereinfacht viele Aufgaben.
Diagonalisierung symmetrischer MatrizenEin Spezialfall von SVD
Jede symmetrische Matrix A lässt sich in der Form A = Q · D · QT
zerlegen; dabei ist Q eine Orthogonal- und D eine Diagonalmatrix
Die Bedeutung dieser Zerlegung diskutieren wir genauer im Kapitel„Eigenwerte und Eigenvektoren“.
Gliederung
1 MatrixzerlegungenLinks-Rechts-ZerlegungOrthogonale MatrizenQR-ZerlegungSingulärwertzerlegung
2 Überbestimmte SystemeKleinste QuadrateLösung durch QR-Zerlegung
3 Beispiele für überbestimmte SystemeLineare ModelleNichtlineare Systeme
C.B & E.H. (MUL) Matrixzerlegungen, Überbest. Systeme 20.III.2014 15 / 36
Überbestimmte SystemeEin lineares Gleichungssystem mit mehr Gleichungen als Unbekannten heißtüberbestimmt
x = 1y = 2
x + y = 4
1 00 11 1
·[
x
y
]
=
124
Allgemein: ein überbestimmtes lineares System
Ax = b mit einer m × n-Matrix A, wobei m > n
• In der Regel hat ein solches System keine (exakte) Lösung.• (Kompromiss-)Lösung sucht möglichst kleinen Residuenvektor
r = b− Ax
• Klassische kleinste-Quadrate-Lösung mit Normalengleichungen
ATAx = ATb
C.B & E.H. (MUL) Matrixzerlegungen, Überbest. Systeme 20.III.2014 16 / 36
Überbestimmte SystemeEin lineares Gleichungssystem mit mehr Gleichungen als Unbekannten heißtüberbestimmt
x = 1y = 2
x + y = 4
1 00 11 1
·[
x
y
]
=
124
Allgemein: ein überbestimmtes lineares System
Ax = b mit einer m × n-Matrix A, wobei m > n
• In der Regel hat ein solches System keine (exakte) Lösung.• (Kompromiss-)Lösung sucht möglichst kleinen Residuenvektor
r = b− Ax
• Klassische kleinste-Quadrate-Lösung mit Normalengleichungen
ATAx = ATb
C.B & E.H. (MUL) Matrixzerlegungen, Überbest. Systeme 20.III.2014 16 / 36
Überbestimmte SystemeEin lineares Gleichungssystem mit mehr Gleichungen als Unbekannten heißtüberbestimmt
x = 1y = 2
x + y = 4
1 00 11 1
·[
x
y
]
=
124
Allgemein: ein überbestimmtes lineares System
Ax = b mit einer m × n-Matrix A, wobei m > n
• In der Regel hat ein solches System keine (exakte) Lösung.• (Kompromiss-)Lösung sucht möglichst kleinen Residuenvektor
r = b− Ax
• Klassische kleinste-Quadrate-Lösung mit Normalengleichungen
ATAx = ATb
C.B & E.H. (MUL) Matrixzerlegungen, Überbest. Systeme 20.III.2014 16 / 36
Überbestimmte SystemeEin lineares Gleichungssystem mit mehr Gleichungen als Unbekannten heißtüberbestimmt
x = 1y = 2
x + y = 4
1 00 11 1
·[
x
y
]
=
124
Allgemein: ein überbestimmtes lineares System
Ax = b mit einer m × n-Matrix A, wobei m > n
• In der Regel hat ein solches System keine (exakte) Lösung.• (Kompromiss-)Lösung sucht möglichst kleinen Residuenvektor
r = b− Ax
• Klassische kleinste-Quadrate-Lösung mit Normalengleichungen
ATAx = ATb
C.B & E.H. (MUL) Matrixzerlegungen, Überbest. Systeme 20.III.2014 16 / 36
Überbestimmte SystemeEin lineares Gleichungssystem mit mehr Gleichungen als Unbekannten heißtüberbestimmt
x = 1y = 2
x + y = 4
1 00 11 1
·[
x
y
]
=
124
Allgemein: ein überbestimmtes lineares System
Ax = b mit einer m × n-Matrix A, wobei m > n
• In der Regel hat ein solches System keine (exakte) Lösung.• (Kompromiss-)Lösung sucht möglichst kleinen Residuenvektor
r = b− Ax
• Klassische kleinste-Quadrate-Lösung mit Normalengleichungen
ATAx = ATb
C.B & E.H. (MUL) Matrixzerlegungen, Überbest. Systeme 20.III.2014 16 / 36
Beispiel: Wägung zweier MassenZwei Massen m1,m2 werden zuerst einzeln, dann gemeinsam abgewogen.Die Messwerte sind:
m1 = 1
m2 = 2
m1 +m2 = 4
Lösungsvorschläge?
• Letzte Gleichung weglassen: Fehler r =
001
• Fehler „aufteilen“, etwa m1 = 1,5;m2 = 2,5 → r =
−0,5−0,5
0
• oder noch fairer auf die drei Komponenten aufteilen. . .
Beispiel: Wägung zweier MassenZwei Massen m1,m2 werden zuerst einzeln, dann gemeinsam abgewogen.Die Messwerte sind:
m1 = 1
m2 = 2
m1 +m2 = 4
Lösungsvorschläge?
• Letzte Gleichung weglassen: Fehler r =
001
• Fehler „aufteilen“, etwa m1 = 1,5;m2 = 2,5 → r =
−0,5−0,5
0
• oder noch fairer auf die drei Komponenten aufteilen. . .
Beispiel: Wägung zweier MassenZwei Massen m1,m2 werden zuerst einzeln, dann gemeinsam abgewogen.Die Messwerte sind:
m1 = 1
m2 = 2
m1 +m2 = 4
Lösungsvorschläge?
• Letzte Gleichung weglassen: Fehler r =
001
• Fehler „aufteilen“, etwa m1 = 1,5;m2 = 2,5 → r =
−0,5−0,5
0
• oder noch fairer auf die drei Komponenten aufteilen. . .
Beispiel: Wägung zweier MassenZwei Massen m1,m2 werden zuerst einzeln, dann gemeinsam abgewogen.Die Messwerte sind:
m1 = 1
m2 = 2
m1 +m2 = 4
Lösungsvorschläge?
• Letzte Gleichung weglassen: Fehler r =
001
• Fehler „aufteilen“, etwa m1 = 1,5;m2 = 2,5 → r =
−0,5−0,5
0
• oder noch fairer auf die drei Komponenten aufteilen. . .
Geometrische InterpretationZeilen des Gleichungssystems sind Geradengleichungen
m1 = 1
m2 = 2
m1 +m2 = 4
Den drei Gleichungen entsprechendrei Gerade im R
2. Keingemeinsamer Schnittpunkt!„In der Mitte des Fehlerdreiecks“,im Punkt (4/3; 7/3) ist dieSumme der Fehlerquadrate
minimal.
1 2 3 4m1
1
2
3
4m2
(m1 − 1)2 + (m2 − 2)2 + (m1 +m2 − 4)2 → min!
Geometrische InterpretationZeilen des Gleichungssystems sind Geradengleichungen
m1 = 1
m2 = 2
m1 +m2 = 4
Den drei Gleichungen entsprechendrei Gerade im R
2. Keingemeinsamer Schnittpunkt!„In der Mitte des Fehlerdreiecks“,im Punkt (4/3; 7/3) ist dieSumme der Fehlerquadrate
minimal.
1 2 3 4m1
1
2
3
4m2
(m1 − 1)2 + (m2 − 2)2 + (m1 +m2 − 4)2 → min!
Geometrische InterpretationZeilen des Gleichungssystems sind Geradengleichungen
m1 = 1
m2 = 2
m1 +m2 = 4
Den drei Gleichungen entsprechendrei Gerade im R
2. Keingemeinsamer Schnittpunkt!„In der Mitte des Fehlerdreiecks“,im Punkt (4/3; 7/3) ist dieSumme der Fehlerquadrate
minimal.
1 2 3 4m1
1
2
3
4m2
(m1 − 1)2 + (m2 − 2)2 + (m1 +m2 − 4)2 → min!
Methode der kleinsten Fehlerquadrate
Suche m1,m2 so dass
(m1 − 1)2 + (m2 − 2)2 + (m1 +m2 − 4)2 → min!
Differenziere nach m1 und m2, setze Ableitungen gleich Null →
2m1 + m2 = 5m1 + 2m2 = 6
Führt man diese Rechnung allgemein für ein überbestimmtes SystemAx = b durch, erhält man die Normalengleichungen ATAx = ATb.
hier:
[
1 0 10 1 1
]
·
1 00 11 1
·[
m1
m2
]
=
[
1 0 10 1 1
]
·
124
C.B & E.H. (MUL) Matrixzerlegungen, Überbest. Systeme 20.III.2014 19 / 36
Zwei mögliche geometrische Interpretationen
Im Raum Rn der Lösungsvektoren
• Gleichungen entsprechen Geraden (Ebenen, Hyperebenen)
• Optimal-Lösung im Schnittbereich (Fehlerdreieck, -Polyeder, . . . )
• Nachteil: „Mitte des Fehlerdreiecks“ nicht exakt definiert.
Im Raum Rm der rechten-Seite-Vektoren
• Matrix mal Vektor ergibt Linearkombination der Spaltenvektoren
• Bei „zu wenig“ Spaltenvektoren lässt sich nicht jede rechte Seite alsLinearkombination erreichen.
• Der geringste Abstand zwischen Linearkombination und rechter Seiteist Normalabstand.
Eine Folie noch, dann kommt eh gleich ein Beispiel. . .
Zwei mögliche geometrische Interpretationen
Im Raum Rn der Lösungsvektoren
• Gleichungen entsprechen Geraden (Ebenen, Hyperebenen)
• Optimal-Lösung im Schnittbereich (Fehlerdreieck, -Polyeder, . . . )
• Nachteil: „Mitte des Fehlerdreiecks“ nicht exakt definiert.
Im Raum Rm der rechten-Seite-Vektoren
• Matrix mal Vektor ergibt Linearkombination der Spaltenvektoren
• Bei „zu wenig“ Spaltenvektoren lässt sich nicht jede rechte Seite alsLinearkombination erreichen.
• Der geringste Abstand zwischen Linearkombination und rechter Seiteist Normalabstand.
Eine Folie noch, dann kommt eh gleich ein Beispiel. . .
Zwei mögliche geometrische Interpretationen
Im Raum Rn der Lösungsvektoren
• Gleichungen entsprechen Geraden (Ebenen, Hyperebenen)
• Optimal-Lösung im Schnittbereich (Fehlerdreieck, -Polyeder, . . . )
• Nachteil: „Mitte des Fehlerdreiecks“ nicht exakt definiert.
Im Raum Rm der rechten-Seite-Vektoren
• Matrix mal Vektor ergibt Linearkombination der Spaltenvektoren
• Bei „zu wenig“ Spaltenvektoren lässt sich nicht jede rechte Seite alsLinearkombination erreichen.
• Der geringste Abstand zwischen Linearkombination und rechter Seiteist Normalabstand.
Eine Folie noch, dann kommt eh gleich ein Beispiel. . .
Zwei mögliche geometrische Interpretationen
Im Raum Rn der Lösungsvektoren
• Gleichungen entsprechen Geraden (Ebenen, Hyperebenen)
• Optimal-Lösung im Schnittbereich (Fehlerdreieck, -Polyeder, . . . )
• Nachteil: „Mitte des Fehlerdreiecks“ nicht exakt definiert.
Im Raum Rm der rechten-Seite-Vektoren
• Matrix mal Vektor ergibt Linearkombination der Spaltenvektoren
• Bei „zu wenig“ Spaltenvektoren lässt sich nicht jede rechte Seite alsLinearkombination erreichen.
• Der geringste Abstand zwischen Linearkombination und rechter Seiteist Normalabstand.
Eine Folie noch, dann kommt eh gleich ein Beispiel. . .
Interpretation von Ax = bZwei Möglichkeiten
Im Raum der x-Vektoren
Jede Zeile der Matrix ist ein Normalvektor in einer Geradengleichung fürx ∈ R
2, Ebenengleichung für x ∈ R3,. . .
Lösung x ist Schnittpunkt aller Geraden (Ebenen, Hyperebenen. . . )
Im Raum der b-Vektoren
Jede Spalte der Matrix A ist ein Vektor. Das Produkt Ax ist eineLinearkombination der Spaltenvektoren.Lösung x gibt genau die Koeffizienten an, mit denen sich b alsLinearkombination der Spaltenvektoren von A erreichen lässt.
Interpretation von Ax = bZwei Möglichkeiten
Im Raum der x-Vektoren
Jede Zeile der Matrix ist ein Normalvektor in einer Geradengleichung fürx ∈ R
2, Ebenengleichung für x ∈ R3,. . .
Lösung x ist Schnittpunkt aller Geraden (Ebenen, Hyperebenen. . . )
Im Raum der b-Vektoren
Jede Spalte der Matrix A ist ein Vektor. Das Produkt Ax ist eineLinearkombination der Spaltenvektoren.Lösung x gibt genau die Koeffizienten an, mit denen sich b alsLinearkombination der Spaltenvektoren von A erreichen lässt.
Interpretation von Ax = bZwei Möglichkeiten
Im Raum der x-Vektoren
Jede Zeile der Matrix ist ein Normalvektor in einer Geradengleichung fürx ∈ R
2, Ebenengleichung für x ∈ R3,. . .
Lösung x ist Schnittpunkt aller Geraden (Ebenen, Hyperebenen. . . )
Im Raum der b-Vektoren
Jede Spalte der Matrix A ist ein Vektor. Das Produkt Ax ist eineLinearkombination der Spaltenvektoren.Lösung x gibt genau die Koeffizienten an, mit denen sich b alsLinearkombination der Spaltenvektoren von A erreichen lässt.
Beispiel: Farbmischung mit RGB-VektorenWelches Grau gibt Rot und Blau?
Gegeben: zwei Farbtöne
RGB
2005050
RGB
50150200
Gesucht: neutrale Grauschattierung RGB 150 150 150
2005050
x +
50150200
y =
150150150
Optimale Lösung erreicht
2005050
0,588 +
50150200
0,674 =
151130164
Beispiel: Farbmischung mit RGB-VektorenWelches Grau gibt Rot und Blau?
Gegeben: zwei Farbtöne
RGB
2005050
RGB
50150200
Gesucht: neutrale Grauschattierung RGB 150 150 150
2005050
x +
50150200
y =
150150150
Optimale Lösung erreicht
2005050
0,588 +
50150200
0,674 =
151130164
Beispiel: Farbmischung mit RGB-VektorenWelches Grau gibt Rot und Blau?
Gegeben: zwei Farbtöne
RGB
2005050
RGB
50150200
Gesucht: neutrale Grauschattierung RGB 150 150 150
2005050
x +
50150200
y =
150150150
Optimale Lösung erreicht
2005050
0,588 +
50150200
0,674 =
151130164
Beispiel: Farbmischung mit RGB-VektorenWelches Grau gibt Rot und Blau?
Gegeben: zwei Farbtöne
RGB
2005050
RGB
50150200
Gesucht: neutrale Grauschattierung RGB 150 150 150
2005050
x +
50150200
y =
150150150
Optimale Lösung erreicht
2005050
0,588 +
50150200
0,674 =
151130164
Orthogonalitätsbedingung im Bildraum
Der Ausdruck
1 00 11 1
·[
m1
m2
]
entspricht derParameterdarstellung eine Ebeneim R
3.Der Punkt (1; 2; 4) liegt nicht aufdieser Ebene. Der Residuenvektor
r =
124
−
1 00 11 1
·[
m1
m2
]
hat minimale Länge, wenn er aufdie Ebene normal steht.
01
23
0
1
2
3
0
2
4
6
Drehe den Bildraum, dann geht’s leichter!Wenn die zwei die Ebeneaufspannenden Vektorenirgendwo hin in den R
3
zeigen, ist der Punkt mitminimalem Abstand vonb nicht so leicht zufinden. . .Drehen wir vorsichtig dasKoordinatensystem. . .bis die zwei Vektoren inder xy -Ebene liegen. DieLösung liegt nun genausenkrecht unter b
01
23
0
1
2
3
0
2
4
6
Drehe den Bildraum, dann geht’s leichter!Wenn die zwei die Ebeneaufspannenden Vektorenirgendwo hin in den R
3
zeigen, ist der Punkt mitminimalem Abstand vonb nicht so leicht zufinden. . .Drehen wir vorsichtig dasKoordinatensystem. . .bis die zwei Vektoren inder xy -Ebene liegen. DieLösung liegt nun genausenkrecht unter b
01
23
0
1
23
0
2
4
Drehe den Bildraum, dann geht’s leichter!
Wenn die zwei die Ebeneaufspannenden Vektorenirgendwo hin in den R
3
zeigen, ist der Punkt mitminimalem Abstand vonb nicht so leicht zufinden. . .Drehen wir vorsichtig dasKoordinatensystem. . .bis die zwei Vektoren inder xy -Ebene liegen. DieLösung liegt nun genausenkrecht unter b 0
12
34
0
12
34
0
1
2
3
4
Drehe den Bildraum, dann geht’s leichter!
Wenn die zwei die Ebeneaufspannenden Vektorenirgendwo hin in den R
3
zeigen, ist der Punkt mitminimalem Abstand vonb nicht so leicht zufinden. . .Drehen wir vorsichtig dasKoordinatensystem. . .bis die zwei Vektoren inder xy -Ebene liegen. DieLösung liegt nun genausenkrecht unter b
0
2
4
01
23
4
0
1
2
3
Drehe den Bildraum, dann geht’s leichter!
Wenn die zwei die Ebeneaufspannenden Vektorenirgendwo hin in den R
3
zeigen, ist der Punkt mitminimalem Abstand vonb nicht so leicht zufinden. . .Drehen wir vorsichtig dasKoordinatensystem. . .bis die zwei Vektoren inder xy -Ebene liegen. DieLösung liegt nun genausenkrecht unter b
0
2
40
1
2
34
0
1
2
3
Drehe den Bildraum, dann geht’s leichter!
Wenn die zwei die Ebeneaufspannenden Vektorenirgendwo hin in den R
3
zeigen, ist der Punkt mitminimalem Abstand vonb nicht so leicht zufinden. . .Drehen wir vorsichtig dasKoordinatensystem. . .bis die zwei Vektoren inder xy -Ebene liegen. DieLösung liegt nun genausenkrecht unter b
0
2
4
6 0
12
340
1
2
3
Suche eine orthogonale Matrix Q, welche das Gleichungssystem ineinen „einfacheren“ Bildraum dreht!
Beispiel von vorhinDie QR-Zerlegung von A liefert die gewünschte Drehmatrix!
Zerlegung A = QR :
1 00 11 1
=1√6
√3 −1 −
√2
0 2 −√
2√3 1
√2
·
√2
√2/2
0√
3/20 0
Transformiertes System Rx = QTb :
√2
√2/2
0√
3/20 0
[
m1
m2
]
=
5/√
27/√
61/√
3
Drehung mit Q anschaulich interpretiert
QR-Zerlegung transformiert überbestimmtes System in lösbaren Anteil undunlösbaren Rest
Bestmögliche Lösung: unlösbare Gleichungen weglassen, die anderen exaktlösen.
QR-Zerlegung löst (überbestimmte)Gleichungssysteme
Zur Lösung von Ax = b führt man QR-Zerlegung durch und löst dasDreieckssystem Rx = QT · b durch Substitution.
Begründung
Ax = b
Q · Rx = b |QT ·QT ·Q · Rx = QT · b
Rx = QT · b
Bei n × n-Systemen setzt mandiese Methode normalerweisenicht ein, weil sierechenaufwändiger als dieLR-Zerlegung ist.Bei n ×m-Systemen (n > m)liefern die ersten m Zeilen von R
die kleinste-Quadrate-Lösung.
Lösung überbestimmte Systeme mittels Normalengleichungen ist anfälligerfür Rundungsfehler als Lösung durch QR-Zerlegung.
C.B & E.H. (MUL) Matrixzerlegungen, Überbest. Systeme 20.III.2014 27 / 36
Überbestimmte Systeme A · x = b: QR-Zerlegung
Aufgabe
Suche x so, dass Residuums-2-Norm ‖r‖2 minimal wird
‖r‖ = ‖b − A · x‖ → min!
Vorgangsweise
Zerlege A = Q · RMultiplikation von r mit QT lässt 2-Norm unverändert. Wandle um:
‖r‖ = ‖QT · r‖ = ‖QT (b − A · x)‖ = ‖QTb − R · x‖Für das transformierte System ist die Minimallösung offensichtlich. . .
C.B & E.H. (MUL) Matrixzerlegungen, Überbest. Systeme 20.III.2014 28 / 36
Angenommen, das überbestimmte System besteht aus m Unbekannten undn = m + k Gleichungen (k > 0). Dann ist R eine n ×m-Matrix, derenletzte k Zeilen lauter Nullen enthalten.Die letzten k Zeilen des Residuumsvektors hängen nicht von x ab.Löse die ersten m Gleichungen des Systems R · x = QTb exakt (wennmöglich): Diese Gleichungen liefern keinen Beitrag zu Residuum.Die restlichen k Gleichungen hängen von x nicht ab. Keine Wahl von xkann den Beitrag dieser Gleichungen zum Residuum ändern.Daher ist die gewählte Lösung optimal für R · x = QTbWeil Transformation die Norm nicht beeinflusst, ist diese Lösung auchoptimale Lösung von A · x = b
C.B & E.H. (MUL) Matrixzerlegungen, Überbest. Systeme 20.III.2014 29 / 36
Überbestimmte Systeme A · x = b: SVD-Zerlegung
Aufgabe
Suche x so, dass Residuums-2-Norm ‖r‖2 minimal wird
‖r‖ = ‖b − A · x‖ → min!
Vorgangsweise
Zerlege A = U · S · V T , substituiere y = V T · x.Multiplikation von r mit UT lässt 2-Norm unverändert. Wandle um:
‖r‖ = ‖UT · r‖ = ‖UTb − S · V T · x‖ = ‖QTb − S · y‖Für das gedrehte System ist die Minimallösung völlig offensichtlich. . .
(Zahlenbeispiel im Skriptum)
C.B & E.H. (MUL) Matrixzerlegungen, Überbest. Systeme 20.III.2014 30 / 36
Übersicht der Verfahrenfür überbestimmte Systeme A · x = b
Normalengleichungen AT · A = ATb Klassischer Lösungsweg. Anfällig fürDaten- und Rundungsfehler (schlechte Konditionszahl).
QR-Zerlegung Standardverfahren zur numerischen Lösung. Algebraischäquivalent zu Norm.gleichungen, aber numerisch wenigerfehlerempfindlich.
MATLAB x = A\b verwendet bei überbestimmten Systemenautomatisch QR-Zerlegung
Sonderfälle (rangA ≤ n) Überbestimmte Systeme, die trotzdem exaktlösbar sind oder eine Schar von (ex. oder kl. Quadr.)Lösungen haben. Normalengleichungen können versagen.Singulärwert-Zerlegung.
C.B & E.H. (MUL) Matrixzerlegungen, Überbest. Systeme 20.III.2014 31 / 36
Gliederung
1 MatrixzerlegungenLinks-Rechts-ZerlegungOrthogonale MatrizenQR-ZerlegungSingulärwertzerlegung
2 Überbestimmte SystemeKleinste QuadrateLösung durch QR-Zerlegung
3 Beispiele für überbestimmte SystemeLineare ModelleNichtlineare Systeme
C.B & E.H. (MUL) Matrixzerlegungen, Überbest. Systeme 20.III.2014 32 / 36
Lineares Modell in zwei VariablenAnpassen einer Ausgleichs-Ebene: Beispiel aus der Matlab-Hilfe
Angenommen, eine Größe y hängt von zwei Parametern x1 und x2 ab. FolgendeMesswerte liegen vor:
x1 : 0.2 0.5 0.6 0.8 1.0 1.1x2 : 0.1 0.3 0.4 0.9 1.1 1.4y : 0.17 0.26 0.28 0.23 0.27 0.24
Wir nehmen ein lineares Modelly = a0 + a1x1 + a2x2 an und setzen diegegebenen Datentripel ein−→ führt auf ein System von 6 linearenGleichungen in den 3 unbekanntenKoeffizienten a0, a1, a2.−→ Kleinste-Quadrate-Lösung liefertEbene mit „bestmöglicher“ Anpassungan Daten
Lineares Modell in zwei VariablenBeispiel: Magnetische Deklinationswerte 2008.5 in Österreich
9 10 11 12 13 14 15 16 17 1846
46.5
47
47.5
48
48.5
49
49.5
1.41.4
1.4
1.61.6
1.6
1.81.8
1.8
22
2
2.22.2
2.2
2.42.4
2.4
2.62.6
2.6
2.82.8
2.8
33
3
3.23.2
3.2
3.43.4
Wien 3◦ 00’
Eisenstadt 3◦ 02’
St.Pölten 2◦ 54’
Graz 2◦ 47’
Linz 2◦ 33’
Klagenfurt 2◦ 30’
Salzburg 2◦ 15’
Innsbruck 1◦ 53’
Bregenz 1◦ 24’Daten: ZAMG
Kleinste-Quadrate-Anpassung
liefert Modell:δ = −2.0987 + 0.2365λ+ 0.0261φ
Überbestimmte nichtlineare SystemeBeispiel: Standortbestimmung durch Trilateration
Die Abstände von drei festen Punkten A,B,Czu einem unbekannten Punkt X sind (etwasungenau) bekannt. Gesucht ist eine möglichstgute Positionsbestimmung.
√
(x1 − 1)2 + (x2 − 1)2 = 6√
(x1 − 8)2 + (x2 − 4)2 = 3.6√
(x1 − 5)2 + (x2 − 8)2 = 4.2
Den drei Gleichungen entsprechen drei Kreiseim R
2. Sie haben keinen gemeinsamenSchnittpunkt.
0 1 2 3 4 5 6 7 8 90
1
2
3
4
5
6
7
8
9
A
B
C
da=6
dc=4.2
db=3.6
X
Überbestimmte nichtlineare SystemeLösung durch Linearisierung und Iteration
f(x) = b , x ∈ Rn , f(x),b ∈ R
m, m > n
Ausgehend von einem Startvektor x(0) bestimmt man eine Korrektur ∆xaus der Lösung des überbestimmten linearen Systems mit der JacobimatrixDf
Df ·∆x = b− f(x)
und gewinnt eine verbesserte Lösung x(1) = x(0) +∆x .
Für die Konvergenz der Iteration kann Unterrelaxation (Dämpfung)notwendig sein:x(n+1) = x(n) + ω∆x mit Unterrelaxationsfaktor 0 < ω ≤ 1.
C.B & E.H. (MUL) Matrixzerlegungen, Überbest. Systeme 20.III.2014 36 / 36
Überbestimmte nichtlineare SystemeLösung durch Linearisierung und Iteration
f(x) = b , x ∈ Rn , f(x),b ∈ R
m, m > n
Ausgehend von einem Startvektor x(0) bestimmt man eine Korrektur ∆xaus der Lösung des überbestimmten linearen Systems mit der JacobimatrixDf
Df ·∆x = b− f(x)
und gewinnt eine verbesserte Lösung x(1) = x(0) +∆x .
Für die Konvergenz der Iteration kann Unterrelaxation (Dämpfung)notwendig sein:x(n+1) = x(n) + ω∆x mit Unterrelaxationsfaktor 0 < ω ≤ 1.
C.B & E.H. (MUL) Matrixzerlegungen, Überbest. Systeme 20.III.2014 36 / 36