Determinanten berechnen: Laplace-Entwicklung und Gauß
Lesen anpassen
Nach dieser Lektion kannst du
eine Determinante nach einer beliebigen Zeile oder Spalte entwickeln und dabei das Schachbrettmuster der Vorzeichen beachten,
die Entwicklung mit dem Prinzip "Ersetze die Spalte durch Einheitsvektoren" begründen,
eine Determinante mit dem Gauß-Verfahren berechnen und Zeilentausch und Skalierung richtig verbuchen,
den Aufwand von Leibniz-Formel, Laplace-Entwicklung und Gauß-Verfahren vergleichen.
Vorausgesetzt: Eigenschaften und Rechenregeln der Determinante, Lineare Gleichungssysteme und das Gauß-Verfahren
Die Leibniz-Formel legt die Determinante fest, aber sie ist kein gutes Rechenverfahren. Für eine -Matrix hat sie Summanden, jeder ein Produkt aus zehn Faktoren. Wer so etwas von Hand oder auch mit dem Rechner auswertet, verschwendet Zeit.
Diese Lektion zeigt zwei bessere Wege. Die Laplace-Entwicklung führt eine -Determinante auf -Determinanten zurück. Sie lohnt sich, wenn eine Zeile oder Spalte viele Nullen hat. Das Gauß-Verfahren bringt die Matrix mit Zeilenumformungen auf Dreiecksform, deren Determinante man ablesen kann. Es ist für große Matrizen das Verfahren der Wahl.
Beide beruhen nur auf den Rechenregeln der vorigen Lektion: Multilinearität, Vorzeichenwechsel beim Vertauschen und .
Die Matrix hat in der ersten Spalte unter der nur Nullen. Rechts unten steht der Block mit Determinante . Was ist ?
Streichungsmatrix und Schachbrettmuster
Sei mit . Die Streichungsmatrix entsteht aus , indem man die -te Zeile und die -te Spalte streicht. Achtung: ist eine Zahl, eine Matrix.
Das Vorzeichen ist , wenn gerade ist, sonst . Über die Matrix verteilt ergibt das ein Schachbrettmuster, links oben beginnend mit (siehe Formel).
Beispiel: Für ist (Zeile und Spalte gestrichen), und an der Stelle steht im Schachbrett ein .
Gegenbeispiel: Die Matrix ist keine Streichungsmatrix dieses : Sie entsteht durch Streichen von Zeile und Spalte , sie ist . Die Reihenfolge der Indizes ist immer erst Zeile, dann Spalte.
Laplace-Entwicklung
Sei mit . Für jede feste Spalte gilt die Entwicklung nach der -ten Spalte, für jede feste Zeile die Entwicklung nach der -ten Zeile:
Beweisidee: Man zerlegt die -te Spalte in Vielfache von Einheitsvektoren und schiebt den Einheitsvektor jeweils in die linke obere Ecke.
Schritt 1: Es ist . Wegen der Linearität in Spalte ist , wobei aus entsteht, indem man die -te Spalte durch ersetzt.
Schritt 2: In tauscht man die Spalte nacheinander mit ihren linken Nachbarn, bis sie vorn steht. Das sind Vertauschungen, und die übrigen Spalten bleiben in ihrer Reihenfolge. Ebenso bringt man die Zeile mit Vertauschungen nach oben. Es entsteht eine Matrix mit erster Spalte und dem Block rechts unten, und .
Schritt 3: Zieht man von den Spalten von passende Vielfache der ersten Spalte ab, wird die erste Zeile zu ; der Block und die Determinante ändern sich nicht. In der Leibniz-Formel dieser Matrix enthält jeder Summand mit den Faktor . Die Permutationen mit sind die Permutationen von , mit demselben Signum, und ihre Summanden ergeben genau die Leibniz-Formel von . Also .
Die Zeilenentwicklung ist die Spaltenentwicklung von , denn und .
Entwicklung einer -Determinante
Entwicklung einer -Determinante
Viele Nullen. In hat die zweite Spalte nur einen Eintrag ungleich , nämlich mit Vorzeichen . Die Entwicklung nach der zweiten Spalte hat also nur einen Summanden:
Zur Kontrolle nach der ersten Zeile: .
Ohne Nullen. Für aus der ersten Lektion entwickeln wir nach der ersten Spalte:
Das ist derselbe Wert wie mit Sarrus. Wähle immer die Zeile oder Spalte mit den meisten Nullen: Jede Null spart eine ganze Unterdeterminante.
Berechne mit einer geschickt gewählten Entwicklung.
Entwicklung einer -Determinante
Entwicklung einer -Determinante
Sei . Die zweite Spalte hat nur den Eintrag , mit Vorzeichen . Streicht man Zeile und Spalte , bleibt , das wir nach der ersten Zeile entwickeln:
Zwei Entwicklungen mit Nullen ersetzen hier die Summanden der Leibniz-Formel durch zwei -Determinanten.
Eine -Determinante mit Gauß
Eine -Determinante mit Gauß
Gesucht ist für . Mit ist die -te Zeile gemeint.
Links oben steht . Tausche und ; das kostet ein Vorzeichen.
Faktoren falsch herum verbucht
Faktoren falsch herum verbucht
Man teilt eine Zeile durch , um kleinere Zahlen zu bekommen, und schreibt . Oder man ersetzt durch und hält das für eine Umformung, die nichts ändert.
Teilt man eine Zeile von durch , ist , also : Der Faktor wandert vor die neue Determinante. Und ist zwei Umformungen in einer: erst mal (Faktor ), dann abziehen (kein Faktor). Also . Unverändert bleibt die Determinante nur, wenn zu einer Zeile ein Vielfaches einer anderen Zeile addiert wird und die Zeile selbst den Faktor behält.
Aus entsteht , indem man die zweite Zeile durch teilt und danach die erste und die dritte Zeile vertauscht. Es ist . Welchen Wert hat ?
Schachbrett vergessen
Schachbrett vergessen
Bei der Entwicklung nach der zweiten Zeile werden alle Summanden mit addiert, wie bei der ersten Zeile mit dem Muster gewohnt, nur eben ohne das Minus.
Das Vorzeichen hängt von der Position ab, nicht von der Reihenfolge der Summanden: In Zeile lautet das Muster . Am sichersten schreibt man vor jedem Summanden mit den tatsächlichen Indizes hin.
Aufwandsvergleich
Aufwandsvergleich
Die Leibniz-Formel hat Summanden mit je Multiplikationen. Die Laplace-Entwicklung ohne Nullen ist nicht besser: Eine -Determinante wird zu Determinanten der Größe , jede davon zu der Größe und so weiter, insgesamt wieder in der Größenordnung .
Das Gauß-Verfahren braucht im -ten Schritt für jede der Zeilen darunter einen Quotienten und Multiplikationen. Das sind zusammen Multiplikationen und Divisionen, also etwa .
Bis sind die Verfahren gleich teuer. Danach wächst schneller als jede Potenz von . Ein Rechner mit Multiplikationen pro Sekunde bräuchte für die Multiplikationen der Leibniz-Formel bei rund Jahre, für das Gauß-Verfahren einige Mikrosekunden.
Zusammenfassung
Die Streichungsmatrix entsteht durch Streichen von Zeile und Spalte ; das Vorzeichen folgt einem Schachbrettmuster.
Laplace-Entwicklung: für jede Spalte , ebenso für jede Zeile.
Entwickle nach der Zeile oder Spalte mit den meisten Nullen; Nullen kann man vorher mit Zeilenumformungen erzeugen.
Gauß: auf Dreiecksform bringen, Zeilentausch kostet ein Vorzeichen, das Herausziehen eines Faktors aus einer Zeile ergibt den Vorfaktor .
Addition eines Vielfachen einer anderen Zeile ändert die Determinante nicht; dagegen multipliziert sie mit .
Leibniz und Laplace ohne Nullen kosten etwa Operationen, Gauß etwa .
Übungen
Welches Vorzeichen gehört in der Laplace-Entwicklung einer -Matrix zum Eintrag ?
Berechne .
Berechne mit dem Gauß-Verfahren .
Für welche reelle Zahl ist ? Schreibe das Ergebnis als Dezimalzahl.
Berechne .
Zeige für die Formel der Vandermonde-Determinante .