Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Anzahl Rechenoperationen für Determinante

Anzahl Rechenoperationen für Determinante

Universität / Fachhochschule

Determinanten

Tags: Determinant

Meyer5000 aktiv_icon

13:40 Uhr, 09.05.2021

Es seien

K

ein Körper,

n \in ℕ

und

A \in K^{(n, n)}

eine

n \times n -

Matrix. Bestimmen Sie die Anzahl der Rechenoperationen (Mulitplikation und Addition), die nötig sind, um

det (A)

zu berechnen.

a)

mit Gauß-Verfahren auf Zeilenstufenform bringen und Diagonale multiplizieren.

b)

mit der Leipnizformel.

Zu

a) :

Sei

A \in K^{(n, n)}

gegeben. Die Determinante einer

n \times n -

Matrix besteht aus

n!

Summanden, von denen jeder ein Produkt von

n

Zahlen ist. Also benötigt man für die Multiplikation

n! \cdot (n - 1)

Rechenoperationen. Bei der Addition müsste es dann doch ähnlich sein, oder?

Zu

b)

habe ich noch keinen Ansatz.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

kitingmachine aktiv_icon

13:46 Uhr, 09.05.2021

Du entwickelst ja nach einer Zeile oder Spalte d.h. du erhälst zunächst n terme. In jedem Term steht dann die Determinante einer (n-1)x(n-1) Determinante, diese wird wieder nach der Leibnitzformel entwickelt usw

Meyer5000 aktiv_icon

13:59 Uhr, 09.05.2021

Wenn wir

det A

mit Hilfe der Leibnizformel berechnen, erhalten wir doch

n!

Summanden, die aus jeweils

n + 1

Faktoren bestehen, oder? Das sollte dann

(n + 1) \cdot n! = (n + 1)!

Multiplikationen und

n!

Additionen ergeben oder?

Für Gauß:
erste Spalte:

n \cdot (n - 1)

Add. und Mult.
zweite Spalte:

(n - 1) \cdot (n - 2)

Add. und Mult.

. .

.
Zeilenstufenform:

2 \cdot 1

Add. und Mult.
Diagonale berechnen: 0 für Add. und

n

für Mult.

Das ergibt für die Multiplikation:

n + \sum_{i = 1}^{n - 1} i \cdot (i + 1) = \frac{n^{3} + 2 n}{3}

und für die Addition:

\sum_{i = 1}^{n - 1} i \cdot (i + 1) = \frac{n^{3} - n}{3}

Also insgesamt:

\frac{n \cdot (2 n^{2} + 1)}{3}

Meyer5000 aktiv_icon

14:51 Uhr, 09.05.2021

Hab gerade mal ein wenig recherchiert, scheint so richtig zu sein.

Angenommen, mir steht ein Computer zur Verfügung, der für jede Rechenoperation 5 Nanosekunden benötigt, also

5 \cdot 10^{- 9}

Sekunden. Wie groß kann die Matrix A maximal sein, sodass das Verfahren

(a)

bzw.

(b)

innerhalb von 2 Tagen terminiert?

Zunächst einmal gilt ja: 2 Tage

\Leftrightarrow 48

Stunden

\Leftrightarrow 2.880

Minuten

\Leftrightarrow 172.800

Sekunden.

Da ich für die Leibnizformel

(n + 1)!

Rechenoperationen benötige, benötige ich ja insgesamt

5 \cdot 10^{- 9} \cdot (n + 1)!

Sekunden für

n

Rechenschritte. Also muss ich doch berechnen:

5 \cdot 10^{- 9} \cdot (n + 1)! = 1728000

und dies dann nach

n

auflösen oder?

Für Gauß gilt dann:

5 \cdot 10^{- 9} \cdot \frac{n \cdot (2 n^{2} + 1)}{3} = 1728000

.

Ich habe allerdings noch keinen Rechner gefunden, der das für mich nach

n

auflöst xD

Meyer5000 aktiv_icon

19:05 Uhr, 09.05.2021

?????

Roman-22

20:48 Uhr, 09.05.2021

>

Ich habe allerdings noch keinen Rechner gefunden, der das für mich nach

n

auflöst xD
Da scheinst du aber nicht wirklich viel gesucht zu haben. Onkel Wolfram liefert dir bereitwillig die gesuchten

n = 37286

(klicke auf "Approximate form") bzw.

n = 15

is.gd/bDzjG3
is.gd/LwWMJi

Generell sollte aber jedes CAS diese Gleichungen lösen können.
Genauer gesagt sind es ja Ungleichungen, denn du suchst ja das größte (ganzzahlige)

n,

für das noch

... ... \leq 172800

gilt.

!!

in Deinem Text ist da jeweils eine Null zu viel!

Wollte man es als Gleichung lösen, müsste man die Faktoriellen mit der Gamma-Funktion beschreiben

\to

is.gd/6NTd1E

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1535533

1535511

	Status: nicht eingeloggt	Noch nicht registriert?