Determinanatenberechnung einer Matrix in c++

[Taurin]

Walli schrieb:

Ja, auf Dreiecksform bringen, dann ist die Determinante das Produkt der Elemente auf der Hauptdiagonale mal der Anzahl der Zeilenvertauschungen hoch -1.

Äh, da hast du was bei der Potenz verdreht.
Wenn D die obere Dreiecksmatrix ist, die aus der (n x n)-Matrix A durch den Gauss-Algorithmus mit k Zeilenvertauschungen hervorgegangen ist, dann ist
$\det(A) = (-1)^{k} \cdot \Pi d_i$ mit $d_i$ Diagonalelemnte von D.

[MBCS-CITP]

Eine andere elegante Methode arbeitet mit dem Laplaceschen Entwicklungssatz. Dabei wird die Matrix jeweils um eine Dimension reduziert, bis man nur noch 2 x 2 Matrizen hat. Das laesst sich schoen als recursice Methode schreiben. Dabei vermeidet man die Rundungsfehler grosser Matrizen beim Gauss-Algorithmus.

[melb]

und das geht nur für matrizen mit mehr als 3 dim.?!

[Walli]

Taurin schrieb:

Walli schrieb:

Ja, auf Dreiecksform bringen, dann ist die Determinante das Produkt der Elemente auf der Hauptdiagonale mal der Anzahl der Zeilenvertauschungen hoch -1.

Äh, da hast du was bei der Potenz verdreht.
Wenn D die obere Dreiecksmatrix ist, die aus der (n x n)-Matrix A durch den Gauss-Algorithmus mit k Zeilenvertauschungen hervorgegangen ist, dann ist
$\det(A) = (-1)^{k} \cdot \Pi d_i$ mit $d_i$ Diagonalelemnte von D.

Richtig, meinte ich eigentlich auch , sorry. Hätte ich es sofort in Latex getippt wäre mir der Dreher nicht passiert.

MBCS-CITP schrieb:

Eine andere elegante Methode arbeitet mit dem Laplaceschen Entwicklungssatz. Dabei wird die Matrix jeweils um eine Dimension reduziert, bis man nur noch 2 x 2 Matrizen hat. Das laesst sich schoen als recursice Methode schreiben. Dabei vermeidet man die Rundungsfehler grosser Matrizen beim Gauss-Algorithmus.

Das dürfte recht ineffizient bei größeren Matrizen sein.

[MBCS-CITP]

Bei einer 2-dim Matrix ist die Sache relativ einfach:

D = a₁₁a₂₂-a₂₁a₁₂

Diesen Algorithmus schreibsts Du z. B. Berechne2Dim

Dann sieht die Methode etwa so aus (Pseudo-Code):

double Matrix::Determinate (Matrix   *pSource)
{
    if (pSource->GetDim () == 2)
        return pSource->Berechne2Dim ();
    else
        return pSource->Laplace (pSource);
}

double Matrix::Laplace (Matrix   *pSource)
{
    double     rFactor,
               rNegPos = 1.0,
               rReturn = 0.0;
    Matrix     clLaplac;
    MatrixCol *pCol;

    int        iLoop_x = 0,
               iLoop_Col_source,
               iLoop_Col_dest, 

               iDim_X;

    iDim_X = pSource->GetDim_X ();

    while (iLoop_x < pSource->GetDim_x ())
    {
        rFactor = Matrix [0, iLoop];

        iLoop_source = 0;
        iLoop_dest   = 0;
        while (iLoop_source < iDim_X)
        {
            if (iLoop_dest == iLoop_x)
                iLoop_dest++

            pCol = pSource->GetCol [iLoop_source];
            clLaplace->SetCol (&pCol [1], iLoop_dest);

            iLoop_source++;
            iLoop_dest++;
        }

        rReturn += rNegPos * rFactor * Determinate (&clLaplace);

        rNegPos = rNegPos * (-1.0);
        iLoop++
    }

    return rReturn;

So im Groben - die einzeln Methoden muessen noch mit Leben gefuellt werden, aber der grundsaetzliche weg sollte klar sein.

[Jester]

Walli schrieb:

MBCS-CITP schrieb:

Eine andere elegante Methode arbeitet mit dem Laplaceschen Entwicklungssatz. Dabei wird die Matrix jeweils um eine Dimension reduziert, bis man nur noch 2 x 2 Matrizen hat. Das laesst sich schoen als recursice Methode schreiben. Dabei vermeidet man die Rundungsfehler grosser Matrizen beim Gauss-Algorithmus.

Das dürfte recht ineffizient bei größeren Matrizen sein.

Es sei denn, man findet ne tolle Zeile oder Spalte nach der man entwickeln kann. Dann kann es natürlich viel Aufwand sparen. Vielleicht auch ne Mischung: mit Gauß ne schöne Zeile/Spalte basteln und dann nach der Entwickeln. Dabei vielleicht auch benutzen, daß es egal ist, ob man in den Zeilen oder den Spalten Gauß anwendet.

[MBCS-CITP]

Ich vermute stark, dass ein Laplace wirklich rechenaufwendiger waere (obwohl er eleganter aussieht), ich moechte aber zu bedenken geben, dass der Gauss-Algorithmus mittels Teilern arbeiten muss, d. h. man duerfte groessere Rundungsfehler habe. Um diese beim Gauss zu vermeiden wurden ganze Buecher geschrieben (Stichwort Pivot-Verfahren).

[Taurin]

Bitte korrigieren, wenn ich mich irre:
Der Aufwand, eine Determinate einer (n x n)-Matrix mit Laplace zu berechnen sei T(n). Um die Determinate einer (2 x 2)-Matrix zu berechnen, brauchen wir 2 Multiplikationen und eine Subtraktion, also T(2) = 3. Nehmen wir mal an, um die Determinate einer größeren Determinate zu berechen reiche es aus, n Determinaten von Matrizen der größe ((n-1) x (n-1)) zu berechnen. Wir müssen etwas mehr tun, aber das soll erstmal reichen. Also T(n) = n * T(n-1) = n * (n-1) * T(n - 2) = n * (n-1) * (n-3) * T(n - 3) = ... = n! / 2 * 3
Dagegen kommt Gauß mit einer Komplexität von O(n^3) daher und gewinnt in Sachen Geschwindigkeit um längen.

[Jester]

Taurin: Was wenn jetzt aber in einer Zeile oder Spalte nur ein oder zwei Zahlen nicht 0 sind. Dann kannste das Problem in ein oder zwei Probleme mit einer Ordnung weniger zerlegen. Das könnte schon was bringen.

Und wenn die Matrix noch nicht so günstig ist, dann kann man sie mit Gauß möglicherweise in ne günstigere Form bringen. Das meinte ich. Laplace pur und stumpf hingeschrieben ist natürlich völlig unbrauchbar.

[Taurin]

Ja, klar. Ich wollte nur MBCS-CITP nur noch mal vorführen, wie rechenaufwendig Laplace ist und ihn in seiner "vermutung" bestärken