Algorithmus - Lösung eines LGS per LU-Zerlegung

• Bewiesen durch:
  • Invarianz der Lösungsmenge bzgl inverser Matrizen (da die Permutationsmatrix nach Invertierbarkeit von n x n Matrizen invertierbar ist.)
• Involvierte Definitionen:
  • LGS
  • LU-Zerlegung
  • Lösung eines LGS
  • Lösung eines LGS per Dreiecksmatrix
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Algorithmus: Lösen von LGS mittels LU-Zerlegung

Sei eine quadratische Matrix.
Sei eine LU-Zerlegung von .
Sei .

Da , gilt weiter, dass:

Dadurch erhalten wir in zwei Schritten:

1. Löse (wir erhalten , das wir für Schritt 2. benötigen)
2. Löse (wir erhalten und sind fertig).

Beweis

Angenommen, es gilt

Dann können wir auch schreiben als

Sei , dann gilt weiter

Indem wir das LGS

lösen, erhalten wir also schon den korrekten Wert für . Aber eigentlich ist es ja unser Ziel, zu ermitteln und nicht .

Wie wir jetzt auf kommen können, steht aber eigentlich schon da:

wir müssen also nur noch das LGS lösen und sind fertig.