Aufgabe:
Angenommen ein Computer kann Additionen und Multiplikationen in 0,2 Mikrosekunden durchführen. Schätze ab, für welche Größen von Matrizen mit der Leibniz-Formel in höchstens 48 Stunden Determinanten berechnen kann. Schätze ab, für welche Größen von Matrizen mit dem Gauß-Algorithmus in höchstens 48 Stunden Determinanten berechnen kann.
Problem/Ansatz:
Leibniz-Formel
\( \sum \limits_{\tau \in S_{n}} \operatorname{sgn}_{n}(\pi) a_{\pi(1) 1} a_{\pi}(2) 2 \cdots a_{\pi(n) n} \)
Somit gíbt es n! Permutationen, weshalb es n! Summanden gibt und jeder Summand aus n+1 Faktoren besteht.
Es gibt also \( n ! \cdot(n+1) \) Multiplikationen und \( n \) ! Addítionen \( \Rightarrow \) Insgesamt also \( (n+2)^{*} n \) ! Operationen.
Gauß:
Die Determinante einer nxn-Matrix besteht aus n! Summanden, vor denen jeder ein Produkt von \( n \) Zahlen ist.
Erste Spalte: \( n \cdot(n-1) \) Add. und Mult.
Zweite Spalte: \( (n-1) \cdot(n-2) \) Add. und Mult.
Treppenform: 2 *1 Add. und Mult.
Diagonalform: 0 für Add und n für Mult.
Multiplikation: \( n+\sum \limits_{i=1}^{n-1} i \cdot(i+1)=\frac{n^{3}+2 n}{3} \)
Addition: \( \sum \limits_{i=1}^{n-1} i \cdot(i+1)=\frac{n^{3}-n}{3} \)
Gesamt: \( \frac{n \cdot\left(2 n^{2}+1\right)}{3} \)\(\begin{aligned}\text { Es gilt: } 2 \text { Tage } \Leftrightarrow 48 \text { Stunden } \Leftrightarrow 2880 \text { Minuten } \\\qquad \Leftrightarrow 172800 \text { Sekunden }\end{aligned}\)
Da man für die Leibnizformel \( (n+1) \) ! Rechenoperationen benötigt, benötigt man insgesamt \(2 \cdot 10^{-7} \cdot(n+1) !\) Sekunden für n Rechenschritte. Es gilt also
\(2 \cdot 10^{-7} \cdot(n+1) !=172800\)
Für den Gauß-Algorithmus gilt:
\(2 \cdot 10^{-7} \cdot \frac{n \cdot\left(2 n^{2}+1\right)}{3}=172800\)
Stimmen meine Überlegungen soweit, und wenn ja, wie komme ich dann auf meine zwei geforderten n? (Das nach n Auflösen müsste ja eigentlich mit Wolfram oder ähnlichem gehen, was mir aber kein Ergebnis geliefert hat (vermutlich hab ich irgendeinen Fehler übersehen?))
Danke für Hilfe ☺
