🍍 🖖🏿 👋🏾 Berechnen Sie die Haskell-Matrix-Determinante 👩🏿‍🏫 🔚 🙍🏽

Ich habe beschlossen, den Code zur Berechnung der Determinanten zu veröffentlichen. Der Code funktioniert, obwohl er nicht vorgibt, virtuos zu sein. Es war einfach interessant, dieses Problem auf Haskell zu lösen. Es werden zwei Ansätze zur Lösung des Problems betrachtet: einfache Rekursion und Gaußsche Methode.

Ein bisschen Theorie

Wie Sie wissen, ist die Determinante einer quadratischen Matrix n * n die Summe von n! Begriffe, von denen jeder ein Produkt ist, das genau ein Matrixelement aus jeder Spalte und genau eines aus jeder Zeile enthält. Das Zeichen des nächsten Stückes:

a_{1, i 1} * a_{2, i 2} * . . . a_{n, i n}

${a}_{1,i1}*{a}_{2,i2}*...{a}_{n,in}$

wird durch die Parität der Substitution bestimmt:

(\begin{matrix} 1 & 2 & \dots & n \\ i_{1} & i_{2} & \dots & i_{n} \end{matrix})

$\begin{pmatrix}1 & 2 &… & n \\ {i}_{1} & {i}_{2} &… & {i}_{n} \end{pmatrix}$

Eine direkte Methode zur Berechnung der Determinante besteht darin, sie durch die Elemente einer Zeile oder Spalte in die Summe der Produkte von Elementen einer Zeile oder Spalte durch ihre algebraischen Komplemente zu zerlegen. Das algebraische Komplement des Matrixelements

a_{i, j}

${a}_{i,j}$

es gibt

{(- 1)}^{i + j} * M_{i, j}

${(-1)}^{i+j}*{M}_{i,j}$

dabei

M_{i, j}

${M}_{i,j}$

- es gibt ein Nebenelement (i, j), d.h. Determinante, die aus der ursprünglichen Determinante durch Löschen der i-ten Zeile und der j-ten Spalte erhalten wird.

Ein solches Verfahren erzeugt einen rekursiven Prozess, mit dem jede Determinante berechnet werden kann. Die Leistung dieses Algorithmus lässt jedoch zu wünschen übrig - O (n!). Daher wird eine solche direkte Berechnung verwendet, mit Ausnahme symbolischer Berechnungen (und mit Determinanten nicht zu hoher Ordnung).

Die Gauß-Methode erweist sich als viel produktiver. Sein Wesen basiert auf folgenden Bestimmungen:

1. Determinante der oberen Dreiecksmatrix

ist gleich dem Produkt seiner diagonalen Elemente. Diese Tatsache ergibt sich unmittelbar aus der Zerlegung der Determinante in Bezug auf die Elemente der ersten Zeile oder der ersten Spalte. 2. Wenn Sie in der Matrix zu den Elementen einer Zeile die Elemente einer anderen Zeile hinzufügen, multipliziert mit derselben Zahl, ändert sich der Wert der Determinante nicht. 3. Wenn zwei Zeilen (oder zwei Spalten) in der Matrix vertauscht sind, ändert der Wert der Determinante ihr Vorzeichen in das Gegenteil.

(\begin{matrix} a_{1, 1} & a_{1, 2} & \dots & a_{1, n} \\ 0 & a_{2, 2} & \dots & a_{2, n} \\ 0 & 0 & \dots & . . . \\ 0 & 0 & \dots & a_{n, n} \end{matrix})

$\begin{pmatrix}{a}_{1,1} & {a}_{1,2} &… & {a}_{1,n} \\ 0 & {a}_{2,2} &… & {a}_{2,n} \\ 0 & 0 &… & ...\\ 0 & 0 &… & {a}_{n,n} \\\end{pmatrix}$

Wir können bei Auswahl der Koeffizienten die erste Zeile der Matrix mit allen anderen hinzufügen und in der ersten Spalte an allen Positionen außer der ersten Nullen erhalten. Um in der zweiten Zeile Null zu erhalten, müssen Sie der ersten Zeile die erste hinzufügen, multipliziert mit

- a_{2, 1} / a_{1, 1}

$-{a}_{2,1}/{a}_{1,1}$

Um in der dritten Zeile Null zu erhalten, addieren Sie die erste Zeile multipliziert mit

- a_{3, 1} / a_{1, 1}

$-{a}_{3,1}/{a}_{1,1}$

usw. Letztendlich wird die Matrix auf eine Form reduziert, in der alle Elemente enthalten sind

a_{n, 1}

${a}_{n,1}$

für n> 1 ist gleich Null.

Wenn in der Matrix das Element

a_{1, 1}

${a}_{1,1}$

Wenn sich herausstellt, dass es gleich Null ist, können Sie in der ersten Spalte ein Element ungleich Null finden (vorausgesetzt, es befindet sich an der k-ten Stelle) und die erste und die k-te Zeile vertauschen. Bei dieser Transformation ändert die Determinante einfach ihr Vorzeichen, was berücksichtigt werden kann. Wenn die erste Spalte keine Elemente ungleich Null enthält, ist die Determinante gleich Null.

Wenn Sie auf ähnliche Weise handeln, können Sie außerdem Nullen in der zweiten Spalte, dann in der dritten usw. erhalten. Es ist wichtig, dass sich die zuvor erhaltenen Nullen nicht ändern, wenn die Zeichenfolgen hinzugefügt werden. Wenn für eine Zeile kein Element ungleich Null für den Nenner gefunden werden kann, ist die Determinante gleich Null und der Prozess kann gestoppt werden. Die normale Beendigung des Gaußschen Prozesses erzeugt eine Matrix, in der alle Elemente unterhalb der Hauptdiagonale gleich Null sind. Wie oben erwähnt, ist die Determinante einer solchen Matrix gleich dem Produkt der diagonalen Elemente.

Fahren wir mit der Programmierung fort.

Wir arbeiten mit Gleitkommadaten. Wir repräsentieren Matrizen als Listen von Strings. Definieren wir zunächst zwei Typen:

type Row    = [Double]
type Matrix = [Row]

Einfache Rekursion

Ohne zu zögern werden wir die Determinante um die Elemente der ersten (d. H. Null) Zeile erweitern. Wir brauchen ein Programm zum Konstruieren des Moll, das durch Löschen der ersten Zeile und der k-ten Spalte erhalten wird.

--  k-     
deln :: Matrix -> Int -> Matrix
deln matrix k = map (\ r -> (take (k) r)++(drop (k+1) r)) matrix

Und hier ist der Minderjährige:

--  k-   
minor :: Matrix -> Int -> Double
minor matrix k = det $ deln (drop 1 matrix) k

Bitte beachten Sie: Moll ist eine Determinante. Wir rufen die det-Funktion auf, die wir noch nicht implementiert haben. Um det zu implementieren, müssen wir die alternierende Summe der Produkte des nächsten Elements der ersten Zeile durch die Determinante des nächsten Moll bilden. Um umständliche Ausdrücke zu vermeiden, erstellen wir eine separate Funktion, um das Summenzeichen zu bilden:

sgn :: Int -> Double
sgn n = if n `rem` 2 == 0 then 1.0 else (-1.0)

Jetzt können wir die Determinante berechnen:

--   
det :: Matrix -> Double
det [[a,b],[c,d]] = a*d-b*c
det matrix = sum $ map (\c -> ((matrix !! 0)!!c)*(sgn c)*(minor matrix c))  [0..n]
             where n = length matrix - 1

Der Code ist sehr einfach und erfordert keine besonderen Kommentare. Um die Leistung unserer Funktionen zu testen, schreiben wir die Hauptfunktion:

main = print $ det [[1,2,3],[4,5,6],[7,8,(-9)]]

Der Wert dieser Determinante beträgt 54, was überprüft werden kann.

Gauß-Methode

Wir benötigen einige Dienstprogrammfunktionen (die an anderer Stelle verwendet werden können). Der erste ist der Austausch von zwei Zeilen in der Matrix:

--    
swap :: Matrix -> Int -> Int -> Matrix
swap matrix n1 n2 = map row [0..n]
                    where n=length matrix - 1
                          row k | k==n1 = matrix !! n2
                                | k==n2 = matrix !! n1
                                | otherwise = matrix !! k

Wie Sie dem obigen Code entnehmen können, wird die Funktion Zeile für Zeile durchlaufen. Wenn in diesem Fall eine Zeile mit der Nummer n1 angetroffen wird, wird die Zeile n2 zwangsweise ersetzt (und umgekehrt). Der Rest der Linien bleibt an Ort und Stelle.

Die folgende Funktion berechnet die Zeichenfolge r1, die mit der Zeichenfolge r2 hinzugefügt wird, die Element für Element mit der Zahl f multipliziert wird:

--   r1+f*r2
comb :: Row -> Row -> Double -> Row
comb r1 r2 f = zipWith (\ x y -> x+f*y) r1 r2

Hier ist alles äußerst transparent: Aktionen werden in den Zeilen der Matrix ausgeführt (dh in [Double] -Listen). Die folgende Funktion führt diese Transformation jedoch für die Matrix durch (und erhält natürlich eine neue Matrix):

--    r1  r2,   f
trans :: Matrix -> Int -> Int -> Double -> Matrix
trans matrix n1 n2 f = map row [0..n]
                       where n=length matrix - 1
                             row k | k==n1 = comb (matrix !! n1) (matrix !! n2) f
                                   | otherwise = matrix !! k

Die Funktion getNz sucht nach der Nummer des ersten Elements ungleich Null in der Liste. Es wird benötigt, wenn das nächste diagonale Element gleich Null ist.

--     
getNz :: Row -> Int
getNz xs = if length tmp == 0 then (-1) else snd $ head tmp
           where tmp=dropWhile (\ (x,k) -> (abs x) <= 1.0e-10) $ zip xs [0..]

Wenn alle Elemente der Liste Null sind, gibt die Funktion -1 zurück.

Die Suchfunktion prüft, ob die Matrix für die nächste Transformation geeignet ist (sie muss ein nächstes diagonales Element ungleich Null haben). Ist dies nicht der Fall, wird die Matrix durch Permutation von Zeilen transformiert.

--        
search :: Matrix -> Int -> Matrix
search matrix k | (abs ((matrix !! k) !! k)) > 1.0e-10 = matrix
                | nz < 0 = matrix  --      
                | otherwise = swap matrix k p 
                           where n   = length matrix
                                 lst = map (\ r -> r !! k) $ drop k matrix
                                 nz  = getNz lst
                                 p   = k + nz

Wenn es nicht möglich ist, das führende Element (ungleich Null) zu finden (die Matrix ist entartet), gibt die Funktion es unverändert zurück. Die Funktion mkzero bildet in der nächsten Spalte der Matrix Nullen:

--     
mkzero :: Matrix -> Int -> Int -> Matrix
mkzero matrix k p | p>n-1 = matrix
                  | otherwise = mkzero (trans matrix p k (-f)) k (p+1)
                    where n = length matrix
                          f = ((matrix !! p) !! k)/((matrix !! k) !! k)

Die Dreiecksfunktion bildet die obere Dreiecksform der Matrix:

--     
triangle :: Matrix -> Int -> Matrix
triangle matrix k | k>=n = matrix
                  | (abs v) <= 1.0e-10 = [[0.0]] --  
                  | otherwise = triangle (mkzero tmp k k1) k1 
                    where n   = length matrix
                          tmp = search matrix k
                          v   = (tmp !! k) !! k --  
                          k1  = k+1

Wenn es im nächsten Schritt nicht möglich war, das führende Element zu finden, gibt die Funktion eine Nullmatrix 1. Ordnung zurück. Jetzt können Sie die Parade-Funktion zum Reduzieren der Matrix auf die obere Dreiecksform zusammenstellen:

--  
gauss :: Matrix -> Matrix
gauss matrix = triangle matrix 0

Um die Determinante zu berechnen, müssen wir die diagonalen Elemente multiplizieren. Erstellen Sie dazu eine separate Funktion:

--   
proddiag :: Matrix -> Double
proddiag matrix = product $ map (\ (r,k) -> r !!k) $ zip matrix [0,1..]

Nun, und der "Bogen" ist die tatsächliche Berechnung der Determinante:

--  
det :: Matrix -> Double
det matrix = proddiag $ triangle matrix 0

Lassen Sie uns überprüfen, wie diese Funktion funktioniert:

main = print $ det  [[1,2,3],[4,5,6],[7,8,-9]]

[1 of 1] Compiling Main             ( main.hs, main.o ) 
Linking a.out ...                                                                                 
54.0

Vielen Dank an diejenigen, die bis zum Ende gelesen haben!

Der Code kann hier heruntergeladen werden

Berechnen Sie die Haskell-Matrix-Determinante

Ein bisschen Theorie

Fahren wir mit der Programmierung fort.

Einfache Rekursion

Gauß-Methode

More articles: