Klausur Februar 2012

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Klausur Februar 2012
Wie macht man das bei Aufgabe 4a) bei dem 2.Punkt mit den 3 Koordinaten. Wie interpoliert man in z-Richtung? Weil nach Formel wäre es streng genommen ja z_M - z_0/ z_1 - z_0 und dann würde im Nenner ne Null stehen → nicht so gut. Nehme ich das Gewicht, dass ich so wie beim 1.Punkt berechne einfach mal die z-Koordinate, also 5? wäre dann ja das gegenüberliegende Volumen für jeden Punkt oder?


Falls du den Punkt M = [3, 2.5] meinst, dann ist das auch nur ein Punkt mit zwei Koordinaten! Nämlich x = 3 und y = 2.5! Also nicht x = 3, y = 2 und z = 5! Oder habe ich deine Frage falsch verstanden?


genau, den meinte ich. Also die z Komponente spielt wirklich keine Rolle?


Ne spielt keine Rolle weil sich s ja eh nur im 2 dimensionalen abspielt! Also gibts da gar keine z-Komponente!

Aufgabe 8 Nichtlineare Optimierung
Zur Aufgabe 8 Nichtlineare Optimierung:

Ich bin mir grade nicht sicher ob ich auf dem richtigen Weg bei der Aufgabe bin, mein Lösungsansatz ist der Folgende.

Gradientenverfahren ist ja das Newton-Verfahren, d.h. Iterationsvorschrift ist
[color=limegreen] x_i+1 = x_i - Inverse(hesse) * grad(Q)(x_i) [/color]

Um den Gradienten zu bilden hab ich die Funktion Q erstmal “ausmultipliziert”, dann abgeleitet, daraus dann die Hessematrix bestimmt, daraus wiederum die Inverse Hesse.
Danach hab ich alles samt x_0 in obige Vorschrift eingesetzt, das Ganze 2mal, weil man 2 Iter-Schritte machen sollte.
Raus kam nach dem ersten Schritt (-1;-3)^T und nach dem Zweiten (1;1)^T

Meine Frage: Wo bringt man dabei die Suchrichtung sowie die optimale Schrittweite (wie in der Aufgabenstellung genannt) unter?
Und wie lautet die Suchrichtung s, bzw. wie kommt man auf diese?


Mein Ansatz war schon falsch merke ich grade.
Das Gradientenverfahren hat eine ganz andere Vorschrift nämlich
[color=limegreen] x_i+1 = x_i + s_i * t_i [/color]

Jetzt leuchtet mir auch die gegebene Formel für t_i ein.
Und s_i bestimmt wohl einfach indem man grad(Q)(x_i) ausrechnet.

Hat sich also geklärt.


Wie geht denn die 4a)

z.B. bei Punkt Q
für w_00 = [4-(x-1)]/4 + [3-(y-1)]/3

Stimmt das? Meine Idee dazu:
x-1 bzw. y-1 da es verschoben ist,
Dividiert durch 4 bzw. 3 da es nicht auf 1 Normiert ist,
Und dann x und y Komponente addiert…

Wenn ich dann aber die Werte [2,2] einsetze kommt 17/12 raus → Also etwas >1; Das scheint mir falsch zu sein…

EDIT:
Hab meinen Fehler… Mann muss ganz normal bilinear Interpolieren, und nicht die x und y Komponenten zusammenfassen. Eigentlich kar, aber da hab ich wohl gestern Nacht nicht mehr klar denken können :slight_smile:
Meine Überlegungen zur Normierung und Verschiebung scheinen richtig zu sein!

f1(x) = [4-(x-1)]/4 * P01 + [x-1]/4 * P10
f2(x) = [4-(x-1)]/4 * P01 + [x-1]/4 * P11
f3(x,y) = [3-(y-1)]/3 * f1(x) + [y-1]/3 * f2(x)

w00 = [3-(y-1)]/3 * [4-(x-y)]/4 = 1/2
w10 = [3-(y-1)]/3 * [x-1]/4 = 1/6
w01 = [y-1]/3 * [4-(x-1)]/4 = 1/4
w11 = [y-1]/3 * [x-1]/4 = 1/12

w00 + w10 + w01 +w11 = 1; Also scheint’s nun zu passen!


Ich stell mal meinen Loesungsvorschlag hier rein.
Ueber Verbesserungsvorschlaege und Bestaetigungen waere ich sehr dankbar.

O(n)
O(n^2)
O(n^3)
O(n^2)
O(n)
O(n)
O(n^2)
O(n)

a)
val = (3, 1, 5, 6, -2, -1)
col_ind = (1, 3, 1, 3, 1, 2)
row_ptr = (0, 0, 2, 2, 4, 6)

b)
Ich bin mir nicht wirklich sicher, ob ich die Frage vestanden habe:
m: Laenge des row_ptr Array’s - 1
n: Ist mindestens um 1 groesser, als der groesste Wert im col_ins Array

c)
|0 0 0 0 0|
|0 4 0 -2 0|
|0 0 3 8 0|
|0 0 7 0 4|

  1. Ausgelassen, da dieses Semester nicht klausurrelevant

a)
Fuer Q
w_00 = 1/2
w_10 = 1/6
w_11 = 1/12
w_01 = 1/4

Fuer M
w_00 = w_10 = w_11 = w_01 = 1/4

b) Eigentlich analog zur Hausaufgabe, aber ich hab das ganze nochmal allgemein aufgeschrieben:
F_s(s,t) = (1-t)C_s(s) + tC_n(s)
F_t(s,t) = (1-s)C_w(t) + sC_o(t)
F_s,t(s,t) = (1-s)(1-t)P_sw + s(1-t)P_so + stP_no + (1-s)tP_nw

Coonspatch F(s,t) = F_s(s,t) + F_t(s,t) - F_s,t(s,t)

s = t = 0,5
=> Gewichte der Kurvenmittelpunkte sind 1/2, Gewichte der Eckpunkte sind -1/4

a)
Singulaewerte: 1, 1/2, 1/3
Rang: r = 3
Bild: span{(0,-1,0)^T, (-1, 0, 0)^T, (0, 0, 1)^T}
Kern: span{(-1/2, 1/2, -1/2, 1/2)^T}
Konditionszahl: 1/(1/3) = 3

b)
U^T * (1, 0, -2)^T = (0, -1, -2)^T
S^~1 * (0, -1, -2)^T = (0, -2, -6, 0)^T
V * (0, -2, -6, 0)^T = (2, -4, -4, 2)^T

c)
|0 0 0 0|
|-1/2 -1/2 1/2 1/2|
|0 0 0 0|

6, 7 ausgelassen

a)
s_1 = grad(1, 1)^T = A(1, 1)^T + (-1, 1)^T = (0, 1)^T
t_1 = …einfach einsetzen = -1
x_1 = x_0 - (0, 1)^T = (1, 0)^T

s_2 = (1, 0)^T
t_2 = -1/2
x_2 = (1/2, 0)^T

b)
(1, 1) A x = 0
bsp x = (0, 1)^T

c)
Konvergenzordung:
Potenzordnung p mit der der Fehler kleiner wird:
|x* - x_i+1| <= C * |x* - x_i|^p
0 < C < 1

lineare Konvergenz:
wie oben mit p = 1

quadratische Konvergenz:
wie oben mit p = 2

a)
1 <= x < 3 : 1 - x
3 <= x < 5 : (5 - x)*(-1) + (x - 3)
5 <= x < 7 : (7 - x) - (x - 5)

b)
Interpolation geht genau durch die Punkte
Approximation: Bsp durch lineare Approximation erhaelt man eine Gerade mit minimalem Residuum, kann nuetzlich sein, um Messfehler herauszufiltern

c)
Polynomgrad 5 => 6 Punkte noetig

d)
Das wurden jetzt mal wirklich verdammt haessliche Werte. Ich tipp jetzt nicht die Pyramide ab. Wie das geht sollte jeder wissen, wenn ich mich verrechnet hab, naja, das waer dann auch nur ein Punkt abzug. Mein Ergebnis ist jedenfalls:
0*1 + 2/pi * (x - 0) + 8/(-3pi^2) * (x - 0)(x - pi/2) + 8/(3pi^3) * (x - 0)(x - pi/2) (x - 3pi/2)

a)
Hier nur der Endpunkt:
(55/2, 44)^T

c)
sum steht hier fuer das Summenzeichen mit i von 0 bis n. Die affine Abbildung nenne ich der Einfachheit jetzt f. B steht fuer ein Bernsteinpolynom, unten i, oben n und an der Stelle u

sum(f(b_i) * B) =
sum((A * b_i + t) * B) =
sum(A * b_i * B) + sum(t * B) =
Alle Bernsteinpolynome aufsummiert an der Stelle u ergeben 1 =
sum(A * b_i * B) + t =
A*sum(b_i * B) + t =
A * C(n) + t =
f(C(u))

d)
Endpunkt Interpolation, Tangentialeigenschaft, konvexe Huelle


CCS, nicht CRS
einfach transponieren dann stimmts :smiley:


Bei der 8 a) hab ich etwas anderes raus:
[m]
grad(Q) = ( 4x + y^2 )
(2x^2 -4x +4 +2y)

grad(Q(x_0)) = (5,4)^T

s = (-5,-4)^T
t = 2/13

x_1 = (3/13, 5/13)^T
[/m]

kann das jemand bestätigen oder wiederlegen?


Da komme ich auf (55/2 , 44).

Mein Baum sieht so aus(angabe ausgenommen):

(44,88) , (22,66) , (22,22) , (44,0)
(33,77) , (22,44) , (33,11)
(55/2,121/2),(55/2,55/2)
(55/2,44)

1 „Gefällt mir“

Zu Aufgabe 5c):

Setze ich bei der Rang 1 Approximation nur die Singulärwerte gleich 0, oder auch die zugehörigen Spalten/ Zeilen von U und V^T?


Hab noch ne dritte Lösung im Angebot und geb gleich mal die ausformulierten Formeln, mit denen ich gerechnet hab, mit an, falls ich mich da irgendwo vertan hab:

[m]
Q(vec(x)) = 2x^2 +y^2 - 2xy + 2y - 2x + 2

grad(Q) = ( 4x - 2y - 2 )
( 2y - 2x + 2)

t(s_i) = 2x * s_x - y * s_x - s_x + x * s_y - y * s_y + s_y
- ---------------------------------------------------
2 (s_x)^2 + (s_y)^2 - 2 s_x s_y

[color=blue]grad(Q(x_0)) = (0,2)^T
s_0 = (0,-2)^T
t_0 = 1/2[/color]

x_1 = x_0 + t_0 * s_0 = (1, 2)^T

[color=blue]grad(Q(x_1)) = (-2,4)^T
s_1 = (2,-4)^T
t_1 = - 1/4[/color]

x_2 = x_1 + t_1 * s_1 = (1/2, 1)^T
[/m]


In der Übung haben wir das so gemacht:
Rang-1 Approximation = (größter Singulärwert) * (1. Spalte U) * (1. Zeile V^T)

5b)

Bei mir in der Angabe steht statt (1,-1,-2)^T der Vektor (1,0,-2)^T, womit ich auf (-4,2,2,-4)^T komme.


für Q(x,y) hab ich das gleiche raus, wie du. Als Gradient hab ich (dQ/dx, dQ/dy)^T im Kopf, von daher würde ich sagen, deine Lösung ist falsch…


Ich habe hier:
| 0 0 0 0 |
| -1/2 -1/2 1/2 1/2 |
| 0 0 0 0 |

kann das jemand bestätigen?

5c)

Meine sieht mit

| -3 -3 -3 -3 |
| (-31/6) (-31/6) (31/6) (31/6) |
| -2 2 2 -2 |

nicht hübscher aus.

Sind wir beide uns darin einig, dass wir mit SIGMA eine Matrix haben, die nur ganz links oben eine 1 und sonst Nullen stehen hat?


Danke hab ich uebersehen. Du hast natuerlich recht.

Du hast recht, ich hab im letzten Schritt in der letzten Komponente vergessen durch 2 zu teilen

Also du hast quasi aus der Matrix heraus die Funktion wieder bestimmt, oder?
Wenn ich das mache kriege ich:
2x^2 - 2xy + y^2 - 2x + 2y + 2

Als Gradient:
4x - 2y - 2
-2x + 2y + 2

An der Stelle (1, 1)^T ergibt bei mir (0, 2) als Suchrichtung
Eingesetzt in die Schrittweiten Gleichung bekomme ich -3/2
[color=limegreen]EDIT:
Schon wieder ein Rechenfehler, ich krieg hier wieder genau -1/2 raus.
Damit sollten beide Loesungswege aequivaltet sein und es ist egal, ob man sich die mords Arbeit macht, die Funktions aus der Matrix abzulesen, abzuleiten, oder ob man grad = Ax + b schreiben[/color]
[color=crimson]
EDIT:
Ich seh grad, t_0 war -1 und nicht -1/2…
Scheint also doch nicht das gleiche zu sein :confused:
[/color]
[color=orange]
EDIT:
Ich Idiot… es kommt das gleiche Raus, da der Gradient hier (0, 2) statt (0, 1) ist
Somit erhaelt man bei beiden Verfahren das gleiche Ergebnis.
Ich empfehle die Methode, die ich im ersten Post Verwendet habe mit grad(x) = Ax + b, da man sich hier Rechnerei in der Schrittweitenbestimmung spart:
t = - (s^T * s) / (s^T A s)
[/color]
Dann eingesetzt in die Iterationsformel
(1, 1)^T - 3/2 * (0, 2)^T = (1, -2)^T

Hm, ich hatte eigentlich gedacht, dass ich bei quadratischen Funktionalen als Gradient einfach Ax + b nehmen kann. Aber leider kommen hier zwei verschiedene Sachen raus.
Dein Gradient stimmt aber meiner Meinung nach nich. Du hast glaube ich vergessen das „b“ mit in die funktion aufzunehmen.