====== Lösungsvorschlag ======

==== Aufgabe 1 (Theoriefragen) ====
**a)**\\
  * O(n^2)
  * O(n^3)
  * O(n)
  * p=1
  * O(h^2)
  * n+1
  * 1
  * 3

**b)**\\
  | 1 | 1.25 | 1.5 | 1.75 | 2 | 2.5 | 3 | 3.5 | 4 | 5 | 6 | 7 | 8 |

==== Aufgabe 2 (Lineare Gleichungssysteme) ====
**2.1 a)**\\
      |  1  0  0 0 |         | 2 -1 1  0 |
      | -2  1  0 0 |         | 0  2 0  2 |
  L = |  2 -1  1 0 |     R = | 0  0 1 -2 |
      |  0  0 -2 1 |         | 0  0 0  2 |
      
 **2.1 b)**\\
      |  2 |   | sqrt(36) |   | -4 |
      | -4 |   |    0     |   | -4 |
  L = |  4 | - |    0     | = |  4 |
      |  0 |   |    0     |   |  0 |
      
**2.2 c)**\\
  * Doppelte Gitterweite => 4-fache Anzahl Iterationen
  * Doppelte Fehlertoleranz => linear mehr Iterationen

   154 |  207 |  260
   620 |  830 | 1040
  2480 | 3320 | 4160
  
**2.2 d)**\\
  * Gauss-Seidel benoetigt halb so viele Iterationen wie Jacobi

    77 |  103 |  130
   310 |  415 |  520
  1240 | 1660 | 2080
  
 **2.2 e)**\\
  * Gauss-Seidel benoetigt Wurzel-n-mal so viele Iterationen wie Jacobi

  13 | 18 | 23
  25 | 35 | 45
  50 | 70 | 90
       
==== Aufgabe 3 (Programmierung: LR-Zerlegung) ====

==== Aufgabe 4 (Speicherung duennbesetzter Matrizen) ====
**a)**\\
  val = [5, 1, 3, -6, -2, -1]
  col_ind = [2, 4, 2, 4, 1, 3]
  row_ptr = [1, 1, 3, 3, 5, 7]

**b)**\\
Im CRS-Format sind gegeben: val, col_ind, row_ptr
Von Null verschiedene
  * Zeilen: Anzahl versch. Elemente in row_ptr - 1. Alternativ: for i in range(0, len(row_ptr)-1): if (row_ptr[i] != row_ptr[i+1]) row_count++;
  * Spalten: Anzahl versch. Elemente in col_ind
  * Elemente: letztes Element row_ptr - 1. Alternativ: len(val) = len(col_ind)

**c)**\\
  bB_1 = 0 (kein Wert in 1. Spalte)
  bB_2 = 4*b_2 = 4
  bB_3 = 3*b_3 + 7*b_4 = 7
  bB_4 = (-2)*b_2 + 8*b_3 = -2
  
  => bB = (0, 4, 7, -2)

==== Aufgabe 5 (Polynominterpolation) ====
**a)**\\
          | -1   fuer x in [-1, 0)
   l(x) = {  2   fuer x in [0, 1.5)
          |  4   fuer x in [1.5, 2]
          
**b)**\\
          | 3x/2 + 1/2   fuer x in [-1, 1)
   l(x) = { 2x           fuer x in [1, 2]

**c)**\\
l_0 = [(x-1)(x-2)/(-1-1)(-1-2)] = 1/6 * (x^2 -3x +2)\\
l_1 = [(x+1)(x-2)/(1+1)(1-2)] = -1/2 * (x^2 -x -2)\\
l_2 = [(x+1)(x-1)/(2+1)(2-1)] = 1/3 * (x^2 - 1)

Ich glaube nicht, dass das Ausmultiplizieren gefordert war. Dies wird in neueren Klausuren auch explizit angemerkt.

**d)**\\
-1, 2 und 4 (das sind genau die y_i)

**e)**\\
n_0 = 1\\
n_1 = (x+1)\\
n_2 = (x+1)(x-1)

**f)**\\
z. B. Aitken-Neville:
  |x_i  y_i
  |
  |-1   -1   
  |          \  3/2
  | 1    2   /         \ 1/6
  |          \   2     /
  | 2    4   /
  
=> p(x) = -1 + 3/2*(x+1) + 1/6*(x+1)(x-1)

==== Aufgabe 6 (Bezier-Kurven) ====
**a)**
  | 8|
  |16| \ | 6|
  | 0| / |14| \ | 5| 
  | 8| \ | 2| / |12| \ | 5|
  | 8| / | 6| \ | 5| / |11|
  | 0| \ |14| / | 8|
  |32| / |14|
  |56|
  
 **b)**\\
Affine Transformation \Phi(x, y) = (y, x)^T + (-2, 0)^T.

b_0 = (14, 8)^T
b_1 = (6, 0)^T
b_2 = (-2, 8)^T
b_3 = (54, 32)^T

**c)**\\

Sehr ungenau, aber man sieht das Konzept: https://i.imgur.com/IPK64lC.png

**d)**\\
  * liegt nicht in der konvexen Huelle der Kontrollpunkte
  * nicht tangential in den Endpunkten
  * nicht variationsreduzierend

**e)**\\

Man skizziere sich drei Punkte und führe den De-Casteljau-Algorithmus aus.
Zuerst interpoliert man d_0 und d_1: 1/2 (d_0 + d_1)\\
Dann d_1 und d_2: 1/2 (d_1 + d_2)\\
Nun interpoliert man diese beiden Punkte und gelangt zu:\\
1/2 (1/2 (d_0 + d_1)) + 1/2 (1/2 (d_1 + d_2)) = 1/4 d_0 + 1/2 d_1 + 1/4 d_2

==== Aufgabe 7 (Programmierung: Bilineare Interpolation) ====
<code>
def getInterpolatedPixel(img, u, v): # img ist np array
  xf = v * (img.shape[1] - 1)
  yf = u * 8img.shape[0] - 1)
  p00 = (floor(xf), floor(yf))
  p01 = (ceil(xf), floor(yf))
  p10 = (floor(xf), ceil(yf))
  p11 = (ceil(xf), ceil(yf))
  w0 = xf - p00[0]
  w1 = yf - p11[1]
  return w1 * ((1-w0) * img[p00] + w0 * img[p01]) + (1-w1) * ((1-w0) * img[p10] + w0 * img[p11]))
</code>
==== Aufgabe 8 (Baryzentrische Koordinaten) ====
**a)**\\
  * P_0: [0, 1, 0]
  * P_1: [1/2, 0, 1/2]
  * P_2: [2/3, 1/3, 0]
  * P_3: [2/5, 1/5, 2/5]

**b)**\\
  * alpha = 5/8
  * beta = 2/8
  * gamma = 1/8

**c)**\\
U = 0.5

**d)**\\
  * rho < 0, sigma > 0, tau > 0, rho + sigma + tau = 1
  * rho > 1, sigma < 0, tau < 0, rho + sigma + tau = 1. (rho > 1 ist redundant, da dies aus rho = 1 - sigma - tau > 1 folgt.)

==== Aufgabe 9 (Faltung) ====
**a)**\\
[..., 0, 1, 2, 7/3, 2, 1, 2/3, 1, 2, 7/3, 2, 1, 2/3, 1, ...]

**b)**\\
1. nein, Reihenfolge egal
2. h = h_1 * h_2

**c)**\\
(f * d_a)(x) = \int f(y) d_a(x-y) dy = f(x-a), denn x - y = a <=> y = x - a, und an dieser Stelle wird f 'evaluiert'. Steht auch so in den Folien.

**d)**\\
Der erste Uebergang leicht nach unten gebogen (quadratisch), dann linear:
(-1/2, 0) -> (3/2, 1) -> (3/2 + x, 1 + x)

Quadratisch kommt daher, dass man in das erste Dreieck hineinläuft. Die 'Slices' des Dreiecks, die man immer hinzufügt, werden größer und größer, sozusagen 1 + 2 + 3 + 4, was bekanntermaßen O(n^2) ist.\\
Es tritt dann bei x=0,5 vollkommene Überlappung auf. Nun haben wir ein Trapez, das mit größer werdendem x immer weiter nach rechts geschoben wird und oben durch f begrenzt wird. Formel für den Flächeninhalt eines Trapezes ist h * (a + c)/2. Die Höhe, oder hier die Breite des Trapezes, ändern wir nicht, sie bleibt konstant 1. Lediglich a und c ändern wir, diese sind aber gerade die Bilder unter f. Da diese immer 'gleichzeitig' nach rechts geschoben werden, ändert sich a + c auch nur linear. Der Flächeninhalt ist also linear in x. Nun braucht man nur zwei Punkte sich im Kopf kurz zu errechnen und zeichnet sich seine Gerade durch.

**e)**\\
Unterscheide nach x < -2, -2 <= x <= 2, 2 < x < \infty.\\
(f*g_2)(x) =\\
0 falls x < -2,
1/8 (x+2)^2 falls 2 <= x <= 2,\\
x falls 2 < x < \infty (also sonst)

==== Aufgabe 10 (Hauptkomponentenanalyse) ====

**a)**\\

Schwerpunkt S = (1, 1)^T\\
A := (p_0 - S | p_1 - S | ... | p_4 - S)

Dann ist C = 1/(5 - 1) * AA^T = 1/2 {{9, 0}, {0, 4}}.

**b)**\\
<code>
det(B-\lambda Id) = (1-\lambda)(7-\lambda) // bitte a^2-b^2 = (a-b)(a+b) nutzen :)

Eig(1) = span{(1, 1)^T}\\
Eig(7) = span{(-1, 1)^T}</code>

==== Aufgabe 11 (Numerische Integration) ====

**a)**\\
2 + 18 = 20

**b)**\\
1/8 * ( 0+1 + 1+8 + 8+27 + 27+64) = 136/8 = 17

**c)**\\
<code>
T_f(1/2) = 20    \
                  v
T_f(1/4) = 17  ---> T_f^1 (1/4) = (4T_f(1/4) - T_f(1/2))/3 = 16 (was übrigens der exakte Wert des Integrals ist)
</code>

**d)**\\
<code>(1 - 0) * (1/6 * f(0) + 4/6 * f((0 + 1)/2) + 1/6 * f(1)) = 16</code>

Hier muss der exakte Wert rauskommen, denn die Simpson-Regel angwandt auf ein kubisches Polynom ist immer exakt (folgt aus der einen Fehlerabschätzung, welche max{|f^(4)(x)|} erwähnt, was ja 0 bei kubischen Polynomen ist!).

**e)**\\
O(h^2)

**f)**\\
O(h^4)