Probleme beim Lösen von linearem Gleichungssystem

Es gibt 29 Antworten in diesem Thema. Der letzte Beitrag () ist von Artentus.

    Probleme beim Lösen von linearem Gleichungssystem

    Hallo liebe Community.

    Wie ihr vielleicht wisst arbeite ich zurzeit an einer Mathemtikbibliothek: MathUtils
    Aufgrund einer Nachfrage möchte ich jetzt noch dreidimensionale Geraden einbauen. Auf Gleichheit und Parallelität kann ich bereits prüfen, jetzt wollte ich noch den Schnittpunkt berechnen. Dafür habe ich folgendes lineares Gleichungssystem aufgestellt:

    Quellcode

    1. I: p1.X + f1 * v1.X = p2.X + f2 * v2.X
    2. II: p1.Y + f1 * v1.Y = p2.Y + f2 * v2.Y
    3. III: p1.Z + f1 * v1.Z = p2.Z + f2 * v2.Z

    Da die Koordinaten bekannt sind, muss ich nun noch nach f1 und f2 auflösen. Das wollte ich so machen:

    Quellcode

    1. mit I: f1 = ((p2.X + f2 * v2.X) - p1.X) / v1.X
    2. in II: p1.Y + (((p2.X + f2 * v2.X) - p1.X) / v1.X) * v1.Y = p2.Y + f2 * v2.Y

    Wenn ich das dann ausrechne und in III einsetze könnte ich prüfen, ob ein Schnittpunkt existiert. Wenn ja, dann in einer der beiden Geradengleichungen einsetzen und fertig, soweit die Theorie.
    Mein Problem ist jetzt aber, dass ich diese letzte Zeile nicht nach f2 aufgelöst bekomme. Gibts irgendwelche Mathegenies unter euch, die das hinbekommen?

    Hi
    allgemein löst du LGS btw. afaik am besten über den Gauß-Algorithmus, da gibt's auch einen Wikipediaartikel dazu. Solltest du nicht eigentlich die Inverse schon über den Algorithmus berechnet haben oder hast du's direkt gemacht? Inverse wär' btw. das auflösen von einer m x m -Matrix M
    M | Id_m
    nach
    Id_m | M
    Id_m ist die Identitätsmatrix für eine m x m -Matrix (also einfach eine m x m-Matrix mit M_i,j = 1 für i = j, 0 sonst), solltest ja schon haben.

    Gruß
    ~blaze~

    @~blaze~
    Vielen Dank für den Tipp, aber ich kann dir da nicht ganz folgen. Wenn du das gaußsche Eliminationsverfahren meinst, wo hat das was mit der Inversen oder der Einheitsmatrix zu tun? Oder meinst du vielleicht den Gauß-Jordan-Algorithmus?
    Allerdings wüsste ich auch nicht so ganz, wie ich das auf das obige Problem anwenden sollte, im Artikel steht auf der rechten Seite ja immer nur eine Zahl.

    Ist das nicht beides das gleiche? Im Prinzip hast du ja ein LGS der Form
    a_11 * x_11 + ... + a_1n * x_1n = b1
    .
    .
    .
    a_m1 * x_m1 + ... + a_mn * x_mn = b_m

    Das LGS kannst du eben auch so darstellen, dass du eine Matrix aus den a-und b -Werten bildest. Bei der Inversen wird genau der Algorithmus angewendet (setzt aber eine quadratische Matrix voraus). Dabei wird eben eine linke Matrix M und eine rechte Matrix (Identitätsmatrix) verwendet und es werden die Zeilen so aufaddiert, dass auf der linken Seite die Identitätsmatrix entsteht (das eben über den Gaussalgo). Die rechte Matrix ist dann die Inverse.
    Naja, schau' dir den auf jeden Fall mal an, der ist nicht allzu schwer und relativ einfach umzusetzen (kannst sogar 'nen Optimierungsschritt machen).

    Gruß
    ~blaze~

    Implementier mal für die Matrix private Funktionen für
    - Multiplikation bzw. Division einer Zeile mit einem Faktor (Multp. genügt ja)
    - Addition zweier Zeilen
    - Vertauschung zweier Zeilen

    Voraussetzung für die Anwendung des GA mit endlicher bzw. nicht-leerer Lösungsmenge wäre ja, dass keine Spalte 0 ist und dass die Anzahl der Zeilen abzüglich der elminierbaren Zeilen (also Zeilen, die durch Addition eines Vielfachen anderer Zeilen in allen Spalten zu 0 werden können) der Anzahl der Spalten entspricht. Wenn die Matrix diese Voraussetzungen erfüllt, kannst du einfach alle Zeilen durchgehen (mit Laufvariable i), diese vollständig durch den Eintrag a_i,i dividieren (sodass eben a_i,i nach der Division zu 1 wird), außer a_i,i ist 0. Wenn a_i,i 0 ist, vertauscht du die Zeile mit der nächsten, für die der Wert in der i-ten Spalte ungleich 0 ist. Anschließend sorgst du für alle Zeilen j der Matrix, wo j != i ist, dass der Wert in Spalte i zu 0 wird. Dadurch erhältst du eben eine Einheitsmatrix auf der linken Seite und auf der rechten das Resultat (Inverse oder Lösung des LGS für den Vektor x, wenn nach x aufgelöst werden soll).
    Ich kann dir auch den Algorithmus noch mal in Programmform hinschreiben.

    Gruß
    ~blaze~

    @~blaze~
    Vielen Dank schon mal für diese ausführliche Erklärung. Ich habe einen Großteil schon umgesetzt, jedoch weiß ich nicht, wie ich den letzten Schritt implementieren soll (Zeile 59). Das ist mein bisheriger Code:
    Spoiler anzeigen

    C-Quellcode

    1. private void MultiplyRow(int row, double factor)
    2. {
    3. for (int x = 0; x < ColumnCount; x++)
    4. this[x, row] *= factor;
    5. }
    7. private void AddRows(int row1, int row2)
    8. {
    9. for (int x = 0; x < ColumnCount; x++)
    10. this[x, row1] += this[x, row2];
    11. }
    13. private void ChangeRows(int row1, int row2)
    14. {
    15. for (int x = 0; x < ColumnCount; x++)
    16. {
    17. var tempVal = this[x, row1];
    18. this[x, row1] = this[x, row2];
    19. this[x, row2] = tempVal;
    20. }
    21. }
    23. private SquareMatrix GetInverse()
    24. {
    25. var myClone = (SquareMatrix)this.Clone();
    26. var result = SquareMatrix.GetIdentity(Size);
    28. //Diagonale auf 1 setzen
    29. for (int i = 0; i < Size; i++)
    30. {
    31. var next = i;
    32. while (myClone[i, i] == 0) //nächste gültige Zeile ermitteln
    33. {
    34. next++;
    36. if (next >= Size) //keine gültige Zeile vorhanden
    37. throw new InvalidOperationException();
    39. if (myClone[next, i] != 0)
    40. {
    41. //aktuelle Zeile mit gültiger Zeile austauschen
    42. myClone.ChangeRows(i, next);
    43. result.ChangeRows(i, next);
    44. }
    45. }
    47. //Zeile so multiplizieren, dass (i,i) 1 wird
    48. var f = 1 / myClone[i, i];
    49. myClone.MultiplyRow(i, f);
    50. result.MultiplyRow(i, f);
    51. }
    53. //Rest auf 0 setzen
    54. for (int x = 0; x < ColumnCount; x++)
    55. for (int y = 0; y < RowCount; y++)
    56. {
    57. if (x != y) //Diagonale auslassen
    58. {
    59. //und jetzt?
    60. }
    61. }
    63. return result;
    64. }

    Wäre wohl noch praktisch, wenn du eine Methode definierst, die Addition und Multiplikation in einem einzigen Schritt macht.
    Subtrahiere einfach die x-te Zeile mit einem Faktor von der y-ten, sodass eine 0 drinsteht. Dadurch ergibt sich die Einheitsmatrix. Das ist, als würdest du den Gauß-Algorithmus optimiert auf dem Blatt rechnen. Ob es jetzt in der ausgeschriebenen Form oder als Matrix notiert wird, ist prinzipiell ja egal. ;)

    Das Verfahren lässt sich btw. noch optimieren. Es werden viele 0-Werte multipliziert.

    Gruß
    ~blaze~

    Nochmals vielen Dank, mit deiner Hilfe hab ich es jetzt hinbekommen:
    Spoiler anzeigen

    C-Quellcode

    1. private void MultiplyRow(int row, double factor)
    2. {
    3. for (int x = 0; x < ColumnCount; x++)
    4. this[x, row] *= factor;
    5. }
    7. private void SubtractRows(int row1, int row2, double factor)
    8. {
    9. for (int x = 0; x < ColumnCount; x++)
    10. this[x, row1] -= this[x, row2] * factor;
    11. }
    13. private void ChangeRows(int row1, int row2)
    14. {
    15. for (int x = 0; x < ColumnCount; x++)
    16. {
    17. var tempVal = this[x, row1];
    18. this[x, row1] = this[x, row2];
    19. this[x, row2] = tempVal;
    20. }
    21. }
    23. /// <summary>
    24. /// Berechnet die invertierte Matrix dieser quadratischen Matrix.
    25. /// </summary>
    26. /// <returns></returns>
    27. public SquareMatrix GetInverse()
    28. {
    29. var myClone = (SquareMatrix)this.Clone();
    30. var result = SquareMatrix.GetIdentity(Size);
    32. //Zeilen richtig anordnen
    33. for (int i = 0; i < Size; i++)
    34. {
    35. var next = i;
    36. while (myClone[i, i] == 0) //nächste gültige Zeile ermitteln
    37. {
    38. next++;
    40. if (next >= Size) //keine gültige Zeile vorhanden
    41. throw new InvalidOperationException();
    43. if (myClone[next, i] != 0)
    44. {
    45. //aktuelle Zeile mit gültiger Zeile austauschen
    46. myClone.ChangeRows(i, next);
    47. result.ChangeRows(i, next);
    48. }
    49. }
    50. }
    52. //Zeilen subtrahieren
    53. for (int x = 0; x < ColumnCount; x++)
    54. for (int y = 0; y < RowCount; y++)
    55. if (x != y) //Diagonale auslassen
    56. {
    57. var f = myClone[x, y] / myClone[x, x]; //Faktor berechnen
    58. myClone.SubtractRows(y, x, f);
    59. result.SubtractRows(y, x, f);
    60. }
    62. //Diagonale auf 1 setzen
    63. for (int i = 0; i < Size; i++)
    64. {
    65. //Zeile so multiplizieren, dass (i,i) 1 wird
    66. var f = 1 / myClone[i, i];
    67. myClone.MultiplyRow(i, f);
    68. result.MultiplyRow(i, f);
    69. }
    71. return result;
    72. }

    Beim Beispiel auf Wikipedia erhalte ich das richtige Ergebnis, und zwar um einiges Effizienter als bei meiner alten Methode adj(A) / det(A). :thumbup:
    Jedoch glaube ich, dass der Algorithmus bei manchen Matrizen versagen kann, die eigentlich lösbar sein müssten. Das Problem liegt in diesem Abschnitt:

    C-Quellcode

    1. for (int i = 0; i < Size; i++)
    2. {
    3. var next = i;
    4. while (myClone[i, i] == 0) //nächste gültige Zeile ermitteln
    5. {
    6. next++;
    8. if (next >= Size) //keine gültige Zeile vorhanden
    9. throw new InvalidOperationException();
    11. if (myClone[next, i] != 0)
    12. {
    13. //aktuelle Zeile mit gültiger Zeile austauschen
    14. myClone.ChangeRows(i, next);
    15. result.ChangeRows(i, next);
    16. }
    17. }
    18. }

    Hier werden die Zeilen sortiert, damit man in der Diagonalen nicht 0 stehen hat. Das Problem ist aber, dass so auch Zeilen verschoben werden könnten, die eigentlich an einer anderen Position benötigt werden, wobei für die jeweils aktuelle Stelle auch eine andere Zeile möglich wäre. Bsp.:

    Quellcode

    1. 0 0 2
    2. 1 4 0
    3. 2 0 3

    Bei dieser Matrix würde der Algorithmus Zeile 2 auf Position 1 verschieben. Somit bleibt für Zeile 2 keine Gültige Zeile mehr übrig. Der Algorithmus müsste also eigentlich Zeile 3 auf Position 1 verschieben. Ich weiß aber nicht, wie ich das ohne sehr viele Schleifen lösen könnte.


    Und noch was: Wie löse ich jetzt damit mein LGS?

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Artentus“ ()

    ich bin mittm Gauss nicht sehr bekannt - welche Diagonale darf keine 0 enthalten? Die fallende Diagonale - richtig?

    Ja, das wird ein Optimierungs-Problem, also ein fröhliches Ausprobieren aller Möglichkeiten. Bei so Ausprobier-Algos ists ein Prinzip, zunächst die Items mit den wenigsten "Freiheitsgraden" zu verwenden. Also Zeile#1 hat nur eine Mögliche Position, nämlich an dritter stelle. Wenndedann die Freiheiten für den Rest neu berechnest, stellst fest, dass nun Zeile#3 nurnoch eine Freiheit hat. Und im nächsten Durchgang ists zeile#2, die nur noch eine Freiheit hat, und Problem solved.

    hier brauch man glaub die Freiheiten auch nichtmal jedesmal neu berechnen.
    Es sind Datensätze zu schaffen, die den Freiheitsgrad mitführen.
    Und dann ein rekursives ausprobieren aller Möglichkeiten, wobei die Möglichkeiten in Reihenfolge der Freiheitsgrade abgearbeitet werden.

    Dieser Algo führt im Obigen Beispiel wie gezeigt ohne Rekursion direkt auf eine Lösung, aber auch für wesentlich umfangreichere Matritzen wird sehr effektiv bereits frühzeitig eine gangbare Lösung angesteuert.
    Mühsam wirds bei Matritzen ohne Lösung, denn da werden dann eben doch alle Möglichkeiten durchprobiert.
    Aber unlösbare Matritzen müssteste halt von vornherein ausschließen - kann ja nicht so kompliziert sein.

    Unlösbare Matrizen könnte ich schon ausschließen, die Frage ist nur, ob es das wert wäre. Meines Wissens nach kann man das nur prüfen, indem man die Determinante berechnet und diese dann auf ungleich 0 prüft. Dabei wäre aber viel Rekursion erforderlich, die in dem Fall, dass die Matrix lösbar ist, viel unnötige Performance zieht. Von daher wäre es glaube ich geschickter, das direkt mit zu prüfen.

    Wie gesagt, eine leere Lösungsmenge haben lineare Gleichungssysteme nur dann, wenn abgesehen von einem Faktor mehr voneinander verschiedene Zeilen vorhanden sind, als Unbekannte. Wenn weniger Gleichungen vorhanden sind, als Unbekannte, hat man nat. unendlich viele Lösungen. Die Anzahl der bis auf einen Faktor voneinander verschiedenen Zeilen wird btw. auch als Rang einer Matrix bezeichnet. Z.B. hat die Matrix
    1 | 2
    2 | 4
    den Rang 1, da ja die 2. Gleichung der 1. entspricht. Wenn also M eine n x n-Matrix ist, gilt für die Lösungsmenge des LGS, dass es
    - genau eine Lösung hat, wenn rang(M) = n
    - unendlich^(n-rang(M)) viele Lösungen hat, wenn rang(M) < n
    - keine Lösung hat, wenn rang(M) > n
    die Bestimmung des Ranges folgt bereits aus dem Gaussalgorithmus. Hast du eine Beispielmatrix, bei der das nicht funktioniert, sodass ich dir den Algorithmus anpassen kann? Ein effizienteres Verfahren zur Lösung ist mir btw. nicht bekannt.
    Aso: Bei der genannten Matrix oben wird halt dann Zeile 1 mit Zeile 2 vertauscht und im nächsten Schritt Zeile 2 mit Zeile 3 - sollte es zumindest. War mir bei der Formulierung des ganzen oben nicht mehr sicher, ob es nötig ist, dass man Vertauschung und Lösung in einem Schritt erledigt, wird aber wohl doch der Fall sein. Danach sollte es auf jeden Fall funktionieren, da der GA für beliebige Matrizen funktioniert.

    Gruß
    ~blaze~

    Das einzige Problem, das ich bemerkt hab' ist, dass es sein kann, dass sich Matrixzeilen beim Abschnitt "Zeilen subtrahieren" nochmal verändern, sodass die Vertauschung im Abschnitt "Zeilen richtig anordnen" falsch ist. Kannst du die beiden Codes nochmal vereinen, sodass vor der Division der Zeilen überprüft wird? Ansonsten kann es evtl. sein, dass durch 0 geteilt wird.

    Gruß
    ~blaze~

Facebook
Telefonspende