Entwicklungssatz von Laplace
Der Entwicklungssatz von Laplace ist eine rekursive Methode zur Berechung der Determinante einer quadratischen Matrix (siehe lineare Algebra).
(defmethod determinant ((this matrix))
(= (. this rows) (. this columns))
(laplace-expansion (. this elements)))
Wenn die Matrix nur eine Zeile und eine Spalte hat, ist die Determinante gleich dem einzigen Element der Matrix. In diesem Fall gibt es keine Rekursion.
Hat die Matrix mehr als eine Zeile und Spalte, dann wird sie nach der ersten Zeile entwickelt. Das bedeutet, man summiert spezielle Produkte der Determinanten der Untermatrixen, bei denen die erste Zeile der ursprünglichen Matrix ausgelassen ist. Die Determinante einer Untermatrix wird als Minor bezeichnet.
(defproc laplace-expansion (rows)
(if
(single? rows)
(first (first rows))
(minor-sum
(first rows)
(rest rows)
1
1
0)))
Die Funktion minor-sum summiert die Minoren multipliziert mit den Elementen der ausgelassenen Zeile und mit wechselndem Vorzeichen.
(defproc minor-sum (row rows column-index sign sum)
(if
(null? row)
sum
(minor-sum
(rest row)
rows
(+ 1 column-index)
(- sign)
(+ sum (* sign (first row) (minor rows column-index))))))
Der Minor ist die Determinante einer Untermatrix - die ursprünglichen Matrix ohne die erste Zeile und ohne die mit colum-index festgelegten Spalte.
(defproc minor (rows column-index)
(laplace-expansion
(without-column rows column-index)))
Die Hilfsfunktion without-column entfernt die mit colum-index festgelegte Spalte aus der Matrix.
(defproc without-column (rows column-index)
(map-with
(curry (without-component _ column-index))
rows))
Die Hilfsfunktion without-component entfernt das mit index angegebene Element aus der Liste components.
(defproc without-component (components index)
(if
(= index 1)
(rest components)
(cons
(first components)
(without-component
(rest components)
(- index 1)))))
Quellen
https://de.wikipedia.org/wiki/Determinante#Laplacescher_Entwicklungssatz
https://de.wikipedia.org/wiki/Minor_%28Mathematik%29
(defmethod determinant ((this matrix))
(= (. this rows) (. this columns))
(laplace-expansion (. this elements)))
Wenn die Matrix nur eine Zeile und eine Spalte hat, ist die Determinante gleich dem einzigen Element der Matrix. In diesem Fall gibt es keine Rekursion.
Hat die Matrix mehr als eine Zeile und Spalte, dann wird sie nach der ersten Zeile entwickelt. Das bedeutet, man summiert spezielle Produkte der Determinanten der Untermatrixen, bei denen die erste Zeile der ursprünglichen Matrix ausgelassen ist. Die Determinante einer Untermatrix wird als Minor bezeichnet.
(defproc laplace-expansion (rows)
(if
(single? rows)
(first (first rows))
(minor-sum
(first rows)
(rest rows)
1
1
0)))
Die Funktion minor-sum summiert die Minoren multipliziert mit den Elementen der ausgelassenen Zeile und mit wechselndem Vorzeichen.
(defproc minor-sum (row rows column-index sign sum)
(if
(null? row)
sum
(minor-sum
(rest row)
rows
(+ 1 column-index)
(- sign)
(+ sum (* sign (first row) (minor rows column-index))))))
Der Minor ist die Determinante einer Untermatrix - die ursprünglichen Matrix ohne die erste Zeile und ohne die mit colum-index festgelegten Spalte.
(defproc minor (rows column-index)
(laplace-expansion
(without-column rows column-index)))
Die Hilfsfunktion without-column entfernt die mit colum-index festgelegte Spalte aus der Matrix.
(defproc without-column (rows column-index)
(map-with
(curry (without-component _ column-index))
rows))
Die Hilfsfunktion without-component entfernt das mit index angegebene Element aus der Liste components.
(defproc without-component (components index)
(if
(= index 1)
(rest components)
(cons
(first components)
(without-component
(rest components)
(- index 1)))))
Quellen
https://de.wikipedia.org/wiki/Determinante#Laplacescher_Entwicklungssatz
https://de.wikipedia.org/wiki/Minor_%28Mathematik%29