Matrixzerlegungen. Überbestimmte...

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