Heinrich Voss - mat.tuhh.de · Cholesky Zerlegung lösen. Diese Methode erfordert zur Aufstellung der Normalgleichungen (unter Beachtung der Symmetrie von ATA) 1 2 n(n + 1) + n innere

Lineare Ausgleichsprobleme

Heinrich [email protected]

Hamburg University of TechnologyInstitute for Numerical Simulation

TUHH Heinrich Voss Kapitel 5 2010 1 / 73

http://www.tu-harburg.de/mat/hp/voss/



Wir betrachten in diesem Abschnitt das lineare Ausgleichsproblem

‖Ax − b‖2 = min! (1)

mit gegebenem A ∈ Rm×n, m ≥ n, und b ∈ Rm.

Dieses Problem wurde bereits in Kapitel 7 der Vorlesung Lineare Algebrabehandelt. Wir werden zunächst vor allem die Ergebnisse dieser Vorlesungzusammentragen. Wir werden dann die Singulärwertzerlegung einer Matrixbetrachten, werden dann die Pseudoinverse einer Matrix einführen und aufdas Konditionsproblem für Lineare Gleichungssysteme undAusgleichsprobleme eingehen. Schließlich werden wir kurz auf das Problemder Regularisierung schlecht gestellter Probleme eingehen.




Wir betrachten in diesem Abschnitt das lineare Ausgleichsproblem

‖Ax − b‖2 = min! (1)

mit gegebenem A ∈ Rm×n, m ≥ n, und b ∈ Rm.

Dieses Problem wurde bereits in Kapitel 7 der Vorlesung Lineare Algebrabehandelt. Wir werden zunächst vor allem die Ergebnisse dieser Vorlesungzusammentragen. Wir werden dann die Singulärwertzerlegung einer Matrixbetrachten, werden dann die Pseudoinverse einer Matrix einführen und aufdas Konditionsproblem für Lineare Gleichungssysteme undAusgleichsprobleme eingehen. Schließlich werden wir kurz auf das Problemder Regularisierung schlecht gestellter Probleme eingehen.



Normalgleichungen

Notwendig für eine Lösung des Ausgleichsproblems (1) ist, dass der Gradientdes Funktionals

φ(x) = (Ax − b)T (Ax − b)

verschwindet, d.h. 2AT (Ax − b) = 0 oder

AT Ax = AT b. (2)

Die Gleichungen (2) heißen die Normalgleichungen des Ausgleichsproblems(1).



Normalgleichungen

Notwendig für eine Lösung des Ausgleichsproblems (1) ist, dass der Gradientdes Funktionals

φ(x) = (Ax − b)T (Ax − b)

verschwindet, d.h. 2AT (Ax − b) = 0 oder

AT Ax = AT b. (2)

Die Gleichungen (2) heißen die Normalgleichungen des Ausgleichsproblems(1).



Normalgleichungen

Dass jede Lösung von (2) auch das Ausgleichsproblem (1) löst, sieht man so:

Es ist für alle h ∈ Rn

‖A(x + h)− b‖22 = (Ax + Ah − b)T (Ax + Ah − b)

= ‖Ax − b‖22 + ‖Ah‖2

2 + 2hT (AT Ax − AT b)

= ‖Ax − b‖22 + ‖Ah‖2

2 ≥ ‖Ax − b‖22.

Schließlich ist die Matrix AT A genau dann regulär, wenn die Matrix A denRang n besitzt. Damit ist das Ausgleichsproblem genau dann eindeutiglösbar, wenn Rang(A) = n gilt.



Normalgleichungen




= ‖Ax − b‖22 + ‖Ah‖2


= ‖Ax − b‖22 + ‖Ah‖2

2 ≥ ‖Ax − b‖22.




Normalgleichungen




= ‖Ax − b‖22 + ‖Ah‖2


= ‖Ax − b‖22 + ‖Ah‖2

2 ≥ ‖Ax − b‖22.




Satz 5.1

Die Lösungen des Ausgleichsproblems

‖Ax − b‖2 = min!

sind genau die Lösungen der Normalgleichungen

AT Ax = AT b.

(1) ist genau dann eindeutig lösbar, wenn A linear unabhängige Spaltenbesitzt.



Satz 5.1

Die Lösungen des Ausgleichsproblems

‖Ax − b‖2 = min!

sind genau die Lösungen der Normalgleichungen

AT Ax = AT b.

(1) ist genau dann eindeutig lösbar, wenn A linear unabhängige Spaltenbesitzt.



Normalgleichungen

Besitzt A unabhängige Spalten, so ist die Koeffizientenmatrix AT A positivdefinit, und man kann daher die Normalgleichungen unter Benutzung derCholesky Zerlegung lösen.

Diese Methode erfordert zur Aufstellung der Normalgleichungen (unterBeachtung der Symmetrie von AT A) 1

2 n(n + 1) + n innere Produkte vonVektoren der Länge m, also n2m + 3nm flops und zur Lösung derNormalgleichungen 1

3 n3 +O(n2) flops.

Das Verfahren ist geeignet bei Problemen mit kleinem n (n = 2 oder n = 3).Bei größerem n können Stabilitätsprobleme auftreten und eines der folgendenVerfahren ist vorzuziehen.



Normalgleichungen




3 n3 +O(n2) flops.




Normalgleichungen




3 n3 +O(n2) flops.




Orthogonale Zerlegung

Ist A ∈ Rm×n, m ≥ n, eine gegebene Matrix mit linear unabhängigen Spalten,so gibt es eine Matrix Q ∈ Rm×n mit orthogonalen Spalten und eine obereDreiecksmatrix R ∈ R(n,n), so dass gilt

A = QR. (3)

(3) heißt eine QR Zerlegung der Matrix A.

Wir haben bereits in der Vorlesung Lineare Algebra gesehen, dass man dieQR Zerlegung einer Matrix mit Hilfe der Orthogonalisierung nachGram–Schmidt oder durch Multiplikation mit geeigneten HouseholderTransformationen bestimmen kann.



Orthogonale Zerlegung

Ist A ∈ Rm×n, m ≥ n, eine gegebene Matrix mit linear unabhängigen Spalten,so gibt es eine Matrix Q ∈ Rm×n mit orthogonalen Spalten und eine obereDreiecksmatrix R ∈ R(n,n), so dass gilt

A = QR. (3)

(3) heißt eine QR Zerlegung der Matrix A.

Wir haben bereits in der Vorlesung Lineare Algebra gesehen, dass man dieQR Zerlegung einer Matrix mit Hilfe der Orthogonalisierung nachGram–Schmidt oder durch Multiplikation mit geeigneten HouseholderTransformationen bestimmen kann.



QR Zerlegung

Beim Gram–Schmidt Verfahren werden im j-ten Schritt, d.h. nachdem dieersten j − 1 Spalten q1, . . . ,q j−1 von Q bereits bestimmt wurden, von der j-tenSpalte aj von A die Anteile in Richtung von q i , i = 1, . . . , j − 1, abgezogen undder so bestimmte, zu den q i orthogonale Vektor normiert. Dabei werdenzugleich die Elemente rij := (q i )T aj bestimmt.

Algorithmus [Klassische Gram–Schmidt Orthogonalisierung]for i=1 : n do

q(:, i) = a(:, i);for j=1 : i-1 do

r(j , i) = q(:, j)′ ∗ a(:, i);q(:, i) = q(:, i)− r(j , i) ∗ q(:, j);

end forr(i , i) = ‖q(:, i)‖2;q(:, i) = q(:, i)/r(i , i);

end for



QR Zerlegung

Beim Gram–Schmidt Verfahren werden im j-ten Schritt, d.h. nachdem dieersten j − 1 Spalten q1, . . . ,q j−1 von Q bereits bestimmt wurden, von der j-tenSpalte aj von A die Anteile in Richtung von q i , i = 1, . . . , j − 1, abgezogen undder so bestimmte, zu den q i orthogonale Vektor normiert. Dabei werdenzugleich die Elemente rij := (q i )T aj bestimmt.

Algorithmus [Klassische Gram–Schmidt Orthogonalisierung]for i=1 : n do

q(:, i) = a(:, i);for j=1 : i-1 do

r(j , i) = q(:, j)′ ∗ a(:, i);q(:, i) = q(:, i)− r(j , i) ∗ q(:, j);


end for



QR Zerlegung

Wir haben vorausgesetzt, dass die Spalten von A linear unabhängig sind. Istdies nicht der Fall, so wird der Algorithmus mit rii = 0 für ein i abbrechen.Diese Abfrage wird man natürlich noch in einen Algorithmus einbauen.

Sind die Spalten von A nahezu linear abhängig, so ist das oben angegebeneklassische Gram-Schmidt Verfahren numerisch instabil. Die berechnetenVektoren q j sind also nicht orthogonal.

Etwas besser wird die Stabilität, wenn man die Berechnung der rij ersetztdurch rij = (q j )T q i . Diese dem klassischen Gram–Schmidt Verfahrenäquivalente Methode heißt modifiziertes Gram–Schmidt Verfahren.



QR Zerlegung






QR Zerlegung






Gram-Schmidt Verfahren

Algorithmus [Modifizierte Gram-Schmidt Orthogonalisierung]for i=1 : n do

q(:, i) = a(:, i);for j=1 : i-1 do

r(j , i) = q(:, j)′ ∗ q(:, i);q(:, i) = q(:, i)− r(j , i) ∗ q(:, j);


end for



Beispiel

Das folgende Beispiel von Björck zeigt die Überlegenheit des modifiziertenGram–Schmidt Verfahrens.

Sei

A =

1 1 1ε 0 00 ε 00 0 ε

wobei ε so klein ist, dass fl(1 + ε2) = 1 gilt.



Beispiel

Das folgende Beispiel von Björck zeigt die Überlegenheit des modifiziertenGram–Schmidt Verfahrens.

Sei

A =

1 1 1ε 0 00 ε 00 0 ε

wobei ε so klein ist, dass fl(1 + ε2) = 1 gilt.




Dann erhält man mit dem klassischen und dem modifizierten Gram–SchmidtVerfahren (bis auf Normierung der Spalten) die Matrizen

QkGS =

1 0 0ε −ε −ε0 ε 00 0 ε

und QmGS =

1 0 0ε −ε −ε/20 ε −ε/20 0 ε

.

Für die minimalen Winkel ϕkGS und ϕmGS zwischen zwei Spalten gilt

cosϕkGS =12

und cosϕmGS = − ε√2. �




Dann erhält man mit dem klassischen und dem modifizierten Gram–SchmidtVerfahren (bis auf Normierung der Spalten) die Matrizen

QkGS =

1 0 0ε −ε −ε0 ε 00 0 ε

und QmGS =

1 0 0ε −ε −ε/20 ε −ε/20 0 ε

.

Für die minimalen Winkel ϕkGS und ϕmGS zwischen zwei Spalten gilt

cosϕkGS =12

und cosϕmGS = − ε√2. �



Householder Matrizen

Stabiler als das Gram–Schmidt Verfahren sind Methoden zur Bestimmung derQR Zerlegung einer Matrix, die auf der Multiplikation von A mit geeignetenorthogonalen Matrizen beruhen. Wir betrachten zunächst dieOrthogonalisierung mit Hilfe von Householder Matrizen.

DefinitionEs sei w ∈ Rn mit ‖w‖2 = 1. Dann heißt die Matrix

H := I − 2wwT

Householder Matrix. Die Householder Matrix H beschreibt eine Spiegelung

an der Hyperebene w⊥.

Offensichtlich ist H ist eine symmetrische und orthogonale Matrix, d.h.HT = H und HT H = H2 = I.






H := I − 2wwT

Householder Matrix.

Die Householder Matrix H beschreibt eine Spiegelung








H := I − 2wwT









H := I − 2wwT







Die explizite Matrixgestalt von H wird außerordentlich selten benötigt.

H = I − βuuT ist vollständig charakterisiert durch einen Normalenvektor u derHyperebene, an der gespiegelt wird, und durch den Skalierungsfaktorβ = 2/‖u‖2

2. Sind diese beiden bekannt, so kann man eine Multiplikationeines Vektors x mit H ausführen gemäß

Hx = x − β(uT x)u.

Es sind also ein inneres Produkt und ein _axpy, d.h. 4n flops, erforderlich.

Wegen H−1 = HT = H gilt dasselbe für das Lösen eines Gleichungssystemsmit der Koeffizientenmatrix H.































Um die Orthogonalisierung einer Matrix mit Householder Transformationenauszuführen, benötigen wir zu gegebenem Vektor x ∈ Rn, x 6= 0, eineHouseholder Matrix H mit

Hx = ±‖x‖2e1, e1 = (1,0, . . . ,0)T .

In der Vorlesung Lineare Algebra wurde gezeigt (und dies rechnet man auchleicht nach), dass für den Fall, dass x kein Vielfaches von e1 ist, dieHouseholder Matrizen

H± = I − βw±wT±,

die durch die Normalenvektoren

w± = x ± ‖x‖2e1,

bestimmt sind, das Gewünschte leisten.




Um die Orthogonalisierung einer Matrix mit Householder Transformationenauszuführen, benötigen wir zu gegebenem Vektor x ∈ Rn, x 6= 0, eineHouseholder Matrix H mit

Hx = ±‖x‖2e1, e1 = (1,0, . . . ,0)T .

In der Vorlesung Lineare Algebra wurde gezeigt (und dies rechnet man auchleicht nach), dass für den Fall, dass x kein Vielfaches von e1 ist, dieHouseholder Matrizen

H± = I − βw±wT±,

die durch die Normalenvektoren

w± = x ± ‖x‖2e1,

bestimmt sind, das Gewünschte leisten.




Ist x ein Vielfaches des ersten Einheitsvektors e1, so ist einer der beidenVektoren der Nullvektor, und zwar gilt w− = 0 im Fall x1 > 0 und w+ = 0 imFall x1 < 0.

Ist x ≈ ce1, so erhält man für w− im Fall c > 0 und für w+ im Fall c < 0Auslöschung.

Um diese zu vermeiden, wählen wir daher stets

H = I − 2‖w‖2

2wwT , w = x + sign(x1)‖x‖2e1.







H = I − 2‖w‖2








H = I − 2‖w‖2





Damit erhalten wir den folgenden Algorithmus zur Berechnung der MatrixH = I − βuuT , die x in span(e1) abbildet:

Algorithmus [Householder Vektor]function [u, β] = householder(x)µ = x(2 : n)′ ∗ x(2 : n);u = [1; x(2 : n)];if µ == 0 thenβ = 0;

elseu(1) = x(1) + sign(x(1))

√x(1)2 + µ;

β = 2/(u(1)2 + µ);end if




Damit erhalten wir den folgenden Algorithmus zur Berechnung der MatrixH = I − βuuT , die x in span(e1) abbildet:

Algorithmus [Householder Vektor]function [u, β] = householder(x)µ = x(2 : n)′ ∗ x(2 : n);u = [1; x(2 : n)];if µ == 0 thenβ = 0;

elseu(1) = x(1) + sign(x(1))

√x(1)2 + µ;

β = 2/(u(1)2 + µ);end if



QR Zerlegung

Wir verwenden nun Householder Matrizen, um die Matrix A orthogonal aufobere Dreiecksgestalt zu transformieren. Sei dazu H1 wie oben beschriebengewählt, so dass

H1a1 = ±‖a1‖2e1 =: r11e1.

Dann gilt mit P1 = H1 (und mit einer Matrix A1 ∈ R(m−1,n−1))

P1A =

(r11 r(1,2 : n)0 A1

).



QR Zerlegung

Wir verwenden nun Householder Matrizen, um die Matrix A orthogonal aufobere Dreiecksgestalt zu transformieren. Sei dazu H1 wie oben beschriebengewählt, so dass

H1a1 = ±‖a1‖2e1 =: r11e1.

Dann gilt mit P1 = H1 (und mit einer Matrix A1 ∈ R(m−1,n−1))

P1A =

(r11 r(1,2 : n)0 A1

).



QR Zerlegung

Ist nach j Schritten, 1 ≤ j < n, die Gestalt

r11 r12 . . . r1j r1,j+1 r1,j+2 . . . r1n0 r22 . . . r2j r2,j+1 r2,j+2 . . . r2n...

.... . .

......

......

0 0 . . . rjj rj,j+1 rj,j+2 . . . rj,n

0 0 . . . 0 rj+1,j+1 rj+1,j+2 . . . rj+1,n...

.... . .

......

......

0 0 . . . 0 rm,j+1 rm,j+2 . . . rm,n

erreicht,

so wählen wir eine Householder Matrix Hj+1 ∈ R(m−j,n−j), so dassHj+1r(j + 1 : m, j + 1) eine Vielfaches des ersten Einheitsvektors ist, undsetzen hiermit

Pj+1 =

(Ij Oj,n−j

Om−j,j Hj+1

).



QR Zerlegung

Ist nach j Schritten, 1 ≤ j < n, die Gestalt


.... . .

......

......

0 0 . . . rjj rj,j+1 rj,j+2 . . . rj,n

0 0 . . . 0 rj+1,j+1 rj+1,j+2 . . . rj+1,n...

.... . .

......

......

0 0 . . . 0 rm,j+1 rm,j+2 . . . rm,n

erreicht,

so wählen wir eine Householder Matrix Hj+1 ∈ R(m−j,n−j), so dassHj+1r(j + 1 : m, j + 1) eine Vielfaches des ersten Einheitsvektors ist, undsetzen hiermit

Pj+1 =

(Ij Oj,n−j

Om−j,j Hj+1

).



QR Zerlegung

Dann gilt

Pj+1Pj . . .P1A =


.... . .

......

......

0 0 . . . rjj rj,j+1 rj,j+2 . . . rj,n0 0 . . . 0 rj+1,j+1 rj+1,j+2 . . . rj+1,n

0 0 . . . 0 0 rj+2,j+2 . . . rj+2,n...

.... . .

......

......

0 0 . . . 0 0 rm,j+2 . . . rm,n

.

Nach n Schritten ist damit die obere Dreiecksgestalt erreicht (wobei wirvorausgesetzt haben, dass die Matrix A linear unabhängige Spalten besitzt,da sonst das Verfahren vorher abgebrochen wäre).



QR Zerlegung

Dann gilt

Pj+1Pj . . .P1A =


.... . .

......

......

0 0 . . . rjj rj,j+1 rj,j+2 . . . rj,n0 0 . . . 0 rj+1,j+1 rj+1,j+2 . . . rj+1,n

0 0 . . . 0 0 rj+2,j+2 . . . rj+2,n...

.... . .

......

......

0 0 . . . 0 0 rm,j+2 . . . rm,n

.

Nach n Schritten ist damit die obere Dreiecksgestalt erreicht (wobei wirvorausgesetzt haben, dass die Matrix A linear unabhängige Spalten besitzt,da sonst das Verfahren vorher abgebrochen wäre).



QR Zerlegung

Setzt manQT := PnPn−1 . . .P1,

so ist Q eine orthogonale Matrix, und es gilt

A = Q(

ROm−n,n

)= P1P2 . . .Pn

(R

Om−n,n

).

Die Householder Matrizen Hj (und damit die Faktoren Pj in Q) sind jeweilsdurch Vektoren uj und Skalare βj vollständig bestimmt.



QR Zerlegung

Setzt manQT := PnPn−1 . . .P1,

so ist Q eine orthogonale Matrix, und es gilt

A = Q(

ROm−n,n

)= P1P2 . . .Pn

(R

Om−n,n

).

Die Householder Matrizen Hj (und damit die Faktoren Pj in Q) sind jeweilsdurch Vektoren uj und Skalare βj vollständig bestimmt.



QR Zerlegung

Die uj können (bis auf die erste Komponente) im Verlauf eines Algorithmusunterhalb der Diagonalen von A gespeichert werden. Tatsächlich müssendiese Elemente wegen der Gestalt der uj nicht einmal geändert werden.

Die ersten Komponenten von uj und die βj müssen in einem zusätzlichenArray gespeichert werden.

Die Elemente von R können das obere Dreieck von A einschließlich derDiagonale überschreiben.



QR Zerlegung






QR Zerlegung






QR Zerlegung mit Householder

Algorithmus [QR Zerlegung mit Householder Matrizen]

for i=1 : min(m-1,n) do[u, β] = householder(a(i : m, i));a(i : m, i + 1 : n) = a(i : m, i + 1 : n)− β ∗ u ∗ (u′ ∗ a(i : m, i + 1 : n));a(i , i) = a(i , i)− βu(1)u′ ∗ a(i : m, i);uu(i) = u(1);be(i) = β;

end for

Man zählt leicht ab, dass dieser Algorithmus im wesentlichen 2n2m − 23 n3

flops benötigt für die QR Zerlegung von A.



QR Zerlegung mit Householder

Algorithmus [QR Zerlegung mit Householder Matrizen]

for i=1 : min(m-1,n) do[u, β] = householder(a(i : m, i));a(i : m, i + 1 : n) = a(i : m, i + 1 : n)− β ∗ u ∗ (u′ ∗ a(i : m, i + 1 : n));a(i , i) = a(i , i)− βu(1)u′ ∗ a(i : m, i);uu(i) = u(1);be(i) = β;

end for

Man zählt leicht ab, dass dieser Algorithmus im wesentlichen 2n2m − 23 n3

flops benötigt für die QR Zerlegung von A.



Givens Matrizen

Eine weitere Möglichkeit zur Bestimmung der QR Zerlegung bieten die GivensRotationen.

Es ist bekannt, dass eine Rotation im R2 um den Winkel θ gegeben ist durch

x 7→(

cos θ − sin θsin θ cos θ

)x .

Entsprechend kann man eine Multiplikation eines Vektors x ∈ Rn mit derMatrix

R(i , j , θ) =

Ii−1 0 O 0 O0T cos θ 0T − sin θ 0T

O 0 Ij−i−1 0 O0T sin θ 0T cos θ 0T

O 0 O 0 In−j

als Rotation in der von ei und ej aufgespannten Ebene auffassen.



Givens Matrizen



x 7→(


)x .


R(i , j , θ) =



O 0 O 0 In−j




Givens Matrizen



x 7→(


)x .


R(i , j , θ) =



O 0 O 0 In−j




Givens MatrizenR(i , j , θ) heißt eine Givens Rotation oder seltener auch Jacobi Rotation.

Diese Abbildungen wurden 1958 von Givens benutzt, um eine Matrixorthogonal auf obere Dreiecksgestalt zu transformieren. Jacobi verwandtediese Abbildung schon 1846 zur Lösung des vollständigen symmetrischenEigenwertproblems.

Es sei nun für x ∈ Rn die j-te Komponente xj von Null verschieden. Wirwählen θ so, dass

cos θ =xi√

x2i + x2

j

und sin θ =−xj√

x2i + x2

j

.

Dann gilt (cos θ − sin θsin θ cos θ

)(xixj

)=

( √x2

i + x2j

0

),

und daher wird in R(i , j , θ)x die j-te Komponente annulliert.






cos θ =xi√

x2i + x2

j


x2i + x2

j

.


)(xixj

)=

( √x2

i + x2j

0

),







cos θ =xi√

x2i + x2

j


x2i + x2

j

.


)(xixj

)=

( √x2

i + x2j

0

),







cos θ =xi√

x2i + x2

j


x2i + x2

j

.


)(xixj

)=

( √x2

i + x2j

0

),

und daher wird in R(i , j , θ)x die j-te Komponente annulliert.TUHH Heinrich Voss Kapitel 5 2010 25 / 73


Givens Rotationen

Damit ist klar, wie man mit einer Folge von Multiplikationen mit GivensRotationen eine QR Zerlegung einer Matrix A ∈ Rm×n bestimmen kann.

Man annulliert nacheinander die Elemente der ersten Spalte unterhalb derDiagonale mit geeigneten Rotationen R(1,2, θ12), R(1,3, θ13), . . . ,R(1,m, θ1m), und dann mit Rotationen R(i , j , θij ), i = 2, . . . ,n, j = i + 1, . . . ,mdie Elemente der weiteren Spalten von links nach rechts und von oben nachunten.

Genauso kann man mit Rotationen R(m − 1,m, θm−1,m),. . . ,R(1,2, θ12) dieElemente der ersten Spalte unterhalb der Diagonale von unten nach obenannullieren, und dann die weiteren Spalten von links nach rechts auf gleicheWeise behandeln.



Givens Rotationen






Givens Rotationen






Givens Reflexionen

Analog kann man auch die sog. Givens Reflexionen verwenden, dieausgehend von der Spiegelung

x 7→(

cos θ sin θsin θ − cos θ

)x

im R2 analog definiert werden.



Givens Matrizen

Ein Vorteil der Verwendung von Givens Rotationen oder Reflexionengegenüber den Householder Transformationen zur QR Zerlegung einer MatrixA besteht darin, dass man auf übersichtliche Weise gewisse Nullen in Aberücksichtigen und damit die Arbeit vermindern kann.

Ein Nachteil ist, dass die direkte Implementierung des beschriebenenVerfahrens doppelt so teuer ist wie die QR Zerlegung mit HouseholderMatrizen.

Man beachte aber, dass Gentleman (1973) und Hammarling (1974) eineMethode, die schnelle Givens Transformation, angegeben haben, mit der derAufwand genauso hoch ist, wie mit Householder Matrizen. Diese wurde in derBLAS1 verwendet.



Givens Matrizen






Givens Matrizen






Ausgleichsproblem

Ist eine QR Zerlegung

A = Q(

ROm−n,n

)der Matrix A ∈ Rm×n bekannt, so ist es leicht, das lineare Ausgleichsproblem

‖Ax − b‖2 = min!

zu lösen.

Da die Multiplikation eines Vektors mit einer orthogonalen Matrix seineEuklidische Länge nicht verändert, gilt

‖Ax − b‖2 = ‖QT (Ax − b)‖2 =

∥∥∥∥( ROm−n,n

)x −QT b

∥∥∥∥2



Ausgleichsproblem

Ist eine QR Zerlegung

A = Q(

ROm−n,n

)der Matrix A ∈ Rm×n bekannt, so ist es leicht, das lineare Ausgleichsproblem

‖Ax − b‖2 = min!

zu lösen.

Da die Multiplikation eines Vektors mit einer orthogonalen Matrix seineEuklidische Länge nicht verändert, gilt

‖Ax − b‖2 = ‖QT (Ax − b)‖2 =

∥∥∥∥( ROm−n,n

)x −QT b

∥∥∥∥2



Ausgleichsproblem

Mit

QT b =:

(b1b2

), b1 ∈ Rn, b2 ∈ Rm−n

folgt‖Ax − b‖2

2 = ‖Rx − b1‖22 + ‖b2‖2

2.

Den zweiten Summanden kann man durch die Wahl von x nicht beeinflussen.Daher ist die Lösung des Ausgleichsproblems

x = R−1b1,

und der Defekt ist ‖b2‖.



Ausgleichsproblem

Mit

QT b =:

(b1b2

), b1 ∈ Rn, b2 ∈ Rm−n

folgt‖Ax − b‖2

2 = ‖Rx − b1‖22 + ‖b2‖2

2.

Den zweiten Summanden kann man durch die Wahl von x nicht beeinflussen.Daher ist die Lösung des Ausgleichsproblems

x = R−1b1,

und der Defekt ist ‖b2‖.



Singulärwertzerlegung

DefinitionSei A ∈ Rm×n. Gilt für orthogonale Matrizen U ∈ R(m,m) und V ∈ R(n,n) undeine Diagonalmatrix Σ = (σiδij )i,j ∈ Rm×n

A = UΣV T , (1)

so heißt (1) eine Singulärwertzerlegung ( SVD) von A.



Beispiel

Ist A ∈ R(n,n) symmetrisch mit den Eigenwerten µ1, . . . , µn und ist v1, . . . , vn

ein zugehöriges System von orthonormalen Eigenvektoren, so gilt mit derDiagonalmatrix Σ := diag{µ1, . . . , µn} und mit V := (v1, . . . , vn)

A = V ΣV T ,

und dies ist eine Singulärwertzerlegung von A. �




Setzt man U = (u1, . . . ,um) und V = (v1, . . . , vn), so ist (1) äquivalent zu

Av i =

{σiui , 1, . . . ,min(m,n),0 m + 1, . . . ,n (falls n > m). (2)

Ohne Einschränkung können die σi nichtnegativ gewählt werden. Ist etwaσj < 0, so ersetze man die j-te Spalte v j von V durch −v j .

Ferner können wir durch Umordnung von Zeilen von V T bzw. Spalten von Uerreichen, dass σ1 ≥ σ2 ≥ . . . gilt.

Wir werden nun nur noch Singulärwertzerlegungen betrachten, in denen dieDiagonalelmente σ1, . . . , σmin(m,n) nichtnegativ und der Größe nach geordnetsind.





Av i =









Av i =









Av i =








Es seien in einer Singulärwertzerlegung (1) von A ∈ Rm×n dieDiagonalelemente σ1, . . . , σmin(m,n) von Σ nicht negativ. Dann heißen die σi dieSingulärwerte oder die singulären Werte von A.

Beispiel 5.8Es sei A ∈ R(n,n) symmetrisch und µi und v i wie in Beispiel 5.8, wobei dieReihenfolge so gewählt ist, dass|µ1| ≥ |µ2| ≥ · · · ≥ |µr | > µr+1 = · · · = µn = 0 gilt.Es sei ui := v i , falls µi ≥ 0, und ui := −v i , falls µi < 0, und hiermitU := (u1, . . . ,un). Dann gilt

A = UΣV T , Σ = (|µi |δij ),

und |µ1|, . . . , |µn| sind die singulären Werte von A. �




Es seien in einer Singulärwertzerlegung (1) von A ∈ Rm×n dieDiagonalelemente σ1, . . . , σmin(m,n) von Σ nicht negativ. Dann heißen die σi dieSingulärwerte oder die singulären Werte von A.

Beispiel 5.8Es sei A ∈ R(n,n) symmetrisch und µi und v i wie in Beispiel 5.8, wobei dieReihenfolge so gewählt ist, dass|µ1| ≥ |µ2| ≥ · · · ≥ |µr | > µr+1 = · · · = µn = 0 gilt.Es sei ui := v i , falls µi ≥ 0, und ui := −v i , falls µi < 0, und hiermitU := (u1, . . . ,un). Dann gilt

A = UΣV T , Σ = (|µi |δij ),

und |µ1|, . . . , |µn| sind die singulären Werte von A. �




(1) =⇒ AT = V ΣT UT . (3)

Besitzt also A eine Singulärwertzerlegung, so auch AT , und die von Nullverschiedenen singulären Werte stimmen überein.

(3) kann man (entsprechend (2)) schreiben als

AT ui =

{σiv i , 1, . . . ,min(m,n)0 n + 1, . . . ,m (falls m > n).

(1)&(3) =⇒ AT A = V ΣT ΣV T ,AAT = UΣΣT UT ,

(4)

d.h. die Quadrate der singulären Werte von A (und AT ) sind Eigenwerte vonAT A und AAT , und {v1, . . . , vn} bzw. {u1, . . . ,um} ist ein Orthonormalsystemvon Eigenvektoren von AT A bzw. AAT .




(1) =⇒ AT = V ΣT UT . (3)



AT ui =



(4)





(1) =⇒ AT = V ΣT UT . (3)



AT ui =



(4)





(5) zeigt, dass die singulären Werte σi eindeutig bestimmt sind, nicht aber dieMatrizen U und V , da mehrfache Eigenwerte von AAT und AT A auftretenkönnen.

Existenzsatz:Jedes A ∈ Rm×n besitzt eine Singulärwertzerlegung.




(5) zeigt, dass die singulären Werte σi eindeutig bestimmt sind, nicht aber dieMatrizen U und V , da mehrfache Eigenwerte von AAT und AT A auftretenkönnen.

Existenzsatz:Jedes A ∈ Rm×n besitzt eine Singulärwertzerlegung.



Satz 5.12Ist die Singulärwertzerlegung von A durch (1) gegeben und giltσ1 ≥ σ2 ≥ · · · ≥ σr > σr+1 = · · · = σmin(m,n) = 0, so ist

(i) r der Rang von A,

(ii) Kern(A) := {x ∈ Rn : Ax = 0} = span{v r+1, . . . , vn},

(iii) Bild(A) := {Ax : x ∈ Rn} = span{u1, . . . ,ur},

(iv) A =r∑

i=1σiui (v i )T = Ur Σr V T

r mit Ur = (u1, . . . ,ur ),

Vr = (v1, . . . , vr ), Σr = diag(σ1, . . . , σr ),

(v) ‖A‖2S :=

m∑i=1

n∑j=1

a2ij =

r∑i=1

σ2i ,

(vi) ‖A‖2 := σ1.







(iv) A =r∑


r mit Ur = (u1, . . . ,ur ),

Vr = (v1, . . . , vr ), Σr = diag(σ1, . . . , σr ),

(v) ‖A‖2S :=

m∑i=1

n∑j=1

a2ij =

r∑i=1

σ2i ,

(vi) ‖A‖2 := σ1.







(iv) A =r∑


r mit Ur = (u1, . . . ,ur ),

Vr = (v1, . . . , vr ), Σr = diag(σ1, . . . , σr ),

(v) ‖A‖2S :=

m∑i=1

n∑j=1

a2ij =

r∑i=1

σ2i ,

(vi) ‖A‖2 := σ1.







(iv) A =r∑


r mit Ur = (u1, . . . ,ur ),

Vr = (v1, . . . , vr ), Σr = diag(σ1, . . . , σr ),

(v) ‖A‖2S :=

m∑i=1

n∑j=1

a2ij =

r∑i=1

σ2i ,

(vi) ‖A‖2 := σ1.







(iv) A =r∑


r mit Ur = (u1, . . . ,ur ),

Vr = (v1, . . . , vr ), Σr = diag(σ1, . . . , σr ),

(v) ‖A‖2S :=

m∑i=1

n∑j=1

a2ij =

r∑i=1

σ2i ,

(vi) ‖A‖2 := σ1.







(iv) A =r∑


r mit Ur = (u1, . . . ,ur ),

Vr = (v1, . . . , vr ), Σr = diag(σ1, . . . , σr ),

(v) ‖A‖2S :=

m∑i=1

n∑j=1

a2ij =

r∑i=1

σ2i ,

(vi) ‖A‖2 := σ1.







(iv) A =r∑


r mit Ur = (u1, . . . ,ur ),

Vr = (v1, . . . , vr ), Σr = diag(σ1, . . . , σr ),

(v) ‖A‖2S :=

m∑i=1

n∑j=1

a2ij =

r∑i=1

σ2i ,

(vi) ‖A‖2 := σ1.



Beweis

(i): Da die Multiplikation mit den regulären Matrizen UT und V den Rang nichtverändert, gilt rang(A) = rang(Σ) = r .

(ii): Es ist V T v i = ei . Somit ist

Av i = UΣV T v i = UΣei = 0 für i = r + 1, . . . ,n.

Also giltv r+1, . . . , vn ∈ Kern(A).

Da dim Kern(A) = n − r , bilden diese Vektoren eine Basis von Kern(A).



Beweis








Beweis








Beweis

(iii): Wegen A = UΣV T ist

Bild(A) = U · Bild(Σ) = U · span(e1, . . . ,er ) = span(u1, . . . ,ur ).

(iv): Durch Block-Matrix-Multiplikation erhält man

A = UΣV T =(u1 . . . um

)Σ

(v1)T

...(vn)T

=r∑

i=1

σiui (v i )T .



Beweis

(iii): Wegen A = UΣV T ist

Bild(A) = U · Bild(Σ) = U · span(e1, . . . ,er ) = span(u1, . . . ,ur ).

(iv): Durch Block-Matrix-Multiplikation erhält man

A = UΣV T =(u1 . . . um

)Σ

(v1)T

...(vn)T

=r∑

i=1

σiui (v i )T .



Beweis(v): Es sei A = (a1, . . . ,an).

Da die orthogonale Matrix UT die Euklidische Länge nicht verändert, gilt

‖A‖2S =

n∑i=1

‖ai‖22 =

n∑i=1

‖UT ai‖22 = ‖UT A‖2

S.

Durch entsprechende Argumentation mit den Zeilen von UT A erhält man

‖A‖2S = ‖UT AV‖2

S = ‖Σ‖2S =

r∑i=1

σ2i .

(vi): Wegen des Beweises des Existenzsatzes ist ‖A‖2 ein singulärer Wertvon A, d.h. ‖A‖2 ≤ σ1, und

‖A‖2 = max{‖Ax‖2 : ‖x‖2 = 1} ≥ ‖Av1‖2 = σ1. �





‖A‖2S =

n∑i=1

‖ai‖22 =

n∑i=1

‖UT ai‖22 = ‖UT A‖2

S.


‖A‖2S = ‖UT AV‖2

S = ‖Σ‖2S =

r∑i=1

σ2i .


‖A‖2 = max{‖Ax‖2 : ‖x‖2 = 1} ≥ ‖Av1‖2 = σ1. �





‖A‖2S =

n∑i=1

‖ai‖22 =

n∑i=1

‖UT ai‖22 = ‖UT A‖2

S.


‖A‖2S = ‖UT AV‖2

S = ‖Σ‖2S =

r∑i=1

σ2i .


‖A‖2 = max{‖Ax‖2 : ‖x‖2 = 1} ≥ ‖Av1‖2 = σ1. �





‖A‖2S =

n∑i=1

‖ai‖22 =

n∑i=1

‖UT ai‖22 = ‖UT A‖2

S.


‖A‖2S = ‖UT AV‖2

S = ‖Σ‖2S =

r∑i=1

σ2i .


‖A‖2 = max{‖Ax‖2 : ‖x‖2 = 1} ≥ ‖Av1‖2 = σ1. �



Pseudoinverse

Wir betrachten erneut das lineare Ausgleichsproblem

Es seien A ∈ Rm×n und b ∈ Rm gegeben mit m ≥ n.

Man bestimme x ∈ Rn mit

‖Ax − b‖2 = min! (1)

und untersuchen dieses nun mit Hilfe der Singulärwertzerlegung.

Wir bezeichnen in diesem ganzen Abschnitt mitσ1 ≥ σ2 ≥ · · · ≥ σr > 0 = σr+1 = · · · = σn = 0 die singulären Werte von A, mitA = UΣV T eine Singulärwertzerlegung von A und mit uj bzw. vk die Spaltenvon U bzw. V .



Pseudoinverse

Wir betrachten erneut das lineare Ausgleichsproblem

Es seien A ∈ Rm×n und b ∈ Rm gegeben mit m ≥ n.

Man bestimme x ∈ Rn mit

‖Ax − b‖2 = min! (1)

und untersuchen dieses nun mit Hilfe der Singulärwertzerlegung.

Wir bezeichnen in diesem ganzen Abschnitt mitσ1 ≥ σ2 ≥ · · · ≥ σr > 0 = σr+1 = · · · = σn = 0 die singulären Werte von A, mitA = UΣV T eine Singulärwertzerlegung von A und mit uj bzw. vk die Spaltenvon U bzw. V .



Satz

Es sei c := UT b ∈ Rm.

Dann ist die Lösungsmenge des linearen Ausgleichsproblems (1) gegebendurch

L = x + Kern(A), (2)

wobei x die folgende spezielle Lösung von (1) bezeichnet:

x :=r∑

i=1

ci

σiv i . (3)



Satz

Es sei c := UT b ∈ Rm.

Dann ist die Lösungsmenge des linearen Ausgleichsproblems (1) gegebendurch

L = x + Kern(A), (2)

wobei x die folgende spezielle Lösung von (1) bezeichnet:

x :=r∑

i=1

ci

σiv i . (3)



Beweis

Da die Multiplikation mit einer orthogonalen Matrix die Euklidische Längenicht ändert, gilt mit z := V T x

‖Ax − b‖22 = ‖UT (Ax − b)‖2

2 = ‖ΣV T x − UT b‖22

= ‖Σz − c‖22 = ‖(σ1z1 − c1, . . . , σr zr − cr ,−cr+1, . . . ,−cm)T‖2

2.

Hieraus liest man die Lösung von (1) sofort ab: zi := ciσi

, i = 1, . . . , r , undzi ∈ R beliebig für i = r + 1, . . . ,n, d.h.

x =r∑

i=1

ci

σiv i +

n∑i=r+1

ziv i , zi ∈ R, i = r + 1, . . . ,n. (4)

Da die letzten n − r Spalten von V den Kern von A aufspannen, kann man dieLösungsmenge L von (1) schreiben als (2), (3). �



Beweis


‖Ax − b‖22 = ‖UT (Ax − b)‖2

2 = ‖ΣV T x − UT b‖22


2.



x =r∑

i=1

ci

σiv i +

n∑i=r+1

ziv i , zi ∈ R, i = r + 1, . . . ,n. (4)




Beweis


‖Ax − b‖22 = ‖UT (Ax − b)‖2

2 = ‖ΣV T x − UT b‖22


2.



x =r∑

i=1

ci

σiv i +

n∑i=r+1

ziv i , zi ∈ R, i = r + 1, . . . ,n. (4)




Pseudonormallösung

In Satz 5.1 wurde gezeigt (und das liest man auch aus Satz 5.19 ab), dass dieLösung des Ausgleichsproblems (1) genau dann eindeutig ist, wennr = Rang(A) = n gilt. Wir erzwingen nun auch im Fall r < n die Eindeutigkeit,indem wir zusätzlich fordern, dass die Euklidische Norm der Lösungmöglichst klein werden soll.

DefinitionEs sei L die Lösungsmenge des Ausgleichsproblems (1).x ∈ L heißt Pseudonormallösung von (1), falls

‖x‖2 ≤ ‖x‖2 für alle x ∈ L.



Pseudonormallösung

In Satz 5.1 wurde gezeigt (und das liest man auch aus Satz 5.19 ab), dass dieLösung des Ausgleichsproblems (1) genau dann eindeutig ist, wennr = Rang(A) = n gilt. Wir erzwingen nun auch im Fall r < n die Eindeutigkeit,indem wir zusätzlich fordern, dass die Euklidische Norm der Lösungmöglichst klein werden soll.

DefinitionEs sei L die Lösungsmenge des Ausgleichsproblems (1).x ∈ L heißt Pseudonormallösung von (1), falls

‖x‖2 ≤ ‖x‖2 für alle x ∈ L.



Pseudonormallösung

Aus der Darstellung (4) der allgemeinen Lösung von (1) liest man ab, dass xaus (3) Pseudonormallösung von (1) ist, denn∥∥∥∥∥x +

n∑i=r+1

ziv i

∥∥∥∥∥ 22 = ‖x‖2

2 +n∑

i=r+1

|zi |2 · ‖v i‖22 ≥ ‖x‖2

2.

Ferner ist die Pseudonormallösung eindeutig bestimmt, und x istoffensichtlich die einzige Lösung von (1) mit x ∈ Kern(A)⊥ ∩ L. Daher gilt

SatzEs gibt genau eine Pseudonormallösung x von (1).Diese ist charakterisiert durch x ∈ Kern(A)⊥ ∩ L.



Pseudonormallösung


n∑i=r+1

ziv i

∥∥∥∥∥ 22 = ‖x‖2

2 +n∑

i=r+1

|zi |2 · ‖v i‖22 ≥ ‖x‖2

2.





Pseudonormallösung


n∑i=r+1

ziv i

∥∥∥∥∥ 22 = ‖x‖2

2 +n∑

i=r+1

|zi |2 · ‖v i‖22 ≥ ‖x‖2

2.





Pseudoinverse

Für jedes A ∈ Rm×n ist durch

Rm 3 b 7→ x ∈ Rn : ‖Ax − b‖2 ≤ ‖Ax − b‖2 ∀x ∈ Rn, ‖x‖2 minimal

eine Abbildung erklärt. Diese ist offensichtlich linear (vgl. die Darstellung vonx in (3), kann also durch eine Matrix A† ∈ R(n,m) dargestellt werden.

DefinitionEs sei A ∈ Rm×n. Dann heißt die Matrix A† ∈ R(n,m), für die durch x := A†b füralle b ∈ Rm die Pseudonormallösung des Ausgleichsproblems (1) gegebenist, die Pseudoinverse ( oder Moore-Penrose Inverse) von A.



Pseudoinverse

Für jedes A ∈ Rm×n ist durch

Rm 3 b 7→ x ∈ Rn : ‖Ax − b‖2 ≤ ‖Ax − b‖2 ∀x ∈ Rn, ‖x‖2 minimal

eine Abbildung erklärt. Diese ist offensichtlich linear (vgl. die Darstellung vonx in (3), kann also durch eine Matrix A† ∈ R(n,m) dargestellt werden.

DefinitionEs sei A ∈ Rm×n. Dann heißt die Matrix A† ∈ R(n,m), für die durch x := A†b füralle b ∈ Rm die Pseudonormallösung des Ausgleichsproblems (1) gegebenist, die Pseudoinverse ( oder Moore-Penrose Inverse) von A.



Bemerkung

Ist Rang(A) = n, so ist das Ausgleichsproblem (1) eindeutig lösbar, und ausden Normalgleichungen folgt, dass die Lösung x = (AT A)−1AT b ist.In diesem Fall ist also A† = (AT A)−1AT .

Ist noch spezieller n = m und A regulär, so ist A† = A−1.Die Pseudo-Inverse wird also zur "’normalen Inversen"’, wenn diese existiert,und ist somit eine konsistente Erweiterung dieses Begriffes. �



Bemerkung

Ist Rang(A) = n, so ist das Ausgleichsproblem (1) eindeutig lösbar, und ausden Normalgleichungen folgt, dass die Lösung x = (AT A)−1AT b ist.In diesem Fall ist also A† = (AT A)−1AT .

Ist noch spezieller n = m und A regulär, so ist A† = A−1.Die Pseudo-Inverse wird also zur "’normalen Inversen"’, wenn diese existiert,und ist somit eine konsistente Erweiterung dieses Begriffes. �



Aus unserer Konstruktion ergibt sich sofort im allgemeinen Fall

Satz 5.25Sei A ∈ Rm×n mit der Singulärwertzerlegung

A = UΣV T , Σ = (σiδij )i,j .

Dann gilt

(i) Σ† = (τiδij )j,i , τi =

{σ−1

i , falls σi 6= 00, falls σi = 0

,

(ii) A† = V Σ†UT .






Dann gilt


{σ−1


,

(ii) A† = V Σ†UT .






Dann gilt


{σ−1


,

(ii) A† = V Σ†UT .






Dann gilt


{σ−1


,

(ii) A† = V Σ†UT .



Pseudoinverse

Die explizite Matrix-Darstellung der Pseudoinverse braucht man genausohäufig wie die der inversen Matrix, nämlich fast nie. �

Aus der Darstellung der Pseudoinversen in Satz 5.25 (ii) folgt unmittelbar

Korollar 5.27Für jede Matrix A ∈ Rm×n gilt

A†† = A

und(A†)T = (AT )†.

A† besitzt also die üblichen Eigenschaften der Inversen A−1 für reguläres A.Es gilt jedoch i.a.

(AB)† 6= B†A†.



Pseudoinverse




A†† = A

und(A†)T = (AT )†.


(AB)† 6= B†A†.



Pseudoinverse




A†† = A

und(A†)T = (AT )†.


(AB)† 6= B†A†.



Pseudoinverse




A†† = A

und(A†)T = (AT )†.


(AB)† 6= B†A†.



Störung von Ausgleichsproblemen

Wir übertragen nun den Begriff der Kondition einer Matrix auf singuläre undallgemeiner auf nicht quadratische Matrizen.

Es ist klar, dass für den quadratischen, nicht regulären Fall dieserverallgemeinerte Konditionsbegriff nicht mehr als Verstärkungsfaktor für dieStörung linearer Systeme gedeutet werden kann. Er spielt aber eine ähnlicheRolle für lineare Ausgleichsprobleme.

Wir beschränken uns auf die Euklidische Norm.
















Wir betrachten das lineare Ausgleichsproblem

‖Ax − b‖2 = min!

mit A ∈ Rm×n, Rang(A) = r ,

und eine Störung hiervon

‖(A + ∆A)(x + ∆x)− (b + ∆b)‖2 = min!.

Die Normalgleichungen lauten

(A + ∆A)T ((A + ∆A)(x + ∆x)− (b + ∆b)) = 0.





‖Ax − b‖2 = min!



‖(A + ∆A)(x + ∆x)− (b + ∆b)‖2 = min!.


(A + ∆A)T ((A + ∆A)(x + ∆x)− (b + ∆b)) = 0.





‖Ax − b‖2 = min!



‖(A + ∆A)(x + ∆x)− (b + ∆b)‖2 = min!.


(A + ∆A)T ((A + ∆A)(x + ∆x)− (b + ∆b)) = 0.




Zieht man von den Normalgleichungen diejenigen des AusgangsproblemsAT Ax − AT b = 0 ab und vernachlässigt man Terme zweiter Ordnung, so folgt

AT A∆x + ∆AT Ax + AT ∆Ax − AT ∆b −∆AT b = 0,

d.h.

∆x = (AT A)−1(AT ∆b − AT ∆Ax) + (AT A)−1∆AT (b − Ax)

= A†(∆b −∆Ax) + (AT A)−1∆AT (b − Ax).

Übergang zur Euklidischen Norm liefert wegen ‖A†‖2 = 1σn

und‖(AT A)−1‖2 = 1

σ2n

‖∆x‖2 ≤1σn

(‖∆b‖2 + ‖∆A‖2‖x‖2) +1σ2

n‖∆A‖2‖Ax − b‖2. (1)






d.h.


= A†(∆b −∆Ax) + (AT A)−1∆AT (b − Ax).


und‖(AT A)−1‖2 = 1

σ2n

‖∆x‖2 ≤1σn

(‖∆b‖2 + ‖∆A‖2‖x‖2) +1σ2

n‖∆A‖2‖Ax − b‖2. (1)






d.h.


= A†(∆b −∆Ax) + (AT A)−1∆AT (b − Ax).


und‖(AT A)−1‖2 = 1

σ2n

‖∆x‖2 ≤1σn

(‖∆b‖2 + ‖∆A‖2‖x‖2) +1σ2

n‖∆A‖2‖Ax − b‖2. (1)




Wir betrachten zunächst den Fall, dass nur die rechte Seite b Störungenenthält, d.h. ∆A = 0.

Dann gilt‖∆x‖2

‖x‖2≤ 1σr

‖∆b‖2

‖x‖2.

Die Darstellung der Pseudonormallösung liefert

‖x‖22 =

r∑i=1

c2i

σ2i≥ 1σ2

1

r∑i=1

c2i =

1σ2

1‖

r∑i=1

(ui )T bui‖22.






‖x‖2≤ 1σr

‖∆b‖2

‖x‖2.


‖x‖22 =

r∑i=1

c2i

σ2i≥ 1σ2

1

r∑i=1

c2i =

1σ2

1‖

r∑i=1

(ui )T bui‖22.






‖x‖2≤ 1σr

‖∆b‖2

‖x‖2.


‖x‖22 =

r∑i=1

c2i

σ2i≥ 1σ2

1

r∑i=1

c2i =

1σ2

1‖

r∑i=1

(ui )T bui‖22.




Da offenbarr∑

i=1(ui )T bui die Projektion von b auf den Bildbereich von A ist,

folgt also für den relativen Fehler

‖∆x‖2

‖x‖2≤ σ1

σr

‖∆b‖2

‖PBild(A)b‖2=σ1

σr

‖∆b‖2

cos θ‖b‖2(2)

wobei θ den Winkel zwischen b und seiner Projektion auf den Bildbereich vonA bezeichnet.

Diese Ungleichung beschreibt wieder, wie sich der relative Fehler der rechtenSeite eines Ausgleichsproblems auf die Lösung auswirken kann. Wirdefinieren daher

Definition: A ∈ Rm×n besitze die Singulärwertzerlegung A = UΣV T . Dannheißt κ2(A) := σ1

σrdie Kondition der Matrix A.




Da offenbarr∑



‖∆x‖2

‖x‖2≤ σ1

σr

‖∆b‖2


σr

‖∆b‖2

cos θ‖b‖2(2)








Da offenbarr∑



‖∆x‖2

‖x‖2≤ σ1

σr

‖∆b‖2


σr

‖∆b‖2

cos θ‖b‖2(2)








Bemerkung: Ist A ∈ R(n,n) regulär, so stimmt diese Definition der Kondition mitder vorher gegebenen (für die Euklidische Norm) überein.

Bemerkung: Wegen κ2(AT A) = κ2(A)2 und κ2(A) > 1 sind dieNormalgleichungen eines linearen Ausgleichsproblems schlechterkonditioniert als die Koeffizientenmatrix des Ausgleichsproblems.




Bemerkung: Ist A ∈ R(n,n) regulär, so stimmt diese Definition der Kondition mitder vorher gegebenen (für die Euklidische Norm) überein.

Bemerkung: Wegen κ2(AT A) = κ2(A)2 und κ2(A) > 1 sind dieNormalgleichungen eines linearen Ausgleichsproblems schlechterkonditioniert als die Koeffizientenmatrix des Ausgleichsproblems.




Wir lassen nun auch Störungen der Koeffizientenmatrix A zu, nehmen aberan, dass A linear unabhängige Spalten besitzt, d.h. r = n.

Wegen 1σn

= κ2(A)‖A‖2

folgt aus der Abschätzung (1)

‖∆x‖2

‖x‖2≤ κ2(A)

( ‖∆b‖2

‖A‖2‖x‖2+‖∆A‖2

‖A‖2

)+ κ2(A)2 ‖∆A‖2

‖A‖2

‖Ax − b‖2

‖A‖2‖x‖2.

und mit (2) erhält man

‖∆x‖2

‖x‖2≤ κ2(A)

( ‖∆b‖2

cos θ‖b‖2+‖∆A‖2

‖A‖2

)+ κ2(A)2 ‖∆A‖2

‖A‖2tan θ.

Relative Fehler der Koeffizientenmatrix werden also sogar um den Faktorκ2(A)2 verstärkt, wenn das Residuum Ax − b von Null verschieden ist.





Wegen 1σn

= κ2(A)‖A‖2


‖∆x‖2

‖x‖2≤ κ2(A)

( ‖∆b‖2

‖A‖2‖x‖2+‖∆A‖2

‖A‖2

)+ κ2(A)2 ‖∆A‖2

‖A‖2

‖Ax − b‖2

‖A‖2‖x‖2.


‖∆x‖2

‖x‖2≤ κ2(A)

( ‖∆b‖2


‖A‖2

)+ κ2(A)2 ‖∆A‖2

‖A‖2tan θ.






Wegen 1σn

= κ2(A)‖A‖2


‖∆x‖2

‖x‖2≤ κ2(A)

( ‖∆b‖2

‖A‖2‖x‖2+‖∆A‖2

‖A‖2

)+ κ2(A)2 ‖∆A‖2

‖A‖2

‖Ax − b‖2

‖A‖2‖x‖2.


‖∆x‖2

‖x‖2≤ κ2(A)

( ‖∆b‖2


‖A‖2

)+ κ2(A)2 ‖∆A‖2

‖A‖2tan θ.






Wegen 1σn

= κ2(A)‖A‖2


‖∆x‖2

‖x‖2≤ κ2(A)

( ‖∆b‖2

‖A‖2‖x‖2+‖∆A‖2

‖A‖2

)+ κ2(A)2 ‖∆A‖2

‖A‖2

‖Ax − b‖2

‖A‖2‖x‖2.


‖∆x‖2

‖x‖2≤ κ2(A)

( ‖∆b‖2


‖A‖2

)+ κ2(A)2 ‖∆A‖2

‖A‖2tan θ.




Regularisierung

Einige Probleme der Anwendungen (z.B. in der Tomographie oder bei derAusbreitung von Rissen in den Materialwissenschaften) führen auf lineareGleichungssysteme oder Ausgleichsprobleme mit schlecht konditioniertenKoeffizientenmatrizen.

In diesen Fällen lassen die Störungsüberlegungen in Abschnitt 4.4 und 5.5erwarten, dass die bisher betrachteten Verfahren zu schlechten oder garunbrauchbaren Ergebnissen führen.



Regularisierung

Einige Probleme der Anwendungen (z.B. in der Tomographie oder bei derAusbreitung von Rissen in den Materialwissenschaften) führen auf lineareGleichungssysteme oder Ausgleichsprobleme mit schlecht konditioniertenKoeffizientenmatrizen.

In diesen Fällen lassen die Störungsüberlegungen in Abschnitt 4.4 und 5.5erwarten, dass die bisher betrachteten Verfahren zu schlechten oder garunbrauchbaren Ergebnissen führen.



Beispiel

Das Problem, die orthogonale Projektion einer gegebenen Funktionf : [0,1]→ R auf den Raum Πn−1 der Polynome vom Höchstgrad n − 1 bzgl.des inneren Produkts

〈f ,g〉 :=

∫ 1

0f (x)g(x) dx

zu berechnen, führt bei der Wahl der Basis {1, x , . . . , xn−1} auf das lineareGleichungssystem

Ay = b (1)

mit der MatrixA = (aij )i,j=1,...,n, aij :=

1i + j − 1

, (2)

der sogenannten Hilbert Matrix, und b ∈ Rn, bi := 〈f , x i−1〉.



Beispiel

Wir wählen für die Dimensionen n = 10, n = 20 und n = 40 die rechte Seitevon (1) so, dass y = (1, . . . ,1)T die eindeutige Lösung ist, und behandeln (1)mit den bekannten numerischen Verfahren. Unter MATLAB erhält man mit derLR-Zerlegung mit Spaltenpivotsuche (in MATLAB A\b), mit dem CholeskyVerfahren, der QR Zerlegung der Matrix A und der Singulärwertzerlegung vonA die folgenden Fehler in der Euklidischen Norm:

n = 10 n = 20 n = 40LR Zerlegung 5.24 E-4 8.25 E+1 3.78 E+2Cholesky 7.15 E-4 numer. nicht pos. def.QR Zerlegung 1.41 E-3 1.67 E+2 1.46 E+3SVD 8.24 E-4 3.26 E+2 8.35 E+2

Die Ergebnisse sind also (wenigstens für die Dimensionen n = 20 odern = 40) unbrauchbar.



Beispiel






Beispiel






BeispielEin ähnliches Verhalten zeigt sich bei dem Ausgleichsproblem. Wir betrachtenfür n = 10, n = 20 und n = 40 und m = n + 10 die Ausgleichsprobleme

‖Ax − b‖2 = min!

mit der Hilbert Matrix A ∈ Rm×n, wobei b so gewählt ist, dass x = (1, . . . ,1)T

die Lösung ist mit dem Residuum Ax − b = 0.

Die folgende Tabelle enthält wieder die Fehler in der Euklidischen Norm fürdie Lösung der Normalgleichungen mit der LR-Zerlegung (das CholeskyVerfahren führte schon bei n = 10 zu der Meldung, dass dieKoeffizientenmatrix nicht positiv definit ist), mit der QR Zerlegung und derSingulärwertzerlegung. Die Lösungen sind ebenfalls unbrauchbar.

n = 10 n = 20 n = 40Normalgleichungen 2.91 E+2 2.40 E+2 8.21 E+2QR Zerlegung 1.93 E-5 5.04 E+0 1.08 E+1SVD 4.67 E-5 6.41 E+1 3.72 E+2




‖Ax − b‖2 = min!








‖Ax − b‖2 = min!







Regularisierung

Bei schlecht konditionierten Ausgleichsproblemen oder Gleichungssystemen(n = m) ist das folgende Vorgehen zu empfehlen:

Bestimme die Singulärwertzerlegung A = UΣV T von A; setze

Σ†τ = diag(ηiδji ), ηi :=

{σ−1

i falls σi ≥ τ,0 sonst,

wobei τ > 0 eine gegebene Zahl ist,

A†τ := V Σ†τUT , x := A†τb.

A†τ heißt effektive Pseudoinverse von A.



Regularisierung




{σ−1







Regularisierung




{σ−1







Regularisierung

Von den Bedingungen aus Satz 5.29 bleiben nur

A†τAA†τ = A†τ , A†τA = (A†τA)T , AA†τ = (AA†τ )T

erhalten.

An Stelle von AA†A = A gilt nur

‖AA†τA− A‖2 ≤ τ.

Das obige Verfahren nennt man eine Regularisierung. Zu kleine singuläreWerte werden unschädlich gemacht, um die Kondition zu verbessern. Dafürnimmt man einen Verfahrensfehler in Kauf.

Man löst an Stelle des Gleichungssystems Ax = b das System Ax = Pb,wobei P die orthogonale Projektion auf den Teilraum span{ui : σi ≥ τ}bezeichnet.



Regularisierung



erhalten.


‖AA†τA− A‖2 ≤ τ.





Regularisierung



erhalten.


‖AA†τA− A‖2 ≤ τ.





Regularisierung



erhalten.


‖AA†τA− A‖2 ≤ τ.





Tikhonov Regularisierung

Die bekannteste Regularisierung wurde unabhängig von Philips (1962) undTikhonov (1963) eingeführt und wird als Tichonov Regularisierung bezeichnet.

Sie entspricht einer Dämpfung des Einflusses kleiner singulärer Werte bei derLösung.

Man löst an Stelle des Systems Ax = b das Gleichungssystem

(AT A + αIn)x = AT b (4)

mit einem Regularisierungsparameter α > 0.




















Offenbar ist (4) äquivalent zu

‖Ax − b‖22 + α‖x‖2

2 = min! (5)

(dies ist die übliche Formulierung der Tichonov Regularisierung) oder zu

‖Ax − b‖2 = min, A =

(A√αIn

), b =

(b0

). (6)

Diese letzte Formulierung wurde zusammen mit der QR Zerlegung der MatrixA von Golub (1965) erstmals verwendet, um die Regularisierung stabilauszuführen.





‖Ax − b‖22 + α‖x‖2

2 = min! (5)


‖Ax − b‖2 = min, A =

(A√αIn

), b =

(b0

). (6)






‖Ax − b‖22 + α‖x‖2

2 = min! (5)


‖Ax − b‖2 = min, A =

(A√αIn

), b =

(b0

). (6)





Wegen AT A = AT A +αIn besitzt A die singulären Werte√σ2

i + α, wenn die σi

die singulären Werte von A sind, und die Kondition von (1) wird verkleinert zu√σ2

1+α

σ2n+α

.

Ist β := UT b, so ist (6) wegen (4) äquivalent zu

V (ΣT UT UΣ + αIn)V T x = V ΣT UT b = V ΣTβ,

d.h.

x = V (ΣT Σ + αIn)−1ΣTβ =n∑

i=1

βiσi

σ2i + α

v i .

Man benötigt also nur die Singulärwertzerlegung von A, um das regularisierteProblem für verschiedene Regularisierungsparameter α zu lösen.







1+α

σ2n+α

.



d.h.


i=1

βiσi

σ2i + α

v i .








1+α

σ2n+α

.



d.h.


i=1

βiσi

σ2i + α

v i .





Wir wenden auf das Gleichungssystem (1) die Regularisierungen durchAbschneiden der kleinen singulären Werte an und die verschiedenen Formender Tichonov Regularisierungen.

Dabei wird der Regularisierungsparameter α jeweils so gewählt, dass derFehler minimal wird.

Dies ist bei praktischen Problemen natürlich nicht möglich (die Lösung desProblems wird ja erst noch gesucht). Strategien zur Wahl des Parametersfindet man in Hansen (1998), Engl (1997) oder Louis (1989).

Als grobe Richtlinie kann man sagen, dass man eine numerische Lösung, diebedingt durch die schlechte Kondition eines Problems verfälscht ist, häufigdaran erkennt, das sie stark oszilliert. Man variiert dann interaktiv denParameter solange, bis man die Lösung glaubt (d.h. bis die gefundeneLösung die physikalischen Eigenschaften des modellierten Problems richtigwiedergibt).

























Für das lineare Gleichungssystem (1), (2) erhält man die Fehler der folgendenTabelle. Dabei wurden die Normalgleichungen der Tychnow Regularisierung(3) mit der Cholesky Zerlegung gelöst (die LR-Zerlegung mit dem MATLABBefehl \ lieferte ähnliche Ergebnisse) und das regularisierteAusgleichsproblem (4) wurde mit der QR Zerlegung von A und derSingulärwertzerlegung von A gelöst.

n = 10 n = 20 n = 40Tichonov Cholesky 1.41 E-3 2.03 E-3 3.51 E-3Tichonov QR 3.50 E-6 5.99 E-6 7.54 E-6Tichonov SVD 3.43 E-6 6.33 E-6 9.66 E-6Abgeschnittene SVD 2.77 E-6 3.92 E-6 7.35 E-6




Für das lineare Gleichungssystem (1), (2) erhält man die Fehler der folgendenTabelle. Dabei wurden die Normalgleichungen der Tychnow Regularisierung(3) mit der Cholesky Zerlegung gelöst (die LR-Zerlegung mit dem MATLABBefehl \ lieferte ähnliche Ergebnisse) und das regularisierteAusgleichsproblem (4) wurde mit der QR Zerlegung von A und derSingulärwertzerlegung von A gelöst.





Für das Ausgleichsproblem erhält man





Für das Ausgleichsproblem erhält man




L Kurve

Ein häufig verwendetes Verfahren zur Schätzung des optimalenRegularisierungsparameters ist die L-Kurven Methode.

In ihr betrachtet man die Kurve

α 7→ (‖Axα − b‖2, ‖xα‖2).

Diese sog. L-Kurve hat häufig die Gestalt des Buchstaben L wie in der Skizze,wobei der Parameter α, der zu dem “Knick” gehört, optimal ist.



L Kurve



α 7→ (‖Axα − b‖2, ‖xα‖2).




L Kurve



α 7→ (‖Axα − b‖2, ‖xα‖2).




L Kurve

Für Systeme, für die Koeffizienten bT uj der (ungestörten) rechten Seite bzgl.der singulären Vektoren uj von A schneller abfallen als die singulären Werteσj von A, kann man die L-Kurven Methode begründen.

Im allgemeinen Fall kann diese Methode aber versagen.



L Kurve

Für Systeme, für die Koeffizienten bT uj der (ungestörten) rechten Seite bzgl.der singulären Vektoren uj von A schneller abfallen als die singulären Werteσj von A, kann man die L-Kurven Methode begründen.

Im allgemeinen Fall kann diese Methode aber versagen.



L Kurve

10−3

10−2

10−1

100

101

100

101

102

103

104

105

||Axλ−b||2

||xλ|| 2

L Kurve; Hilbertmatrix der Dimension 100; Stoerung 0.1%

α=1α=1e−2α=1e−4

α=1e−6

α=1e−8

α=1e−10

α=1e−12

α=1e−14

α=1e−16



L Kurve

Die Abbildung enthält die L-Kurve für das Gleichungssystem mit derHilbertmatrix der Dimension 100 und der Lösung x = (1, . . . ,1)T , wobeizusätzlich die rechte Seite mit einem zufälligen Fehler von höchstens 0.1%verfälscht worden ist (Für dieses Beispiel ist die im letzten Absatz genannteBedingung übrigens nicht erfüllt).

Die folgende Tabelle enthält ‖Axα − b‖2, ‖xα‖2 und den Fehler ‖xα − x‖2 fürverschiedene Parameter α. Tatsächlich ist der Fehler minimal für α = 1e− 06,und bei diesem Parameter liegt auch der Knick der L-Kurve.



L Kurve

Die Abbildung enthält die L-Kurve für das Gleichungssystem mit derHilbertmatrix der Dimension 100 und der Lösung x = (1, . . . ,1)T , wobeizusätzlich die rechte Seite mit einem zufälligen Fehler von höchstens 0.1%verfälscht worden ist (Für dieses Beispiel ist die im letzten Absatz genannteBedingung übrigens nicht erfüllt).

Die folgende Tabelle enthält ‖Axα − b‖2, ‖xα‖2 und den Fehler ‖xα − x‖2 fürverschiedene Parameter α. Tatsächlich ist der Fehler minimal für α = 1e− 06,und bei diesem Parameter liegt auch der Knick der L-Kurve.



L Kurve

α ‖Axα − b‖2 ‖xα‖2 ‖xα − x‖2

1e+00 4.0508e+00 6.2357e+00 5.3199e+001e-01 8.7802e-01 8.6987e+00 2.9868e+001e-02 1.6321e-01 9.5915e+00 1.6413e+001e-03 3.0354e-02 9.8697e+00 9.0701e-011e-04 6.2919e-03 9.9553e+00 5.2049e-011e-05 2.2522e-03 9.9819e+00 2.5714e-011e-06 1.7941e-03 9.9944e+00 1.0069e-011e-07 1.7862e-03 1.0017e+01 4.9295e-011e-08 1.8052e-03 1.0287e+01 2.3157e+001e-09 1.8355e-03 1.7458e+01 1.4260e+011e-10 1.9748e-03 8.3028e+01 8.2396e+011e-11 2.3529e-03 2.0179e+02 2.0153e+021e-12 2.5359e-03 5.3920e+02 5.3911e+02


Documents

Heinrich Voss - mat.tuhh.de · Cholesky Zerlegung lösen. Diese Methode erfordert zur Aufstellung der Normalgleichungen (unter Beachtung der Symmetrie von ATA) 1 2 n(n + 1) + n innere