FSI Informatik/pruefungen/bachelor/algoks/loesungss14

Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » algoks » loesungss14

1a) n^2, n, n, n, n^2, n^2, h^3, h^2

1b)

||x_(i+1) - x*|| <= C ||x_i - x*||^p, C Konstante.

2a)

x = [1, 1, 2, 2]

2b)

w1 = a1 + alpha * e; e = einheitsvektor
a1 = erste Spaltenvektor von A
alpha = sgn |a11| * ||a1|| = -1 * sqrt(4)
——> w1 = [-1 1 -1 1 ] + [-2 0 0 0 ]

         w1 = [ -3 1 -1 1 ]

2c)

R =

_              _
| 2  0  -2   1 |
| 0  2  -1   0 |
| 0  0   1   2 |
| 0  0   0   1 |
|_            _|

L =

_             _
| 1  0   0  0 |
| 2  1   0  0 |
| -1  0   1  0| 
| 2 -2  -1  1 |
|_           _|

3a)

|||A|||1 = 70/25
|||A|||2 = 2
|||A||| inf = 72/25

3b)

Singulärwerte: 2,1
rang(A) = 2

3c)

img(A) = <1/5 * [3, 0, -4, 0]T, 1/5 * [0, -3, 0, -4]T>
kern(A) = <1/5 * [-1,-2,4,-2]^T, 1/5 * [-2,-4,-2,1]^T>

3d)

x = 1/25 * [0, 0, 10, 20]T = [0, 0, 2/5, 4/5]^T

Formel: https://fsi.informatik.uni-erlangen.de/dw/_media/pruefungen/bachelor/algoks/pseudoinv.png

3e)

Rang(A) < min[n,m] → damit löst x = A~1b das Problem mit minimalen Residuum ||Ax-b||2 = min und löst mit gleicher Norm ||x||2

4a)

Triangle::Triangle(const Point2D &a, const Point2D &b, const Point2D &c)
{
	A=a;
	B=b;
	C=c;
}

4b)

float Triangle::area() const
{
	return 0.5*(A.x * (B.y-C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y));
}

4c)

void Triangle::barycentric(const Point2D &P, float & alpha, float &beta, float &gamma) const
{
	Triangle t1(A,B,P), t2(A,P,C), t3(P,B,C);
	alpha = t3.area()/area();
	beta = t2.area()/area();
	gamma = t1.area()/area();
}

4d)

bool Triangle::inside(const Point2D &P) const
{
	float alpha,beta,gamma;
	barycentric(P, alpha, beta, gamma);
 
        // >1 muss nicht beachtet werden, weil
        // alpha+beta+gamma=1
        // z.B alpha > 1 <-> mindest. eins von den anderen beiden < 0
	if(alpha < 0 || beta < 0 || gamma <0)
		return false;
 
	return true;
}

5a)

Baryzentrische Koordinaten: [2/6, 1/2,1/6]T

5b)

Zuerst die Rechtecke interpolieren:
fR = 12
fS = 56
fT = 48

Dann über baryzentrische Koordinaten im Dreieck interpolieren (Gleichungssystem aufstellen, und die letzte Koordinate „wegschmeißen“):
Lösung des Gleichungssystems:
Baryzentrische Koordinaten: [2/6, 1/2,1/6]T

Interpolation:
24/6 + 56/2 + 48/6 = 40

Anderer Vorschlag: baryzentrische Koordinaten der Dreieecke bereits in a) berechnet (1/3, 1/2, 1/6)

f_RST0 = 1/3 * 12 + 1/2 * 48 + 1/6 * 36 = 34
f_RST1 = 1/3 * 12 + 1/2 * 72 + 1/6 * 72 = 52
⇒ f_P = 1/3 * 52 + 2/3 * 34 = 40 (lineare Interpolation der Dreieckstemperaturen)

6a)

Das Jacobi-Verfahren konvergiert, weil die Matrix A strikt diagonaldominant ist.

6b)

x1 = [2, -1, 1]T
x2 = [5/3, - 9/4, 2]T

6c)

[2, -2, 7/3]T

6d)

Die entstehende Matrix wüde so aussehen (beispielhaft eine 4×4 Matrix):

Bn =

_                    _
| 1/2  1/4   0     0 |
| 1/4  1/2 1/4    0  |
|  0    1/4 1/2  1/4 |
|  0     0   1/4  1/2|
|_                  _|

Das Verfahren konvergiert, weil die Matrix schwach diagonaldominant und unzerlegbar ist.

6e)

Die Tridiagonalmatrix ist in O(n) mit dem Gaus-Verfahren direkt lösbar. Daher wäre es wohl besser keine Näherung zu benutzen.

7a)

- Nein, da uTAv nicht 0
- Ja, da uTAv = 0

7b)

Quelle1 (Wikipedia): Daraus folgt, dass das CG-Verfahren ein System zu einer Matrix mit nur k verschiedenen Eigenwerten in k Schritten löst.

Quelle2 (http://www.matheboard.de/archive/486945/thread.html): Das CG Verfahren liefert eine exakte Lösung nach maximal n Schritten, wenn du eine nxn Matrix betrachtest.

–> Es braucht 3 Schritte

7c)

[x1,y1] = ~~[-1/2, 3/2]^T~~ ~~[-3/2, 3/2]^T~~

grad(F) = [ 4x - 2xy^2 + 1, 2y - 2yx^2 - 1 ]^T
s0 = -grad(F)(x0, y0) = - [-1, -1]^T = [1, 1]^T
[x1, y1]^T = x0 + t * s0 = [-1, 1]^T + 0,5 [1, 1]^T = [-1/2, 3/2]^T

7d)

ə_x=4x-4xy^2+1
ə_y=2y-2yx^2-1

grad(f)(0,0)^T = (1, -1)T\\
        
        |4-4y^2   -4xy|          |4  0|
H_f=  |-4xy      2-2x^2|  -->   |0  2|

                                                |2  0|
->  H_f^(-1)((x_0,y_0)^T)= 1/(4*2) *  |0  4| 
-> (x_0,y_0)^T+(-H_f^(-1))*grad(f)(0,0)
-> [x1, y1] = [-1/4, 1/2]^T

8a)

float CoonsPatch::evaluateBilinear(float s, float t) const
{
	return (1-s) * ((1-t)*m_t0.f(0) + t*m_t0.f(1)) + s* ((1-t) * m_t1.f(0) + t * m_t1.f(1));
}

8b)

float CoonsPatch::evaluateAt(float s, float t) const
{
	float fst = evaluateBilinear(s, t);
	float fs = m_s0.f(s)*(1-t) + t * m_s1.f(s);
	float ft = m_t0.f(t)*(1-s) + s * m_t1.f(t);
	return fs+ft-fst;
}

8c)

float CoonsPatch::evaluateDerivativeT(float s, float t) const
{
	float fst = (1-s) * (-1*m_t0.f(0) + 1*m_t0.f(1)) + s* (-1 * m_t1.f(0) + 1 * m_t1.f(1));
	float fs = m_s0.f(s)*(-1) + m_s1.f(s);
	float ft = m_t0.d(t)*(1-s) + s * m_t1.d(t);
	return fs+ft-fst;
}

9.1a)

Rechte Grafik: Die Geraden liegen orthogonal zueinander. Das Problem ist also gut konditioniert, weil sich kleine Änderungen in den Eingabedaten nicht stark auf die Lösung auswirken

Linke Grafik: Die Geraden sind annähernd parallel. Das Problem ist also schlecht konditioniert, weil kleine Änderungen in den Eingabedaten große Änderungen in der Lösung zur Folge haben

9.1b)

Linke Grafik: Schlecht konditioniert, weil man hier sehr viele y-Werte um einen ähnlichen x-Wert hat.

Rechte Grafik: Hier sind die Unterschiede der y-Werte im Vergleich zu den Unterschieden in den x-Werten nicht so dramatisch. –> gut konditioniert

9.2a)

Linke Kurve:
- Liegt nicht in der konvexen Hülle
- Es liegt keine beschränkte Schwankung vor(Eine Gerade schneidet eine Bézierkurve höchstens so oft, wie sie ihr Kontrollpolygon schneidet (die Kurve ist variationsreduzierend, bzw. hat eine beschränkte Schwankung).)
- Kein tangentialer Schmusekurs am rechten Punkt

Rechte Kurve:
- Tangente des Start-/Endpunktes verläuft nicht entlang der Strecke P0P1 bzw. P2P3

9.2b)

10.1a)

1. Separierbar: [1, 2, 1]T * [1, 2, 1] * 1/16

2. Nicht separierbar

3. Nicht Separierbar

4. Nicht separierbar

10.1b)

N² * (M² Additionen + M² Multiplikationen) = 2 * N²M²

10.1c)

2 * (N * N * (M + M)) = 4 * N²M

10.2)

Angabe der Lösung zerlegt in Strecken, wobei P1 (x,y) immer den Startpunkt meint und P2 (x,y) den Endpunkt einer Strecke.
P1 = (0,0) und P2 = (1,0) würde also die Strecke auf der x-Achse meinen von x = 0 bis x = 1

Lösung:
Mit Maple: http://imgur.com/VEw9d2R Strecke1: P1 = (-1.5, 0) bis P2 = (-1/2, 1/2), leicht nach oben gebogen
Strecke2: P1 = (-1/2, 1/2) bis P2 = (1/2, 0), leicht nach unten gebogen

Alternative Lösung: (-1.5, 0), (-1, 0.375), (-0.5, 0.5), (0, 0.125), (0.5, 0)

Beachte: Es ist keine lineare Interpolation dieser Punkte. Da h2 linear ist, muss das Integral 'intuitiv' quadratisch in x sein. Wenn wir bei x=-1,5 sind und uns nach rechts bewegen, fügen wir erst einen großen Schlitz des Dreicks hinzu, dann einen kleineren, dann noch einen kleineren, quasi 5 + 4 + 3 + 2 + 1, was bekanntlich O(n^2) ist.

Plot: http://imgur.com/a/Mk1GB

10.3)

1. Fall: keine Überlappung
x < -1
Yi(x) = 0
2. Fall: teilweise Überlappung (einlaufend)
-1 ⇐ x < 1
Yii(x) = (3/4)x + (3/4)
3. Fall: vollständige Überlappung
1 ⇐ x <3
Yiii(x) = (3/2)
4. Fall: teilweise Überlappung (auslaufend)
3⇐ x <5
Yiv(x) = (15/4) - (3/4)x
5. Fall: keine Überlappung
5 < x
Yv(x) =0

Alternative Lösung:
1. Fall: keine Überlappung
x < -1
(h3*h4)(x) = 0
2. Fall: teilweise Überlappung (einlaufend)
-1 ⇐ x < 1
(h3*h4)(x) = (3/4)x - (3/2)
3. Fall: vollständige Überlappung
1 ⇐ x <3
(h3*h4)(x) = (3/2)
4. Fall: teilweise Überlappung (auslaufend)
3⇐ x <5
(h3*h4)(x) = -(3/4)x + (9/2)
5. Fall: keine Überlappung
5 < x
(h3*h4)(x) = 0