Dahmen-Reusken Kapitel 4 1 - News | IGPM · Wir nehmen A und b wie in Beispiel 4.12. Die Methode uber die QR-Zerlegung von A, auf einer Maschine mit eps ≈ 10−16, ergibt δ = 10−4:

KAPITEL 4. Lineare Ausgleichsrechnung

Beispiel 4.1. Das Ohmsche Gesetz:

U = RI

Eine Meßreihe von Daten:

(Ui, Ii) (Spannung, Stromstarke), i = 1, . . . , m.

Aufgabe: man bestimme aus diesen Meßdaten den Widerstand R im

Stromkreis. Theoretisch:

Ui = RIi, i = 1, . . . , m.

Aber Daten sind mit Fehlern behaftet.

-

6

##

##

##

##

##

##

###

b

b b

b

b

b

b

I

U

Ui

Ii

Dahmen-Reusken Kapitel 4 1

Man kann hierzu versuchen, die durch eine Wahl von R bedingten

Residuen Ui − RIi zu quadrieren, aufzusummieren und dasjenige R zu

suchen, das diesen Ausdruck minimiert:

f(R) :=m∑

i=1

(RIi − Ui)2 = min .

Da f eine quadratische Funktion ist, kann nur ein Extremum vorliegen,

das durch die Nullstelle der Ableitung gegeben ist:

0 = f ′(R) =m∑

i=1

2(RIi − Ui)Ii = 2R

( m∑

i=1

I2i

)

− 2m∑

i=1

UiIi.

Hier ergibt sich diese Nullstelle R∗ als

R∗ =

( m∑

i=1

UiIi

)/( m∑

i=1

I2i

)

. △


Beispiel 4.2.

In der Fourieranalyse wird eine T -periodische Funktion f durch eine

Linearkombination der T -periodischen trigonometrischen Polynome

1, cos(ct), sin(ct), cos(2ct), sin(2ct), . . . , cos(Nct), sin(Nct)

mit c := 2πT in der Form

gN(t) =1

2a0 +

N∑

k=1

(ak cos(kct) + bk sin(kct)) ,

approximiert.

Annahme: nicht f , sondern nur eine Reihe von Meßdaten

bi ≈ f(ti), 0 ≤ t1 < t2 < . . . < tm ≤ T,

ist bekannt, wobei m > 2N + 1.

Ansatz zur Bestimmung der Koeffizienten a0, a1, b1, a2, b2, . . . , aN , bN :

m∑

i=1

(gN(ti) − bi)2 = min . △


Das allgemeine lineare Ausgleichsproblem

Das Minimierungsproblem

m∑

i=1

(y(ti;x1, . . . , xn) − bi)2 =

m∑

i=1

(ai,1x1 + . . . + ai,nxn − bi)2 = min

wird in Matrixform dargestellt. Setzt man

A = (ai,j)m,ni,j=1 ∈ R

m×n, b ∈ Rm,

nimmt das Minimierungsproblem eine kompakte Form an:

‖Ax − b‖22 = minx∈Rn

.

Also:

Zu gegebenem A ∈ Rm×n und b ∈ R

n, bestimme x∗ ∈ Rn, fur das

‖Ax∗ − b‖2 = minx∈Rn

‖Ax − b‖2gilt.


Beispiel 4.3.

Man vermutet, daß die Meßdaten

t 0 1 2 3

y 3 2.14 1.86 1.72

einer Gesetzmaßigkeit der Form

y = f(t) = α1

1 + t+ β

mit noch zu bestimmenden Parametern α, β ∈ R gehorchen. Das zu-

gehorige lineare Ausgleichsproblem hat die Gestalt (4.14), mit

x =

(

αβ

)

, A =

1 112 113 114 1

, b =

32.141.861.72

. △


Normalgleichungen

Die Losung von (4.14) laßt sich auf die Losung des linearen Glei-

chungssystems

ATAx = AT b

reduzieren, das haufig als Normalgleichungen bezeichnet wird.

Beachte: fur A ∈ Rm×n ist die Matrix ATA ∈ Rn×n stets quadratisch.

Kernaussage:

Satz 4.5. x∗ ∈ Rn ist genau dann Losung des linearen Ausgleichs-

problems (4.14), wenn x∗ Losung der Normalgleichungen

ATAx = AT b

ist. Das System der Normalgleichungen hat stets mindestens eine

Losung. Sie ist genau dann eindeutig, wenn Rang(A) = n gilt.


Geometrische Interpretation

Anschaulich ist klar, daß die Differenz b − Ax gerade senkrecht auf

dem Bildraum Bild(A) = {Ax | x ∈ Rn} stehen muß, damit der Abstand

‖Ax − b‖2 minimal ist. Also gilt:

‖Ax − b‖2 = min ⇐⇒ Ax − b ⊥ Bild(A) ,

-R

n

@@

@I

��

��

��

��

��

��Ax∗

x∗ ∈ Rn

b − Ax∗

b

6

��

��

��

��

��

��

��

��

��

Rm−n Bild(A)

= {Ax |x ∈ Rn}

@@

@@


In Beispiel 3.32 wurde bereits folgende Tatsache gezeigt:

Bemerkung 4.6. Falls A ∈ Rm×n vollen (Spalten-)Rang n hat,

so ist die Matrix ATA ∈ Rn×n symmetrisch positiv definit.

Annahme: Wir beschranken uns in den Abschnitten 4.3 und 4.4 auf

den Fall, daß A vollen Spaltenrang hat: Rang(A) = n.

Der Fall Rang(A) < n wird in Abschnitt 4.7 diskutiert.


Kondition des linearen Ausgleichsproblems

κ2(A) := maxx6=0

‖Ax‖2‖x‖2

/

minx6=0

‖Ax‖2‖x‖2

.

Ausgleichsproblem mit Storungen:

‖Ax − b‖2 = min .

--��*

��

��

��

��

��

��HHHHHHj

Θ Ax∗ Ax

b

b

δb

Satz 4.7. Fur die Kondition des linearen Ausgleichsproblems

bezuglich Storungen in b gilt

‖x − x∗‖2‖x∗‖2

≤ κ2(A)

cosΘ

‖b − b‖2‖b‖2

.


Beispiel 4.8.

A :=

1 10 00 1

, b :=

0.0110

.

Man kann einfach nachrechnen, daß κ2(A) ≈ 2.62 und

x∗ = (ATA)−1AT b =

(

0.010

)

gilt. Fur b = (0.01,1,0.01)T erhalt man

x = (ATA)−1AT b =

(

00.01

)

.

Daraus folgt

‖x − x∗‖2‖x∗‖2

≈ 100‖b − b‖2‖b‖2

,

also eine schlechte Kondition. Es gilt

cosΘ =‖Ax∗‖2‖b‖2

= 0.01. △


Kondition des linearen Ausgleichsproblems

Satz 4.9. Fur die Kondition des linearen Ausgleichspro-

blems bezuglich Storungen in A gilt

‖x − x∗‖2‖x∗‖2

≤(

κ2(A) + κ2(A)2 tanΘ) ‖A − A‖2

‖A‖2.


Numerische Losung des linearen Ausgleichsproblems

Losung der Normalgleichungen

Die Matrix ATA ist symmetrisch positiv definit.

Folglich ergibt sich die Methode:

• Berechne ATA, AT b.

• Berechne die Cholesky-Zerlegung

LDLT = ATA

von ATA.

• Lose

Ly = AT b, LTx = D−1y

durch Vorwarts- bzw. Ruckwartseinsetzen.


Nachteile dieser Vorgehensweise

• Die Berechnung von ATA ist fur große m aufwendig und birgt

die Gefahr von Genauigkeitsverlust durch Ausloschungseffekte. Die

Eintrage von ATA sind also mit (moglicherweise erheblichen relati-

ven) Fehlern behaftet.

• Bei der Losung des Systems ATAx = AT b uber das Cholesky-

Verfahren werden die Rundungsfehler in ATA und AT b mit

κ2(ATA)

verstarkt. Es gilt

κ2(ATA) = κ2(A)2.

Folglich wird die Rundungsfehlerverstarkung durch κ2(A)2 beschrie-

ben.


Beispiel 4.12.

A =

√3

√3

δ 00 δ

, b =

2√

3δδ

, 0 < δ ≪ 1.

Das lineare Ausgleichsproblem ‖Ax − b‖2 = min hat die Losung

x∗ = (1,1)T (fur alle δ > 0). Außerdem gilt Θ = 0.

Daher wird die Kondition dieses Problems durch κ2(A) beschrieben.

Man rechnet einfach nach, daß

κ2(A) ≈√

6

δ

gilt. Ein stabiles Verfahren sollte ein Resultat x liefern, mit

‖x − x∗‖2‖x∗‖2

/ κ2(A) eps .


Die Losung dieses Problems uber die Normalgleichungen und das

Cholesky-Verfahren auf einer Maschine mit eps ≈ 10−16 ergibt:

δ = 10−4 :‖x − x∗‖2‖x∗‖2

≈ 2 ∗ 10−8 ≈ 1

3κ2(A)2 eps

δ = 10−6 :‖x − x∗‖2‖x∗‖2

≈ 2 ∗ 10−4 ≈ 1

3κ2(A)2 eps .


Losung uber QR-Zerlegung

Satz 4.13. Sei A ∈ Rm×n mit Rang(A) = n und b ∈ R

m. Sei

Q ∈ Rm×m eine orthogonale Matrix und R ∈ Rn×n eine obere

Dreiecksmatrix, so daß

QA = R :=

(

R∅

)

} n} m − n

.

Dann ist die Matrix R regular. Schreibt man

Qb =

(

b1b2

)

} n} m − n

,

dann ist x∗ = R−1b1 die Losung des linearen Ausgleichsproblems

(4.14). Die Norm ‖Ax∗ − b‖2 ist gerade durch ‖b2‖2 gegeben.

Grundidee:

‖Ax − b‖22 = ‖QAx − Qb‖22 = ‖Rx − Qb‖22 = ‖Rx − b1‖22 + ‖b2‖22.


Aus Satz 4.13 ergibt sich nun folgende Methode:

• Bestimme von A die QR-Zerlegung

QA =

(

R∅

)

(R ∈ Rn×n),

z.B. mittels Givens-Rotationen oder Householder-Spiegelung-

en und berechne Qb =(

b1b2

)

.

• Lose

Rx = b1

mittels Ruckwartseinsetzen.

Die Norm des Residuums minx∈Rn ‖Ax − b‖2 = ‖Ax∗ − b‖2 ist gerade

durch ‖b2‖2 gegeben.


Beispiel 4.15.

Sei

A =

3 70 124 1

, b =

1015

,

d.h. m = 3, n = 2. Man bestimme die Losung x∗ ∈ R2 von

‖Ax − b‖2 = min .

• Annullierung von a3,1:

A(2) = G1,3A =

5 50 120 −5

, b(2) = G1,3b =

101−5

.

(In der Praxis werden die Transformationen G1,3A und G1,3b aus-

gefuhrt, ohne daß G1,3 explizit berechnet wird.)


• Annullierung von a(2)3,2:

A(3) = G2,3A(2) =

5 50 130 0

=

(

R∅

)

, b(3) = G2,3b(2) =

103713

− 5513

.

Losung von(

5 50 13

)

(x1

x2

)

=(103713

)

durch Ruckwartseinsetzen:

x∗ =

(

301

169,

37

169

)T.

Als Norm des Residuums ergibt sich:

‖b2‖2 =55

13. △


Wegen Satz 3.41 gilt

κ2(A) = κ2(R),

d.h., das Quadrieren der Kondition, das bei den Normalgleichun-

gen auftritt, wird vermieden. Außerdem ist die Berechnung der

QR-Zerlegung uber Givens- oder Householder-Transformationen

ein sehr stabiles Verfahren, wobei die Fehlerverstarkung durch

κ2(A) (und nicht κ2(A)2) beschrieben wird.


Beispiel 4.16

Wir nehmen A und b wie in Beispiel 4.12. Die Methode uber die QR-

Zerlegung von A, auf einer Maschine mit eps ≈ 10−16, ergibt

δ = 10−4 :‖x − x∗‖2‖x∗‖2

≈ 2.2 ∗ 10−16,

δ = 10−6 :‖x − x∗‖2‖x∗‖2

≈ 1.6 ∗ 10−16.

Wegen der sehr guten Stabilitat dieser Methode sind diese Resultate

viel besser als die Resultate in Beispiel 4.12. △


4.5 Zum statistischen Hintergrund - lineare Regression

Gegeben seien Daten (t1, y1), . . . , (tm, ym) mit

ti: feste (deterministische) Meßpunkte,

yi: Realisierungen von Zufallsvariablen Yi.

Lineare Regression basiert auf dem Ansatz

Yi =n∑

k=1

ak(ti)xk + Fi, i = 1, . . . , m,

ak(t): geeignete Ansatzfunktionen,

Fi: Meßfehler (Zufallsvariablen).

Ziel: eine Schatzung x = (x1, . . . , xn)T fur den unbekannten Parame-

tersatz x = (x1, . . . , xn)T ∈ Rn bestimmen.

Einen solchen Schatzer liefert die lineare Ausgleichsrechnung.

Sei namlich x die Losung des linearen Ausgleichsproblems

‖Ax − y‖22 → min .

Dann ist x ebenfalls eine Zufallsvariable.


x als Best Linear Unbiased Estimator (BLUE)

Annahmen:

- Fi unabhangig, identisch verteilt mit Erwartungswert E(Fi) = 0

- Varianz-Kovarianzmatrix

V (F) := E(FFT ) =(

E(FiFj))m

i,j=1= σ2I

Dann gilt

E(x) = x, V (x) = E

(

(x − x)(x − x)T)

= σ2(ATA)−1.

Der Schatzer ist erwartungstreu und hat minimale Varianz.

Man spricht von einem Best Linear Unbiased Estimator (BLUE).


x als Maximum-Likelihood-Schatzer

Annahmen:

- Fi unabhangig, identisch verteilt mit Erwartungswert 0

- Varianz-Kovarianzmatrix V (F) = σ2I- Fi normalverteilt

⇒: Yi normalverteilt, E(Y ) = Ax, V (Y ) = σ2I. Dichtefunktion von Yi:

fi(z) =1

σ√

2πe−1

2

(

z−(Ax)iσ

)2

.

Fur die Meßreihe y1, . . . , ym ist die Likelihood-Funktion definiert durch

L(x; y1, . . . , ym) :=m∏

i=1

fi(yi) =

(

1

2πσ2

)m2

e− 1

2σ2‖y−Ax‖22.

Ein Parameterwert x heißt Maximum-Likelihood-Schatzwert, wenn

L(x; y1, . . . , ym) ≥ L(x; y1, . . . , ym) fur alle x ∈ Rn

Der Maximum-Likelihood-Schatzer ist gerade der Schatzer x aus dem

linearen Ausgleichsproblem, weil

‖y − Ax‖2 = minx∈Rn

‖y − Ax‖2.


4.6 Orthogonale Projektion auf einem Teilraum

Gegeben: ein Vektorraum V uber R mit einem Skalarprodukt 〈·, ·〉.

Durch ‖v‖ := 〈v, v〉12 wird eine Norm auf V definiert.

Aufgabe. Sei U ⊂ V ein n-dimensionaler Teilraum von V .

Zu v ∈ V bestimme u∗ ∈ U , fur das

‖u∗ − v‖ = minu∈U

‖u − v‖

gilt.

Im Falle des linearen Ausgleichsproblems ist U = Bild(A), A ∈ Rm×n,

V = Rm, 〈u, v〉 =

∑mj=1 ujvj, D.h. ‖ · ‖ = ‖ · ‖2.

Bemerkung 4.18. Weil U ein endlich-dimensionaler Teilraum ist, exi-

stiert ein Element in U mit minimalem Abstand zu v, d.h. es existiert

u∗ ∈ U , fur das ‖u∗ − v‖ = minu∈U ‖u − v‖ gilt. △


Satz 4.20. Unter den Bedingungen von Aufgabe 4.17 existiert ein

eindeutiges u∗ ∈ U , das

‖u∗ − v‖ = minu∈U

‖u − v‖

erfullt. Ferner gilt das genau dann, wenn

〈u∗ − v, u〉 = 0 ∀u ∈ U,

d.h. , u∗ − v senkrecht (bzgl. 〈·, ·〉) zu U ist.

u∗ ist somit die orthogonale Projektion (bzgl. 〈·, ·〉) von v auf U .

Die Losung der Aufgabe 4.17 ist also die orthogonale Projektion

(bzgl. 〈·, ·〉) von v auf den Unterraum U .

��

��

��

��

��

��

-

�

Uu∗

v


Eigenschaften der Projektion

Zu v ∈ V existiert ein eindeutiges PU(v) ∈ U , so daß v − PU(v) ⊥ U ,

d.h. , 〈v − PU(v), u〉 = 0 ∀ u ∈ U.

Mit PU : V → U ist also eine wohldefinierte Abbildung gegeben.

(i) Die Abbildung PU : V → U ist linear.

(ii) PU ist ein Projektor, d.h. PU(u) = u fur alle u ∈ U (P2U = PU).

(iii) Die Abbildung PU ist symmetrisch,

d.h. 〈PU(v), w〉 = 〈v, PU(w)〉, ∀ v, w ∈ V.

(iv) PU is beschrankt und zwar gilt ‖PU‖ = sup‖v‖=1 ‖PU(v)‖ = 1.


Wie kann man PU(v) berechnen?

Sei {φ1, . . . , φn} eine Basis fur U . Dann hat u = PU(v) eine eindeutige

Darstellung

PU(v) =n∑

j=1

cjφj

mit gewissen Koeffizienten cj = cj(v). Es gilt

0 = 〈v − PU(v), φk〉 = 〈v, φk〉 −n∑

j=1

cj〈φj, φk〉, k = 1, . . . , n.

Definiert man die Gram-Matrix G :=(

〈φk, φj〉)n

j,k=1und die Vektoren

c = (c1, . . . , cn)T , v = (〈v, φ1〉, . . . , 〈v, φn〉)T so ergibt sich

Gc = v

Die Berechnung einer orthogonalen Projektion lauft also im

allgemeinen auf die Losung eines symmetrisch positiv definiten

Gleichungssystems hinaus.


4.7 Singularwertzerlegung (SVD) und Pseudoinverse

Wir definieren die Losungsmenge

L(b) := {x ∈ Rn | x ist Losung des linearen Ausgleichproblems}

Lemma 4.24. Die Losungsmenge L(b) hat folgende Eigenschaften:

(i) Es existiert ein eindeutiges x∗ ∈ Rn, so daß x∗ = L(b)∩Kern(A)⊥,

wobei Kern(A)⊥ := {z ∈ Rn | yTz = 0 ,∀ y ∈ Kern(A)}.

(ii) Fur alle x ∈ L(b) \ {x∗} gilt ‖x‖2 > ‖x∗‖2, d.h., x∗ hat die kleinste

Euklidische Norm in L(b).

Folgerung 4.25. Sei b ∈ Rm, A ∈ Rm×n. Die Aufgabe

bestimme x∗ mit minimaler Euklidischer Norm,

fur das ‖Ax∗ − b‖2 = minx∈Rn ‖Ax − b‖2 gilt,

hat eine eindeutige Losung.


Singularwertzerlegung

Satz 4.27. Zu jeder Matrix A ∈ Rm×n existieren orthogonale

Matrizen U ∈ Rm×m, V ∈ R

n×n und eine Diagonalmatrix

Σ := diag(σ1, . . . , σp) ∈ Rm×n, p = min{m, n} ,

mit

σ1 ≥ σ2 ≥ . . . ≥ σp ≥ 0,

so daß

UTAV = Σ.

Die σi heißen Singularwerte von A (singular values). Die Spalten der

Matrizen U, V nennt man die Links- bzw.Rechtssingularvektoren.


Pseudoinverse

Satz 4.28. Sei UTAV = Σ eine Singularwertzerlegung von

A ∈ Rm×n mit Singularwerten

σ1 ≥ . . . ≥ σr > σr+1 = . . . = σp = 0, p = min{m, n}.Definiere A+ ∈ Rn×m durch

A+ = V Σ+UT mit

Σ+ = diag(σ−11 , . . . , σ−1

r ,0, . . . ,0) ∈ Rn×m .

Dann ist A+b = x∗ die Losung des allgemeinen linearen

Ausgleichproblems.

A+ heißt Pseudoinverse von A.


Lemma 4.29. Sei UTAV = Σ eine Singularwertzerlegung von A mitSingularwerten σ1 ≥ . . . ≥ σr > σr+1 = . . . = σp = 0, p = min{m, n}.Die Spalten der Matrizen U und V werden mit ui bzw. vi notiert.Dann gilt:

(i) Avi = σiui, ATui = σivi, i = 1, . . . , p.

(ii) Rang(A) = r.

(iii) Bild(A) = span{u1, . . . , ur}, Kern(A) = span{vr+1, . . . , vn}.

(iv) ‖A‖2 = σ1.

(v) Sei κ∗2(A) := ‖A‖2‖A+‖2 = σ1

σr. Falls Rang(A) = n ≤ m, so gilt

κ∗2(A) = κ2(A) =

max‖x‖2=1 ‖Ax‖2min‖x‖2=1 ‖Ax‖2

(vi) {σi | i = 1, . . . , r} = {√

λi(ATA) | i = 1, . . . , n } \ {0} .


Abb. 4.6. Orthogonale Basis in Rn und R

m

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

..

.

.

.

.

.

.

..

.

.

.

..

.

.

.

..

.

.

..

.

..

.

..

.

..

.

..

.

..

..

..

.

...............................................................................................................................................

...................................................................................................................................................

..............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

....................................................................................................................................................................................................................................................................................................................... .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

..

.

.

.

.

.

..

.

.

.

.

..

.

.

..

.

.

..

.

..

.

..

.

..

.

..

.

..

..

..........................................................................................................................................

.....................

.....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

......................................................................................................................................................................................................................................................................................................................

BB

BBB

BBBM

��1

r

span{vr+1, . . . , vn}

= Kern(A)

span{v1, . . . , vr}

= Bild(AT )

Rn

0

��

PPPPPPPPq

r

span{ur+1, . . . , um}

= Kern(AT )

span{u1, . . . , ur}

= Bild(A)

Rm

0

�-A

AT


Abb. 4.7. Geometrische Interpretation der Singularwertzerlegung

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

..

.

.

.

.

.

.

..

.

.

.

..

.

.

.

..

.

.

..

.

..

.

..

.

..

.

..

.

..

..

..

.

...............................................................................................................................................

...................................................................................................................................................

..............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

....................................................................................................................................................................................................................................................................................................................... .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

..

.

.

.

.

.

.

..

.

.

.

..

.

.

.

..

.

.

..

.

..

.

..

.

..

.

..

.

..

....................................................................................................................................................

...................................................................................................................................................

..............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

.......................................................................................................................................................................................................................................................................................................................

BB

BBB

BBBM

��1

r

vi

vTi x

vTj x

vj

Rn

x

��

��

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.............

.............

.............

.............

.............

...

.

.

.

.

.

.

.

.

.

.

...............................................................

.....................................................

......

.

..

.

..

.

............

.

.

.

.

.

.

...

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

........

��

PPPPPPPPq

r

σjvTj x

σivTi x

ui

uj

Rm

Ax

��*.............

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.............

.............

.............

.............

.............

...

..........

.

.

.

..

.

.

.

.

.

.....................................................

.....................................................

........

.

.

.

.

.

.

.

.

..........

..

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

........

.

.

.

.

.

.

.

.

-A


4.7.1 Berechnung von Singularwerten

Lemma 4.30. Sei A ∈ Rm×n, und seien Q1 ∈ Rm×m, Q2 ∈ Rn×n

orthogonale Matrizen. Dann haben A und Q1AQ2 die gleichen Sin-

gularwerte.

Transformation auf Bidiagonalgestalt; Beispiel:

Eine Householder-Transformation Q1, so daß

Q1A =

∗ ∗ ∗ ∗0 ∗ ∗ ∗0 ∗ ∗ ∗0 ∗ ∗ ∗0 ∗ ∗ ∗

=

(

∗ vT1

∅ ∗

)


Sei Q1 ∈ R3×3 eine Householder-Transformation, so daß

Q1v1 = ( ∗ 0 0)T . Mit Q1 :=

(

1 ∅∅ Q1

)

erhalt man

Q1AQ1 =

(

∗ vT1

∅ ∗

) (

1 ∅∅ Q1

)

=

∗ ∗ 0 00 ∗ ∗ ∗0 ∗ ∗ ∗0 ∗ ∗ ∗0 ∗ ∗ ∗

.

Auf ahnliche Weise konnen Nulleintrage erzeugt werden in der 2. Spal-te, 2. Zeile, 3. Spalte und 4. Spalte:

Q1AQ1 → Q2Q1AQ1 =

∗ ∗ 0 00 ∗ ∗ ∗0 0 ∗ ∗0 0 ∗ ∗0 0 ∗ ∗

→ Q2Q1AQ1Q2 =

∗ ∗ 0 00 ∗ ∗ 00 0 ∗ ∗0 0 ∗ ∗0 0 ∗ ∗

→ Q3Q2Q1AQ1Q2 =

∗ ∗ 0 00 ∗ ∗ 00 0 ∗ ∗0 0 0 ∗0 0 0 ∗

→ Q4Q3Q2Q1AQ1Q2 =

∗ ∗ 0 00 ∗ ∗ 00 0 ∗ ∗0 0 0 ∗0 0 0 0

.


Bemerkung 4.31. Der Aufwand zur Berechnung der oberen Bidiago-

nalmatrix B in 4.65 betragt mn2 + O(mn) Operationen. △

Die Matrix A und die sich ergebende Bidiagonalmatrix B haben die

gleichen Singularwerte.

Die Singularwerte der Matrix A sind die Wurzeln der Eigenwerte der

Tridiagonalmatrix BTB.

Fur die Berechnung der Eigenwerte dieser Matrix werden im allgemei-

nen sehr viel weniger arithmetische Operationen benotigt als fur die

Berechnung der Eigenwerte der (vollbesetzten) Matrix ATA.


4.7.2 Rangbestimmung

Lemma 4.32. Sei UTAV = Σ eine Singularwertzerlegung von A mit

Singularwerten σ1 ≥ . . . ≥ σr > σr+1 = . . . = σp = 0, p = min{m, n}.Fur 0 ≤ k ≤ p − 1 gilt:

min{ ‖A − B‖2 | B ∈ Rm×n, Rang(B) ≤ k } = σk+1 .

Folgerung 4.33. Fur A und A = A + ∆A ∈ Rm×n mit Singularwerten

σ1 ≥ . . . ≥ σp bzw. σ1 ≥ . . . ≥ σp, p = min{m, n}, gilt

|σk − σk||σ1|

≤ ‖∆A‖2‖A‖2

, fur k = 1, . . . , p.

In diesem Sinne ist das Problem der Singularwertbestimmung gut kon-

ditioniert.


Der Numerische Rang

Sei A = (ai,j) eine mit Rundungsfehlern behaftete Annaherung von A,

wobei ai,j = ai,j(1 + ǫi,j) mit |ǫi,j| ≤ eps.

Mit E := (ai,jǫi,j) ∈ Rm×n ergibt sich

‖A − A‖2 = ‖E‖2 ≤ √m‖E‖∞ ≤ √

m‖A‖∞ eps ≤ √mn‖A‖2 eps .

Deswegen definieren wir:

BA(eps) := {C ∈ Rm×n | ‖A − C‖2

‖A‖2≤ √

mn eps } .

Der numerische Rang Rangnum(A) der Matrix A ist:

Rangnum(A) := min{Rang(B) | B ∈ BA(eps) } .

Dieser numerische Rang hangt von der Maschinengenauigkeit eps ab.


Bestimmung des numerischen Ranges:

Seien σ1 ≥ . . . ≥ σp die Singularwerte der Matrix A. Es gilt

minRang(B)≤k

‖A − B‖2‖A‖2

=σk+1

σ1, 1 ≤ k < p .

Die Umgebung BA(eps) enthalt also eine Matrix B mit Rang(B) = k

genau dann, wenn σk+1/σ1 ≤ √mn eps.

Der numerische Rang der Matrix A ist deshalb:

Rangnum(A) = min{1 ≤ k ≤ p | σk+1 ≤ σ1√

mn eps }.


4.34. Beispiel

Wir betrachten die Matrizen

A1 =

110

13 0

210

23 3

310

33 0

410

43 7

, A2 = A1 + 10 eps

1000

(

1 0 0)

,

wobei eps ≈ 2 ∗ 10−16. Es gilt Rang(A1) = 2, Rang(A2) = 3 .

Die berechneten Singularwerte dieser Matrizen sind

7.776, 1.082, 1.731 ∗ 10−16 bzw. 7.776, 1.082, 2.001 ∗ 10−15.

In beiden Fallen sind die drei berechneten Singularwerte strikt positiv,

jedoch gilt

Rangnum(A1) = Rangnum(A2) = 2.

In der Praxis wurde man hieraus schließen, daß beide Matrizen den

Rang 2 haben. △


Documents

Dahmen-Reusken Kapitel 4 1 - News | IGPM · Wir nehmen A und b wie in Beispiel 4.12. Die Methode uber die QR-Zerlegung von A, auf einer Maschine mit eps ≈ 10−16, ergibt δ = 10−4: