Click here to load reader

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

  • View
    0

  • Download
    0

Embed Size (px)

Text of R. Hiptmair Herbstsemester 2014 ETH Zurich¨ S. Pintarelli Lineare … · 2014. 12. 11. · R....

  • R. HiptmairS. PintarelliE. Spindler

    Herbstsemester 2014

    Lineare Algebra und NumerischeMathematik für D-BAUG

    ETH ZürichD-MATH

    Beispiellösung für Serie 10

    Einleitung. In dieser Serie werden Sie zum ersten Mal gebeten, numerische Algorithmen inMATLAB zu implementieren, wobei Grundlagenkenntnisse über 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 Lösung eines überbestimmten 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 Unterräume U , V orthogonale Komplemente in R2 oder R3bilden, siehe [LANM, Abschnitt 4.3.2] der Vorlesung. Das bedeutet, Sie sollen herausfinden, obdie Unterräume 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 Unterräume 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 Unterräume keine orthogonalen Komplemente in R2.

    Serie 10 Seite 2 Aufgabe 10.1

  • 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 Unterräume 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 = 0Da 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 Unterräume senkrecht zueinander stehen!). Für dieDimensionen gilt dimU = 1 und dimV = 2, da

    [ −301

    ]und

    [ −210

    ]linear unabhängig sind:

    α1[ −3

    01

    ]+ α2

    [ −210

    ]=

    [000

    ]⇔ α1 = α2 = 0 .

    Deshalb gilt dimU + V = 1+2+0 = 3. Somit spannen die beiden Unterräume 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 Länge des Differenzvektors (“Abstand der Punkte”) am nächstenliegt. Dies führte 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 . . .

    Serie 10 Seite 3 Aufgabe 10.2

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

    (→ Tipp)

    Lösung: 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 erfüllen, dass q = y − pparallel 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 natürlich 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− 44 + 16 + 16

    =1

    18,

    was uns mit (10.2.1) die Lösung

    p = y − αn =

    111

    − 118

    24−4

    = 19

    8711

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

    Tipp: Sie können Ihren Rechenaufwand dadurch reduzieren, dass Sie a und b geschickt wählen.Erinnern Sie sich dazu an [LANM, Lemma IV.3.4.A]. Das Vektorprodukt aus [LANM, Ab-schnitt 4.3.5] kann auch nützlich sein.

    Lösung: Berechnen wir die Orthogonalprojektion mithilfe der Ausgleichsrechnung, benötigenwir zwei Vektoren, welche die Ebene aufspannen. Wir wählen 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 a1steht:

    a2 = n× a1 =

    24−4

    ×011

    = 8−22

    .Eine Orthonormalbasis des R3 ist folglich

    B =®

    1

    ‖n‖n,

    1

    ‖a1‖a1,

    1

    ‖a2‖a2´,

    Serie 10 Seite 4 Aufgabe 10.2

  • wobei 1‖a1‖a1, 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‖a1, 1‖a2‖a

    2

    schreiben können. Wir erhalten das überbestimmte lineare Gleichungssystemî1‖a1‖a

    1, 1‖a2‖a2óñα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 Lösung 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‖ (a1)>1‖a2‖ (a

    2)>

    y ,ñ1 00 1

    ôñα1α2

    ô=

    1‖a1‖a1>y1‖a2‖a

    2>y

    ,ñα1α2

    ô=

    [ √2

    23

    √2

    ].

    wobei wir verwendet haben, dass B eine Orthonormalbasis darstellt. Wir erhalten die Lösung

    p = α1a1 + α2a

    2 =√2

    1√2

    011

    + 23

    √2

    1

    6√2

    8−22

    =011

    + 19

    8−22

    = 19

    8711

    .Da wir dieselbe Lösung wie in Teilaufgabe 10.2b) erhalten, haben wir richtig gerechnet.

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

    Der Höhepunkt 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”durchführen, um seine Details zu verstehen. Zusätzlich sollen Sie lernen, wie man als Nebenpro-dukt auch die Matrix R aus der QR-Zerlegung gemäss [LANM, Satz IV.3.4.F] erhält.

    (→ Tipp)

    Gegeben seien die Matrizen

    A =

    2 11 12 1

    ∈ R3,2 , B = 2 3 −11 −1 0−1 1 0

    ∈ R3,3 .

    Serie 10 Seite 5 Aufgabe 10.3

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

    Lösung: 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

    ,

    q̃2 := a2 − 〈a2,q1〉q1 =

    111

    − 13(2 + 1 + 2)

    1

    3

    212

    = 19

    9− 109− 59− 10

    = 19

    −14−1

    ,

    q2 :=

    √2

    6

    −14−1

    .

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

    13212

    , √26

    −14−1

    für den Spaltenraum

    von A.

    Für die Spalten von B, b1 :=[

    21−1

    ], b2 =

    [3−11

    ], b3 =

    [ −100

    ]. erhalten wir analog

    q1 :=1

    ‖b1‖b1 =

    √6

    6

    21−1

    ,

    q̃2 := b2 − 〈b2,q1〉q1 =

    3−11

    − √66

    (6− 1− 1)√6

    6

    21−1

    = 13

    9− 4−3− 23 + 2

    = 53

    1−11

    ,

    q2 :=q̃2

    ‖q̃2‖=

    √3

    3

    1−11

    ,

    q̃3 := b3 − 〈b3,q1〉q1 − 〈b3,q2〉q2 =

    −100

    + 26

    21−1

    + 13

    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 ‖q̃3‖ = 0 erfüllt ist.

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

    √66

    21−1

    , √33

    1−11

    für den Spaltenraum

    von B.

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

    (→ Tipp)

    Serie 10 Seite 6 Aufgabe 10.3

  • (→ Tipp)

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

    Für 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 530

    √23

    ].

    Für 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 natürliche Zahl n. Durch n Messungen der skalaren Grösse x haben wir n(leicht verschiedene) Messwerte m1,m2, . . .,mn für x erhalten, aus denen wir durch Lösen einesüberbestimmten linearen Gleichungssystems im Sinne der kleinsten Quadrater eine Schätzung fürx erhalten wollen.

    10.4a) Repetieren Sie den Abschnitt [LANM, Thm. 4.4] der Vorlesung über die Kleinste-Quadrate-Lösung von überbestimmten linearen Gleichungssystemen.

    10.4b) Stellen Sie das überbestimmte lineare Gleichungssystem für das vorliegende Problem auf.

    Lösung: Wir schreiben das überbestimmte lineare Gleichungssystem des vorliegenden Problemsauf. Wir suchen x ∈ R, sodass gilt

    11...1

    x =m1m2...mn

    . (10.4.1)

    10.4c) Stellen Sie die zugehörigen Normalengleichugen gemäss Satz [LANM, Thm. IV.4.3.B]der Vorlesung auf.

    Serie 10 Seite 7 Aufgabe 10.4

  • Lösung: Um das Gleichungssystem zu lösen, 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-Lösung gemäss Definition [LANM, Thm. IV.4.2.B]aus der Vorlesung und interpretieren Sie das Ergebnis.

    Lösung: Die kleinste-Quadrate-Lösung erhalten wir, indem wir die Gleichung (10.4.3) nach xauflösen. 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 verläuft:

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

    ? ? 10.5a) Auf welches überbestimmte lineare Gleichungssystem führt die Schätzung von f?

    (→ Tipp)

    Lösung: 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.

    Serie 10 Seite 8 Aufgabe 10.5

  • 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 für 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 gemäss [LANM, Satz IV.4.3.B] zum überbestimmtenlinearen Gleichungssystems aus Teilaufgabe 10.5a).

    Lösung: 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 schätzen.

    (→ Tipp)

    Lösung: Lösen wir die Normalengleichungen A>Ax = A>b, wobei wir A, b, x aus Teilauf-gabe 10.5b) übernehmen, 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 zurück 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.

    Serie 10 Seite 9 Aufgabe 10.6

  • ? ? 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 zurückgibt.

    Wir wissen, dass sich die durch die Funktion transform implementierte Abbildung v 7→ wals Matrix×Vektor-Produkt w = Av schreiben lässt. Welche Matrix A ∈ Rn,n repräsentiert dieMATLAB-Funktion function w = transform(v), sprich, für welche Matrix A ∈ Rn,ngilt

    w = 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

    Lösung: Da wir Einsicht in die MATLAB-Funktion

    function w = transform(v)

    haben, können wir Zeile für Zeile dieser Funktion in Matrixform darstellen:

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

    Als erstes wird der Vektor v “auf den Kopf gestellt”. Dies können 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

    Serie 10 Seite 10 Aufgabe 10.6

  • hinzugezählt. 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 = 10 sonst

    .

    Natürlich 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 zugänglicheMATLAB-Funktion

    function w = topsecret(v)

    einen Spaltenvektor v ∈ Rn der Länge n ∈ N als Eingabe nimmt und daraufhin einen Spal-tenvektor w ∈ Rn zurückgibt. Weiter wissen wir, dass sich die MATLAB-Funktion durch eineMatrixmultiplikation realisieren lässt, d.h. es gibt ein A ∈ Rn,n, sodass

    w = Av.

    Serie 10 Seite 11 Aufgabe 10.6

  • Schreiben Sie ein MATLAB-Skript findmatrix.m, mit dessen Hilfe Sie Sie diese Matrix Aberechnen können.

    (→ Tipp)

    Lösung: Ziel der Aufgabe ist es, eine allgemein gültige Strategie zu finden, mit welcher wir dieMatrix A berechnen können, wenn wir zwar wissen, wie die Ergebnisse w = Av für beliebigev ∈ Rn aussehen, wir aber A nicht explizit kennen.

    Wir nehmen die kanonische Basis des Rn, E :=

    e1 = 100...0

    , e2 = 010...0

    , . . . , en = 00...

    01

    . Wir

    stellen fest, dass gilt

    Aei = (A):,i , für alle i ∈ {1, . . . , n} .

    Somit erhalten wir A durch Berechnen von

    A(:,i) = topsecret(ei)

    für 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 “verschlüsselte MATLAB-Funktion” function w = topsecret(v) gege-ben (topsecret.p), auf welche Sie Ihren Code auch anwenden sollen. Diese Funktion könnenSie 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 für n = 3 und n = 4 an.

    Lösung: Wir überprüfen unsere Behauptung mit der gegebenen MATLAB-Funktion transform.maus Teilaufgabe 10.6b). Wir erhalten tatsächlich die Matrix, welche wir in Teilaufgabe berechnethaben (siehe Listing 10.5).

    Serie 10 Seite 12 Aufgabe 10.6

  • 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

    Für das Berechnen der Matrix A der MATLAB-Funktion topsecret.p müssen wir den Codenur leicht abändern (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 für 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

    Serie 10 Seite 13 Aufgabe 10.6

  • 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 können, wenn Sie beim Schreiben ihres MATLAB-Codes die Rechenregelnaus der linearen Algebra geschickt nutzen. Matrix-Vektor-multiplikationen sind im Allgemeinfallsehr rechenaufwendig (quadratische Komplexität 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 für eine natürliche Zahl n ∈ N. Wir betrachtendie beiden MATLAB-Funktionen

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

    welche für einen Spaltenvektor v ∈ Rn einen Spaltenvektor w ∈ Rn zurückgeben. 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

    3 % Rueckgabe der Funktion: Transformierter Spaltenvektor w der

    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

    3 % Rueckgabe der Funktion: Transformierter Spaltenvektor w der

    Laenge n

    Serie 10 Seite 14 Aufgabe 10.7

  • 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 zurück. Geben Sie die Matrix A an.

    Lösung: Für 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 für i, j ∈ {1, . . . , n}.

    10.7b) Erzeugen Sie Laufzeitplots für die beiden Funktionen mit Hilfe des Templates

    rankonemulttiming.m ,

    welches Sie von der Vorlesungshomepage herunterladen können.

    Lösung: Wir ergänzen 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 ;

    Serie 10 Seite 15 Aufgabe 10.7

  • 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 für die beiden MATLAB-Funktionen fürgrosse n ∈ N an.

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

    Lösung: 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)

    für abmult1.m.

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

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

    für abmult2.m.

    Serie 10 Seite 16 Aufgabe 10.7

  • 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 kostengünstiger, was auch der Laufzeitplot in Ab-bildung 10.1 verrät.

    Aufgabe 10.8 Dünnbesetzte Matrizen in MATLAB

    In [LANM, Abschnitt 5.4] haben Sie gelernt, dass dünnbesetzte Matrizen in MATLAB mit Hilfespezieller Datenstrukturen repräsentiert werden und dass man diese aus Effizienzgründen verwen-den muss. Sie haben auch gesehen, wie die MATLAB-Funktion sparse zur Initialisierung vondünnbesetzten Matrizen verwendet wird. In dieser Aufgabe sollen Sie den Einsatz von sparseüben.

    Implementieren Sie in jeder der folgenden Teilaufgaben eine MATLAB-Funktion, welche für einegegebene natürliche Zahl n die jeweilige dünnbesetzte Matrix resp. sparse Matrix erstellt.

    ? 10.8a) Schreiben Sie die MATLAB-Funktion

    function Z = ZShaped( n ) ,

    Serie 10 Seite 17 Aufgabe 10.8

  • die eine n× n dünnbesetzte Matrix Z zurückgibt, deren nicht-nulle Einträge die Form des Buch-stabens Z bilden, wobei die Einträge wie folgt lauten:

    (Z)1,j = 1, für j = 1, . . . , n

    (Z)j,n+1−j = j, für j = 1, . . . , n

    (Z)n,j = n, für j = 1, . . . , n.

    Alle anderen Einträge der Matrix sind gleich 0.

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

    Lösung:

    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 dünnbesetzte Matrix X, deren nicht-null Einträge die Form des Buchstabens Xbilden, wobei die Einträge wie folgt lauten:

    (X)j,j = 2, für j = 1, . . . , n

    (X)j,n+1−j = 2, für j = 1, . . . , n.

    Alle anderen Einträge der Matrix sind gleich 0.

    Lösung:

    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

    Serie 10 Seite 18 Aufgabe 10.8

  • 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 dünnbesetzte Dreibandmatrix T, mit den folgenden Einträgen

    (T)j,j = 1, für j = 1, . . . , n

    (T)j+1,j = 2, für j = 1, . . . , n− 1(T)j+2,j = 3, für j = 1, . . . , n− 2

    Alle anderen Einträge der Matrix sind gleich 0.

    Lösung:

    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)

    Serie 10 Seite 19 Aufgabe 10.8

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

    (a) Z-förmige Matrix

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

    (b) X-förmige 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 für die Matrizen aus den Teilaufgaben 10.8a)-10.8c), wobei n=5

    ? ? 10.8d) Betrachten Sie die drei dünnbesetzten Matrizen genauer, welche in Teilaufgaben 10.8a)-10.8c) eingeführt wurden. Untersuchen Sie, für welche dieser Matrizen ihr Quadrat, erhaltendurch Matrixmultiplikation mit sich selbst, wieder eine dünnbesetzte Matrix ergibt.

    Lösung:

    • Sei Z eine Matrix mit nicht-null Einträgen, welche angeordnet sind in Form des Buchsta-bens Z und bezeichne B := Z · Z dessen Quadrat. Für 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 Fälle 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 Fälle verschieden von Null:

    – i = 1,– i = n,– j = i.

    Dies bedeutet, dass B “dünnbesetzt” ist und nicht-null Einträge in Form des gespiegeltenBuchstabens Z hat: Z.

    • Im Fall X, also im Falle einer Matrix mit nicht-null Einträgen in Form des Buchstabens X,definieren wir B := X ·X .Für einen beliebigen Eintrag von B erhalten wir per Definition der Matrix-Matrix-Multiplikation,dass

    bij =n∑k=1

    xikxkj .

    Serie 10 Seite 20 Aufgabe 10.8

  • 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 “dünnbesetzt” ist und wieder nicht-null Einträge in Form des Buch-stabens X hat.

    • Wir betrachten den letzen Fall T, also den Fall einer Tridiagonalmatrix, und definierenB := T · T. Für 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 für 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 dafürist, 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 “dünnbesetzte” Fünfbandmatrix. Das bedeutet, dasses nur nicht-null Einträge auf der Hauptdiagonalen und den vier ersten Nebendiagonalenunter der Hauptdiagonalen gibt.

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

    y = multTridiagonal(x) ,

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

    (→ Tipp)Lösung:

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

    Serie 10 Seite 21 Aufgabe 10.8

  • 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 Schätzung von Punkten mittels Relativen Distanzen (MATLAB)

    Diese Aufgabe beschäftigt sich mit einer Anwendung der Kleinste-Quadrate-Lösung eines überbestimmtenlinearen Gleichungssystems (Abschnitt [LANM, Thm. 4.4] der Vorlesung) auf ein Schätzproblemaus dem Vermessungswesen.

    Sei m ∈ N gegeben. Für n gegebene Punkte auf einer geraden Strasse mit Positionen pi ∈ Rfür i ∈ {1, . . . ,m} mit p1 < p2 < . . . < pm sind folgende Abstände (möglicherweise ungenau)vermessen worden:

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

    Abbildung 10.3: Lage der Messpunkte und Definition der Abstände dij für 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 schätzen.

    ? 10.9a) Wie viele Gleichungen bzw. Werte für dij sind gegeben?

    (→ Tipp)

    Lösung: Es gibtÄm2

    äWerte für dij .

    ? 10.9b) Geben Sie die in Teilaufgabe 10.9a) beschriebenen Gleichungen an, d.h. formulierenSie das überbestimmte lineare Gleichungssystem Ax = b mit einer geeigneten Matrix A undRechte-Seite-Vektor b, das von den unbekannten Punktpositionen erfüllt würde, wenn diese feh-lerfrei gemessen worden wären.

    Serie 10 Seite 22 Aufgabe 10.9

  • Lösung: 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 überbestimmtes 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 für eine Kleinste-Quadrate-Lösung (siehe Definition [LANM, Thm. IV.4.2.B]). Schla-gen Sie eine Modifikation des Problems (P) vor, die eine eindeutige Kleinste-Quadrate-Lösungder modifizierten Problemstellung garantiert und geben Sie das zugehörige überbestimmte lineareGleichungssystem an.

    Tipp: Nicht rechnen! Überlegen Sie sich, welche Änderung in den Punktpositionen keine Aus-wirkung auf deren relative Entfernungen haben wird.

    Lösung: 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 für alle n ≥ i > j ≥ 1. Dies istäquivalent dazu, dass gilt pi = pj für alle i, j.

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

    Serie 10 Seite 23 Aufgabe 10.9

  • 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 Lösung haben wird, siehe [LANM, Thm. I.4.5.B]aus der Vorlesung.

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

    p̃i − p̃j = pi − p1 − pj + p1 = dij.

    Zusätzlich gilt per Definition p̃1 = 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 · · ·...

    ......

    ......

    ......

    0p̃2...p̃m

    =

    d21d31d32d41d42...

    äquivalent zu Ãx̃ = d, wobei wir

    Ã =

    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̃ :=

    p̃2p̃3...p̃m

    . Dieabgeänderte

    Äm2

    ä×(n−1) Matrix à hat trivialen Kern (Kern(Ã) = {0}), da wir für die Gleichung

    Ãx̃ = 0 nur die Lösung p̃2 = 0, p̃3 = 0, . . . erhalten. Somit ist à 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-Lösung.

    ? ? 10.9d) Stellen Sie die Normalengleichungen für den Fallm = 5 und das modifizierte überbestimmtelineare Gleichungssystem aus der vorherigen Teilaufgabe auf.

    (→ Tipp)

    Serie 10 Seite 24 Aufgabe 10.9

  • Lösung: Für n = 5 sieht die Matrix des modifizierten Systems wie folgt aus:

    Ã =

    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 überbestimmte Gleichungssystem gegeben durch

    Ãx̃ =

    d21d31d32d41d42d43d51d52d53d54

    .

    Wir berechnen nun die einzelnen Terme für die Normalengleichungen:

    Ã>Ã =

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

    und

    Ã>d =

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

    .Die Normalengleichungen lauten folglich Ã>Ãx̃ = Ã>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 Lösung des modifizierten Problems aus Teilaufgabe 10.9c) im Sinne derkleinsten Quadrate berechnet.

    (→ Tipp)

    Serie 10 Seite 25 Aufgabe 10.9

  • Lösung:

    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 überbestimmtes lineares Gleichungssystem zu führen, 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)

    “bestmöglichst” (im Sinne der kleinsten Quadrate) erfüllt.

    ? 10.10a)Welches überbestimmte nichtlineare Gleichungssystem ergibt sich zunächst aus (10.10.1)?

    Lösung: Wir erhalten das folgende überbestimmte nichtlineare Gleichungssystem

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

    ? ? ? 10.10b)In welches überbestimmte lineare Gleichungssystem lässt es sich transformieren?

    Serie 10 Seite 26 Aufgabe 10.10

  • Tipp: Verwenden Sie die Umkehrfunktion der Exponentialfunktion.

    (→ Tipp)

    Lösung: Wir definieren g(t) = log f(t). Diese Funktion g ist wohldefiniert, da gilt f(t) > 0, füralle 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, überbestimmte 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 gemäss Satz [LANM, Thm. IV.4.3.B] aus der Vor-lesung zu dem überbestimmten lineare Gleichungssystem aus der vorhergehenden Teilaufgabeauf.

    (→ Tipp)

    Lösung: 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-Lösung x =Çaβ

    åliefert uns dann durch α = ea und β die “bestmöglichste”

    Lösung 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-Schätzung von α und β zurückgibt.

    (→ Tipp)Lösung:

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

    Serie 10 Seite 27 Aufgabe 10.10

  • 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 für 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.

    Tipps für Aufgabe 10.3

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

    Serie 10 Seite 28 Aufgabe 10.10

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

  • können. Sie können diesen Code mit den Daten der Aufgabe laufen lassen und sich Zwi-schenresultate ausgeben lassen.

    10.3b) Der Gram-Schmidt- Orthonormalisierungsalgorithmus berechnet zunächst nur die orth-normalen Vektoren q1, . . . ,qk. Wie in der Vorlesung erklärt, erhält man die Einträge 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 Überlegungen aus der Vorlesung, die schliesslich in [LANM, Satz IV.3.4.F]mündeten.

    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 realisierenlässt. Damit können Sie die QR-Zerlegung der gegebenen Matrizen berechnen und Ihreauf Papier erhaltenen Ergebnisse kontrollieren.

    Tipps für Aufgabe 10.5

    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 geschätzt werden müssen. Sie sind also die Unbekannten des überbestimmtenlinearen Gleichungssystems, das demzufolge 5 Gleichungen und 2 Unbekannte umfasst.

    10.5c) Die Kleinste-Quadrate-Lösung erhält man natürlich durch Lösen der Normalengleichun-gen aus Satz [LANM, Thm. IV.4.3.B], einem linearen Gleichungssystem der Grösse 2×2. Sie können Ihr Resultat einfach mit MATLAB überprüfen, indem Sie das überbestimmtelineare Gleichungssystem mit \ lösen, siehe [LANM, Abschnitt 5.5].

    Tipps für Aufgabe 10.6

    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 für Spalte auf, in dem Sie den MATLAB-Matrixbaukasten verwenden (Komma-Operator zum Nebeneinanderstellen von Matri-zen).

    Tipps für Aufgabe 10.7

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

    Tipps für Aufgabe 10.8

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

    Serie 10 Seite 29 Aufgabe 10.10

  • 10.8e) Betrachten Sie zunächst die konkrete Matrix für n = 5 in Abbildung ?? und überlegenSie 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 können.

    Tipps für Aufgabe 10.9

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

    10.9d) In diesem Fall sind 10 Distanzen gegeben. Die Position des ersten Punkts kann willkürlichals p1 = 0 festgelegt werden, was uns mit 4 Unbekannten belässt.

    10.9e) Man muss sich natürlich ein klares Nummerierungsschema für die Zeilen der Matrix desüberbestimmten linearen Gleichungssystems überlegen. Diese Konvention ist beliebigaber man muss sie dann konsequent anwenden.

    Tipps für Aufgabe 10.10

    10.10b) Wie Sie in der Schule und auch in Analysis gelernt haben, ist der Logarithmus log dieUmkehrfunktion der Exponentialfunktion. Für ihn gilt die Rechenregel log(ξζ) = log ξ+log ζ für 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 überbestimmtes lineares Gleichungssystem transformierthaben, erledigt MATLABs Operator \ den Rest, wie Sie in [LANM, Abschnitt 5.5] ge-lernt haben. Vergessen Sie aber nicht, die Transformation rückgängig zu machen und dierichtigen Parameterwerte zurückzugeben.

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

    Fächern im Vorraum zum HG G 53. Die Serien müssen sauber und ordentlich geschriebenund zusammengeheftet abgegeben werden, sofern eine Korrektur gewünscht wird.

    Die Abgabe der Hausaufgaben wird nachdrücklich empfohlen!Bitte markieren Sie deutlich die Aufgaben, deren Korrektur Sie wünschen!

    Serie 10 Seite 30 Aufgabe 10.10

  • • Zentralpräsenz:

    – 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 Semesterpräsenzprofitieren wollen.

    • Homepage: Hier werden zusätzliche Informationen zur Vorlesung und die Serien und Mu-sterlösungen als PDF verfügbar sein.www.math.ethz.ch/education/bachelor/lectures/hs2014/other/linalgnum BAUG

    Veröffentlichung am 3. Dezember 2014.Abzugeben bis 10. Dezember 2014.

    Literatur

    [LANM] Vorlesungszusammenfassung für 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

    Serie1010.1 Orthogonale Komplemente10.2 Orthogonalprojektion auf eine Ebene in 3D10.3 QR-Zerlegung von Matrizen mithilfe des Gram-Schmidt Algorithmus10.4 Einfache Lineare Ausgleichsrechnung10.5 Kleinste-Quadrate-Fit einer Funktion10.6 Matrix aus MatrixVektor (Matlab)10.7 Effiziente Matrix-Vektor-Multiplikation (Matlab)10.8 Dünnbesetzte Matrizen in Matlab10.9 Schätzung von Punkten mittels Relativen Distanzen (Matlab)10.10 Auf Umwegen zum linearen Ausgleichsproblem (Matlab)