**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 4x4 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