Lösungsvorschlag

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)

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
 

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:
  1. Bestimme eine QR-Zerlegung der Matrix A.
  2. Berechne z=Q^Tb.
  3. Löse Rx=z durch Rückwärtseinsetzen.

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

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.

a)

  const float &Image::operator() (unsigned int i, unsigned int j) const {
    return data[i*width+j];
  }

b)

  const float &Image::operator() (unsigned int i, unsigned int j) const {
    return data[i*width+j];
  }

c)

  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;
  }

d)

  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;
  }

e)

  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;
  }

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
 

a)

  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;
}

b)

  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;
  }

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

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]

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

1. (keine Überlappung) t < -1: h(x)*h(x)= 0
2. (Eintrittsphase) -1 ⇐ t <1: h(x)*h(x) = Integral form -2 to t-1 of 1/2 dx = t/2+0.5
3. (Vollständige Überlappung) 1 ⇐ t < 3: h(x)*h(x) = Integral form t-3 to t-1 of 1/2 dx = 1
4. (Austrittsphase) 3 ⇐ t < 5: h(x)*h(x) = Integral form t-3 to 2 of 1/2 dx = -t/2 + 5/2
5. (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

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