Matrix dividieren

Werbeanzeige

TLEP

Frischling

Beiträge: 22

Wohnort: bei Riesa

26.07.2006, 16:47

Matrix dividieren

hi,

so ich hab mal ein theoretisches Problem:
Auf Seite 83 (3. Auflage 3D-Spieleprogrammierung) wird erklärt, wie eine 3x3 Matrix invertiert wird. In dem Text steht: "Wir dürfen dieses Prinzip auch auf eine 4x4-Martix übertragen, wenn wir davon ausgehen, dass die rechte Spalte (0, 0, 0, 1) ist, was normalerweise auch der Fall ist - außer bei Projektionsmatrizen. ..." Aber ich komm nicht darauf, wie das funktionieren soll. Um genau zu sein, versteh ich nicht, wie D. Scherfgen den foglenden Code entwickelt hat:

C-/C++-Quelltext

TRIBASE_API tbMatrix tbMatrixInvert(const tbMatrix& m)
{
    // Kehrwert der Determinante vorberechnen

    float fInvDet = tbMatrixDet(m);
    if(fInvDet == 0.0f) return tbMatrixIdentity();
    fInvDet = 1.0f / fInvDet;

    // Invertierte Matrix berechnen

    tbMatrix mResult;
    mResult.m11 =  fInvDet * (m.m22 * m.m33 - m.m23 * m.m32);
    mResult.m12 = -fInvDet * (m.m12 * m.m33 - m.m13 * m.m32);
    mResult.m13 =  fInvDet * (m.m12 * m.m23 - m.m13 * m.m22);
    mResult.m14 =  0.0f;
    mResult.m21 = -fInvDet * (m.m21 * m.m33 - m.m23 * m.m31);
    mResult.m22 =  fInvDet * (m.m11 * m.m33 - m.m13 * m.m31);
    mResult.m23 = -fInvDet * (m.m11 * m.m23 - m.m13 * m.m21);
    mResult.m24 =  0.0f;
    mResult.m31 =  fInvDet * (m.m21 * m.m32 - m.m22 * m.m31);
    mResult.m32 = -fInvDet * (m.m11 * m.m32 - m.m12 * m.m31);
    mResult.m33 =  fInvDet * (m.m11 * m.m22 - m.m12 * m.m21);
    mResult.m34 =  0.0f;
    mResult.m41 = -(m.m41 * mResult.m11 + m.m42 * mResult.m21 + m.m43 * mResult.m31);
    mResult.m42 = -(m.m41 * mResult.m12 + m.m42 * mResult.m22 + m.m43 * mResult.m32);
    mResult.m43 = -(m.m41 * mResult.m13 + m.m42 * mResult.m23 + m.m43 * mResult.m33);
    mResult.m44 =  1.0f;

    return mResult;
}

Der Ansatz ist, wenn man eine Matrix a mit einer anderen Matrix b dividiert, multipliziert man a mit dem Kehrwert von Matrix b (s. auch Seite 67). Man braucht also den Kehrwert von Matrix b. Wenn man eine Matrix mit ihrer Kehrwert-Matrix multipliziert, bekommt man die Identitätsmatrix.
Nun steht an dieser Stelle im Buch, dass sich nun "...eine recht komplizierte Gleichung aufstellen..." läßt. Weiter wird nicht darauf eingegangen. Wenn man nun eine Matrix mit einer anderen Matrix multipliziert und als Ergebnis die Identitätsmatrix vorgibt, in etwa so:

Quellcode

|a._11 a._12 a._13 a.14|   |b._11 b._12 b._13 b.14|   |1 0 0 0|
|a._21 a._22 a._23 a.24|   |b._11 b._12 b._13 b.14|   |0 1 0 0|
|a._31 a._32 a._33 a.34| * |b._11 b._12 b._13 b.14| = |0 0 1 0|
|a._41 a._42 a._43 a.44|   |b._11 b._12 b._13 b.14|   |0 0 0 1|

und die einzelnen Rechnungen darstellt:

Quellcode

a._11*b._11 + a._12*b._21 + a._13*b._31 + a._14*b._41 = 1
a._11*b._12 + a._12*b._22 + a._13*b._32 + a._14*b._42 = 0
a._11*b._13 + a._12*b._23 + a._13*b._33 + a._14*b._43 = 0
a._11*b._14 + a._12*b._24 + a._13*b._34 + a._14*b._44 = 0

a._21*b._11 + a._22*b._21 + a._23*b._31 + a._24*b._41 = 0
a._21*b._12 + a._22*b._22 + a._23*b._32 + a._24*b._42 = 1
a._21*b._13 + a._22*b._23 + a._23*b._33 + a._24*b._43 = 0
a._21*b._14 + a._22*b._24 + a._23*b._34 + a._24*b._44 = 0

a._31*b._11 + a._32*b._21 + a._33*b._31 + a._34*b._41 = 0
a._31*b._12 + a._32*b._22 + a._33*b._32 + a._34*b._42 = 0
a._31*b._13 + a._32*b._23 + a._33*b._33 + a._34*b._43 = 1
a._31*b._14 + a._32*b._24 + a._33*b._34 + a._34*b._44 = 0

a._41*b._11 + a._42*b._21 + a._43*b._31 + a._44*b._41 = 0
a._41*b._12 + a._42*b._22 + a._43*b._32 + a._44*b._42 = 0
a._41*b._13 + a._42*b._23 + a._43*b._33 + a._44*b._43 = 0
a._41*b._14 + a._42*b._24 + a._43*b._34 + a._44*b._44 = 1

Die Matrix a ist jetzt gegeben und die Matrix b gesucht: also hat man hier vier Gleichungssysteme mit jeweil vier Unbekannten, die wiederum die einzelnen Elemente der Matrix b wiederspiegeln. Wenn ich jetzt daran denke, diese Geichungssysteme zu lösen(über Gauß'schen-Algorithmus oder "Einsetzverfahren"), weis ich schon jetzt das ich nicht auf die oben genannte Lösung kommen werde.

Ist mein Ansatz über das Lösen der Gleichungssysteme flasch oder zu umständlich? Gibt noch eine einfachere Möglichkeit?

Zum Seitenanfang

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

26.07.2006, 17:44

Dein Ansatz ist richtig, aber zu umständlich. David nutzt zum ausrechnen die Determinante der Matrix. Dass ermöglicht einen recht kompakten Algo zum Invertieren einer Matrix

Kannst doch mal im Inet oder in einem Buch dich zu dem Thema Determinante schlau machen.

PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

Zum Seitenanfang

TLEP

Frischling

Beiträge: 22

Wohnort: bei Riesa

26.07.2006, 19:29

Ok, aber ich seh irgendwie keine Berechnung einer Determinate für eine 4x4 Matrix im Buch. Ist die Funktion tbMatrixInvert(...) eigentlich auch für eine 4x4 Matrix, die Determinate wird ja nur aus der oberen 3x3 Teilmatrix berechnet und die Werte für m14,m24,m34,m44 in der Funktion einfach auf 0 bzw. letztes auf 1 gesetz.
Hab was im Internet gefunden, für beliebig große Matrizen. Naja, da werd ich wohl noch weiter suchen...

Zum Seitenanfang

WarMuuh!!

Treue Seele

Beiträge: 170

26.07.2006, 21:17

wenn du so ne matrix hast:

	C-/C++-Quelltext
1 2 3 4	x x x y x x x y x x x y 0 0 0 1

dann is die determinante = die determinante alle x
und da denk ich weißt du ja, wie man die determinante ausrechnet

Zum Seitenanfang

TLEP

Frischling

Beiträge: 22

Wohnort: bei Riesa

26.07.2006, 21:23

ja genau das ist es ja was ich nicht will... ich möchte das mal etwas allgemeiner machen. Es soll für jede belibige Matrix eine Invertion ermöglicht werden.
Ich glaube das geht wohl doch nur über das Lösen der Gleichungsysteme.

Zum Seitenanfang

WarMuuh!!

Treue Seele

Beiträge: 170

26.07.2006, 21:25

naja, nein, gugg dir mal den laplaceschen entwicklungssatz an, das da oben is n spezialfall von dem...

Zum Seitenanfang

TLEP

Frischling

Beiträge: 22

Wohnort: bei Riesa

26.07.2006, 21:28

Ok das werd ich machen, obwohl ich darüber noch nix weis

Ich freu mich schon wieder darauf, was neues zu lernen!

Zum Seitenanfang

TLEP

Frischling

Beiträge: 22

Wohnort: bei Riesa

27.07.2006, 00:47

Musste grade feststellen, dass der Laplaceschen Entwicklungssatz nur für die Berechnung der Determinante zuständig ist. Wie kann ich jetzt mit deren Hilfe eine nicht umständliche Manipulation der Matrix durchführen, so dass ich als Ergebnis die invertierte Matrix bekomme?

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

27.07.2006, 06:23

Also, erst einmal muss gesagt werden, dass man nicht jede Matrix invertieren kann.
Es gibt zum Invertieren von Matrizen auch einen Wikipedia-Artikel: http://de.wikipedia.org/wiki/Inverse_Matrix
Dort sind auch die Formeln für Matrizen der Größe 2x2 und 3x3 angegeben.
Siehe außerdem: http://de.wikipedia.org/wiki/Adjunkte

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

TLEP

Frischling

Beiträge: 22

Wohnort: bei Riesa

27.07.2006, 16:25

Ok, jetzt hab ichs hin bekommen... Danke an euch!
Ich poste mal meine Lösung, ihr könnt ja evtl. Fehler und Kritik schreiben!

Also:
1. Determinante berechnen

Ich hab die Determinante(Det.) über den Laplace'schen Entwicklungssatz ermittelt.

Quellcode

| _11 _12 _13 _14|
| _21 _22 _23 _24|
| _31 _32 _33 _34| -> determinieren
| _41 _42 _43 _44|

          |_22 _23 _24|       |_21 _23 _24|       |_21 _22 _24|       |_21 _22 _23|
Det.= _11*|_32 _33 _34| - _12*|_31 _33 _34| + _13*|_31 _32 _34| - _14*|_31 _32 _33|
          |_42 _42 _44|       |_41 _42 _44|       |_41 _42 _44|       |_41 _42 _43|

Man multipliziert nich einfach mit den vier 3x3 Matrizen, sondern rechnet wiederum ihre Det. aus:

Quellcode

|_22 _23 _24|
|_32 _33 _34| -> _22*( _33*_44 - _43*_34 ) - _23*( _32*_44 - _42*_34 ) + _24*( _32*_43 - _42*_33 )
|_42 _43 _44|

|_21 _23 _24|
|_31 _33 _34| -> _21*( _33*_44 - _43*_34 ) - _23*( _31*_44 - _41*_34 ) + _24*( _31*_43 - _41*_33 )
|_41 _43 _44|

|_21 _22 _24|
|_31 _32 _34| -> _21*( _32*_44 - _42*_34 ) - _22*( _31*_44 - _41*_34 ) + _24*( _31*_42 - _41*_32 )
|_41 _42 _44|

|_21 _22 _23|
|_31 _32 _33| -> _21*( _32*_43 - _42*_33 ) - _22*( _31*_43 - _41*_33 ) + _23*( _31*_42 - _41*_32 )
|_41 _42 _43|

Diese vier "Teil-Det." werden nun oben eingesetzt:

Quellcode

Det.=  _11*( _22*( _33*_44 - _43*_34 ) - _23*( _32*_44 - _42*_34 ) + _24*( _32*_43 - _42*_33 ) )
     - _12*( _21*( _33*_44 - _43*_34 ) - _23*( _31*_44 - _41*_34 ) + _24*( _31*_43 - _41*_33 ) )
     + _13*( _21*( _32*_44 - _42*_34 ) - _22*( _31*_44 - _41*_34 ) + _24*( _31*_42 - _41*_32 ) )
     - _14*( _21*( _32*_43 - _42*_33 ) - _22*( _31*_43 - _41*_33 ) + _23*( _31*_42 - _41*_32 ) )

2. Adjunkte berechnen

Eine Möglichkeit eine inverse Matrix zu erzeugen ist: die invertierte Det. multipliziert mit der Adjunkte(Adj). Die Adj. ist eine Matrix, die aus der Ausgangsmatrix ermittelt wird. Die einzelnen Elemente der Matrix werden wie folgt berechnet:
Das Element i, j der Adj. ist gleich (-1)^(i+j) * Det.( Mat.^(j, i) )

Diese Det. wird wieder nach dem Laplace'schen Entwicklungssatz berechnet, allerdings werden diesmal nicht die i'te Zeile und j'te Spalte gestrichen, sondern genau umgekehrt:

Quellcode

               ( |_22 _23 _24| )                   ( |_12 _13 _14| )
Adj.(_11)= Det.( |_32 _33 _34| )    Adj.(_12)=-Det.( |_32 _33 _34| )
               ( |_42 _43 _44| )                   ( |_42 _43 _44| )

               ( |_12 _13 _14| )                   ( |_12 _13 _14| )
Adj.(_13)= Det.( |_22 _23 _24| )    Adj.(_14)=-Det.( |_22 _23 _24| )
               ( |_42 _43 _44| )                   ( |_32 _33 _34| )

               ( |_21 _23 _24| )                   ( |_11 _13 _14| )
Adj.(_21)=-Det.( |_31 _33 _34| )    Adj.(_22)= Det.( |_31 _33 _34| )
               ( |_41 _43 _44| )                   ( |_41 _43 _44| )

               ( |_11 _13 _14| )                   ( |_11 _13 _14| )
Adj.(_23)=-Det.( |_21 _23 _24| )    Adj.(_24)= Det.( |_21 _23 _24| )
               ( |_41 _43 _44| )                   ( |_31 _33 _34| )

               ( |_21 _22 _24| )                   ( |_11 _12 _14| )
Adj.(_31)= Det.( |_31 _32 _34| )    Adj.(_32)=-Det.( |_31 _32 _34| )
               ( |_41 _42 _44| )                   ( |_41 _42 _44| )

               ( |_11 _12 _14| )                   ( |_11 _12 _14| )
Adj.(_33)= Det.( |_21 _22 _24| )    Adj.(_34)=-Det.( |_21 _22 _24| )
               ( |_41 _42 _44| )                   ( |_31 _32 _34| )

               ( |_21 _22 _23| )                   ( |_11 _12 _13| )
Adj.(_41)=-Det.( |_31 _32 _33| )    Adj.(_42)= Det.( |_31 _32 _33| )
               ( |_41 _42 _43| )                   ( |_41 _42 _43| )

               ( |_11 _12 _13| )                   ( |_11 _12 _13| )
Adj.(_43)=-Det.( |_21 _22 _23| )    Adj.(_44)= Det.( |_21 _22 _23| )
               ( |_41 _42 _43| )                   ( |_31 _32 _33| )

3. Multiplikation von invertierter Det. und Adj.

Naja die Überschrift sagt eigentlich schon alles! Einfach jedes Element der Adj. mit der invertierten Det. multiplizieren. Ich hab das auch gleich mal in C++ geschrieben:

C-/C++-Quelltext

        inline T MatrixDet( void )
        {
            return  _11*( _22*( _33*_44 - _43*_34 ) + _23*( _42*_34 - _32*_44 ) + _24*( _32*_43 - _42*_33 ) ) +
                    _12*( _21*( _43*_34 - _33*_44 ) + _23*( _31*_44 - _41*_34 ) + _24*( _41*_33 - _31*_43 ) ) +
                    _13*( _21*( _32*_44 - _42*_34 ) + _22*( _41*_34 - _31*_44 ) + _24*( _31*_42 - _41*_32 ) ) +
                    _14*( _21*( _42*_33 - _32*_43 ) + _22*( _31*_43 - _41*_33 ) + _23*( _41*_32 - _31*_42 ) );
        }
        inline Matrix<T> MatrixInvert( void )
        {
            T tdet = MatrixDet();
            if( tdet == 0 )
                return MatrixIdentity();//noch nicht fertig


            tdet = 1/tdet;

            return Matrix<T>(   tdet * ( _22*( _33*_44 - _43*_34) + _23*( _42*_34 - _32*_44 ) + _24*( _32*_43 - _42*_33 ) ),
                                tdet *-( _12*( _33*_44 - _43*_34) + _13*( _42*_34 - _32*_44 ) + _14*( _32*_43 - _42*_33 ) ),
                                tdet * ( _12*( _23*_44 - _43*_24) + _13*( _42*_24 - _22*_44 ) + _14*( _22*_43 - _42*_23 ) ),
                                tdet *-( _12*( _23*_34 - _33*_24) + _13*( _32*_24 - _22*_34 ) + _14*( _22*_33 - _32*_23 ) ),

                                tdet *-( _21*( _33*_44 - _43*_34) + _23*( _41*_34 - _31*_44 ) + _24*( _31*_43 - _41*_33 ) ),
                                tdet * ( _11*( _33*_44 - _43*_34) + _13*( _41*_34 - _31*_44 ) + _14*( _31*_43 - _41*_33 ) ),
                                tdet *-( _11*( _23*_44 - _43*_24) + _13*( _41*_24 - _21*_44 ) + _14*( _21*_43 - _41*_23 ) ),
                                tdet * ( _11*( _23*_34 - _33*_24) + _13*( _31*_24 - _21*_34 ) + _14*( _21*_33 - _31*_23 ) ),

                                tdet * ( _21*( _32*_44 - _42*_34) + _22*( _41*_34 - _31*_44 ) + _24*( _31*_42 - _41*_32 ) ),
                                tdet *-( _11*( _32*_44 - _42*_34) + _12*( _41*_34 - _31*_44 ) + _14*( _31*_42 - _41*_32 ) ),
                                tdet * ( _11*( _22*_44 - _42*_24) + _12*( _41*_24 - _21*_44 ) + _14*( _21*_42 - _41*_22 ) ),
                                tdet *-( _11*( _22*_34 - _32*_24) + _12*( _31*_24 - _21*_34 ) + _14*( _21*_32 - _31*_22 ) ),

                                tdet *-( _21*( _32*_43 - _42*_33) + _22*( _41*_33 - _31*_43 ) + _23*( _31*_42 - _41*_32 ) ),
                                tdet * ( _11*( _32*_43 - _42*_33) + _12*( _41*_33 - _31*_43 ) + _13*( _31*_42 - _41*_32 ) ),
                                tdet *-( _11*( _22*_43 - _42*_23) + _12*( _41*_23 - _21*_43 ) + _13*( _21*_42 - _41*_22 ) ),
                                tdet * ( _11*( _22*_33 - _32*_23) + _12*( _31*_23 - _21*_33 ) + _13*( _21*_32 - _31*_22 ) ) );
        }

Zur Erkärung vieleicht noch: "Matrix" ist eine Template-Klasse und die beiden Funktionen sind in der Klasse definiert.

Diese Funktionen stimmen auch, da ich diese mit z.B.
mat*mat.MatrixInvert();
geprüft habe und als Ergebnis die Einheitsmatrix herausbekommen habe!

So jetzt nur noch eine "Kleinigkeit", David Scherfgen schrieb das nicht jede Matrix invertierbar sei. Wenn ich mir die Rechnung so anschaue, kann ich als einzigtest daraus schließen, dass wenn die Det. gleich null wird, eine Division nicht möglich ist.

Ist dies das Einzigste oder muss man noch mehr beachten?

Und: Danke, ohne das Forum wäre ich nicht so weit gekommen!

"A programmer is just a tool which converts coffeine into code"
(anonym)

Zum Seitenanfang

Werbeanzeige

spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Matrix dividieren

Matrix dividieren

C-/C++-Quelltext

Quellcode

Quellcode

C-/C++-Quelltext

Quellcode

Quellcode

Quellcode

Quellcode

C-/C++-Quelltext