Bestimmen Sie die Anzahl der Additionen und Multiplikationen für die Berechnung der Determinante einer Matrix

Question

Aufgabe:

Bestimmen Sie die Anzahl der Additionen und Multiplikationen für die Berechnung der Determinante einer Matrix $A \in \mathbb{R}^{n \times n}$ mit:

a) der Definition der Determinante (Leibnizformel):

$\operatorname{det}(A)=\sum \limits_{\pi \in S_{n}} \operatorname{sgn}(\pi) \prod \limits_{j=1}^{n} a_{\pi(i), i}, \quad \text { wobei } A=\left(a_{i, j}\right)_{i, j=1}^{n}$

Vernachlässigen Sie die Kosten der Signumfunktion.

b) dem Gauß-Algorithmus.

Hinweis: $\sum \limits_{i=1}^{n-1} i(i+1)=\frac{n\left(n^{2}-1\right)}{3}$.

Ein moderner Prozessor benötigt für eine Rechenoperation ungefähr eine Nanosekunde. Schätzen Sie die Matrixgröße, wenn die Rechenzeit unter 48 Stunden liegen soll. Bemerkung: Die Entwicklung nach Laplace besitzt einen ähnlich großen Aufwand wie die Leibnizformel. Beide Verfahren eignen sich daher nicht in der Praxis.

Answer 1

Zu a)

Es gibt n! Permutationen also gibt es n! Summanden und jeder Summand besteht aus n+1 Faktoren.

Also n! * (n+1) Multiplikationen und n! Additionen.

insgesamt (n+2) * n! Operationen.

Mit der Stirlingformel für die Fakultät gibt das etwa (n+2)* (n/e)ⁿ * √(2*pi*n) Operationen.

Jede dauert eine Nanosekunde also 10 ^-9 s und 48 h sind 48*3600 s also muss gelten:

(n+2)* (n/e)ⁿ * √(2*pi*n) * 10 ^-9 s =  48*3600 s

(n+2)* n! * 10 ^-9 s =  48*3600 s

(n+2)* n! =  48*3600 *10⁹ = 1,728*10 ¹⁴

nun ist ja 20! schon 2,4*10¹⁸

also muss die Matrix kleiner als 20x20 sein.