Rechenaufw Laplace Entwicklung < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
Hallo
kann mir jemand sagen wie man bei der Laplace Entwicklung auf einen
Rechenaufwand von ca. [mm] 2^{n} [/mm] Operationen kommt .
Ich verstehe das nicht ganz . Habe mir mal die Determinante von einer
3x3 und 4x4 Matrix ausgerechnet und da komme mit der Abschätzung nicht so richtig hin .
Also
bei einer 3x3 Matrix komme ich auf :
5 Additionen
9 Multiplikationen
=> insgesamt also 14 Operationen
das ist weit entfernt von [mm] 2^{3}Operationen [/mm]
bei einer 4x4 Matrix komme ich auf :
14 Operationen pro Streichungsmatrix
Bei 4 Streichungsmatritzen hat man dann
56 Operationen
Wenn man jetzt noch die Streichungsmatrizen aufaddiert und mit dem zugehörigen Element multipliziert kommen noch
7 Operation dazu , also dann insgesamt 63 Operationen
Bei der Abschätzung [mm] 2^{n}
[/mm]
kommt man nur auf 16 Operationen
Gruß
becreative
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo becreative,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Sicher stimmt das mit den [mm] 2^n [/mm] nicht. Für eine Matrix der Dimension n müsste man ja n Determinanten der Dimension n-1 berechnen dazu n Multiplikationen und n-1 Additionen. Wenn A(n) der Aufwand für die Dimension n wäre ergibt sich also
A(n)=n*A(n-1) +2n-1
Aus dem ersten Summanden allein ergibt sich ja das der Aufwand größer als n! ist( da A(2) ja größer 2 ist) und das ist auf jeden Fall mehr als [mm] 2^n [/mm] .
Wo hast Du das mit den [mm] 2^n [/mm] denn her?
viele Grüße
mathemaduenn
P.S. Ich hätte dann auch die gleichen Zahlen.
A(1)=0
A(2)=2*0+2*2-1=3
A(3)=3*3+2*3-1=14
A(4)=4*14+2*4-1=63
Edit: Dieser Ansatz ist (leider oder auch nicht  )selbst für den Laplaceschen Entwicklungssatz zu großzügig. Wie man sich an einem 4x4 Bsp. klar machen kann:
Schritt 1
[mm]\vmat{ 1 & 5 & 9 & 13 \\ 2 & 6 & 10 & 14\\ 3 & 7 & 11 & 15 \\ 4 & 8 & 12 & 16}=1*
\vmat{ 6 & 10 & 14\\ 7 & 11 & 15 \\ 8 & 12 & 16}-2*
\vmat{ 5 & 9 & 13\\ 7 & 11 & 15 \\ 8 & 12 & 16}+3*
\vmat{5 & 9 & 13 \\ 6 & 10 & 14\\ 8 & 12 & 16}-4*
\vmat{5 & 9 & 13 \\ 6 & 10 & 14\\ 7 & 11 & 15}[/mm]
Schritt 2
[mm] \vmat{ 6 & 10 & 14\\ 7 & 11 & 15 \\ 8 & 12 & 16}=6*\vmat{11 & 15 \\ 12 & 16}-7*\vmat{ 10 & 14\\12 & 16}+8*\vmat{10 & 14\\ 11 & 15}
[/mm]
[mm] \vmat{ 5 & 9 & 13\\ 7 & 11 & 15 \\ 8 & 12 & 16}=5*\vmat{11 & 15 \\ 12 & 16}-7*\vmat{9 & 13\\ 12 & 16}+8*\vmat{9 & 13\\ 11 & 15}
[/mm]
[mm] \vmat{5 & 9 & 13 \\ 6 & 10 & 14\\ 8 & 12 & 16}=5*\vmat{10 & 14\\ 12 & 16}-6*\vmat{9 & 13 \\12 & 16}+8*\vmat{9 & 13 \\ 10 & 14}
[/mm]
[mm] \vmat{5 & 9 & 13 \\ 6 & 10 & 14\\ 7 & 11 & 15}=5*\vmat{10 & 14\\ 11 & 15}-6*\vmat{9 & 13 \\ 11 & 15}+7*\vmat{9 & 13 \\ 10 & 14}
[/mm]
Für Schritt 2 müssen 6 2x2 Determinanten a 3 Operationen berechnet werden(18). Dann 4 3x3 Determinanten a 5 Operationen(20). Dann im Schritt 1 die Determinante mit nochmals 7 Operationen also insgesamt 45 Operationen.
Um alle zu berechnenden Unterdeterminanten zu bekommen muß man alle Möglichkeiten durchgehen aus 4 Zeilen 2 zu streichen also [mm] \vektor{4 \\ 2}=6
[/mm]
Wenn man diese Vorgehensweise systematisch durchgeht kommt man auf:
[mm]\sum_{i=2}^n \vektor{n \\ i}(2i-1)=\sum_{i=0}^n \vektor{n \\ i}(2i-1) -n +1=2*\sum_{i=0}^n \vektor{n \\ i}i -\sum_{i=0}^n \vektor{n \\ i}-n+1=n*2^n-2^n-n+1=(n-1)*(2^n-1)[/mm]
Dies enspricht aber immer noch nicht [mm] 2^n
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:26 Do 13.04.2006 | | Autor: | becreative |
Hallo
also das mit dem [mm] 2^{n} [/mm] habe ich aus Peter Deuflhard : Numerische Mathematik 1 Seite 4 . Dort steht :
" mit der rekursiven Bestimmung der Unterdeterminanten nach dem Laplaceschen Entwicklungssatz
det A = [mm] \summe_{i=1}^{n} (-1)^{n} a_{1i} [/mm] det [mm] A_{1i}
[/mm]
sind [mm] 2^{n} [/mm] Operationen auszuführen "
Gruß
BeCreative
|
|
|
| |
|
Hallo becreative,
![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]")
Ich habe mir noch überlegt das mein Ansatz mit der Brechstange natürlich nicht beachtet das man Unterdeterminanten so mehrmals berechnet. Auf [mm] 2^n [/mm] komme ich trotzdem nicht. ![[keineahnung]](/images/smileys/keineahnung.gif "[keineahnung]")
viele grüße
mathemaduenn
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:44 Di 08.03.2011 | | Autor: | rennradler |
Hallo,
die Formel [mm] 2^n [/mm] ist natürlich falsch.
Die angegebene Rekursionsformel
A(n)=n*A(n-1) +2n-1
stimmt schon. Es ist halt die Frage, wie man zählen möchte. Wenn man z.B. ein rekursives Programm schreibt, das die Determinante nach dem Entwicklungssatz von Laplacesche berechnet, dann werden gleiche Determinanten mehrmals berechnet. Für dieses Szenario liefert die Rekursionsformel die richtigen Werte.
Mir ist leider keine explizite Formel bekannt - das will nichts heißen. Ich vermute aber, daß es keine einfache Formel gibt, da
[mm] \limes_{n\rightarrow\infty} \bruch{A(n)}{n!} [/mm] = e
zu gelten scheint.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:11 Di 08.03.2011 | | Autor: | rennradler |
Eine iterative Formel wäre:
[mm] $A(n)=n!\summe_{i=1}^{n}\bruch{1}{i!}-2 [/mm] $
Die kann man leicht durch vollständige Induktion beweisen. Daraus ist auch der von mir oben angegebene Grenzwert abzulesen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Di 18.04.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
(siehe ![[]](/images/popup.gif){kind=small}
hier