Lineare Algebra für Informatik - Exam.pdf

Aufgabe 1)

Betrachten wir den Vektorraum \(\textbf{R}^3\) mit der Standardbasis \(\textbf{e}_1 = (1,0,0)\), \(\textbf{e}_2 = (0,1,0)\) und \(\textbf{e}_3 = (0,0,1)\).

a)

(a) Bestimme, ob die folgenden Mengen von Vektoren eine Basis von \(\textbf{R}^3\) bilden. Begründe deine Antwort.

• \(\textbf{B}_1 = \{(1,0,0), (0,1,0), (0,0,1)\} \)
• \(\textbf{B}_2 = \{(1,2,3), (4,5,6), (7,8,9)\} \)
• \(\textbf{B}_3 = \{(1,0,0), (1,1,0), (1,1,1)\} \)

Lösung:

Um zu prüfen, ob die gegebenen Mengen von Vektoren eine Basis von \(\textbf{R}^3\) bilden, müssen wir untersuchen, ob die Vektoren linear unabhängig sind und den gesamten Vektorraum \(\textbf{R}^3\) aufspannen. Eine Menge von drei Vektoren bildet genau dann eine Basis von \(\textbf{R}^3\), wenn die Vektoren linear unabhängig sind.

• \(\textbf{B}_1 = \{(1,0,0), (0,1,0), (0,0,1)\}\)

Lösung: Diese Vektoren sind die Standardbasisvektoren in \(\textbf{R}^3\). Sie sind per Definition linear unabhängig und spannen den gesamten Raum \(\textbf{R}^3\) auf. Daher bildet \(\textbf{B}_1\) eine Basis von \(\textbf{R}^3\).

Beispiel zur linearen Unabhängigkeit:

\( c_1(1,0,0) + c_2(0,1,0) + c_3(0,0,1) = (0,0,0) \)

\( \Rightarrow (c_1, c_2, c_3) = (0,0,0) \)

Daher sind die Vektoren linear unabhängig.

• \(\textbf{B}_2 = \{(1,2,3), (4,5,6), (7,8,9)\}\)

Lösung: Um zu prüfen, ob diese Vektoren linear unabhängig sind, betrachten wir das Gleichungssystem:

\(c_1(1,2,3) + c_2(4,5,6) + c_3(7,8,9) = (0,0,0)\)

Wir können dieses System als entsprechende Matrix schreiben und die Determinante berechnen. Wenn die Determinante null ist, sind die Vektoren linear abhängig:

\(\begin{vmatrix} 1 & 4 & 7 \ 2 & 5 & 8 \ 3 & 6 & 9 \end{vmatrix}\)

Die Determinante dieser Matrix ist null:

\(\text{det} = 1(5 \cdot 9 - 6 \cdot 8) - 4(2 \cdot 9 - 3 \cdot 8) + 7(2 \cdot 6 - 3 \cdot 5) = 0\)

Da die Determinante null ist, sind die Vektoren linear abhängig. Somit bildet \(\textbf{B}_2\) keine Basis von \(\textbf{R}^3\).

• \(\textbf{B}_3 = \{(1,0,0), (1,1,0), (1,1,1)\}\)

Lösung: Um zu prüfen, ob diese Vektoren linear unabhängig sind, betrachten wir das Gleichungssystem:

\(c_1(1,0,0) + c_2(1,1,0) + c_3(1,1,1) = (0,0,0)\)

Dieses System können wir als entsprechende Matrix schreiben und die Determinante berechnen:

\(\begin{vmatrix} 1 & 1 & 1 \ 0 & 1 & 1 \ 0 & 0 & 1 \end{vmatrix}\)

Die Determinante dieser Matrix ist:

\(\text{det} = 1(1 \cdot 1 - 1 \cdot 0) - 1(0 \cdot 1 - 0 \cdot 1) + 1(0 \cdot 1 - 0 \cdot 1) = 1\)

Da die Determinante ungleich null ist, sind die Vektoren linear unabhängig. Somit bildet \(\textbf{B}_3\) eine Basis von \(\textbf{R}^3\).

• Zusammenfassend:
• \(\textbf{B}_1\) ist eine Basis von \(\textbf{R}^3\).
• \(\textbf{B}_2\) ist keine Basis von \(\textbf{R}^3\).
• \(\textbf{B}_3\) ist eine Basis von \(\textbf{R}^3\).

b)

(b) Nehmen wir an, dass \(\textbf{V} = \{(2,1,0), (1,1,1), (3,0,1)\}\) eine Basis eines Vektorraums ist. Drücke die Vektoren \(\textbf{v} = (5,3,1)\) und \(\textbf{w} = (1,2,3)\) als Linearkombination der Basisvektoren in \(\textbf{V}\) aus.

Lösung:

Um die Vektoren \(\textbf{v} = (5,3,1)\) und \(\textbf{w} = (1,2,3)\) als Linearkombination der Basisvektoren in \(\textbf{V} = \{(2,1,0), (1,1,1), (3,0,1)\}\) auszudrücken, müssen wir die Koeffizienten \(c_1, c_2, c_3\) finden, so dass:

• \(\textbf{v} = c_1(2,1,0) + c_2(1,1,1) + c_3(3,0,1)\)
• \(\textbf{w} = d_1(2,1,0) + d_2(1,1,1) + d_3(3,0,1)\)

Lösung für \(\textbf{v}\):

Das Gleichungssystem für \(\textbf{v} = (5,3,1)\) ist:

 \[ \begin{cases} 2c_1 + c_2 + 3c_3 &= 5 \ c_1 + c_2 &= 3 \ c_2 + c_3 &= 1 \end{cases} \] 

Schritt 1: Löse die zweite Gleichung nach \(c_2\) auf:

 \[ c_2 = 3 - c_1 \] 

Schritt 2: Setze \(c_2\) in die dritte Gleichung ein:

 \[ (3 - c_1) + c_3 = 1 \] \[ c_3 = 1 - 3 + c_1 \] \[ c_3 = c_1 - 2 \] 

Schritt 3: Setze \(c_2\) und \(c_3\) in die erste Gleichung ein:

 \[ 2c_1 + (3 - c_1) + 3(c_1 - 2) = 5 \] \[ 2c_1 + 3 - c_1 + 3c_1 - 6 = 5 \] \[ 4c_1 - 3 = 5 \] \[ 4c_1 = 8 \] \[ c_1 = 2 \] 

Schritt 4: Berechne \(c_2\) und \(c_3\):

 \[ c_2 = 3 - c_1 = 3 - 2 = 1 \] \[ c_3 = c_1 - 2 = 2 - 2 = 0 \] 

Somit ist \(\textbf{v} = 2 \textbf{u}_1 + 1 \textbf{u}_2 + 0 \textbf{u}_3\).

Lösung für \(\textbf{w}\):

Das Gleichungssystem für \(\textbf{w} = (1,2,3)\) ist:

 \[ \begin{cases} 2d_1 + d_2 + 3d_3 &= 1 \ d_1 + d_2 &= 2 \ d_2 + d_3 &= 3 \end{cases} \] 

Schritt 1: Löse die zweite Gleichung nach \(d_2\) auf:

 \[ d_2 = 2 - d_1 \] 

Schritt 2: Setze \(d_2\) in die dritte Gleichung ein:

 \[ (2 - d_1) + d_3 = 3 \] \[ d_3 = 3 - 2 + d_1 \] \[ d_3 = d_1 + 1 \] 

Schritt 3: Setze \(d_2\) und \(d_3\) in die erste Gleichung ein:

 \[ 2d_1 + (2 - d_1) + 3(d_1 + 1) = 1 \] \[ 2d_1 + 2 - d_1 + 3d_1 + 3 = 1 \] \[ 4d_1 + 5 = 1 \] \[ 4d_1 = -4 \] \[ d_1 = -1 \] 

Schritt 4: Berechne \(d_2\) und \(d_3\):

 \[ d_2 = 2 - d_1 = 2 + 1 = 3 \] \[ d_3 = d_1 + 1 = -1 + 1 = 0 \] 

Somit ist \(\textbf{w} = -1 \textbf{u}_1 + 3 \textbf{u}_2 + 0 \textbf{u}_3\).

Zusammengefasst:

• \(\textbf{v} = 2(2,1,0) + 1(1,1,1) + 0(3,0,1)\)
• \(\textbf{w} = -1(2,1,0) + 3(1,1,1) + 0(3,0,1)\)

Aufgabe 2)

Gauß-Algorithmus zur Lösung linearer Gleichungssysteme Gegeben sei das lineare Gleichungssystem mit der Koeffizientenmatrix A und der rechten Seite B. Verwende den Gauß-Algorithmus, um das System zu lösen. Der Algorithmus umfasst die Schritte der Vorwärts-Elimination, um die Koeffizientenmatrix in obere Dreiecksform zu bringen, und der Rückwärtssubstitution, um die Lösungen zu finden. Bei den elementaren Zeilenumformungen sind das Vertauschen von Zeilen, das Multiplizieren einer Zeile mit einem Skalar und das Addieren eines Vielfachen einer Zeile zu einer anderen zugelassen.

Aufgabe 3)

In einer Informatik-Vorlesung an der TU München behandelten wir das Thema Eigenwerte und Eigenvektoren. Die Matrix A, die wir betrachten, ist eine 3x3 Matrix: A = . Ihre Aufgabe ist es, die Eigenwerte und Eigenvektoren dieser Matrix zu berechnen und deren Bedeutung zu erklären.

a)

Subexercise 1: Bestimme die charakteristische Gleichung für die gegebene Matrix A. Berechne die Eigenwerte der Matrix, indem du die Gleichung löst: .

Lösung:

Subexercise 1:Um die charakteristische Gleichung für die gegebene Matrix A zu bestimmen, müssen wir zunächst die Matrix A und die Einheitsmatrix I betrachten. Angenommen, die Matrix A sei:

\( A = \begin{pmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \ 7 & 8 & 9 \end{pmatrix} \)

Um die charakteristische Gleichung aufzustellen, subtrahieren wir \( \lambda \) mal die Einheitsmatrix I von der Matrix A:

\( A - \lambda I = \begin{pmatrix} 1 - \lambda & 2 & 3 \ 4 & 5 - \lambda & 6 \ 7 & 8 & 9 - \lambda \end{pmatrix} \)

Die charakteristische Gleichung ergibt sich nun durch Berechnung der Determinante dieser Matrix und gleichsetzen dieser zu null:

• Die charakteristische Gleichung lautet: \( \det(A - \lambda I) = 0 \)

Berechnen wir die Determinante:

\( \det(A - \lambda I) = \begin{vmatrix} 1 - \lambda & 2 & 3 \ 4 & 5 - \lambda & 6 \ 7 & 8 & 9 - \lambda \end{vmatrix} \)

Zur Berechnung der Determinante einer 3x3 Matrix wenden wir die Regel von Sarrus an:

\( \det(A - \lambda I) = (1 - \lambda) \left[(5 - \lambda)(9 - \lambda) - 6 \cdot 8\right] - 2 \left[4(9 - \lambda) - 6 \cdot 7\right] + 3 \left[4 \cdot 8 - 7(5 - \lambda)\right] \)

Dies vereinfacht sich zu:

\( (1 - \lambda)[(5 - \lambda)(9 - \lambda) - 48] - 2[36 - 4\lambda - 42] + 3[32 - 35 + 7\lambda] \)\( (1 - \lambda)(45 - 14\lambda + \lambda^2 - 48) - 2(-6 - 4\lambda) + 3(-3 + 7\lambda) \)\( (1 - \lambda)(\lambda^2 - 14\lambda - 3) + 12 + 8\lambda - 9 + 21\lambda \)

Zusammenfassen ergibt:

\( \lambda^3 - 14\lambda^2 - 3\lambda^2 + 14\lambda - 3 + 8\lambda + 21\lambda + 12 - 9 \)\( \lambda^3 - 18\lambda^2 + 18\lambda = 0 \)

Zur Lösung der Gleichung setzen wir die charakteristische Gleichung gleich null und lösen sie:

\( \lambda(\lambda^2 - 18\lambda + 18) = 0 \)

Daraus erhalten wir drei mögliche Werte für \( \lambda \):

• \( \lambda_1 = 0 \)
• \( \lambda_2, \lambda_3 = 9 \pm \sqrt{45} \)

Damit sind die Eigenwerte der Matrix A \( \lambda_1 = 0 \), \( \lambda_2 = 9 + \sqrt{45} \) und \( \lambda_3 = 9 - \sqrt{45} \).

b)

Subexercise 2: Nachdem du die Eigenwerte bestimmt hast, berechne die zugehörigen Eigenvektoren für jeden Eigenwert, indem du folgende Gleichung löst: .

Lösung:

Subexercise 2:Nachdem wir im Subexercise 1 die Eigenwerte der Matrix A berechnet haben, müssen wir nun die zugehörigen Eigenvektoren finden. Nehmen wir an, dass die Matrix A die folgende Form hat:

\( A = \begin{pmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \ 7 & 8 & 9 \end{pmatrix} \)

Die Eigenwerte sind nach Subexercise 1 beispielsweise

• \( \lambda_1 = 0 \)
• \( \lambda_2 = 9 + \sqrt{45} \)
• \( \lambda_3 = 9 - \sqrt{45} \)

Um die Eigenvektoren zu berechnen, lösen wir die Gleichung \((A - \lambda I)x = 0\) für jeden Eigenwert \(\lambda\).

• Wenn \(\lambda = \lambda_1\), dann haben wir:

  \( A - 0 \cdot I = A = \begin{pmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \ 7 & 8 & 9 \end{pmatrix} \)

  Setzen wir \(A\) in die Gleichung \((A - \lambda_1 I)x = 0\) ein und lösen wir sie.

  \( \begin{pmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \ 7 & 8 & 9 \end{pmatrix} \begin{pmatrix} x_1 \ x_2 \ x_3 \end{pmatrix} = \begin{pmatrix} 0 \ 0 \ 0 \end{pmatrix} \)

  In diesem spezifischen Fall müssen wir das Gleichungssystem lösen, um die Eigenvektoren zu finden.
• Für \(\lambda = \lambda_2 = 9 + \sqrt{45}\), haben wir:

  \( A - (9 + \sqrt{45}) \cdot I = \begin{pmatrix} 1 - (9 + \sqrt{45}) & 2 & 3 \ 4 & 5 - (9 + \sqrt{45}) & 6 \ 7 & 8 & 9 - (9 + \sqrt{45}) \end{pmatrix} \)

  Wir setzen dies in die Gleichung ein:

  \( \begin{pmatrix} 1 - (9 + \sqrt{45}) & 2 & 3 \ 4 & 5 - (9 + \sqrt{45}) & 6 \ 7 & 8 & 9 - (9 + \sqrt{45}) \end{pmatrix} \begin{pmatrix} x_1 \ x_2 \ x_3 \end{pmatrix} = \begin{pmatrix} 0 \ 0 \ 0 \end{pmatrix} \)

  Auch hier lösen wir das Gleichungssystem, um den Eigenvektor für \(\lambda_2\) zu finden.
• Für \(\lambda = \lambda_3 = 9 - \sqrt{45}\), ist \((A - \lambda I)\) wie folgt:

  \( A - (9 - \sqrt{45}) \cdot I = \begin{pmatrix} 1 - (9 - \sqrt{45}) & 2 & 3 \ 4 & 5 - (9 - \sqrt{45}) & 6 \ 7 & 8 & 9 - (9 - \sqrt{45}) \end{pmatrix} \)

  Wieder setzen wir dies in die Gleichung ein:

  \( \begin{pmatrix} 1 - (9 - \sqrt{45}) & 2 & 3 \ 4 & 5 - (9 - \sqrt{45}) & 6 \ 7 & 8 & 9 - (9 - \sqrt{45}) \end{pmatrix} \begin{pmatrix} x_1 \ x_2 \ x_3 \end{pmatrix} = \begin{pmatrix} 0 \ 0 \ 0 \end{pmatrix} \)

  Auch hier müssen wir das Gleichungssystem lösen.

Nachdem wir die Gleichungssysteme für die verschiedenen Eigenwerte gelöst haben, erhalten wir die entsprechenden Eigenvektoren für jeden Eigenwert.

c)

Subexercise 3: Erkläre, was die berechneten Eigenwerte und Eigenvektoren über die Matrix A aussagen. Wie können diese in der Informatik genutzt werden, um z.B. Stabilitätsanalysen oder Reduktionen der Matrix zu untersuchen?

Lösung:

Subexercise 3:Die Eigenwerte und Eigenvektoren einer Matrix enthalten wichtige Informationen über die Matrix und deren Verhalten. Hier sind einige Erklärungen und Anwendungen dieser Konzepte in der Informatik:

• Bedeutung der Eigenwerte:
  • Die Eigenwerte einer Matrix geben an, ob ein System stabil, instabil oder grenzstabil ist. Wenn alle Eigenwerte einer Matrix negativ sind (bei einer kontinuierlichen Matrix) oder innerhalb des Einheitskreises liegen (bei einer diskreten Matrix), dann ist das System stabil.
  • Der Betrag der Eigenwerte gibt Auskunft über die Stärke der Skalierung in Richtung der Eigenvektoren. Große Eigenwerte bedeuten große Streckungen in diesen Richtungen, während kleine (oder negative) Eigenwerte auf Kompressionen oder Richtungsumkehrungen hinweisen.
• Bedeutung der Eigenvektoren:
  • Eigenvektoren zeigen die Richtungen an, entlang derer die Transformation durch die Matrix am stärksten wirkt. Wenn ein Eigenvektor auf eine Transformation angewendet wird, bleibt seine Richtung unverändert, lediglich seine Länge wird um den entsprechenden Eigenwert skaliert.
  • In der Stabilitätsanalyse kann die Richtung der Eigenvektoren genutzt werden, um die Trajektorie oder das Verhalten eines dynamischen Systems zu verstehen.
• Anwendungen in der Informatik:
  • Stabilitätsanalyse: Eigenwerte werden oft in der Theorie der Differential- und Differenzengleichungen verwendet, um die Stabilität von Systemen (z.B. Regelungssysteme) zu analysieren. Systeme mit negativen oder im Einheitskreis liegenden Eigenwerten sind stabil.
  • Dimensionalitätsreduktion: In der Datenanalyse und maschinellem Lernen wird das Konzept der Hauptkomponentenanalyse (PCA) verwendet, welche auf Eigenvektoren und Eigenwerten basiert. Hierbei wird eine Hochdimensionalitätsreduktion durchgeführt, wobei die wichtigsten Variablen (Hauptkomponenten) mit den größten Eigenwerten ausgewählt werden.
  • Bild- und Signalverarbeitung: Techniken wie die Singular Value Decomposition (SVD) und andere spektrale Methoden beruhen auf der Analyse von Eigenwerten und Eigenvektoren, um Bilder und Signale zu komprimieren oder zu filtern.
  • Graphentheorie: In der Graphentheorie können die Eigenwerte der Adjazenzmatrix eines Graphen verwendet werden, um wichtige Eigenschaften des Graphen zu analysieren, wie z.B. die Konnektivität, das Spektrum oder die Anzahl der Dreiecke im Graphen.
  • Algorithmenoptimierung: Bei der Optimierung von Algorithmen können Eigenwerte helfen, die Konvergenzgeschwindigkeit zu analysieren und zu verbessern. Beispielsweise kann die Condition Number (Verhältnis des größten zum kleinsten Eigenwert) verwendet werden, um die numerische Stabilität eines Systems zu bewerten.

Zusammenfassend lässt sich sagen, dass Eigenwerte und Eigenvektoren eine zentrale Rolle in vielen Bereichen der Informatik spielen. Sie helfen dabei, Systeme zu analysieren, zu optimieren und zu verstehen, indem sie die grundlegenden Transformationen und Beziehungen innerhalb des Systems aufdecken.

d)

Subexercise 4: Nutze die berechneten Eigenwerte und Eigenvektoren, um die Diagonalisierbarkeit der Matrix A zu untersuchen. Ist A diagonalisierbar? Begründe deine Antwort mathematisch.

Lösung:

Subexercise 4:Um die Diagonalisierbarkeit der Matrix A zu untersuchen, nutzen wir die berechneten Eigenwerte und Eigenvektoren. Hier sind die Schritte im Detail:1. **Berechne die Eigenwerte und Eigenvektoren:**Wir haben im vorherigen Subexercise die Eigenwerte und Eigenvektoren der Matrix A berechnet. Nehmen wir an, dass wir die folgenden Eigenwerte und entsprechenden Eigenvektoren haben:

• \(\lambda_1 = \lambda_1, v_1 = \begin{pmatrix} v_{11} \ v_{12} \ v_{13} \end{pmatrix} \)
• \(\lambda_2 = \lambda_2, v_2 = \begin{pmatrix} v_{21} \ v_{22} \ v_{23} \end{pmatrix} \)
• \(\lambda_3 = \lambda_3, v_3 = \begin{pmatrix} v_{31} \ v_{32} \ v_{33} \end{pmatrix} \)

2. **Linearkombination der Eigenvektoren:**Eine Matrix ist diagonalisierbar, wenn die zugehörigen Eigenvektoren linear unabhängig sind. Das bedeutet, dass die Determinante der Matrix P, die aus diesen Eigenvektoren besteht, ungleich null sein muss.Wir konstruieren die Matrix P aus den berechneten Eigenvektoren:

\[P = \begin{pmatrix} v_{11} & v_{21} & v_{31} \ v_{12} & v_{22} & v_{32} \ v_{13} & v_{23} & v_{33} \end{pmatrix}\]

3. **Determinante der Matrix P berechnen:**Wir müssen die Determinante dieser Matrix P berechnen:

\[det(P) = v_{11}(v_{22}v_{33} - v_{23}v_{32}) - v_{12}(v_{21}v_{33} - v_{23}v_{31}) + v_{13}(v_{21}v_{32} - v_{22}v_{31})\]

4. **Prüfung der Determinante:**Falls \(det(P) eq 0,\) sind die Eigenvektoren linear unabhängig und die Matrix A ist diagonalisierbar. Falls \(det(P) = 0,\) sind die Eigenvektoren linear abhängig und die Matrix A ist nicht diagonalisierbar.Beispiel (hypothetische Werte):Angenommen, wir haben folgende Eigenvektoren gefunden:

• \(v_1 = \begin{pmatrix} 1 \ 0 \ 0 \end{pmatrix} \)
• \(v_2 = \begin{pmatrix} 0 \ 1 \ 0 \end{pmatrix} \)
• \(v_3 = \begin{pmatrix} 0 \ 0 \ 1 \end{pmatrix} \)

Dann wäre die Matrix P:

\[P = \begin{pmatrix} 1 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1 \end{pmatrix}\]

In diesem Fall ist die Determinante von P:

\[det(P) = 1(1*1 - 0*0) - 0(0*1 - 0*1) + 0(0*0 - 1*0) = 1\]

Da \(det(P) = 1,\) ist die Matrix A diagonalisierbar.Zusammengefasst ist die Matrix A genau dann diagonalisierbar, wenn die Berechnung der Determinante der Matrix P, die aus den Eigenvektoren besteht, ungleich null ergibt. Dies zeigt, dass die Eigenvektoren linear unabhängig sind und wir die Matrix in eine Diagonalmatrix transformieren können.