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

==== Aufgabe 1 (Theorieaufgaben) ====
**a)**
n^2, n, n^2, n, n^2, n^2, h^2, h^4

Die Komplexität der Multiplikation zweier k-Bandmatrizen ist O(k*n) bzw. nur O(n)

**b)**
  * Richtig
  * Falsch (Ausloeschungen usw)



==== Aufgabe 2 (Duennbesetzte Matrizen) ====
**a)**
  val = [2, 3, -4, 7, 3, 2, 8, 1, -3] 
  row_ind = [3, 4, 5, 2, 3, 4, 2, 4, 5] 
  col_ptr = [1,1,4,7,10,10]

**b)**
   Es wird CRS verwendet
   col_ind (CRS) = row_ind (CCS)
   row_ptr (CRS) = col_ptr (CCS)

**c)**
   [4, 0, 5, 7,0]^T
   
==== Aufgabe 3 (Direkte Verfahren fur lineare Gleichungssysteme) ====
**a)** \\
http://www.numerik.mathematik.uni-mainz.de/didaktikseminar/Gruppe6/
      | 1  0  0  0 |
      | 2  1  0  0 |
  L = |-1  0  1  0 |
      | 2 -2 -1  1 |
      
      | 2  0 -2  1 |
      | 0  2 -1  0 |
  R = | 0  0  1  2 |
      | 0  0  0  1 |
      
**b)**\\
http://www.math.uni-frankfurt.de/~numerik/lehre/Seminare/ProSem_MA_SS11/qrzerlegung.pdf
      | -0.6 -0.8  |
  Q = | -0.8  0.6  |
  
      | -5 -2 |
  R = |  0 -1 |

**c)** \\
  * Um die Lösung x∈ℝn eines linearen Gleichungssystems Ax=b zu bestimmen, sind folgende drei Schritte durchzuführen:
    - Bestimme eine QR-Zerlegung der Matrix A.
    - Berechne z=Q^Tb.
    - Löse Rx=z durch Rückwärtseinsetzen.

  z = [0, 0, 6, 2]^T
  x = [1, 1, 2, 2]^T
  

==== Aufgabe 4 (Singulaerwertzerlegung (SVD)) ====
**a)** \\
Diagonaleintraege von Sigma
  2; 1
  
**b)** \\
Anzahl der Singulaerwerte
  rang(A) = 2
  ||| A |||_F = sqrt(2²+1²) = sqrt(5)

**c)** \\
Nur den ersten Singulaerwert erhalten, andere Singulaerwerte durch 0 ersetzen

  A1 =  2 * 1/5 * [3, 0, -4, 0]^T * 1/5 * [4, -2, -1, -2] 

            | 24 -12 -6 -12 |
            |  0   0  0   0 |
    =  1/25 |-32  16  8  16 |
            |  0   0  0   0 | 

**d)**

  [0, 0, 2/5, 4/5]^T

**e)**
  Minimiert das Residuum, und x hat die kleinste Euklidische Norm.
  
==== Aufgabe 5 (Programmierung: Bilder, Filtern) ====
**a)**
<code cpp>
  const float &Image::operator() (unsigned int i, unsigned int j) const {
    return data[i*width+j];
  }
</code>

**b)**
<code cpp>
  const float &Image::operator() (unsigned int i, unsigned int j) const {
    return data[i*width+j];
  }
</code>

**c)**
<code cpp>
  Image Filter::derivateX(const Image &input) {
    Image output(input.height, input.width-2);
    for(int y=0;y<input.height;y++) {
      for(int x=1;x<input.width-1;x++) {
        output(y,x-1)=0.5*(input(y,x+1) - input(y,x-1));
      }
    }
    return output;
  }
</code>

**d)**
<code cpp>
  Image Filter::laplace(const Image &input) {
    Image output(input.height-2,input.width-2);
    float laplaceFilter[3][3]={{0,1,0},
                                      {1,-4,1},
                                      {0,1,0}};

    for(int y=1;y<input.height-1;y++) {
      for(int x=1;x<input.width-1;x++) {
        float newValue=0;
        for(int i=0;i<3;i++) {
          for(int j=0;j<3;j++) {
            newValue+=laplaceFilter[i][j]*input(y-1+i,x-1+j);
          }
        }
        output(y-1,x-1)=newValue;
      }
    }
    return output;
  }
</code> 

**e)**
<code cpp>
  Image Filter::mean3(const Image &input) {
    Image output(input.height-2,input.width-2);
    Image tmp(input.height,input.width-2);
    float filterX[3]={1.0f/3,1.0f/3,1.0f/3};
    float filterY[3]={1.0f/3,1.0f/3,1.0f/3};
 
    for(int y=0;y<input.height;y++) {
      for(int x=1;x<input.width-1;x++) {
        float newValue=0;
        for(int i=0;i<3;i++) {
          newValue+=filterX[i]*input(y.x-1+i);
        }
        tmp(y,x-1)=newValue;
      }
    }

    for(int y=1;y<tmp.height-1;y++) {
      for(int x=0;x<tmp.width;x++) {
        float newValue=0;
        for(int i=0;i<3;i++) {
          newValue+=filterY[i]*tmp(y-1+i.x);
        }
        output(y-1,x)=newValue;
      }
    }
    return output;
  }
</code>

==== Aufgabe 6 (Iterative Loesungsverfahren) ====
**a)**
   x1 = [1, 2, 5/2, 2, 1]^T
    
**b)**
  x1 = [1, 2, 3, 3, 2]^T

**c)**
   Schwaches Zeilen-SummenKriterium (somit schwach diagonaldominant) + unzerlegbare Matrix => Konvergiert
   
==== Aufgabe 7 (Programmierung: Nichtlineare Optimierung) ====
**a)**
<code cpp> 
  vec2 Optimizer::gradientDescent(const Function &f, const vec2 &x0, int maxIter) {
    vec2 currX=x0;
    for(int i=0;i<maxIter;i++) {
      if(f.gradF(currX).length() < 0.001) {
        break; // Genauigkeit erreicht
      }
      currX = currX + stepLength(f,currX,f.gradF(currX))*f.gradF(currX);
    }
    return currX;
}
</code>

**b)**
<code cpp>
  vec2 Optimizer::newton(const Function &f, const vec2 &x0, int maxIter) {
    vec2 currX=x0;
    for(int i=0;i<maxIter;i++) {
      if(f.gradF(currX).length() < 0.001) {
        break; // Genauigkeit erreicht
      }
      currX = currX - f.hessian(currX).inverse()*f.gradF(currX);
    }
    return currX;
  }
</code>

**c)**
Falls die Hesse-Matrix nicht positiv definit ist, kann sie im jeweiligen Iterationsdurchlauf durch die EInheitsmatrix ersetzt werden. In diesem Falle geht das Newton-Verfahren in das Gradientenabstiegsverfahren ueber.
  Gradientenabstiegsverfahren
  
==== Aufgabe 8 (Bezier-Kurven) ====
**a)**
  Siehe Script
  
**b)**
    [-2 0] [2 4] [6 4] [6 0]
       [0 2] [4 4] [6 2]
         [2 3] [5 3]
           [3½ 3]
  => c0..c3=[-2 0] [0 2] [2 3] [3½ 3]
   d0..d3=[3½ 3] [5 3] [6 2] [6 0]

  
==== Aufgabe 9 (Faltung) ====
**a)**
  [ r ] Distributivitaet\\
  [ r ] Kommutativitaet\\
  [ f ] Denn: Neutrales Element der Faltung zu einer Funktion f ist nicht die Funktion f selbst - es gibt kein neutrales Element im kommutativen Ring mit Faltungsoperation (siehe Wikipedia)\\
  [ r ] Assoziativitaet
  
**b)**
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 (hoffe das ist verständlich, weil ASCII Bild hier rein is doof)

Lösung:\\
Strecke0: P1 = (-unendlich, 0) bis P2 = (-1/2, 0)\\
Strecke1: P1 = (-1/2, 0) bis P2 = (0, 1/2)\\
Strecke2: P1 = (0, 1/2) bis P2 = (1, -1/2)\\
Strecke3: P1 = (1, -1/2) bis P2 = (3/2, 0)\\
Strecke4: P1 = (3/2, 0) bis P2 = (unendlich, 0)

Alternativlösung: (-0.5, 0), (0, 0.5), (0.5, 0.5), (1, 0)

Alternativlösung (Wolfram Language): https://i.imgur.com/7fJeOC4.png

**c)** \\
Erklaert an einem Beispiel: http://nt.eit.uni-kl.de/fileadmin/lehre/guet/uebung/faltung.pdf
  - (keine Überlappung)   t < -1: h(x)*h(x)= 0
  - (Eintrittsphase)   -1 <= t <1: h(x)*h(x) = Integral form -2 to t-1 of 1/2 dx = t/2+0.5
  - (Vollständige Überlappung)  1 <= t < 3: h(x)*h(x) = Integral form t-3 to t-1 of 1/2 dx = 1
  - (Austrittsphase)  3 <= t < 5: h(x)*h(x) = Integral form t-3 to 2 of 1/2 dx = -t/2 + 5/2
  - (keine Überlappung)  5 <=t: h(x)*h(x) = 0

Alternativlösung:\\
x < -1: h3(x)*h4(x)= 0\\
-1 <= x < 1: h3(x)*h4(x)= 0.5 x - 1 (Integrieren von 1 bis x-1)\\
1 <= x < 3: h3(x)*h4(x)= 1\\
3 <= x < 5: h3(x)*h4(x)= -0.5 x +  3 (Integrieren von x-3 bis 3)\\
5 <= x: h3(x)*h4(x)= 0\\

==== Aufgabe 10 ( ) ====
**1a)**
  Baryzentrische Koordinaten: (1/4, 1/2, 1/4)
  
**1b)**
  sigma < 0, rho < 0 --> spitze  Flaeche rechts ueber Punkt T
  tau = 1 --> Gerade durch den Punkt T, sodass die Gerade parallel zur Strecke [RS] liegt
  
**1c)**
    a:b = beta/alpha
    c:d = (beta+gamma)/alpha = (1 - alpha)/alpha
    e:f = gamma/alpha

**2)**
  P: fP = 4
  Mittelpunkt: fM = 1/4*(fA+fB+fC+fD) = 7/2