www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Numerik linearer Gleichungssysteme" - Rechenaufw Laplace Entwicklung
Rechenaufw Laplace Entwicklung < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Numerik linearer Gleichungssysteme"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Rechenaufw Laplace Entwicklung: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 18:49 So 02.04.2006
Autor: becreative


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.

        
Bezug
Rechenaufw Laplace Entwicklung: 2^n stimmt nicht edit
Status: (Antwort) fertig Status 
Datum: 21:06 So 02.04.2006
Autor: mathemaduenn

Hallo becreative,
[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]

Bezug
                
Bezug
Rechenaufw Laplace Entwicklung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
Rechenaufw Laplace Entwicklung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:44 Do 13.04.2006
Autor: mathemaduenn

Hallo becreative,
[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]
viele grüße
mathemaduenn

Bezug
                        
Bezug
Rechenaufw Laplace Entwicklung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:41 Do 13.04.2006
Autor: felixf

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 "

Diese Stelle kann man uebrigens ueber Amazons `search inside' nachlesen :-) (siehe []hier)

Ich wuerd sagen, das ist eindeutig falsch und es ist nicht im geringsten nachzuvollziehen, wie der Autor auf diese Aussage gekommen ist; die Funktion $A(n)$ (von mathemaduenn) ist auch von einer wesentlichen Ordnung als [mm] $2^n$... [/mm]

LG Felix


Bezug
                
Bezug
Rechenaufw Laplace Entwicklung: Rekursionsformel stimmt
Status: (Mitteilung) Reaktion unnötig Status 
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.  

Bezug
                        
Bezug
Rechenaufw Laplace Entwicklung: Nachtrag: Iterative Formel
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
        
Bezug
Rechenaufw Laplace Entwicklung: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:20 Di 18.04.2006
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Numerik linearer Gleichungssysteme"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]