Download pdf - R. Hiptmair Herbstsemester 2014 ETH Zurich¨ S. Pintarelli Lineare … · 2014. 12. 11. · R. Hiptmair S. Pintarelli E. Spindler Herbstsemester 2014 Lineare Algebra und Numerische

R. HiptmairS. PintarelliE. Spindler

Herbstsemester 2014

Lineare Algebra und NumerischeMathematik fur D-BAUG

ETH ZurichD-MATH

Beispiellosung fur Serie 10

Einleitung. In dieser Serie werden Sie zum ersten Mal gebeten, numerische Algorithmen inMATLAB zu implementieren, wobei Grundlagenkenntnisse uber MATLAB, wie sie in der Infor-matikvorlesung vermittelt worden sind, vorausgesetzt werden. Viele MATLAB-Codes, auch zuBeispielen aus der Vorlesung, finden Sie hier.

Hauptthema dieser Serie ist lineare Ausgleichsrechnung. Sie werden viele Aufgaben vorfinden, inwelchen Sie mithilfe von MATLAB die Losung eines uberbestimmten linearen Gleichungssystemsim Sinne der kleinsten Quadrate bestimmen sollen. Behandelt wurde dieses Thema in Abschnitt[LANM, Abschnitt 4.4] der Vorlesung.

Bevor Sie mit den schwierigeren Aufgaben zu diesem Thema beginnen (Aufgaben 10.5, 10.9,10.10), empfehle ich Ihnen, zum Einstieg in lineare Ausgleichsrechnung Aufgabe 10.4 zu bear-beiten.

Weiter finden Sie Aufgaben zum orthogonalen Komplement (Aufgabe 10.1), zur OrthogonalenProjektion (Aufgaben 10.2), zum Gram-Schmidtschen Orthonormalisierungsverfahren (Aufgabe10.3) und der QR-Zerlegung (betrifft Abschnitt [LANM, Thm. 4.3.4] der Vorlesung) (Aufgabe10.3).

? Aufgabe 10.1 Orthogonale Komplemente

Entscheiden Sie, ob die folgenden Unterraume U , V orthogonale Komplemente in R2 oder R3

bilden, siehe [LANM, Abschnitt 4.3.2] der Vorlesung. Das bedeutet, Sie sollen herausfinden, obdie Unterraume U , V von R2 oder R3 orthogonal zueinander sind und gemeinsam den ganzenVektorraum R2 oder R3 aufspannen oder nicht.

Serie 10 Seite 1 Aufgabe 10.1

http://http://www.sam.math.ethz.ch/~hiptmair/tmp/LANM/MATLAB/NumLinAlgMATLAB/

10.1a) U = Span

®ñ1−1

ô´, V = Span

®ñ55

ô´(i)

√U und V bilden orthogonale Komplemente in R2.

(ii) U und V sind keine orthogonalen Komplemente in R2.

In diesem Fall steht der Vektor, welcher den Unterraum U aufspannt senkrecht auf dem Vektor,welcher den Unterraum V aufspannt:

〈ñ1−1

ô,

ñ55

ô〉 = 5− 5 = 0 .

Da gilt V , U ⊂ R2, wobei dimU + V = dimV + dimU − dimU ∩ V (siehe auch[LANM,Thm. III.2.0.N]), wobei U ∩ V = {0} (da die Vektoren [ 1

−1 ] und [ 55 ] senkrecht zueinander ste-hen!), spannen die beiden Unterraume gemeinsam ganz R2 auf. Sie bilden somit orthogonaleKomplemente in R2.

10.1b) U = Span

®ñ12

ô,

ñ−21

ô´, V = Span

®ñ6−3

ô´(i) U und V bilden orthogonale Komplemente in R2.

(ii)√

U und V sind keine orthogonalen Komplemente in R2.

In diesem Fall steht der Vektor, welcher den Unterraum V aufspannt, nicht senkrecht auf denerzeugenden Vektoren des Unterraums U :

〈ñ−21

ô,

ñ6−3

ô〉 = −12− 3 = −15 6= 0 .

Somit sind die beiden Unterraume keine orthogonalen Komplemente in R2.


10.1c) U = Span

000

, 2−33

,111

, V = Span

−110

(i) U und V bilden orthogonale Komplemente in R3.

(ii)√

U und V sind keine orthogonalen Komplemente in R3.

In diesem Fall steht der Vektor, welcher den Unterraum V aufspannt, nicht senkrecht auf denerzeugenden Vektoren des Unterraums U :

〈

2−33

,−110

〉 = −2− 3 = −5 6= 0 .

Somit sind die beiden Unterraume keine orthogonalen Komplemente in R3.

10.1d) U = Span

123

, V = Span

−210

,−301

(i)√

U und V bilden orthogonale Komplemente in R3.

(ii) U und V sind keine orthogonalen Komplemente in R3.

In diesem Fall steht der Vektor, welcher den Unterraum U aufspannt senkrecht auf den Vektoren,welche den Unterraum V erzeugen:

〈

123

,−210

〉 = −2 + 2 + 0 = 0 , 〈

123

,−301

〉 = −3 + 0 + 3 = 0

Da gilt V , U ⊂ R3, wobei dimU + V = dimV + dimU − dimU ∩ V (siehe auch[LANM,Thm. III.2.0.N]), wobei U ∩V = {0} (da die Unterraume senkrecht zueinander stehen!). Fur dieDimensionen gilt dimU = 1 und dimV = 2, da

[ −301

]und

[ −210

]linear unabhangig sind:

α1

[ −301

]+ α2

[ −210

]=

[000

]⇔ α1 = α2 = 0 .

Deshalb gilt dimU + V = 1+2+0 = 3. Somit spannen die beiden Unterraume gemeinsam ganzR3 auf. Sie bilden folglich orthogonale Komplemente in R3.

? Aufgabe 10.2 Orthogonalprojektion auf eine Ebene in 3D

In [LANM, Abschnitt 4.2.3] wurde untersucht, welcher Vektor in einem affinen Teilraum einemgegeben Vektor im Sinne der Lange des Differenzvektors (“Abstand der Punkte”) am nachstenliegt. Dies fuhrte uns auf den Begriff der orthogonalen Projektion, siehe [LANM, Satz IV.2.3.L].In dieser Aufgabe sollen Sie eine Orthogonalprojektion ganz konkret ausrechnen.

Gegeben sind im dreidimensionalen Euklidischen Raum die Ebene

E =¶x ∈ R3 : 2x1 + 4x2 − 4x3 = 0

©und der Vektor y =

[111

]. Berechnen Sie die Orthogonalprojektion von y auf E . . .


10.2a) . . . mithilfe des Normalenvektors n der Ebene E ,

(→ Tipp)

Losung: Sei p die orthogonale Projektion von y auf E . Diese Orthogonalprojektion des Vektorsy auf E muss nach Satz [LANM, Satz IV.2.3.L] aus der Vorlesung erfullen, dass q = y − p

parallel zu n =[

24−4

], dem Normalenvektor der Ebene E (Vektor der senkrecht auf der Ebene

steht), sein muss. Es gibt folglich ein α ∈ R, sodass

q = y − p = αn ⇔ p = y − αn . (10.2.1)

Zudem muss naturlich gelten, dass p =[ p1p2p3

]∈ E :

〈n,p〉 = 2p1 + 4p2 − 4p3 = 0 . (10.2.2)

Aus den beiden Bedingungen (10.2.1) und (10.2.2) erhalten wir somit α:

0 = 〈n,p〉 = 〈n,y − αn〉 = 〈n,y〉 − α〈n,n〉 ⇔ α =〈n,y〉〈n,n〉

=2 + 4− 4

4 + 16 + 16=

1

18,

was uns mit (10.2.1) die Losung

p = y − αn =

111

− 1

18

24−4

=1

9

8711

.10.2b) . . . mithilfe der Formel (IV.2.3.J) aus der Vorlesung, indem Sie zunachst zwei Vektoren aund b ∈ R3 bestimmen, welche E aufspannen.

Tipp: Sie konnen Ihren Rechenaufwand dadurch reduzieren, dass Sie a und b geschickt wahlen.Erinnern Sie sich dazu an [LANM, Lemma IV.3.4.A]. Das Vektorprodukt aus [LANM, Ab-schnitt 4.3.5] kann auch nutzlich sein.

Losung: Berechnen wir die Orthogonalprojektion mithilfe der Ausgleichsrechnung, benotigenwir zwei Vektoren, welche die Ebene aufspannen. Wir wahlen einen Vektor, welcher offensicht-

lich in der Ebene E liegt: a1 =

011

.

Nach Konstruktion steht der Vektor n senkrecht auf a1. Berechnen wir das Vektorprodukt von nund a1, dann erhalten wir einen weiteren Vektor in der Ebene E , welcher senkrecht zu n und a1

steht:

a2 = n× a1 =

24−4

×011

=

8−22

.Eine Orthonormalbasis des R3 ist folglich

B =

®1

‖n‖n,

1

‖a1‖a1,

1

‖a2‖a2

´,


wobei 1‖a1‖a

1, 1‖a2‖a

2 die Ebene E aufspannen.

Wir verwenden den Ansatzp = α1

1

‖a1‖a1 + α2

1

‖a2‖a2 ,

also dass wir die orthogonale Projektion p von y auf E als Linearkombination von 1‖a1‖a

1, 1‖a2‖a

2

schreiben konnen. Wir erhalten das uberbestimmte lineare Gleichungssystemî1‖a1‖a

1, 1‖a2‖a

2óñα1

α2

ô= y . (10.2.3)

Nach Abschnitt [LANM, Thm. 4.4.3] aus der Vorlesung wissen wir, dass die Normalengleichun-gen uns exakt diejenige Losung liefern, welche wir suchen. Wir erhalten aus (10.2.3) die Norma-lengleichung 1

‖a1‖a1>

1‖a2‖a

2>

î 1‖a1‖a

1 1‖a2‖a

2óñα1

α2

ô=

1‖a1‖ (a

1)>

1‖a2‖ (a

2)>

y ,ñ1 00 1

ôñα1

α2

ô=

1‖a1‖a

1>y1‖a2‖a

2>y

,ñα1

α2

ô=

[ √2

23

√2

].

wobei wir verwendet haben, dass B eine Orthonormalbasis darstellt. Wir erhalten die Losung

p = α1a1 + α2a

2 =√2

1√2

011

+2

3

√2

1

6√2

8−22

=

011

+1

9

8−22

=1

9

8711

.Da wir dieselbe Losung wie in Teilaufgabe 10.2b) erhalten, haben wir richtig gerechnet.

Aufgabe 10.3 QR-Zerlegung von Matrizen mithilfe des Gram-Schmidt Al-gorithmus

Der Hohepunkt von [LANM, Kapitel 4] bildete die Gram-Schmidt- Orthonormalisierung aus[LANM, Abschnitt 4.3.4]. In dieser Aufgabe sollen Sie diesen Algorithmus einmal “von Hand”durchfuhren, um seine Details zu verstehen. Zusatzlich sollen Sie lernen, wie man als Nebenpro-dukt auch die Matrix R aus der QR-Zerlegung gemass [LANM, Satz IV.3.4.F] erhalt.

(→ Tipp)

Gegeben seien die Matrizen

A =

2 11 12 1

∈ R3,2 , B =

2 3 −11 −1 0−1 1 0

∈ R3,3 .


? 10.3a) Wenden Sie den Gram-Schmidt- Orthonormalisierungsalgorithmus an und finden Sie eineOrthonormalbasis fur den Spaltenraum von A bzw. B.

Losung: Wir nehmen die Spalten von A: a1 :=[212

], a2 :=

[111

]und wenden den Gram-

Schmidtschen Algorithmus darauf an (siehe Vorlesungsunterlagen, Abschnitt [LANM, Thm. 4.3.4]).

q1 :=1

‖a1‖a1 =

1

3

212

,

q2 := a2 − 〈a2,q1〉q1 =

111

− 1

3(2 + 1 + 2)

1

3

212

=1

9

9− 109− 59− 10

=1

9

−14−1

,

q2 :=

√2

6

−14−1

.

Wir erhalten die Orthonormalbasis A = {q1,q2} =

13

212

, √26

−14−1

fur den Spaltenraum

von A.

Fur die Spalten von B, b1 :=[

21−1

], b2 =

[3−11

], b3 =

[ −100

]. erhalten wir analog

q1 :=1

‖b1‖b1 =

√6

6

21−1

,

q2 := b2 − 〈b2,q1〉q1 =

3−11

− √66

(6− 1− 1)

√6

6

21−1

=1

3

9− 4−3− 23 + 2

=5

3

1−11

,

q2 :=q2

‖q2‖=

√3

3

1−11

,

q3 := b3 − 〈b3,q1〉q1 − 〈b3,q2〉q2 =

−100

+2

6

21−1

+1

3

1−11

= 0 .

Die letzte Gleichung ist gleichbedeutend dazu, dass b3 bereits im Span{q1,q2} liegt. Der Algo-rithmus bricht ab, da die Bedingung ‖q3‖ = 0 erfullt ist.

Wir erhalten die Orthonormalbasis B = {q1,q2} =

√66

21−1

, √33

1−11

fur den Spaltenraum

von B.

? ? 10.3b) Bestimmen Sie die (sparsame) QR-Zerlegung von A bzw. B mithilfe der in Teilaufgabe10.3a) erhaltenen Ergebnisse.

(→ Tipp)


(→ Tipp)

Losung: Wir verwenden Satz [LANM, Thm. IV.3.4.F] aus der Vorlesung und benutzen die Er-gebnisse aus Teilaufgabe 10.3a).

Fur A schreiben wir die Vektoren q1, q2 in die Spalten von Q, und erhalten

Q :=îq1 q2

ó=

23−√26

13

2√2

323−√26

,

R := Q−1A = Q>A =

[23

13

23

−√26

2√2

3−√26

]2 11 12 1

=

[3 5

3

0√23

].

Fur B schreiben wir die Vektoren q1, q2 in die Spalten von Q, und erhalten

Q :=îq1 q2

ó=

√63

√33√

66−√33

−√66

√33

,

R := Q−1A = Q>B =

[√63

√66−√66√

33−√33

√33

] 2 3 −11 −1 0−1 1 0

=

[√6 2

√6

3−√63

0 5√3

3−√33

].

? Aufgabe 10.4 Einfache Lineare Ausgleichsrechnung

Gegeben sei eine naturliche Zahl n. Durch n Messungen der skalaren Grosse x haben wir n(leicht verschiedene) Messwerte m1,m2, . . .,mn fur x erhalten, aus denen wir durch Losen einesuberbestimmten linearen Gleichungssystems im Sinne der kleinsten Quadrater eine Schatzung furx erhalten wollen.

10.4a) Repetieren Sie den Abschnitt [LANM, Thm. 4.4] der Vorlesung uber die Kleinste-Quadrate-Losung von uberbestimmten linearen Gleichungssystemen.

10.4b) Stellen Sie das uberbestimmte lineare Gleichungssystem fur das vorliegende Problem auf.

Losung: Wir schreiben das uberbestimmte lineare Gleichungssystem des vorliegenden Problemsauf. Wir suchen x ∈ R, sodass gilt

11...1

x =

m1

m2

...mn

. (10.4.1)

10.4c) Stellen Sie die zugehorigen Normalengleichugen gemass Satz [LANM, Thm. IV.4.3.B]der Vorlesung auf.


Losung: Um das Gleichungssystem zu losen, benutzen wir die Normalengleichungen aus Satz[LANM, Thm. IV.4.3.B]:

A>Ax = A>b , (10.4.2)

wobei A =

[ 11...1

]und b =

m1m2

...mn

(vergleichen Sie mit Gleichung (10.4.1)).

Daraus ergibt sich durch Einsetzen in (10.4.2) folgende Gleichung

nx = m1 +m2 + · · ·+mn . (10.4.3)

10.4d) Bestimmen Sie die Kleinste-Quadrate-Losung gemass Definition [LANM, Thm. IV.4.2.B]aus der Vorlesung und interpretieren Sie das Ergebnis.

Losung: Die kleinste-Quadrate-Losung erhalten wir, indem wir die Gleichung (10.4.3) nach xauflosen. Wir bekommen

x =m1 + · · ·+mn

n,

was dem arithmetischen Mittel der Messwerte m1, . . . ,mn entspricht.

Aufgabe 10.5 Kleinste-Quadrate-Fit einer Funktion

Auch in dieser Aufgabe geht es wieder um die Bestimmung von Parametern aus Messwerten mitHilfe der Methode der kleinsten Quadrate aus Abschnitt [LANM, Thm. 4.4] der Vorlesung. DieParameter sind hier nicht unmittelbar in der Aufgabenstellung bezeichnet.

Es ist bekannt, dass die Funktion f(x) gegeben ist als gewichtete Summe (eine Linearkombinati-on!) der beiden Funktionen

g1(x) = 2x und g2(x) = 2−x.

Anhand von Messungen wurde festgestellt, dass der Graph von f(x), gegeben durch

Graph(f) := {(x, f(x)) : x ∈ R},

durch folgende Punkte der (x, y)-Ebene verlauft:

xi −2 −1 0 1 2yi −8 −4 −2 4 12

? ? 10.5a) Auf welches uberbestimmte lineare Gleichungssystem fuhrt die Schatzung von f?

(→ Tipp)

Losung: Da die Funktion f als Linearkombination von g1 und g2 dargestellt werden kann, erhal-ten wir

f(x) = αg1(x) + βg2(x) = α2x + β2−x,

wobei α, β ∈ R die Unbekannten sind, welche wir approximieren wollen.


Wir erhalten

1

4α + 4β + 8 = r1

1

2α + 2β + 4 = r2

α + β + 2 = r3

2α +1

2b− 4 = r4

4α +1

4b− 12 = r5.

als Gleichungen fur die Werte des Fehlervektors r = ‖b−Ax∗‖, wobei

A =

14

412

21 12 1

2

4 14

, b =

−8−4−2412

und x =

ñαβ

ô.

? 10.5b) Was sind die Normalengleichungen gemass [LANM, Satz IV.4.3.B] zum uberbestimmtenlinearen Gleichungssystems aus Teilaufgabe 10.5a).

Losung: Wir erhalten mithilfe von Teilaufgabe 10.5a):

A>Ax = A>b ,

mit

A>A =

ñ34116

55 341

16

ô,A>b =

ñ50−37

ô.

? 10.5c) Verwenden Sie die Kleinste-Quadrate-Methode um f(x) aus den Massdaten zu schatzen.

(→ Tipp)

Losung: Losen wir die Normalengleichungen A>Ax = A>b, wobei wir A, b, x aus Teilauf-gabe 10.5b) ubernehmen, so erhalten wir

α =3680

1263und β = −3056

1263.

Aufgabe 10.6 Matrix aus Matrix×Vektor (MATLAB)

In dieser Aufgabe sollen Sie in MATLAB eine Funktion schreiben, welche basierend auf einergegebenen Matrix A ∈ Rn, und einer Eingabe x ∈ Rn, Ax zuruck gibt.

Weiter sollen Sie herausfinden, welche Matrix sich hinter einer bereits gegebenen MATLAB-Funktion vom gleichen Typ verbirgt, ohne dass Sie Einblick in den MATLAB-Code haben. IhrWissen basiert einzig auf der Ausgabe zu beliebigen Eingaben in die MATLAB-Funktion.


? ? 10.6a) Gegeben sei die unten abgedruckte MATLAB-Funktion

function w = transform(v) ,

welche einen Spaltenvektor v ∈ Rn als Eingabe nimmt und einen transformierten Spaltenvektorw ∈ Rn zuruckgibt.

Wir wissen, dass sich die durch die Funktion transform implementierte Abbildung v 7→ wals Matrix×Vektor-Produkt w = Av schreiben lasst. Welche Matrix A ∈ Rn,n reprasentiert dieMATLAB-Funktion function w = transform(v), sprich, fur welche Matrix A ∈ Rn,n

giltw = Av .

Listing 10.1: Funktion aus Aufgabe 10.6c)1 f u n c t i o n w = transform(v)2 % Eingabe der Funktion: Spaltenvektor v der Laenge n

3 % Rueckgabe der Funktion: Transformierter Spaltenvektor w der

Laenge n

4 n = l e n g t h(v);5 w = v(n:-1:1);6 w(n) = w(n) + dot(v,ones(n,1));7 w = w + v(1)*ones(n,1);8 end

Losung: Da wir Einsicht in die MATLAB-Funktion

function w = transform(v)

haben, konnen wir Zeile fur Zeile dieser Funktion in Matrixform darstellen:

w = v(n:-1:1);

Als erstes wird der Vektor v “auf den Kopf gestellt”. Dies konnen wir wie folgt realisieren:

w1 =

0 0 . . . 0 0 10 0 . . . 0 1 0...

... . ... ..

0 0... 0 . .

.. .. ...

...0 1 0 . . . 0 01 0 . . . . . . 0 0

v .

w(n) = w(n) + dot(v,ones(n,1))

In einem zweiten Schritt wird zum letzten Eintrag des Vektors w1 der Wert

〈v,[ 11...1

]〉 =

n∑i=1

vi


hinzugezahlt. Den neuen Vektor w2 erhalten wir folglich durch

w2 = w1 +

0 . . . 0.... . .

...0 . . . 01 . . . 1

v .

w = w + v(1)*ones(n,1);

Als letztes addieren wir zu w2 den Vektorñ v1...v1

ô= v1

ñ1...1

ôhinzu:

w = w2 + v1

1...1

= w2 +

1 0 . . . 0...

.... . .

...1 0 . . . 0

v .Setzen wir alles zusammen, erhalten wir

w =

0 0 . . . 0 0 10 0 . . . 0 1 0...

... . ... ..

0 0... 0 . .

.. .. ...

...0 1 0 . . . 0 01 0 . . . . . . 0 0

v +

0 . . . 0.... . .

...0 . . . 01 . . . 1

v +

1 0 . . . 0...

.... . .

...1 0 . . . 0

v

=

1 0 . . . 0 0 11 0 . . . 0 1 0...

... . ... ..

0 0

1 0 . ... ... . . 0

1 1 0 . . . 0 03 1 . . . . . . 1 1

v .

Es gilt somit

(A)i,j :=

1 i = n+ 1− j oder i = 1 oder j = n, i ∈ {1, . . . , n− 1} , j ∈ {2, . . . , n}3 i = n und j = 1

0 sonst

.

Naturlich kann in dieser Teilaufgabe auch die Strategie aus Teilaufgabe 10.6b) angewandt wer-den.

? ? 10.6b) Nun kehren wir die Aufgabenstellung um: Wir wissen, dass die als Quelltext nicht zuganglicheMATLAB-Funktion

function w = topsecret(v)

einen Spaltenvektor v ∈ Rn der Lange n ∈ N als Eingabe nimmt und daraufhin einen Spal-tenvektor w ∈ Rn zuruckgibt. Weiter wissen wir, dass sich die MATLAB-Funktion durch eineMatrixmultiplikation realisieren lasst, d.h. es gibt ein A ∈ Rn,n, sodass

w = Av.


Schreiben Sie ein MATLAB-Skript findmatrix.m, mit dessen Hilfe Sie Sie diese Matrix Aberechnen konnen.

(→ Tipp)

Losung: Ziel der Aufgabe ist es, eine allgemein gultige Strategie zu finden, mit welcher wir dieMatrix A berechnen konnen, wenn wir zwar wissen, wie die Ergebnisse w = Av fur beliebigev ∈ Rn aussehen, wir aber A nicht explizit kennen.

Wir nehmen die kanonische Basis des Rn, E :=

e1 =

100...0

, e2 = 0

10...0

, . . . , en =

00...01

. Wir

stellen fest, dass gilt

Aei = (A):,i , fur alle i ∈ {1, . . . , n} .

Somit erhalten wir A durch Berechnen von

A(:,i) = topsecret(ei)

fur alle i = 1, . . . , n .

Wir implementieren diese Idee in der MATLAB-Funkion in Listing .

Listing 10.2: MATLAB-Funktion aus Teilaufgabe 10.6b)1 f u n c t i o n A = findmatrix(n)2 % Eingabe:3 % n : natuerliche Zahl, gewuenschte Dimension von A4 % Ausgabe: A, Matrix welche ’transform.m’ repraesentiert5 % Initialisierung6 % Wir stellen fest, dass die Spalten der Einheitsmatrix die7 % kanonische Basis bilden.8 e = eye(n);9 A = NaN(n);

10 f o r i=1:n11 A(:,i) = transform(e(:,i));12 end13 end

? ? 10.6c) Testen Sie Ihren Code findmatrix.m als erstes mit der MATLAB-Funktion functionw = transform(v), von welcher Sie aus 10.6c) wissen, wie die Matrix A aussieht.

Ferner ist die “verschlusselte MATLAB-Funktion” function w = topsecret(v) gege-ben (topsecret.p), auf welche Sie Ihren Code auch anwenden sollen. Diese Funktion konnenSie ganz normal mit topsecret(v) aufrufen, wenn sich das .p-File im Arbeitsverzeichnisbefindet (Sie finden topsecret.p auf der Vorlesungshomepage). Geben Sie die topsecretzugrundeliegenden Matrizen fur n = 3 und n = 4 an.

Losung: Wir uberprufen unsere Behauptung mit der gegebenen MATLAB-Funktion transform.maus Teilaufgabe 10.6b). Wir erhalten tatsachlich die Matrix, welche wir in Teilaufgabe berechnethaben (siehe Listing 10.5).


Listing 10.3: MATLAB-Ausgabe aus Teilaufgabe 10.6c)1 >> A = findmatrix(3)2

3 A =4

5 1 0 16 1 1 07 3 1 18

9 >> A = findmatrix(4)10

11 A =12 1 0 0 113 1 0 1 014 1 1 0 015 3 1 1 1

Fur das Berechnen der Matrix A der MATLAB-Funktion topsecret.p mussen wir den Codenur leicht abandern (siehe Listing 10.4).

Listing 10.4: MATLAB-Funktion aus Teilaufgabe 10.6c)1 f u n c t i o n A = findmatrix2(n)2 % Eingabe:3 % n : natuerliche Zahl, gewuenschte Dimension von A4 % Ausgabe: A, Matrix welche ’topsecret.p’ repraesentiert5 % Initialisierung6 % Wir stellen fest, dass die Spalten der Einheitsmatrix die7 % kanonische Basis bilden.8 e = eye(n);9 A = NaN(n);

10 f o r i=1:n11 A(:,i) = topsecret(e(:,i));12 end13 end

Wir erhalten fur A im Falle von n = 3 und n = 4 die Ausgabe in Listing ??.

Listing 10.5: MATLAB-Ausgabe aus Teilaufgabe 10.6c)1 >> A = findmatrix2(3)2

3 A =4

5 8 1 66 3 5 7


7 4 9 28

9 >> A = findmatrix2(4)10

11 A =12 16 2 3 1313 5 11 10 814 9 7 6 1215 4 14 15 1

? Aufgabe 10.7 Effiziente Matrix-Vektor-Multiplikation (MATLAB)

In Abschnitt [LANM, Beispiel V.3.0.F] aus [LANM, Abschnitt 5.3] haben Sie gesehen, dass Sieviel Rechenzeit sparen konnen, wenn Sie beim Schreiben ihres MATLAB-Codes die Rechenregelnaus der linearen Algebra geschickt nutzen. Matrix-Vektor-multiplikationen sind im Allgemeinfallsehr rechenaufwendig (quadratische Komplexitat O(n2)). Da lohnt es sich, spezielle Strukturenvon Matrizen zu kennen, bei welchen man durch geeignetes Umschreiben der Matrix Rechenauf-wand sparen kann.

Sie haben bereits eine wichtige solche Klasse von Matrizen bereits kennengelernt: Rang-Eins Ma-trizen (Aufgabe 5.2, 6.3, 6.4, 8.7, 8.8). In dieser Aufgabe sollen Sie sich klar machen, inwiefernman die Struktur von Rang-Eins Matrizen ausnutzen kann, um Rechenaufwand zu sparen.

Gegeben seien zwei Spaltenvektoren a,b ∈ Rn fur eine naturliche Zahl n ∈ N. Wir betrachtendie beiden MATLAB-Funktionen

function w = abmult1(a,b,v) und function w = abmult2(a,b,v) ,

welche fur einen Spaltenvektor v ∈ Rn einen Spaltenvektor w ∈ Rn zuruckgeben. Die genauenMATLAB-Funktionen sind nachfolgend gegeben.

(→ Tipp)

Listing 10.6: Erste Funktion1 f u n c t i o n w = abmult1(a,b,v)2 % Eingabe der Funktion: Spaltenvektoren a, b, v der Laenge n


Laenge n

4 n = l e n g t h(v);5 w = (a * b’) * v;6 end

Listing 10.7: Zweite Funktion1 f u n c t i o n w = abmult2(a,b,v)2 % Eingabe der Funktion: Spaltenvektoren a, b, v der Laenge n


Laenge n


4 n = l e n g t h(v);5 w = a * (b’ * v);6 end

10.7a) Beide MATLAB-Funktionen realisieren die Multiplikation mit der gleichen Matrix A ∈Rn,n, d.h. geben den Spaltenvektor w = Av zuruck. Geben Sie die Matrix A an.

Losung: Fur a, b ∈ Rn gilt

A = ab> =

a1a2...an

îb1 b2 . . . bn

ó=

a1b1 a1b2 . . . a1bn

a2b1. . .

......

. . ....

anb1 anb2 . . . anbn

.

Folglich haben wir (A)i,j = aibj fur i, j ∈ {1, . . . , n}.

10.7b) Erzeugen Sie Laufzeitplots fur die beiden Funktionen mit Hilfe des Templates

rankonemulttiming.m ,

welches Sie von der Vorlesungshomepage herunterladen konnen.

Losung: Wir erganzen das MATLAB-Template rankonemulttiming.m und erhalten Listing10.8. Die Ausgabe finden Sie in Abbildung 10.1

Listing 10.8: MATLAB-Funktion aus Teilaufgabe 10.7b)1 f u n c t i o n rankonemulttiming2 % Measurement of runtimes for different ways of multiplying a vector

with a3 % matrix of the form a · bT, where a and b are column4 % vectors, a so-called tensor product matrix.5 N = 1000; % Maximal size of vectors6 a = rand(N,1); b = rand(N,1); % Initialize random column vectors of

length N7 v = rand(N,1);8

9 res = []; % matrix for recording times10 % conduct timings for vectors of different size11 f o r n=10:10:N12 t1 = realmax;13 f o r j=1:314 t i c ;15 w1 = rankonemultslow(a(1:n),b(1:n),v(1:n));16 t1 = min( toc ,t1);17 end18 t2 = realmax;19 f o r j=1:320 t i c ;


21 w2 = rankonemultfast(a(1:n),b(1:n),v(1:n));22 t2 = min( toc ,t2);23 end24 norm(w1-w2), % Check for agreement of results25 res = [res; n, t1, t2];26 end27

28 % Create plots of runtimes.29 f i g u r e;30 p l o t(res(:,1),res(:,2),’b+’,res(:,1),res(:,3),’r.’);31 x l a b e l(’{\bf vector length n}’,’fontsize’,14);32 y l a b e l(’{\bf runtime [s]}’,’fontsize’,14);33 t i t l e (’runtime measurements for multiplication with a*bˆT’);34 l egend(’(a*bˆT)*v’,’a*(bˆT*v)’,’location’,’best’);35

36 p r i n t -depsc2 ’../../LANMFigures/rankonemulttiming.eps’;37 end38

39 % The following two functions perform algebraically equivalentoperations,

40 % however at vastly different computationl cost. Note the differentorder of

41 % multiplications implied by the positions of the brackets.42

43 f u n c t i o n w = rankonemultslow(a,b,v), w = (a*b’)*v; end44 f u n c t i o n w = rankonemultfast(a,b,v), w = a*(b’*v); end

10.7c) Geben Sie den (asymptotischen) Rechenaufwand fur die beiden MATLAB-Funktionen furgrosse n ∈ N an.

Tipp: Der Begriff des asymptotischen Rechenaufwandes wurde in [LANM, Definition V.3.0.D]eingefuhrt.

Losung: Bei der MATLAB-Funktion abmult1.m berechnen wir als erstes die Matrix A = ab>.Dies kostet und einen Aufwand von O(n2). Danach berechnen wir Av, was eine Matrix-Vektor-Multiplikation darstellt und somit Aufwand O(n2) hat. Insgesamt erhalten wir eine Rechenauf-wand von

O(n2) +O(n2) = O(n2)

fur abmult1.m.

Bei abmult2.m berechnen wir zuerst u = b>v ∈ R, was einer Vektor-Vektor-Multiplikationentspricht und somit Aufwand O(n) hat. Danach fuhren wir eine skalare Vektormultiplikationdurch, namlich au. Wieder wenden wir dabei einen Aufwand von O(n) auf.

Total erhalten wirO(n) +O(n) = O(n)

fur abmult2.m.


0 100 200 300 400 500 600 700 800 900 10000

1

2

3

4

5

6

7x 10

−3

vector length n

ru

nti

me [

s]

runtime measurements for multiplication with a*bT

(a*bT)*v

a*(bT*v)

Abbildung 10.1: Ausgabe der MATLAB-Funktion aus Listings 10.8 aus Teilaufgabe 10.7b)

Somit ist die Variante abmult2.m deutlich kostengunstiger, was auch der Laufzeitplot in Ab-bildung 10.1 verrat.

Aufgabe 10.8 Dunnbesetzte Matrizen in MATLAB

In [LANM, Abschnitt 5.4] haben Sie gelernt, dass dunnbesetzte Matrizen in MATLAB mit Hilfespezieller Datenstrukturen reprasentiert werden und dass man diese aus Effizienzgrunden verwen-den muss. Sie haben auch gesehen, wie die MATLAB-Funktion sparse zur Initialisierung vondunnbesetzten Matrizen verwendet wird. In dieser Aufgabe sollen Sie den Einsatz von sparseuben.

Implementieren Sie in jeder der folgenden Teilaufgaben eine MATLAB-Funktion, welche fur einegegebene naturliche Zahl n die jeweilige dunnbesetzte Matrix resp. sparse Matrix erstellt.

? 10.8a) Schreiben Sie die MATLAB-Funktion

function Z = ZShaped( n ) ,


die eine n× n dunnbesetzte Matrix Z zuruckgibt, deren nicht-nulle Eintrage die Form des Buch-stabens Z bilden, wobei die Eintrage wie folgt lauten:

(Z)1,j = 1, fur j = 1, . . . , n

(Z)j,n+1−j = j, fur j = 1, . . . , n

(Z)n,j = n, fur j = 1, . . . , n.

Alle anderen Eintrage der Matrix sind gleich 0.

Tipp: Die Matrix Z in dieser Teilaufgabe hat rein gar nichts mit der Zeilenstufenform zu tun!

Losung:

Listing 10.9: MATLAB-Funktion aus Teilaufgabe 10.8a)1 % INPUT2 % n - parameter describing the size of the matrix3 % OUTPUT4 % Z - nxn matrix, whose non-zero entries are shaped like the letter Z5

6 f u n c t i o n Z = ZShaped(n)7

8 Z = sp ar se(ones(n-1, 1), (1:(n-1))’, ones(n-1,1), n, n) +sp ar se((1:n)’,...

9 (n:-1:1)’, (1:n)’, n, n)+ sp ar se( n*ones(n-1, 1), (2:n)’, ...10 n*ones(n-1,1)’, n, n);

? 10.8b) Ihre Funktion

function X = XShaped( n )

liefert eine n× n dunnbesetzte Matrix X, deren nicht-null Eintrage die Form des Buchstabens Xbilden, wobei die Eintrage wie folgt lauten:

(X)j,j = 2, fur j = 1, . . . , n

(X)j,n+1−j = 2, fur j = 1, . . . , n.


Losung:

Listing 10.10: MATLAB-Funktion aus Teilaufgabe 10.8b)1 % INPUT2 % n - parameter describing the size of the matrix3 % OUTPUT4 % X - nxn matrix, whose non-zero entries are shaped like the letter X


5

6 f u n c t i o n X = XShaped(n)7

8 X = 2* sp ar se((1:n)’,(1:n)’,ones(n,1), n, n) + 2* sp ar se((1:n)’, ...9 (n:-1:1)’,ones(n,1));

10

11 % If n is an odd number then by the previous equation the value ofthe

12 % entry in the middle of the diagonal would be doubled, so we haveto reset

13 % it.14

15 i f mod(n,2)16 X( (n+1)/2, (n+1)/2) = 2;17 end

? 10.8c) Die Funktion

function T = ThreeBand( n )

gibt eine n× n dunnbesetzte Dreibandmatrix T, mit den folgenden Eintragen

(T)j,j = 1, fur j = 1, . . . , n

(T)j+1,j = 2, fur j = 1, . . . , n− 1

(T)j+2,j = 3, fur j = 1, . . . , n− 2


Losung:

Listing 10.11: MATLAB-Funktion aus Teilaufgabe 10.8c)1 % INPUT2 % n - parameter describing the size of the matrix3 % OUTPUT4 % T - nxn, three band matrix5

6 f u n c t i o n T = ThreeBand(n)7

8 T = sp ar se( (1:n)’, (1:n)’, ones(n,1))+ sp ar se((2:n)’,(1:n-1)’,...9 2*ones(n-1,1), n, n)+ sp ar se((3:n)’,(1:n-2)’,3*ones(n-2,1), n, n);

(→ Tipp)


1 1 1 1 10 0 0 2 00 0 3 0 00 4 0 0 05 5 5 5 5

(a) Z-formige Matrix

2 0 0 0 20 2 0 2 00 0 2 0 00 2 0 2 02 0 0 0 2

(b) X-formige Matrix

1 0 0 0 02 1 0 0 03 2 1 0 00 3 2 1 00 0 3 2 1

(c) Dreibandmatrix

Abbildung 10.2: Beispiele fur die Matrizen aus den Teilaufgaben 10.8a)-10.8c), wobei n=5

? ? 10.8d) Betrachten Sie die drei dunnbesetzten Matrizen genauer, welche in Teilaufgaben 10.8a)-10.8c) eingefuhrt wurden. Untersuchen Sie, fur welche dieser Matrizen ihr Quadrat, erhaltendurch Matrixmultiplikation mit sich selbst, wieder eine dunnbesetzte Matrix ergibt.

Losung:

• Sei Z eine Matrix mit nicht-null Eintragen, welche angeordnet sind in Form des Buchsta-bens Z und bezeichne B := Z · Z dessen Quadrat. Fur einen beliebigen Eintrag von B giltaufgrund Definition der Matrix-Matrix-Multiplikation, dass

bij =n∑k=1

zikzkj .

Aufgrund der Definition von Z erhalten wir, dass gilt zik 6= 0, sofern entweder i = 1, i = noder k = n+ 1− i.Die ersten beiden Falle i = 1 und i = n beziehen sich auf die erste und letzte Zeile von B.Im letzen Fall, k = n+ 1− i, erhalten wir

bij = zi,n+1−izn+1−i,j ,

wobei zn+1−i,j nur ungleich Null ist, sofern j = n + 1 − (n + 1 − i) = i. Deshalb ist bijnur in einem der folgenden Falle verschieden von Null:

– i = 1,

– i = n,

– j = i.

Dies bedeutet, dass B “dunnbesetzt” ist und nicht-null Eintrage in Form des gespiegeltenBuchstabens Z hat: Z.

• Im Fall X, also im Falle einer Matrix mit nicht-null Eintragen in Form des Buchstabens X,definieren wir B := X ·X .

Fur einen beliebigen Eintrag von B erhalten wir per Definition der Matrix-Matrix-Multiplikation,dass

bij =n∑k=1

xikxkj .


Aufgrund der Definition von X erhalten wir, dass gilt xik 6= 0, sofern entweder k = i oderk = n+ 1− i. Somit gilt

bij = xiixij + xi,n+1−ixn+1−i,j.

Weiter stellen wir fest, dass xij und xn+1−i,j nur verschieden von Null sind, sofern giltj = 1 oder j = n+ i− 1. Deshalb ist bij ungleich Null, sofern

– j = i,

– j = n+ 1− i.

Dies bedeutet, dass B “dunnbesetzt” ist und wieder nicht-null Eintrage in Form des Buch-stabens X hat.

• Wir betrachten den letzen Fall T, also den Fall einer Tridiagonalmatrix, und definierenB := T · T. Fur einen beliebigen Eintrag von B erhalten wir per Definition der Matrix-Matrix-Multiplikation, dass gilt

bij =n∑k=1

tiktkj .

Aufgrund der Definition von T erhalten wir, dass fur i ≥ 3 der Eintrag tik nur verschiedenvon Null ist, sofern gilt k = i, i+ 1 oder k = i+ 2.

Daraus folgtbij = tiitij + ti,i+1ti+1,j + ti,i+2ti+2,j.

Wir wenden dieselbe Logik nochmals auf tij, ti+1,j und ti+2,j an. So erhalten wir, dass bijverschieden von Null ist, wenn j = i, i + 1, i + 2, i + 3 oder j = i + 4. Grund dafurist, dass tij 6= 0 nur gilt, wenn j = i, i + 1 oder j = i + 2. Weiter gilt ti+1,j 6= 0 nur,sofern j = i + 1, i + 2 oder j = i + 3, und ai+2,j 6= 0 nur, falls j = i + 2, i + 3 oderj = i+ 4. Somit ist die Matrix B eine “dunnbesetzte” Funfbandmatrix. Das bedeutet, dasses nur nicht-null Eintrage auf der Hauptdiagonalen und den vier ersten Nebendiagonalenunter der Hauptdiagonalen gibt.

? ? ? 10.8e) Implementieren Sie fur die Tridiagonalmatrix aus Teilaufgabe 10.8c) eine MATLAB-Funktion,

y = multTridiagonal(x) ,

welche das Matrix-Vektorprodukt der Matrix mit einem Spaltenvektor x ∈ Rn (fur ein n ∈ N alsEingabe) berechnet, ohne dass die Matrix selbst aufgestellt wird, weder als vollbesetzte noch alsdunnbesetzte Matrix! Das Ergebnis von T · x soll in y zuruckgegeben werden.

(→ Tipp)

Losung:

Listing 10.12: MATLAB-Funktion aus Teilaufgabe 10.8e)1 % INPUT2 % x - a vector3 % OUTPUT


4 % y - result of multiplying x by a three band sparse matrix.5

6 f u n c t i o n y = MultiplyThreeBand( x)7

8 y = z e r o s( s i z e(x)); % Initialising y9

10 % First and second entry of y adhere to a different rule than otherentries

11 y(1) = x(1);12 y(2) = 2*x(1)+x(2);13

14 % Computing the remaining entries15 f o r i = 3 : l e n g t h(y)16 y(i) = 3*x(i-2)+2*x(i-1)+x(i);17 end

Aufgabe 10.9 Schatzung von Punkten mittels Relativen Distanzen (MATLAB)

Diese Aufgabe beschaftigt sich mit einer Anwendung der Kleinste-Quadrate-Losung eines uberbestimmtenlinearen Gleichungssystems (Abschnitt [LANM, Thm. 4.4] der Vorlesung) auf ein Schatzproblemaus dem Vermessungswesen.

Sei m ∈ N gegeben. Fur n gegebene Punkte auf einer geraden Strasse mit Positionen pi ∈ Rfur i ∈ {1, . . . ,m} mit p1 < p2 < . . . < pm sind folgende Abstande (moglicherweise ungenau)vermessen worden:

pi − pj = dij, for 1 ≤ j < i ≤ n,

siehe Abbildung 10.3

Abbildung 10.3: Lage der Messpunkte und Definition der Abstande dij fur Aufgabe 10.9

Das Problem (P) besteht darin, die Positionen p1, . . . , pm der Messpunkte aus den gegebenenAbstandsdaten mit Hilfe der Methode der kleinsten Quadrate zu schatzen.

? 10.9a) Wie viele Gleichungen bzw. Werte fur dij sind gegeben?

(→ Tipp)

Losung: Es gibtÄm2

äWerte fur dij .

? 10.9b) Geben Sie die in Teilaufgabe 10.9a) beschriebenen Gleichungen an, d.h. formulierenSie das uberbestimmte lineare Gleichungssystem Ax = b mit einer geeigneten Matrix A undRechte-Seite-Vektor b, das von den unbekannten Punktpositionen erfullt wurde, wenn diese feh-lerfrei gemessen worden waren.


Losung: Wir definieren

A =

−1 1 0 · · ·−1 0 1 0 · · ·0 −1 1 0 · · ·−1 0 0 1 0 · · ·0 −1 0 1 0 · · ·...

......

......

......

und

d =

d21d31d32d41d42...

.

Unser uberbestimmtes lineares Gleichungssystem lautet Ax = d, wobei gilt, dass x =

p1p2...pm

.

Folglich gilt, dass A ∈ R(m2 ),m, d ∈ R(

m2 ) und x ∈ Rm.

? ? ? 10.9c) Bestimmen Sie Kern(A). Interpretieren Sie das Ergebnis und beschreiben Sie die Konse-quenzen fur eine Kleinste-Quadrate-Losung (siehe Definition [LANM, Thm. IV.4.2.B]). Schla-gen Sie eine Modifikation des Problems (P) vor, die eine eindeutige Kleinste-Quadrate-Losungder modifizierten Problemstellung garantiert und geben Sie das zugehorige uberbestimmte lineareGleichungssystem an.

Tipp: Nicht rechnen! Uberlegen Sie sich, welche Anderung in den Punktpositionen keine Aus-wirkung auf deren relative Entfernungen haben wird.

Losung: Wir wollen den Kern(A) berechnen. Das bedeutet, wir suchen alle x ∈ Rd, sodassAx = 0 gilt. Wir haben

−1 1 0 · · ·−1 0 1 0 · · ·0 −1 1 0 · · ·−1 0 0 1 0 · · ·0 −1 0 1 0 · · ·...

......

......

......

p1p2...pm

=

00...0

,

was gleichbedeutend ist zur Bedingung, dass pi − pj = 0 fur alle n ≥ i > j ≥ 1. Dies istaquivalent dazu, dass gilt pi = pj fur alle i, j.

Deshalb gilt Ax = 0 genau dann, wenn pi = α, fur alle i = 1, . . . ,m und beliebiges α ∈ R.


Somit erhalten wir

Kern(A) = Span

11...1

.

Daraus folgt direkt, dass dimKern(A) = 1 , und deshalb Bild(A) < m, was weiter bedeutet,dass die Gleichung Ax = d keine eindeutige Losung haben wird, siehe [LANM, Thm. I.4.5.B]aus der Vorlesung.

Wir betrachten ein leicht geandertes lineares Gleichungssystem. Anstatt die Unbekannten pi zubetrachten, verschieben wir das ganze Gleichungssystem um p1. Das bedeutet, wir definierenpi := pi − p1. Bitte beachten Sie, dass nun immer noch gilt, dass

pi − pj = pi − p1 − pj + p1 = dij.

Zusatzlich gilt per Definition p1 = 0. Somit ist die Gleichung

A =

−1 1 0 · · ·−1 0 1 0 · · ·0 −1 1 0 · · ·−1 0 0 1 0 · · ·0 −1 0 1 0 · · ·...

......

......

......

0p2...pm

=

d21d31d32d41d42...

aquivalent zu Ax = d, wobei wir

A =

1 0 · · ·0 1 0 · · ·−1 1 0 · · ·0 0 1 0 · · ·−1 0 1 0 · · ·...

......

......

......

erhalten, indem wir die erste Spalte von A eliminieren und x definieren als x :=

p2p3...pm

. Die

abgeanderteÄm2

ä×(n−1) Matrix A hat trivialen Kern (Kern(A) = {0}), da wir fur die Gleichung

Ax = 0 nur die Losung p2 = 0, p3 = 0, . . . erhalten. Somit ist A eine Matrix mit RangA =(m − 1) (folgt aus dem Dimensionssatz (siehe [LANM, Thm. III.3.0.H]) unter Ausnutzung vondimKern(A) = 0), und liefert uns somit eine eindeutige Kleinste-Quadrate-Losung.

? ? 10.9d) Stellen Sie die Normalengleichungen fur den Fallm = 5 und das modifizierte uberbestimmtelineare Gleichungssystem aus der vorherigen Teilaufgabe auf.

(→ Tipp)


Losung: Fur n = 5 sieht die Matrix des modifizierten Systems wie folgt aus:

A =

1 0 0 00 1 0 0−1 1 0 00 0 1 0−1 0 1 00 −1 1 00 0 0 1−1 0 0 10 −1 0 10 0 −1 1

.

Somit ist das uberbestimmte Gleichungssystem gegeben durch

Ax =

d21d31d32d41d42d43d51d52d53d54

.

Wir berechnen nun die einzelnen Terme fur die Normalengleichungen:

A>A =

4 −1 −1 −1−1 4 −1 −1−1 −1 4 −1−1 −1 −1 4

und

A>d =

d21 − d32 − d42 − d52d31 + d32 − d43 − d53d41 + d42 + d43 − d54d51 + d52 + d53 + d54

.Die Normalengleichungen lauten folglich A>Ax = A>d .

? ? 10.9e) Erstellen Sie eine MATLAB-Funktion

function p = PointPosEstimate(D) ,

welche als Eingabe die Messwerte dij erwartet (gespeichert in der m × m oberen Dreiecksma-trix D) und daraus die Losung des modifizierten Problems aus Teilaufgabe 10.9c) im Sinne derkleinsten Quadrate berechnet.

(→ Tipp)


Losung:

Listing 10.13: MATLAB-Funktion aus Teilaufgabe 10.9e)1 % INPUT2 % D - a strictly lower triangular matrix3 % OUTPUT4 % p - vector containing the shited values,

\tilde{p}_2,...,\tilde{p}_n5

6 f u n c t i o n p = RoadLengths(D)7

8 % Find the indices of non-zero entries9 [I,J] = f i n d(D’ > 0);

10 % Determine the size of A11 m = s i z e(D, 1);12 n = l e n g t h(I);13 % Build A, in a sparse form14 A = sp ar se([(1:n)’;(1:n)’],[I;J],[-ones(n,1);ones(n,1)],n,m);15 % Remove A’s first column to ensure uniqueness of our least squares

solution16 A = A(:,2:end);17 % Extract the right hand side vector18 d = nonzeros(D’);19 % Finally, solve the equation20 p = A\d;

Aufgabe 10.10 Auf Umwegen zum linearen Ausgleichsproblem (MATLAB)

Diese Aufgabe ist eine versteckte lineare Ausgleichsrechnung. Auf den ersten Blick scheint dieAufgabenstellung nicht auf ein uberbestimmtes lineares Gleichungssystem zu fuhren, doch dannkommt die Umkehrfunktion der Exponentialfunktion zu Hilfe!

Wir betrachten die Funktion f(t) = αeβ·t mit unbekannten Parametern α > 0, β ∈ R. Gegebensind Messwerte (ti, yi), i = 1, . . . , n, n ∈ N, n > 2. Wir wollen nun α, β ∈ R derart bestimmen,dass f(t) die Bedingungen

f(ti) = yi > 0, i = 1, . . . , n , (10.10.1)

“bestmoglichst” (im Sinne der kleinsten Quadrate) erfullt.

? 10.10a)Welches uberbestimmte nichtlineare Gleichungssystem ergibt sich zunachst aus (10.10.1)?

Losung: Wir erhalten das folgende uberbestimmte nichtlineare Gleichungssystem

yi = f(ti) = αeβti fur i = 1, . . . , n .

? ? ? 10.10b)In welches uberbestimmte lineare Gleichungssystem lasst es sich transformieren?


Tipp: Verwenden Sie die Umkehrfunktion der Exponentialfunktion.

(→ Tipp)

Losung: Wir definieren g(t) = log f(t). Diese Funktion g ist wohldefiniert, da gilt f(t) > 0, furalle t ∈ R.

Wir machen den Ansatz

g(t) = log f(t) = logα + log eβt = a+ βt,

wobei wir a := logα definieren. Analog zur Funktion g definieren wir weiter bi : = log yi. Dasdadurch erhaltene, nun komplett lineare, uberbestimmte Gleichungssystem lautet

Ax = b , mit A =

1 t11 t2...

...1 tn

, x =

ñaβ

ôund b =

b1b2...bn

. (10.10.2)

? 10.10c)Stellen Sie die Normalengleichungen gemass Satz [LANM, Thm. IV.4.3.B] aus der Vor-lesung zu dem uberbestimmten lineare Gleichungssystem aus der vorhergehenden Teilaufgabeauf.

(→ Tipp)

Losung: Die Normalengleichungen des linearisierten Problems (10.10.2) aus Teilaufgabe 10.10b)lauten

A>Ax = A>b ,

was nach Einsetzen Folgendes ergibt:

A>A =

ñn

∑ni=1 ti∑n

i=1 ti∑ni=1 t

2i

ôund A>b =

ñ ∑ni=1 bi∑ni=1 tibi

ô.

Die Kleinste-Quadrate-Losung x =

Çaβ

åliefert uns dann durch α = ea und β die “bestmoglichste”

Losung f .

? ? 10.10d)Implementieren Sie eine MATLAB-Funktion

function [alpha,beta] = ExpoFuncFit(t,y)

die in den gleichlangen Spaltenvektoren t und y die Daten (ti, yi) entgegennimmt und eineKleinste-Quadrate-Schatzung von α und β zuruckgibt.

(→ Tipp)

Losung:

Listing 10.14: MATLAB-Funktion aus Teilaufgabe 10.10d)1 % INPUT


2 % t, y - parameters, such that f(t(i)) = y(i)3 % OUTPUT4 % alpha, beta - values such that alpha*exp(beta*t) approximates f,

through5 % least squares.6

7 f u n c t i o n [alpha, beta] = ExpoFuncFit(t, y)8 % Compute the solution of the linearised problem9 x = linearregression(t, l o g(y));

10 % Set the proper output values11 alpha = exp(x(2));12 beta = x(1);13 end14

15 f u n c t i o n x = linearregression(t,y)16 % Solution of linear regression problem (fitting of a line to data)

for17 % data points (t_i,y_i), i=1,\ldots,n, passed in the18 % column vectors t and y.19 % The return value is a 2-vector, containing the slope of the fitted

line20 % in x(1) and its offset in x(2)21 n = l e n g t h(t);22 i f ( l e n g t h(y) ˜= n)23 error(’data size mismatch’);24 end25 % Coefficient matrix of \textbf{overdetermined linear system}26 A = [t,ones(n,1)];27 % Determine least squares solution by using MATLAB’s ‘‘backslash’’28 % operator}29 x = A\y;30 end

Tipps

Tipps fur Aufgabe 10.2

10.2a) Sie wissen aus [LANM, Satz IV.2.3.L] bereits, dass der Differenzenvektor von y undseiner orthogonalen Projektion auf E parallel zu n sein muss. Daher reduziert sich dieRechnung auf die Bestimmung des Schnittpunkts einer Geraden mit einer Ebene.


In [LANM, Code 5.4] steht Ihnen eine Implementierung des Gram-Schmidt- Orthonor-malisierungsalgorithmus in MATLAB zur Verfugung, den Sie auch hier herunterladen


http://www.sam.math.ethz.ch/~hiptmair/tmp/LANM/MATLAB/NumLinAlgMATLAB/gramschmidt.m

konnen. Sie konnen diesen Code mit den Daten der Aufgabe laufen lassen und sich Zwi-schenresultate ausgeben lassen.

10.3b) Der Gram-Schmidt- Orthonormalisierungsalgorithmus berechnet zunachst nur die orth-normalen Vektoren q1, . . . ,qk. Wie in der Vorlesung erklart, erhalt man die Eintrage derMatrix R in der QR-Zerlegung, indem man die Koeffizienten der Linearkombinationender q` berechnet, die wieder die Spalten der Matrix ergeben. Studieren Sie dazu noch-mals die Uberlegungen aus der Vorlesung, die schliesslich in [LANM, Satz IV.3.4.F]mundeten.

10.3b) In [LANM, Abschnitt 5.2], auch in [LANM, Listing 5.6], haben Sie gelernt, dass dieGram-Schmidt- Orthonormalisierung sich in MATLAB durch die Funktion qr realisierenlasst. Damit konnen Sie die QR-Zerlegung der gegebenen Matrizen berechnen und Ihreauf Papier erhaltenen Ergebnisse kontrollieren.


10.5a) Wir haben die Information, dass f eine gewichtete Summe von g1 und g2 ist, also f(x) =w1g1(x) + w2g2(x), wobei die Gewichte w1, w2 ∈ R nicht bekannt sind und aus denMesswerten geschatzt werden mussen. Sie sind also die Unbekannten des uberbestimmtenlinearen Gleichungssystems, das demzufolge 5 Gleichungen und 2 Unbekannte umfasst.

10.5c) Die Kleinste-Quadrate-Losung erhalt man naturlich durch Losen der Normalengleichun-gen aus Satz [LANM, Thm. IV.4.3.B], einem linearen Gleichungssystem der Grosse 2×2. Sie konnen Ihr Resultat einfach mit MATLAB uberprufen, indem Sie das uberbestimmtelineare Gleichungssystem mit \ losen, siehe [LANM, Abschnitt 5.5].


10.6b) Mit welchem Vektor muss man eine Matrix A ∈ Rm,n multiplizieren, um als Ergebnisdie j. Spalte der Matrix zu erhalten? In einer Schleife durchlaufen Sie alle diese Vekto-ren und bauen dann die gesuchte Matrix Spalte fur Spalte auf, in dem Sie den MATLAB-Matrixbaukasten verwenden (Komma-Operator zum Nebeneinanderstellen von Matri-zen).


Diese Aufgabe wiederholt nur das, was Sie schon in der Vorlesung im Zusammenhangmit [LANM, Beispiel V.3.0.F] gelernt haben!


10.8c) Benutzen Sie die MATLAB-Funktion sparse, um die Matrizen zu erstellen. Fur mehrInformationen konsultieren Sie bitte die MATLAB-Hilfe via help sparse oder docsparse.


10.8e) Betrachten Sie zunachst die konkrete Matrix fur n = 5 in Abbildung ?? und uberlegenSie sich in diesem Fall, wie sie das Matrix-Vektorprodukt Tx nur mit Hilfe von

• einfacher Vektorarithmetik (Addition und Skalarmultiplikation),

• Skalarprodukten (MATLAB-Funktion dot),

• Selektion von Teilvektoren mit Hilfe von Indexbereichen (MATLAB-Syntax v(i:j))

realisieren konnen.


10.9a) Dies ist eine Frage aus der elementaren Kombinatorik: Wieviele verschiedene Teilmen-gen mit zwei Elementen lassen sich aus einer Menge mitm Elememtem auswahlen? Dassollten Sie in der Schule gelernt haben.

10.9d) In diesem Fall sind 10 Distanzen gegeben. Die Position des ersten Punkts kann willkurlichals p1 = 0 festgelegt werden, was uns mit 4 Unbekannten belasst.

10.9e) Man muss sich naturlich ein klares Nummerierungsschema fur die Zeilen der Matrix desuberbestimmten linearen Gleichungssystems uberlegen. Diese Konvention ist beliebigaber man muss sie dann konsequent anwenden.


10.10b) Wie Sie in der Schule und auch in Analysis gelernt haben, ist der Logarithmus log dieUmkehrfunktion der Exponentialfunktion. Fur ihn gilt die Rechenregel log(ξζ) = log ξ+log ζ fur alle ξ, ζ > 0. Wenn Sie also den Logarithmus auf (10.10.1) anwenden, dannerhalten Sie logα + βti = yi, i = 1, . . . , n.

10.10c) Nach der Transformation liegt ein lineares Regressionsproblem vor. Schauen Sie sichnochmals [LANM, Beispiel IV.4.3.D] an.

10.10d) Sobald Sie das Problem in ein uberbestimmtes lineares Gleichungssystem transformierthaben, erledigt MATLABs Operator \ den Rest, wie Sie in [LANM, Abschnitt 5.5] ge-lernt haben. Vergessen Sie aber nicht, die Transformation ruckgangig zu machen und dierichtigen Parameterwerte zuruckzugeben.

Allgemeine Informationen:• Abgabe der Serien: Mittwoch, 10.12.2014 in den Ubungen oder bis 15:00 Uhr in den

Fachern im Vorraum zum HG G 53. Die Serien mussen sauber und ordentlich geschriebenund zusammengeheftet abgegeben werden, sofern eine Korrektur gewunscht wird.

Die Abgabe der Hausaufgaben wird nachdrucklich empfohlen!Bitte markieren Sie deutlich die Aufgaben, deren Korrektur Sie wunschen!


• Zentralprasenz:

– Montags, 17:00 - 20:00 Uhr, ETH Zentrum, HG E 41.

– Donnerstags, 17:00 - 20:00 Uhr, ETH Zentrum, HG E 41.

– Freitags, 17:00 - 20:00 Uhr, ETH Zentrum, HG E 41.

Bitte erscheinen Sie bereits zwischen 17:00 - 18:00Uhr, sofern Sie von der Semesterprasenzprofitieren wollen.

• Homepage: Hier werden zusatzliche Informationen zur Vorlesung und die Serien und Mu-sterlosungen als PDF verfugbar sein.www.math.ethz.ch/education/bachelor/lectures/hs2014/other/linalgnum BAUG

Veroffentlichung am 3. Dezember 2014.Abzugeben bis 10. Dezember 2014.

Literatur

[LANM] Vorlesungszusammenfassung fur die Vorlesung “Lineare Algebra und Numerische Ma-thematik, D-BAUG”.

Last modified on 11. Dezember 2014

Serie 10 Seite 31 Literatur

https://www.math.ethz.ch/~hiptmair/tmp/LANM/LANM14.pdf