LÖSUNGSVERSUCH Klausur 5. August 2011

Bachelor Algorithmik kontinuierlicher Systeme
21

deCasteljau…da werden diese nämlich weggelassen^^

22

Jain.
DeCasteljau ist erstmal ein Auswertungsschema. Das kannst du für (Midpoint-)Subdivision ja auch verwenden (siehe z.B. mediadons Post).

Du meinst mit deCasteljau die Auswertung einer Bezier-Kurve an einer bestimmten Stelle. Bei Subdivision geht es ja darum, die gesamte Kurve (beliebig genau) durch Liniensegmente zu approximieren. Und dann ist es klar, dass man die übrigen Punkte angeben muss.

23

die aussage "Midpoint subdivision = Casteljau mit t=1/2 " trifft nur teilweise zu.
bzw die punkte, die mediadon bestimmt hat sind eigentlich nicht richtig.

du sollst hier lediglich EINE iteration ( <-> DeCasteljau) machen, welche dir 3 weitere punkte liefert:
(0 16)T, (32 0)T und (48 16)T.

Nun sollst du 4 kontollpunkte angeben die die linke und rechte teilkurve ausmachen.
diese wären für die linke Teilkurve:

c0 = (0 32)T
c1 = (0 24)T ← dies ist der punkt der die erste gerade halbiert. und das ist eben der unterschied!
c2 = (32 0)T
c3 = (48 16)T

für d0/etc analog^^

24

Naja, man kann aus der deCasteljau-Pyramide die Punkte des Polygons, das durch Subdivision entsteht, ablesen. Das sind genau die Punkte am Rand der Pyramide. Das meinte ich mit “Subdivison = deCasteljau”.
Ich denke, wir meinen beide das gleiche, haben lediglich aneinander vorbeigeredet.

25

Fehlerordnung bei Integration mittels iterierter Trapezregel / Simpsonregel:

Hier hätt ich fast Mist gebaut, denn ohne „iteriert“ wäre es O(h[sup]3[/sup]) / O(h[sup]5[/sup]) (vgl. Skript S. 99, falls ich das richtig interpretiere). Also in der Klausur genau lesen…

26

Btw. hatten wir eine Fehlerordnung zur Romberg-Quadratur?

27

6 c)

Matrix NewtonCurve::getCoefficientMatrix() const { vector<Point2D> &cp = getControlPoints(); int n = cp.size(); Matrix m (n, n); m.setZero(); for (int i=0; i<n; i++) m(i,0) = 1; for (int i=1; i<n; i++) { for (int j=1; j<=i; j++) { m(i,j) = m(i,j-1) * (cp[i] - cp[j - 1]); } } return m; }

Ist das das Geforderte?

Also ein Eintrag m(i,j) entspricht Π[sub]k=0[/sub][sup]j-1[/sup] (x[sub]i[/sub] - x[sub]k[/sub]) (Π = Produkt)
(bzw. bei j=0, also leerem Produkt m(i,0)=1)
Unter Berücksichtigung, dass die Einträge im oberen Dreieck zwangsweise 0 werden.

Eine Zeile stellt also p(x[sub]i[/sub]) in Newton-Basis dar, mit den Koeffizienten als Unbekannten.

Also wenn man das LGS
m * coeff = (y[sub]0[/sub], y[sub]1[/sub], …, y[sub]n-1[/sub])[sup]T[/sup]
nach coeff = (a[sub]0[/sub], a[sub]1[/sub], …, a[sub]n-1[/sub])[sup]T[/sup] auflösen würde, hätte man den Parameter coeff für die d)…

28

Eine Iteration ist das komplette Dreieck, nicht 4->3->fertig sondern 4->3->2->1-> fertig!!! die 2. Iteration ware die Datenpunkte c0-c3 und d0-d3 zu nehmen und mit denen das Dreieck aufzubauen!!!

29

Das Ergebnis für 5a) scheint mir nicht korrekt.

Komme da auf
1/5 * | 10 18 |
| 18 16 |

Attachment:
2011_5a.png: https://fsi.cs.fau.de/unb-attachments/post_103918/2011_5a.png

30

In deiner Rechnung: die erste -9 muss +9 sein, von daher müsste dann
1/5 * |28 18|
|18 10|
rauskommen, also doch

31

Du hast einen Vorzeichenfehler gemacht. Gleich das erste Element der ersten Zeile.
(-3)*(-3) ergibt +9. Du hast -9 raus. Dann müsste auch wieder das selbe rauskommen.

32

Die Zerlegung am Schluss stimmt aber nicht ganz… wenn man die Vektoren normiert, dann schon.

33

In NichtlineareOptimierung.pdf, S. 28 steht u[sup]T[/sup] A v = 0, das trifft auf deine beiden Vektoren nicht zu.

Ich denke man könnte z.B. u = (1 0)[sup]T[/sup] und v = 1/sqrt(2) * (1 1)[sup]T[/sup] wählen.

34

Wie funktioniert denn die 8b) ?

Q(x) = x^T * A * x +2bx + gamma
Q(x) = (1/2)x^T * A * x + b*x + gamma/2

mein gedanke:

  1. Suchrichtung bestimmen: s0 = (grad(Q(x)) = Ax - b = (-1 2)^T

  2. daraus ti berechnen: Formel t_i = - ((Ax +b) * s0) / (s0^TAs0) = 1/13

  3. x_i+1 = x_i + t_i*si
    =>
    1 -1 12/13
    1 + 1/13 * 2 = 15/13

bei der c)
x1 = x0 -Hf(x0)^-1 * grad (F(x0))

Hf => Hf^-1
0 1 0 1
1 0 1 0

x1 = (0 0) - Hf^-1 * (-3 0)^T = (0 +3)^T

35

Hmmm bin der Meinung, das sollte
Ax + b geben oder? allerdings kommt dann fuer grad(Q(xo)) (1,1)T raus
Suchrichtung dachte ich immer -grad(Q(xo)) also (-1,-1)T

dann komm ich aber als Ergebnis auf x1=(-1,-1)T :frowning:

36

Kann mir jemand erklären, wie man auf die Werte bei Schritt 3 kommt?
Mir ist nicht klar, was gerechnet wurde.

R:
index:     0    1
xi/zi     -1    2
yi/fRi    12   12
37

einfach die Formel zur linearen interpolation … zb. für das erste Wertepaar hast du
L = 12 + (x- (-1)) * (12-12)/(2-(-1)) = 12 +(x+1) * 0/3 = 12

das entspricht ca. L = Y_i + (X - X_i) * (Y_{i+1} - Y_i)/(X_{i+1} - x_i)

38

Also meine Lösung zur 9 d) sieht folgendermaßen aus:

Funktionswert an einer bestimmten Stelle zwischen zwei zusammengehörigen Eckpunkten bestimmt sich, indem man die Funktionswerte der einzelnen Eckpunkte je nachdem, wie der Punkt die Strecke teilt, entsprechend gewichtet:
f’ = (x₃¹ - x’)/(x₃¹ - x₃⁰) f₀ + (1-(x₃¹ - x’)/(x₃¹ - x₃⁰)) * f₁

Wobei x₃ eben die dritte Koordinate meint. Das ¹ meint die Koordinate des ersten Punkts(R₁,S₁,T₁), ⁰ analog den anderen Punkt.

Da die x₃ Koordinaten für alle Punkte gleich sind ergibt sich:
f’ = 2/3 * f₀ + 1/3 * f₁

Für R’: 2/3 * 12 + 1/3 * 12 = 12
Für S’: 2/3 * 48 + 1/3 * 72 = 56
Für T’: 2/3 * 36 + 1/3 * 72 = 48

Nun spannen R’, S’, T’ ein Dreieck auf und man kann auf baryzentrische Koordinaten zurückgreifen. x₃ ist dabei 0 und wird einfach ignoriert.
Man muss also ρ, σ und t für den Punkt (2 1)^T bestimmten. Wer Aufgabe c noch im Kopf hat, weiß, dass dies dort schon geschehen ist, mit dem Ergebnis:
ρ = 1/3, σ = 1/2, t=1/6

Also bestimmt sich f_p = 1/3 * 12 + 1/2 * 56 + 1/6 * 48 = 40

39

Danke für die Erklärung, so ergibt es Sinn :slight_smile:

40

kann mir vielleicht jemand erklären, wie man auf die Lösung von der 8c) kommt?
bei 8b) hab ich auch für x_1 = (0 1)^T raus.
danke!