Verfasst am: 27.11.2009, 20:12
Titel: Programm zur Bestimmung der Determinante beliebiger Matrizen
Hallo, ich bin neu hier.
Ich bin Maschinenbaustudent und möchte mich nebenbei mal etwas in Matlab-Programmierung einarbeiten. Dazu habe ich mir eine kleine Funktion überlegt, nämlich das bestimmen der Determinante einer beliebig großen Matrix. (ich weiß die Funktion gibt es schon, aber es soll ja nur zu Übungszwecken sein )
Hier ist der Quellcode:
Ich möchte die Determinante über das Unterdeterminanteverfahren (Cramersche Regel) lösen.
Jetzt habe ich das Problem, dass ich immer das erste Element einer Zeile mit der Determinante der kleineren Matrix (also ohne der Zeile und Spalte des ersten Elements) multiplizieren muss.
Ich müsste also in diesem Teil "sum = sum + (-1)^(k+1)*A(1,k)* detn(A([C],[B]));" bei dem Aufruf der Rekursion die Matrix A um eine Spalte und Zeile verkleinern. Da die Spalte die weg kommt immer die Gleiche ist (nämlich die erste) ist das ganz einfach. Das ist mit der Menge C umgesetzt. Bei der Zeile springt die zu entfernende Zeile aber immer, sie ist immer das k, weshalb ich die Menge B so definiert habe.
Vom Gedanken her müsste das alles passen, ich bekomme aber dennoch nur Fehlermeldungen:
>> detn(A)
Nur quadratische Matrizen!
Error in ==> detn at 3
[n,m]=size(A);
??? Output argument "det" (and maybe others) not assigned during call
to "C:\Users\Frank\Documents\MATLAB\detn.m>detn".
Error in ==> detn at 15
sum = sum + (-1)^(k+1)*A(1,k)* detn(A([C],[B]));
Kann mir vielleicht jemand sagen was ich falsch mache?
Ich hoffe ich hab alles verständlich beschrieben, fällt mir gar nicht so leicht das verständlich auszudrücken
das Problem, in das du läufst: die erste Matrix oder eine bei den rekursiven Matrizen ist nicht quadratisch. Damit wird das Rückgabeargument det im Laufe des Codes nicht definiert, und es gibt den Fehler.
Das Problem dürfte sein, dass B in jeder Iteration der for-Schleife kleiner wird, was aber nicht beabsichtigt sein dürfte. Solchen Problemen kommt man am besten mit dem Debugger auf die Spur.
Hier vermutlich zu korrigieren:
das Problem, in das du läufst: die erste Matrix oder eine bei den rekursiven Matrizen ist nicht quadratisch. Damit wird das Rückgabeargument det im Laufe des Codes nicht definiert, und es gibt den Fehler.
Das Problem dürfte sein, dass B in jeder Iteration der for-Schleife kleiner wird, was aber nicht beabsichtigt sein dürfte. Solchen Problemen kommt man am besten mit dem Debugger auf die Spur.
Hier vermutlich zu korrigieren:
Code:
Bk = B(B~=k);
...
... * detn(A(C, Bk))
Bitte den Code per copy-paste einfügen, damit man ggf. auch was damit ausprobieren kann.
Grüße,
Harald
Danke erst mal, werde das ganze mal weiter ausprobieren und dann den Erfolg/Probleme schildern.
Nächstes mal werde ich den Code pasten, alles klar!
[n,m]=size(A); %Bestimmung der Anzahl an Spalten n und Zeilen m
B=1:n;
C=2:n;
if n == m %Abfrage: Ist Matrix quadratisch?
if n == 2 %Bei Dim. 2 einfache Lösung
det = A(1,1)*A(2,2)-A(2,1)*A(1,2);
elseif n>2 %Bei größerer Matrix Lösung durch Rekursion
det=0; %Lösung durch Unterdeterminantenverfahren
for k=1:n
Bk = B(B~=k);
det = det + (-1)^(k+1)*A(1,k)* detn(A([C],[Bk]));
end
Ich hab das ganze mal für kleinere Determinanten geprüft, läuft.
Jetzt hab ich eine quadratische Matrix der 23ten Dimension eingegeben, und mein PC ist schon seit ner halben Stunde am rechnen
Bin mal gespannt ob er auf ein Ergebnis kommt.
Ist so eine Lösung über Rekursion eigentlich sinnvoll oder im Allgemeinen nicht zu empfehlen? Das geht doch sicherlich ganz schön auf den Arbeitsspeicher und die CPU?!?
Ich werd mal versuchen eine zweite Funktion zu schreiben, die die Determinante anders löst, habe hier auf diesem Javascript ne relativ schnelle Variante gefunden http://www.arndt-bruenner.de/mathe/scripts/determinanten.htm
Mal sehn ob ich das hinbekomme.
das schnellste wird immer noch der in MATLAB eingebaute Befehl det sein.
Rechenzeit bei einer 23x23-Matrix: 0,3s.
Ob Rekursion sinnvoll ist oder nicht, hängt vom konkreten Problem ab. Wenn dadurch Rechenoperationen eingespart werden können, ist es sinnvoll. Wenn nicht, dann nicht.
Natürlich sind Rekursionen effizienter, bei denen man im nächsten Schritt mit einem Problem halber Größe rechnet, als Rekursionen, bei denen man (wie hier) in der nächsten Iteration mit einer nur minimal kleineren Matrix rechnet.
das schnellste wird immer noch der in MATLAB eingebaute Befehl det sein.
Rechenzeit bei einer 23x23-Matrix: 0,3s.
Ob Rekursion sinnvoll ist oder nicht, hängt vom konkreten Problem ab. Wenn dadurch Rechenoperationen eingespart werden können, ist es sinnvoll. Wenn nicht, dann nicht.
Natürlich sind Rekursionen effizienter, bei denen man im nächsten Schritt mit einem Problem halber Größe rechnet, als Rekursionen, bei denen man (wie hier) in der nächsten Iteration mit einer nur minimal kleineren Matrix rechnet.
Grüße,
Harald
Stimmt, Sinn macht es nur wenn der Rechenaufwand des Programms abnimmt. Bei mir mach ich mir aber weniger Gedanken um die Rechenkomplexität als über die Anzahl der Rekursionen.
Also in meinem Fall wird die ganze Geschichte schnell intensiv. Bei einer 3x3Matrix muss das System 3 mal das Programm neu laden, bei einer 4x4 Matrix 4*3 also gleich 12 mal. Das heißt die Anzahl der neu zu ladenenden Programme wäre bei einer 23x23 Matrix 23!/2, was immerhin
dieser Zahl enspricht: 12926008369442488320000.
Ich glaub da muss ich mir einen Supercomputer aus einem Forschungszentrum mieten.
if(A(i+j-1,j)~=0) && (A(i+j,j)~=0)
Wert1=A(i+j-1,j); %Wert in Spalte j auf der Diagonalen
Wert2=A(i+j,j); %Darunter liegender Wert
x(i)=Wert2/Wert1;
A(j+i,:)=A(j+i,:)/x(i); %Gleichmachen der Werte
Also beim Rang 23 ist das Programm gefühlsmäßig gleichschnell zum det(A)-Befehl vom Matlab.
Habe das ganze aber mal für 1200 gemacht, da hat mein Programm ca eine Minute gebraucht, und det(A) nur 2 oder 3 Sekunden.
Ich wüsste mal gerne, was die anders gemacht haben.
Gibt es nicht eine Möglichkeit sich den Quellcode der Befehle anzusehen?
Der ist vermutlich geheim, oder?
Geschwindigkeitsmäßig hat das den Vorteil, dass im Hintergrund optimierter C-Code läuft, was so ziemlich unschlagbar ist, was Performance angeht.
Edit: Ach ja... in deinem Programm solltest du noch ein paar for-Schleifen durch geschickte Vektor-Operationen ersetzen können.
Grüße,
Harald
Einstellungen und Berechtigungen
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
)
RSS