Einführung in die Numerik - Exam

Aufgabe 1)

Gegeben sei das lineare Gleichungssystem:

• \[3x + 2y - z = 1\]
• \[2x - 2y + 4z = -2\]
• \[-x + \frac{1}{2}y - z = 0\]

a)

Führe die Vorwärtselimination durch, um die Koeffizientenmatrix in eine obere Dreiecksform zu bringen. Zeige jeden Einzelschritt klar und deutlich. Achte darauf, dass Du gegebenenfalls geeignete Vielfache der Zeilen subtrahierst, um die Elemente unter der Hauptdiagonale zu Nullen.

Lösung:

Vorwärtselimination zur Umformung der Koeffizientenmatrix in obere Dreiecksform Um das lineare Gleichungssystem zu lösen, verwenden wir das Gauß-Verfahren. Wir beginnen mit der Vorwärtselimination, um die Koeffizientenmatrix in eine obere Dreiecksform zu bringen. Hier sind die Gleichungen des Systems:

• \[3x + 2y - z = 1\]
• \[2x - 2y + 4z = -2\]
• \[-x + \frac{1}{2}y - z = 0\]

• Wir schreiben das System als augmentierte Matrix auf:

• Wir subtrahieren \( \frac{2}{3} \) der ersten Zeile von der zweiten Zeile:

• \(2 - \frac{2}{3} \times 3 = 2 - 2 = 0\)
• \(-2 - \frac{2}{3} \times 2 = -2 - \frac{4}{3} = -\frac{10}{3}\)
• \(4 - \frac{2}{3} \times (-1) = 4 + \frac{2}{3} = \frac{14}{3}\)
• \(-2 - \frac{2}{3} \times 1 = -2 - \frac{2}{3} = -\frac{8}{3}\)

• Wir addieren \( \frac{1}{3} \) der ersten Zeile zur dritten Zeile:

• \(-1 + \frac{1}{3} \times 3 = -1 + 1 = 0\)
• \(\frac{1}{2} + \frac{1}{3} \times 2 = \frac{1}{2} + \frac{2}{3} = \frac{3}{6} + \frac{4}{6} = \frac{7}{6}\)
• \(-1 + \frac{1}{3} \times (-1) = -1 - \frac{1}{3} = -\frac{4}{3}\)
• \(0 + \frac{1}{3} \times 1 = \frac{1}{3}\)

• Wir subtrahieren \( \frac{7}{20} \) der zweiten Zeile von der dritten Zeile:

• \(\frac{7}{6} - \frac{7}{20} \times (-\frac{10}{3}) = \frac{7}{6} + \frac{35}{18} = \frac{21}{18} + \frac{35}{18} = \frac{56}{18} = \frac{28}{9}\)
• \(-\frac{4}{3} - \frac{7}{20} \times \frac{14}{3} = -\frac{4}{3} - \frac{49}{20} = -\frac{80}{60} - \frac{147}{60} = -\frac{227}{60}\)
• \(\frac{1}{3} - \frac{7}{20} \times -\frac{8}{3} = \frac{1}{3} + \frac{56}{60} = \frac{20}{60} + \frac{56}{60} = \frac{76}{60} = \frac{38}{30} = \frac{19}{15}\)

b)

Wende die Rückwärtssubstitution an, um die Lösungen für \(x\), \(y\) und \(z\) zu finden. Zeige den Prozess, beginnend mit der letzten Zeile des umgeformten Systems, detailliert auf.

Lösung:

Rückwärtssubstitution zur Bestimmung der Lösungen für \( x \), \( y \) und \( z \) Nach der Vorwärtselimination haben wir die augmented Matrix in obere Dreiecksform gebracht. Die finale Matrix ist wie folgt:\[\begin{pmatrix}3 & 2 & -1 & | & 1 \ 0 & -\frac{10}{3} & \frac{14}{3} & | & -\frac{8}{3} \ 0 & 0 & -\frac{227}{60} & | & \frac{19}{15} \end{pmatrix}\]Nun wenden wir die Rückwärtssubstitution an, beginnend mit der letzten Zeile.Schritt 1: Lösung für \( z \) (aus der dritten Zeile)Die dritte Zeile der Matrix lautet:\[0 \cdot x + 0 \cdot y - \frac{227}{60} \cdot z = \frac{19}{15}\]Um \( z \) zu finden, lösen wir diese Gleichung:

• \[-\frac{227}{60}z = \frac{19}{15}\]
• \[z = \frac{19}{15} \cdot -\frac{60}{227} = -\frac{19 \cdot 4}{227} = -\frac{76}{227}\]

• \[ -\frac{10}{3}y + \frac{14}{3} \cdot -\frac{76}{227} = -\frac{8}{3}\]
• \[ -\frac{10}{3}y - \frac{14 \cdot 76}{3 \cdot 227} = -\frac{8}{3}\]
• \[ -\frac{10}{3}y - \frac{1064}{681} = -\frac{8}{3}\]
• \[ -\frac{10}{3}y - \frac{4}{3} = -\frac{8}{3} \]
• \[ -\frac{10}{3}y = -\frac{8}{3} + \frac{4}{3}\]
• \[ -\frac{10}{3}y = -\frac{4}{3}\]
• \[ y = \frac{4}{10} = \frac{2}{5}\]

• \[3x + 2 \cdot \frac{2}{5} - \left(-\frac{76}{227}\right) = 1\]
• \[3x + \frac{4}{5} + \frac{76}{227} = 1\]
• \[3x + \frac{4}{5} + \frac{76}{227} = 1\]
• \[3x + \frac{4 \cdot 227 + 5 \cdot 76}{5 \cdot 227} = 1\]
• \[3x + \frac{908 + 380}{1135} = 1\]
• \[3x + \frac{1288}{1135} = 1\]
• \[3x = 1 - \frac{1288}{1135}\]
• \[3x = \frac{1135 - 1288}{1135}\]
• \[3x = \frac{-153}{1135}\]
• \[x = \frac{-153}{1135 \cdot 3}\]
• \[x = -\frac{153}{3405}\]
• \[x = -\frac{51}{1135}\]

• \[x = -\frac{51}{1135}\]
• \[y = \frac{2}{5}\]
• \[z = -\frac{76}{227}\]

c)

Diskutiere die Bedeutung der Pivotisierung im Gauß-Verfahren. Was könnte passieren, wenn keine Pivotisierung angewendet wird? Gib ein Beispiel für eine Situation, in der die Pivotisierung notwendig ist, um Fehler zu vermeiden.

Lösung:

Bedeutung der Pivotisierung im Gauß-Verfahren Die Pivotisierung ist ein essenzieller Schritt im Gauß-Verfahren, bei dem Zeilen oder Spalten der Matrix vertauscht werden, um die numerische Stabilität und Genauigkeit des Verfahrens zu gewährleisten. Im Wesentlichen geht es darum, den besten Kandidaten für die Division zu wählen, um Divisionen durch kleine oder null Werte zu vermeiden.

• Warum ist Pivotisierung wichtig?Die Pivotisierung spielt eine entscheidende Rolle in der Sicherstellung, dass das Gauß-Verfahren korrekt und effizient durchgeführt wird. Hier sind einige Gründe, warum die Pivotisierung wichtig ist:
  • Vermeidung von Division durch null: Ohne Pivotisierung könnte es passieren, dass wir gezwungen sind, durch ein sehr kleines oder sogar null Element zu teilen, was zu undefinierten oder numerisch instabilen Ergebnissen führt.
  • Minimierung numerischer Fehler: Divisionen durch sehr kleine Werte können zu großen numerischen Fehlern und Instabilitäten führen. Indem stets das größte verfügbare Pivotelement gewählt wird, können diese Fehler minimiert werden.
  • Erhöhung der Genauigkeit: Die Pivotisierung hilft, Rundungsfehler zu minimieren, die im Laufe des Verfahrens auftreten können. Dies führt zu genaueren und zuverlässigeren Ergebnissen.

• Numerische Instabilität: Wenn das Pivotelement sehr klein ist, kann die Division zu großen numerischen Fehlern führen.
• Division durch null: Einige Elemente könnten null oder fast null sein, was eine Division unmöglich machen würde.
• Inkorrekte Ergebnisse: Durch die Anhäufung von Rundungsfehlern und Instabilitäten könnten die Lösungen des Gleichungssystems ungenau oder komplett falsch sein.

• \[0.00001x + y = 1\]
• \[x + y = 2\]

• \[Z2 \rightarrow Z2 - \frac{1}{0.00001} Z1\]

• \[Z2 \rightarrow Z2 - 0.00001 \times Z1\]

• Fazit:Die Pivotisierung ist ein kritischer Schritt im Gauß-Verfahren, der dazu beiträgt, numerische Instabilität und Fehler zu minimieren. Ohne Pivotisierung könnten Lösungen ungenau oder sogar falsch sein, insbesondere bei sehr kleinen oder null Werten im Pivotelement.

Aufgabe 2)

• Jacobi-Verfahren und Gauss-Seidel-Verfahren sind iterative Methoden zur Lösung von linearen Gleichungssystemen der Form \( Ax = b \).
• Jacobi-Verfahren: Update der Lösung erfolgt für jede Variable simultan durch Isolation der Variablen in den Gleichungen.
• Formel: \( x^{(k+1)} = D^{-1} (b - (L + U)x^{(k)}) \)
• Konvergenzbedingung: Matrix \( A \) muss diagonaldominant oder positiv definit sein.
• Gauss-Seidel-Verfahren: Verbesserung basiert auf sukzessive Aktualisierung neuer Werte in den Gleichungen.
• Formel: \( x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j < i} a_{ij} x_j^{(k+1)} - \sum_{j > i} a_{ij} x_j^{(k)} \right) \)
• Schnellere Konvergenz als Jacobi, aber Reihenfolge der Berechnungen wichtig.

a)

Gegeben ist das lineare Gleichungssystem

• \( 4x_1 + x_2 = 2 \)
• \( 3x_1 + 5x_2 = 5 \)

Lösung:

Hauptaufgabe: Jacobi-Verfahren und Gauss-Seidel-Verfahren sind iterative Methoden zur Lösung von linearen Gleichungssystemen der Form

• Jacobi-Verfahren: Update der Lösung erfolgt für jede Variable simultan durch Isolation der Variablen in den Gleichungen.
• Formel:

   x^{(k+1)} = D^{-1} (b - (L + U)x^{(k)}) 

• Konvergenzbedingung: Matrix

   A 

  muss diagonaldominant oder positiv definit sein.
• Gauss-Seidel-Verfahren: Verbesserung basiert auf sukzessive Aktualisierung neuer Werte in den Gleichungen.
• Formel:

   x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j  i} a_{ij}  x_j^{(k)}\right)

• Schnellere Konvergenz als Jacobi, aber Reihenfolge der Berechnungen wichtig.

• 4x_1 + x_2 = 2
• 3x_1 + 5x_2 = 5

 x^{(k)} 

•  x_1^{(k+1)} = \frac{1}{4}(2 - x_2^{(k)}) 

•  x_2^{(k+1)} = \frac{1}{5}(5 - 3x_1^{(k)})  

 x_1^{(0)} 

 x_2^{(0)} 

•  x_1^{(0)} = 0 

•  x_2^{(0)} = 0 

 k = 0 

•  x_1^{(1)} = \frac{1}{4}(2 - x_2^{(0)}) = \frac{1}{4}(2 - 0) = 0.5  

•  x_2^{(1)} = \frac{1}{5}(5 - 3 x_1^{(0)}) = \frac{1}{5}(5 - 3 \times 0) = 1 

 k = 1 

•  x_1^{(2)} = \frac{1}{4}(2 - x_2^{(1)}) = \frac{1}{4}(2 -1)= \frac{1}{4}(1) = 0.25

•  x_2^{(2)} = \frac{1}{5}(5 - 3 x_1^{(1)}) = \frac{1}{5}(5-3 \times 0.5) = \frac{1}{5}(3.5) = 0.7

• Iteration 1: (0.5, 1)
• Iteration 2: (0.25, 0.7)

• Verify that the matrix

   A 

  diagonaldominant is:
  • Diagonal elements: 4 and 5
    • Sum of the off-diagonal elements of each row: |1| and |3|
    • Both rows satisfy the diagonal dominance condition:

      |4| > |1|

      |5| > |3|

      Das Jacobi-Verfahren sollte also konvergieren.

b)

Für dasselbe Gleichungssystem aus dem vorherigen Teil, wende das Gauss-Seidel-Verfahren an, um die ersten beiden Iterationen von \( x^{(k)} \) zu berechnen. Vergleiche die Ergebnisse mit denen des Jacobi-Verfahrens.

Lösung:

Hauptaufgabe: Jacobi-Verfahren und Gauss-Seidel-Verfahren sind iterative Methoden zur Lösung von linearen Gleichungssystemen der Form \( Ax = b \).

• Jacobi-Verfahren: Update der Lösung erfolgt für jede Variable simultan durch Isolation der Variablen in den Gleichungen.
• Formel: \( x^{(k+1)} = D^{-1} (b - (L + U)x^{(k)}) \)
• Konvergenzbedingung: Matrix \( A \) muss diagonaldominant oder positiv definit sein.
• Gauss-Seidel-Verfahren: Verbesserung basiert auf sukzessive Aktualisierung neuer Werte in den Gleichungen.
• Formel: \( x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j < i} a_{ij} x_j^{(k+1)} - \sum_{j > i} a_{ij} x_j^{(k)} \right) \)
• Schnellere Konvergenz als Jacobi, aber Reihenfolge der Berechnungen wichtig.

• 4x_1 + x_2 = 2
• 3x_1 + 5x_2 = 5

• \( x_1^{(k+1)} = \frac{1}{4}(2 - x_2^{(k)}) \)
• \( x_2^{(k+1)} = \frac{1}{5}(5 - 3 x_1^{(k+1)}) \)

• \( x_1^{(0)} = 0 \)
• \( x_2^{(0)} = 0 \)

• \( x_1^{(1)} = \frac{1}{4}(2 - x_2^{(0)}) = \frac{1}{4}(2 - 0) = 0.5 \)
• \( x_2^{(1)} = \frac{1}{5}(5 - 3 x_1^{(1)}) = \frac{1}{5}(5 - 3 \times 0.5) = \frac{1}{5}(3.5) = 0.7 \)

• \( x_1^{(2)} = \frac{1}{4}(2 - x_2^{(1)}) = \frac{1}{4}(2 - 0.7) = \frac{1}{4}(1.3) = 0.325 \)
• \( x_2^{(2)} = \frac{1}{5}(5 - 3 x_1^{(2)}) = \frac{1}{5}(5 - 3 \times 0.325) = \frac{1}{5}(4.025) = 0.805 \)

• Iteration 1: (0.5, 0.7)
• Iteration 2: (0.325, 0.805)

• Jacobi-Verfahren Iteration 1: (0.5, 1)
• Jacobi-Verfahren Iteration 2: (0.25, 0.7)
• Gauss-Seidel-Verfahren Iteration 1: (0.5, 0.7)
• Gauss-Seidel-Verfahren Iteration 2: (0.325, 0.805)

c)

Beweise, dass die Matrix \( A \) des gegebenen Gleichungssystems diagonaldominant ist und diskutiere, warum diese Eigenschaft für die Konvergenz der beiden Verfahren wichtig ist.

Lösung:

Hauptaufgabe: Jacobi-Verfahren und Gauss-Seidel-Verfahren sind iterative Methoden zur Lösung von linearen Gleichungssystemen der Form \( Ax = b \).

• Jacobi-Verfahren: Update der Lösung erfolgt für jede Variable simultan durch Isolation der Variablen in den Gleichungen.
• Formel: \( x^{(k+1)} = D^{-1} (b - (L + U)x^{(k)}) \)
• Konvergenzbedingung: Matrix \( A \) muss diagonaldominant oder positiv definit sein.
• Gauss-Seidel-Verfahren: Verbesserung basiert auf sukzessive Aktualisierung neuer Werte in den Gleichungen.
• Formel: \( x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j < i} a_{ij} x_j^{(k+1)} - \sum_{j > i} a_{ij} x_j^{(k)} \right) \)
• Schnellere Konvergenz als Jacobi, aber Reihenfolge der Berechnungen wichtig.

• Gleichungen:
  • 4x_1 + x_2 = 2
  • 3x_1 + 5x_2 = 5
• Die entsprechende Matrix \( A \) ist: \( A = \begin{pmatrix} 4 & 1 \ 3 & 5 \end{pmatrix} \)

• \( |a_{ii}| \geq \sum_{j eq i} |a_{ij}| \)

• Erste Zeile:
  • Das Diagonalelement ist: \( |a_{11}| = |4| = 4 \)
  • Die Summe der Beträge der übrigen Elemente in derselben Zeile ist: \( |a_{12}| = 1 \)
  • Überprüfung: \( 4 \geq 1 \), ergo ist die erste Zeile diagonaldominant.
• Zweite Zeile:
  • Das Diagonalelement ist: \( |a_{22}| = |5| = 5 \)
  • Die Summe der Beträge der übrigen Elemente in derselben Zeile ist: \( |a_{21}| = 3 \)
  • Überprüfung: \( 5 \geq 3 \), ergo ist die zweite Zeile diagonaldominant.

• Die Diagonaldominanz einer Matrix gewährleistet, dass sowohl das Jacobi-Verfahren als auch das Gauss-Seidel-Verfahren konvergieren, d.h., sie liefern eine Lösung, die sich mit jeder Iteration der tatsächlichen Lösung des Gleichungssystems annähert.
• Diagonaldominanz sorgt dafür, dass die Updates (Iterationsergebnisse) in den Verfahren stabil und berechenbar sind, indem sie sicherstellt, dass die dominanten Elemente (Diagonalelemente) den größten Einfluss auf die Lösungsvariablen haben.
• Ohne Diagonaldominanz könnten die Verfahren divergieren oder sehr langsam konvergieren, weil die Off-Diagonal-Elemente zu großen Korrekturen bei jedem Iterationsschritt führen könnten.

Aufgabe 3)

Gegeben sei die Matrix \[ A = \begin{pmatrix} 4 & 12 & -16 \ 12 & 37 & -43 \ -16 & -43 & 98 \end{pmatrix} \]. Diese Matrix soll mithilfe der LU-, QR- und Cholesky-Zerlegung analysiert werden. Beachte dabei, dass \(A\) symmetrisch und positiv definit ist.

a)

Führe die LU-Zerlegung der Matrix \(A\) durch und bestimme die Matrizen \(L\) und \(U\). Zeige alle Zwischenschritte ausführlich.

Lösung:

LU-Zerlegung der Matrix A

Gegeben sei die Matrix

\[ A = \begin{pmatrix} 4 & 12 & -16 \ 12 & 37 & -43 \ -16 & -43 & 98 \end{pmatrix} \]

Für die LU-Zerlegung soll die Matrix A als Produkt zweier Matrizen L und U dargestellt werden, wobei L eine untere Dreiecksmatrix und U eine obere Dreiecksmatrix ist, d.h.:

\[ A = LU \]

Schritt 1: Festlegung der Strukturen von L und U

L und U haben die folgenden Strukturen:

• L = \begin{pmatrix} l_{11} & 0 & 0 \ l_{21} & l_{22} & 0 \ l_{31} & l_{32} & l_{33} \end{pmatrix}

• U = \begin{pmatrix} u_{11} & u_{12} & u_{13} \ 0 & u_{22} & u_{23} \ 0 & 0 & u_{33} \end{pmatrix}

Schritt 2: Ermittlung der Einträge von U

• Da die erste Zeile der Matrix A identisch ist mit der ersten Zeile der Matrix U, gilt:

• u_{11} = 4
• u_{12} = 12
• u_{13} = -16

Schritt 3: Berechnung der Einträge von L

• Da A = LU und die erste Spalte der Matrix L mit der ersten Spalte der Matrix A übereinstimmt, können wir die Einträge von L berechnen:

• l_{21} = \frac{a_{21}}{u_{11}} = \frac{12}{4} = 3
• l_{31} = \frac{a_{31}}{u_{11}} = \frac{-16}{4} = -4

Die Matrizen nehmen nun die folgenden Formen an:

• L = \begin{pmatrix} 1 & 0 & 0 \ 3 & l_{22} & 0 \ -4 & l_{32} & l_{33} \end{pmatrix}

• U = \begin{pmatrix} 4 & 12 & -16 \ 0 & u_{22} & u_{23} \ 0 & 0 & u_{33} \end{pmatrix}

Schritt 4: Fortsetzung der Berechnung für U und L

• Zur Berechnung von u_{22} verwenden wir:

• l_{21} * u_{12} + l_{22} * u_{22} = a_{22}

• 3 * 12 + l_{22} * u_{22} = 37
• 36 + l_{22} * u_{22} = 37
• l_{22} * u_{22} = 1

• Da l_{22} = 1 (Diagonalelemente von L sind alle 1):

• u_{22} = 1

• l_{22} = 1

Nun:

• L = \begin{pmatrix} 1 & 0 & 0 \ 3 & 1 & 0 \ -4 & l_{32} & l_{33} \end{pmatrix}

• U = \begin{pmatrix} 4 & 12 & -16 \ 0 & 1 & u_{23} \ 0 & 0 & u_{33} \end{pmatrix}

• Zur weiteren Berechnung von u_{23}:

• 3 * u_{13} + u_{23} = a_{23}

• 3 * (-16) + u_{23} = -43
• -48 + u_{23} = -43
• u_{23} = 5

• Nun gilt:

• U = \begin{pmatrix} 4 & 12 & -16 \ 0 & 1 & 5 \ 0 & 0 & u_{33} \end{pmatrix}

• Nun berechnen wir weiterhin die restlichen für l_{32} & u_{33}:

• a_{32} = l_{31} * u_{12} + l_{32} * u_{22} ~

• -43 = (-4 * 12) + l_{32}*1 ~
• -43 = -48 + l_{32} ~
• l_{32}=5

• a_{33} =l_{31} * u_{13} + l_{32} *u_{23} + l_{33}*u_{33} ~

• 98 = (-4)*(-16) + (5) * (5) + l_{33}*u_{33}

• 98=64+25 +l_{33}*u_{33}

• 98=89 + l_{33}*u_{33}

• l_{33} * u_{33}=9 ~ da l_{33}=1

• u_{33}=9

• Die endgültigen Matrizen sind daher:

• L = \begin{pmatrix} 1 & 0 & 0 \ 3 & 1 & 0 \ -4 & 5 & 1 \end{pmatrix}

• U = \begin{pmatrix} 4 & 12 & -16 \ 0 & 1 & 5 \ 0 & 0 & 9 \end{pmatrix}

c)

Führe die Cholesky-Zerlegung der Matrix \(A\) durch und bestimme die Matrix \(L\). Zeige alle Zwischenschritte ausführlich und überprüfe deine Lösung, indem du den Produkt \(LL^T\) bildest und mit der ursprünglichen Matrix \(A\) vergleichst.

Lösung:

Cholesky-Zerlegung der Matrix A

Gegeben sei die Matrix

\[ A = \begin{pmatrix} 4 & 12 & -16 \ 12 & 37 & -43 \ -16 & -43 & 98 \end{pmatrix} \]

Die Cholesky-Zerlegung zerlegt die Matrix A in das Produkt einer unteren Dreiecksmatrix L und deren Transponierten, also:

\[ A = LL^T \]

Da A symmetrisch und positiv definit ist, ist die Cholesky-Zerlegung anwendbar.

Schritt 1: Struktur der Matrix L

Wir definieren die untere Dreiecksmatrix L als:

• \[ L = \begin{pmatrix} l_{11} & 0 & 0 \ l_{21} & l_{22} & 0 \ l_{31} & l_{32} & l_{33} \end{pmatrix} \]

Schritt 2: Bestimmung der Elemente von L

Wir berechnen die Elemente von L durch schrittweises Lösen der Gleichungen, die sich aus den Einträgen der Matrix A ergeben:

Berechnung von \( l_{11} \):

• \[ l_{11} = \sqrt{a_{11}} = \sqrt{4} = 2 \]

Berechnung von \( l_{21} \):

• \[ l_{21} = \frac{a_{21}}{l_{11}} = \frac{12}{2} = 6 \]

Berechnung von \( l_{31} \):

• \[ l_{31} = \frac{a_{31}}{l_{11}} = \frac{-16}{2} = -8 \]

Berechnung von \( l_{22} \):

• \[ l_{22} = \sqrt{a_{22} - l_{21}^2} = \sqrt{37 - 6^2} = \sqrt{37 - 36} = \sqrt{1} = 1 \]

Berechnung von \( l_{32} \):

• \[ l_{32} = \frac{a_{32} - l_{31}l_{21}}{l_{22}} = \frac{-43 - (-8) \cdot 6}{1} = \frac{-43 + 48}{1} = 5 \]

Berechnung von \( l_{33} \):

• \[ l_{33} = \sqrt{a_{33} - l_{31}^2 - l_{32}^2} = \sqrt{98 - (-8)^2 - 5^2} = \sqrt{98 - 64 - 25} = \sqrt{9} = 3 \]

Schritt 3: Die Matrix L

• \[ L = \begin{pmatrix} 2 & 0 & 0 \ 6 & 1 & 0 \ -8 & 5 & 3 \end{pmatrix} \]

Schritt 4: Überprüfung der Lösung

Wir überprüfen die Lösung, indem wir das Produkt \( LL^T \) bilden und mit der ursprünglichen Matrix A vergleichen:

• \[ L^T = \begin{pmatrix} 2 & 6 & -8 \ 0 & 1 & 5 \ 0 & 0 & 3 \end{pmatrix} \]

• \[ LL^T = \begin{pmatrix} 2 & 0 & 0 \ 6 & 1 & 0 \ -8 & 5 & 3 \end{pmatrix} \begin{pmatrix} 2 & 6 & -8 \ 0 & 1 & 5 \ 0 & 0 & 3 \end{pmatrix} = \begin{pmatrix} 4 & 12 & -16 \ 12 & 37 & -43 \ -16 & -43 & 98 \end{pmatrix} \]

Da \( LL^T = A \), ist unsere Cholesky-Zerlegung korrekt.

d)

Verwende die Cholesky-Zerlegung, um das lineare Gleichungssystem \(A\mathbf{x} = \begin{pmatrix} 1 \ 2 \ 3 \end{pmatrix}\) zu lösen. Zeige alle Zwischenschritte und berechne den Lösungsvektor \(\mathbf{x}\).

Lösung:

Lösen des linearen Gleichungssystems mit der Cholesky-Zerlegung

Gegeben sei das lineare Gleichungssystem

\[ A\mathbf{x} = \begin{pmatrix} 1 \ 2 \ 3 \end{pmatrix} \]

und die Matrix

\[ A = \begin{pmatrix} 4 & 12 & -16 \ 12 & 37 & -43 \ -16 & -43 & 98 \end{pmatrix} \]

Wir haben bereits die Cholesky-Zerlegung von A gefunden:

\[ A = LL^T \]

• \[ L = \begin{pmatrix} 2 & 0 & 0 \ 6 & 1 & 0 \ -8 & 5 & 3 \end{pmatrix} \]

Um das Gleichungssystem zu lösen, verwenden wir die Zerlegung in zwei Schritten: Zuerst lösen wir \( L \mathbf{y} = \mathbf{b} \) und dann \( L^T \mathbf{x} = \mathbf{y} \), wobei \( \mathbf{b} = \begin{pmatrix} 1 \ 2 \ 3 \end{pmatrix} \).

Schritt 1: Lösen von \( L \mathbf{y} = \mathbf{b} \)

\[ \begin{pmatrix} 2 & 0 & 0 \ 6 & 1 & 0 \ -8 & 5 & 3 \end{pmatrix} \begin{pmatrix} y_1 \ y_2 \ y_3 \end{pmatrix} = \begin{pmatrix} 1 \ 2 \ 3 \end{pmatrix} \]

• Für die erste Gleichung: \[ 2y_1 = 1 \Rightarrow y_1 = \frac{1}{2} \]

• Für die zweite Gleichung: \[ 6y_1 + y_2 = 2 \Rightarrow 6 \cdot \frac{1}{2} + y_2 = 2 \Rightarrow 3 + y_2 = 2 \Rightarrow y_2 = -1 \]

• Für die dritte Gleichung: \[ -8y_1 + 5y_2 + 3y_3 = 3 \Rightarrow -8 \cdot \frac{1}{2} + 5 \cdot (-1) + 3y_3 = 3 \Rightarrow -4 - 5 + 3y_3 = 3 \Rightarrow -9 + 3y_3 = 3 \Rightarrow 3y_3 = 12 \Rightarrow y_3 = 4 \]

Wir erhalten also den Vektor \( \mathbf{y} \):

• \[ \mathbf{y} = \begin{pmatrix} \frac{1}{2} \ -1 \ 4 \end{pmatrix} \]

Schritt 2: Lösen von \( L^T \mathbf{x} = \mathbf{y} \)

Nun lösen wir das System

• \[ L^T = \begin{pmatrix} 2 & 6 & -8 \ 0 & 1 & 5 \ 0 & 0 & 3 \end{pmatrix} \]

\[ \begin{pmatrix} 2 & 6 & -8 \ 0 & 1 & 5 \ 0 & 0 & 3 \end{pmatrix} \begin{pmatrix} x_1 \ x_2 \ x_3 \end{pmatrix} = \begin{pmatrix} \frac{1}{2} \ -1 \ 4 \end{pmatrix} \]

• Für die dritte Gleichung: \[ 3x_3 = 4 \Rightarrow x_3 = \frac{4}{3} \]

• Für die zweite Gleichung: \[ x_2 + 5x_3 = -1 \Rightarrow x_2 + 5 \cdot \frac{4}{3} = -1 \Rightarrow x_2 + \frac{20}{3} = -1 \Rightarrow x_2 = -1 - \frac{20}{3} = -\frac{3}{3} - \frac{20}{3} = -\frac{23}{3} \]

• Für die erste Gleichung: \[ 2x_1 + 6x_2 - 8x_3 = \frac{1}{2} \Rightarrow 2x_1 + 6 \cdot \left( -\frac{23}{3} \right) - 8 \cdot \frac{4}{3} = \frac{1}{2} \Rightarrow 2x_1 - 46 - \frac{32}{3} = \frac{1}{2} \] Dies lösen wir Schritt für Schritt:

• \[ 2x_1 - 46 - \frac{32}{3} = \frac{1}{2} \]

• Wir multiplizieren alles mit 3, um die Brüche zu entfernen:

• \[ 6x_1 - 138 - 32 = \frac{3}{2} \cdot 3 \Rightarrow 6x_1 - 170 = \frac{3}{2} \Rightarrow 6x_1 = 170 + \frac{3}{2} \Rightarrow 6x_1 = \frac{340}{2} + \frac{3}{2} = \frac{343}{2} \Rightarrow x_1 = \frac{343}{12} \]

Wir erhalten also den Lösungsvektor \( \mathbf{x} \) als:

• \[ \mathbf{x} = \begin{pmatrix} \frac{343}{12} \ -\frac{23}{3} \ \frac{4}{3} \end{pmatrix} \]

Aufgabe 4)

Gegeben seien die Datenpunkte \

• (x_0, y_0) = (1, 1)
• (x_1, y_1) = (2, 4)
• (x_2, y_2) = (3, 9)

a)

Berechne das Interpolationspolynom im Lagrange-Form für die gegebenen Datenpunkte. Stelle sicher, dass dein Polynom vollständig ausgeschrieben ist und alle Berechnungsschritte klar nachvollziehbar sind.

• Formel des Lagrange-Polynoms: \[ P(x) = \sum_{i=0}^{n} y_i \frac{(x-x_0) \cdots (x-x_{i-1})(x-x_{i+1}) \cdots (x-x_n)}{(x_i-x_0) \cdots (x_i-x_{i-1})(x_i-x_{i+1}) \cdots (x_i-x_n)} \]

Lösung:

Um das Interpolationspolynom in der Lagrange-Form für die gegebenen Datenpunkte zu berechnen, folgen wir den angegebenen Schritten und der Formel:

• Datenpunkte:
  • (x_0, y_0) = (1, 1)
  • (x_1, y_1) = (2, 4)
  • (x_2, y_2) = (3, 9)
• Formel des Lagrange-Polynoms: \[ P(x) = \sum_{i=0}^{n} y_i \frac{(x-x_0) \cdots (x-x_{i-1})(x-x_{i+1}) \cdots (x-x_n)}{(x_i-x_0) \cdots (x_i-x_{i-1})(x_i-x_{i+1}) \cdots (x_i-x_n)} \]

Nun berechnen wir die einzelnen Lagrange-Basispolynome und setzen die Werte der gegebenen Punkte ein:

• Für i = 0: \[ L_0(x) = \frac{(x-2)(x-3)}{(1-2)(1-3)} = \frac{(x-2)(x-3)}{1 \cdot (-2)} = \frac{(x-2)(x-3)}{-2} \] \[ L_0(x) = -\frac{1}{2}(x-2)(x-3) \]
• Für i = 1: \[ L_1(x) = \frac{(x-1)(x-3)}{(2-1)(2-3)} = \frac{(x-1)(x-3)}{1 \cdot (-1)} = -\frac{(x-1)(x-3)}{1} \] \[ L_1(x) = -(x-1)(x-3) \]
• Für i = 2: \[ L_2(x) = \frac{(x-1)(x-2)}{(3-1)(3-2)} = \frac{(x-1)(x-2)}{2 \cdot 1} = \frac{(x-1)(x-2)}{2} \] \[ L_2(x) = \frac{1}{2}(x-1)(x-2) \]

Setzen wir nun die Werte der y-Punkte ein, um das endgültige Polynom zu berechnen:

• Interpolationspolynom: \[ P(x) = y_0 \cdot L_0(x) + y_1 \cdot L_1(x) + y_2 \cdot L_2(x) \] \[ P(x) = 1 \cdot \left(-\frac{1}{2}(x-2)(x-3)\right) + 4 \cdot \left(-(x-1)(x-3)\right) + 9 \cdot \left(\frac{1}{2}(x-1)(x-2)\right) \]
• Wir expandieren und vereinfachen die Terme:
• \[ P(x) = -\frac{1}{2}(x^2 - 5x + 6) - 4(x^2 - 4x + 3) + \frac{9}{2}(x^2 - 3x + 2) \] \[ = -\frac{1}{2}x^2 + \frac{5}{2}x - 3 - 4x^2 + 16x - 12 + \frac{9}{2}x^2 - \frac{27}{2}x + 9 \]
• Weiteres Kürzen führt zu:
• \[ P(x) = (-\frac{1}{2} + \frac{9}{2} - 4)x^2 + (\frac{5}{2} + 16 - \frac{27}{2})x + (-3 - 12 + 9) \] \[ P(x) = x^2 \]

Damit lautet das vollständige Interpolationspolynom im Lagrange-Form:

• Endgültiges Interpolationspolynom: \[ P(x) = x^2 \]

b)

Bestimme das Newton-Interpolationspolynom für die gleichen Datenpunkte. Erzeuge das Polynom Schritt für Schritt, indem Du die Berechnung der Koeffizienten \(a_i\) darstellst.

• Formel des Newton-Polynoms: \[ P(x) = a_0 + a_1(x-x_0) + a_2(x-x_0)(x-x_1) + \cdots + a_n(x-x_0)(x-x_1) \cdots (x-x_{n-1}) \]

Lösung:

Um das Newton-Interpolationspolynom zu bestimmen, verwenden wir die gegebene Formel und folgen den angegebenen Schritten. Wir berechnen die Koeffizienten \(a_i\) Schritt für Schritt.

Datenpunkte:

• (x_0, y_0) = (1, 1)
• (x_1, y_1) = (2, 4)
• (x_2, y_2) = (3, 9)

Formel des Newton-Polynoms:

• \[ P(x) = a_0 + a_1(x-x_0) + a_2(x-x_0)(x-x_1) + \cdots + a_n(x-x_0)(x-x_1) \cdots (x-x_{n-1}) \]

Schritte zur Bestimmung der Koeffizienten \(a_i\):

1. Die Koeffizienten \(a_i\) berechnen wir anhand der Differenzenquotienten.

Berechnung von \(a_0\):

• \(a_0 = y_0 = 1\)

Berechnung von \(a_1\):

• \[ a_1 = \frac{y_1 - y_0}{x_1 - x_0} = \frac{4 - 1}{2 - 1} = 3 \]

Berechnung von \(a_2\):

• \[ a_2 = \frac{f[x_2, x_1] - f[x_1, x_0]}{x_2 - x_0} \]
• Zuerst berechnen wir die Differenzenquotienten:
• \[ f[x_1, x_0] = \frac{y_1 - y_0}{x_1 - x_0} = 3 \]
• \[ f[x_2, x_1] = \frac{y_2 - y_1}{x_2 - x_1} = \frac{9 - 4}{3 - 2} = 5 \]
• Jetzt können wir \(a_2\) berechnen:
• \[ a_2 = \frac{5 - 3}{3 - 1} = \frac{2}{2} = 1 \]

Nun setzen wir die Koeffizienten in das Newton-Interpolationspolynom ein:

• \[ P(x) = a_0 + a_1(x-x_0) + a_2(x-x_0)(x-x_1) \]
• \[ P(x) = 1 + 3(x-1) + 1(x-1)(x-2) \]

Das endgültige Interpolationspolynom lautet:

• \[ P(x) = 1 + 3(x-1) + (x-1)(x-2) \]

Erweitern und vereinfachen wir das Polynom:

• \[ P(x) = 1 + 3(x-1) + (x^2 - 3x + 2) \]
• \[ P(x) = 1 + 3x - 3 + x^2 - 3x + 2 \]
• \[ P(x) = x^2 \]

Damit lautet das vollständige Newton-Interpolationspolynom:

• Endgültiges Newton-Interpolationspolynom: \[ P(x) = x^2 \]

c)

Berechne den Interpolationsfehler für die oben bestimmten Polynome, falls der wahre Funktionswert \(f(x) = x^2\) ist. Nutze die Interpolationsfehler-Formel und erläutere, wie der Fehler beeinflusst wird.

• Formel des Interpolationsfehlers: \[ f(x) - P(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} (x-x_0)(x-x_1) \cdots (x-x_n) \]

Lösung:

Um den Interpolationsfehler zu berechnen, verwenden wir die Formel des Interpolationsfehlers und setzen die entsprechenden Werte ein.

• Gegebene Datenpunkte:
• (x_0, y_0) = (1, 1)
• (x_1, y_1) = (2, 4)
• (x_2, y_2) = (3, 9)
• Wahre Funktion:
• \(f(x) = x^2\)

Interpolationspolynome:

• Wir haben bereits sowohl das Lagrange-Polynom als auch das Newton-Polynom bestimmt:
• \(P(x) = x^2\)

Da beide Polynome perfekt mit der wahren Funktion \(f(x)\) übereinstimmen, betrachten wir den Interpolationsfehler:

• Die Formel des Interpolationsfehlers lautet:
• \[ f(x) - P(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} (x-x_0)(x-x_1) \cdots (x-x_n) \]
• Für unsere Berechnungen haben wir:
• \(n = 2\)
• \(f(x) = x^2\)
• \(P(x) = x^2\)
• Die Ableitung der wahren Funktion \(f(x)\) ist:
• \(f'(x) = 2x\)
• \(f''(x) = 2\)
• \(f'''(x) = 0\)

Da die dritte Ableitung \(f'''(x)\) null ist, haben wir:

• \(f^{(3)}(\xi) = 0\)
• \[ f(x) - P(x) = \frac{0}{3!} (x-1)(x-2)(x-3) \]

Der Interpolationsfehler ist daher null für die Interpolationspunkte:

• \[ f(x) - P(x) = 0 \]

Erläuterung: Da das Polynom \(P(x)\) exakt mit der wahren Funktion \(f(x) = x^2\) übereinstimmt, ist der Interpolationsfehler null. Bei einer höheren Polynominterpolation könnte der Fehler durch höhere Ableitungen und größere Differenzen der \(x\)-Punkte beeinflusst werden. Da jedoch die dritte Ableitung von \(x^2\) null ist, ergibt sich kein Fehler.