61
Matrixzerlegungen. Überbestimmte Systeme 6. Vorlesung 170 004 Numerische Methoden I Clemens Brand und Erika Hausenblas Montanuniversität Leoben 27. März 2014

Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

  • Upload
    others

  • View
    4

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

Matrixzerlegungen.Überbestimmte Systeme

6. Vorlesung170 004 Numerische Methoden I

Clemens Brand und Erika Hausenblas

Montanuniversität Leoben

27. März 2014

Page 2: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

Gliederung

1 MatrixzerlegungenLinks-Rechts-ZerlegungOrthogonale MatrizenQR-ZerlegungSingulärwertzerlegung

2 Überbestimmte SystemeKleinste QuadrateLösung durch QR-Zerlegung

3 Beispiele für überbestimmte SystemeLineare ModelleNichtlineare Systeme

Page 3: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 4: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 5: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 6: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 7: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 8: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

]

Page 9: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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 \”

Page 10: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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.

Page 11: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 12: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 13: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 14: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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.

Page 15: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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.

Page 16: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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.

Page 17: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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“.

Page 18: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 19: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

Ü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

Page 20: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

Ü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

Page 21: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

Ü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

Page 22: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

Ü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

Page 23: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

Ü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

Page 24: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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. . .

Page 25: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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. . .

Page 26: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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. . .

Page 27: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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. . .

Page 28: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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!

Page 29: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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!

Page 30: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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!

Page 31: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 32: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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. . .

Page 33: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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. . .

Page 34: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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. . .

Page 35: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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. . .

Page 36: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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.

Page 37: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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.

Page 38: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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.

Page 39: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 40: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 41: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 42: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 43: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 44: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 45: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 46: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 47: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 48: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 49: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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!

Page 50: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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.

Page 51: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 52: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

Ü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

Page 53: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 54: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

Ü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

Page 55: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

Ü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

Page 56: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 57: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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

Page 58: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

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φ

Page 59: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

Ü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

Page 60: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

Ü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

Page 61: Matrixzerlegungen. Überbestimmte Systemeinstitute.unileoben.ac.at/amat/lehrbetrieb/num/vl-skript/sli06s14.pdf · Die Matrix-Vektor-Multiplikation y =A· x Grundlegende Bedeutung

Ü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