C++ lineare Gleichungssysteme lösen

  • Hallo, ich hoffe ihr könnt mir helfen. Ich möchte lineare Gleichungssysteme lösen. Die Umformung zur Diagonalform war nicht sonderlich schwer und klappt perfekt. Nur mit dem Rückwärtseinsetzten hapert es. Wenn ich beispielsweise 2 Zeilen vertausche kommen andere Werte raus. Könnt ihr mir helfen wie ich das auch noch schaffe. Ach ja, tut mir Leid, dass der Code etwas unstrukturiert ist, nachher schreibe ich auch noch eine Klasse... ich wollte mich nur erstmal mit den inhaltlichen Problemen auseinandersetzten:shiner:

    Einmal editiert, zuletzt von henriknikolas (9. März 2014 um 09:47)

  • Hab nur mal kurz drauf geschaut.

    Ich glaub dass es genau umgekehrt ist, dass Diagonalisieren funktioniert nicht, das Rückeinsetzen schon.

    Zumindest, wenn ich die erste mit der 2ten Zeile vertausche

    Code
    Matrix vor Diagonalisieren
    0|0|1|3|10
    0|2|1|1|11
    1|1|1|1|15
     0|2|1|4|23


    dann bekomme ich folgende Diagonalmatrix:

    Code
    0|0|1|3|10
    0|2|0|-2|1
    1|0|0|-1|4.5
    0|0|0|3|12

    Wenn man von der Reihenfolge der Zeilen absieht, ist das zwar eine Diagonalmatrix, allerdings sind die Lösungen dieser Matrix nicht mehr die selben wie bei der ersten.

    Wieso suchst du eigentlich in der aktuellen Zeile nach dem ersten Eintrag ungleich Null? Solltest du nicht nach dem erste Eintrag ungleich Null in der Spalte suchen. Schau dir mal diesen PseudoCode an: http://en.wikipedia.org/wiki/Gaussian_elimination#Pseudocode, der gibt dir im Grunde genau vor, was zu tun ist. Anstatt argmax kannst du auch immer die erste Zeile, bei der, der Eintrag ungleich Null ist, nehmen.

    Ich werde den Code jetzt nicht näher anschauen, da mich deine Notation ziemlich verwirrt. (Eventuell dich auch.)
    Normalerweise speichert man ein Gleichungssystem im Format Matrix[Zeile][Spalte] und nicht Matrix[Spalte][Zeile].

  • So ich hab das mit der Matrix[Zeile][Spalte] geändert. Hatte Mathe und C++ einfach ein bisschen durcheinander gewürfelt. Jetzt kommt man auf das gleiche Ergebnis. Ich versuch den Pseudocode auf Wikipedia mal zu verstehen, leider ist der ja auf Englisch. Meine Idee war bis jetzt das man immer eine Zeile setzt und die von den darunterliegenden abzieht, sodass eine Variable in der Zeile 0 wird. Dafür muss man den Quotienten der beiden Zeilen für die Variable, die eliminiert werden soll, bilden. Wenn das aber eine DIvision durch 0 ergibt... deshalb hab ich überprüft ob der Divisor 0 ist, ist jetzt auch schwer zu erklären.

  • Hab nur mal kurz drauf geschaut.

    Ich glaub dass es genau umgekehrt ist, dass Diagonalisieren funktioniert nicht, das Rückeinsetzen schon.

    Zumindest, wenn ich die erste mit der 2ten Zeile vertausche

    Code
    Matrix vor Diagonalisieren
    0|0|1|3|10
    0|2|1|1|11
    1|1|1|1|15
     0|2|1|4|23


    dann bekomme ich folgende Diagonalmatrix:

    Code
    0|0|1|3|10
    0|2|0|-2|1
    1|0|0|-1|4.5
    0|0|0|3|12


    So hab das jetzt mal gemacht und hab das folgende Ergebnis raus:
    0|2|1|1|11
    1|0|0.5|0.5|4.5
    0|0|1|3|15
    0|0|0|3|12
    Wahrscheinlich hast du vergessen Ergebnis[0] und Ergebnis[1] zu tauschen:cool:

  • Wahrscheinlich hast du vergessen Ergebnis[0] und Ergebnis[1] zu tauschen:cool:


    Kann sein.


    Jetzt ist der Code schon ein wenig übersichtlicher und auch die Diagonalmatrix stimmt, wenn man z.B. die erste Zeile mit der 3.ten tauscht.

    Der Code für's Rückeinsetzen funktioniert aber nur, wenn man wirklich eine Diagonalmatrix hat, sprich die Matrix beginnt in der ersten Zeile mit 0 Nuller, die 2. Zeile beginnt mit 1 Nuller, die 3. mit 2 Nuller, usw. Die Zeilen gehören allerdings noch sortiert. Du kannst dir das leicht überlegen. Beim zurückeinsetzten fängt man ja in der letzten Zeile an (wo alle Faktoren bis auf einen 0 sind) und berechnet die Lösung für die letzte Variable. Dann geht man zur vorletzten Zeile (wo alle bis auf die letzten 2 Faktoren Null sind) und berechnet daraus die Lösung für die vorletzte Variable. Usw.

    Ich bin mir nicht sicher, ob dein Code für's Diagonalisieren immer funktioniert. Normalerweise geht man so vor.

    • Man sucht eine Zeile, bei der die 1. Position ungleich 0 ist. Diese Zeile vertauscht man mit der ersten Zeile. Danach zieht man diese Zeile mit einem geeigneten Faktor von den darunter ab. Damit sichert man sich, dass in der ersten Spalte zuerst ein Element ungleich 0 ist und dann lauter 0er.
    • Dann sucht man eine Zeile, die an der 2. Position ungleich 0 ist. (die erste Zeile dürfen wir nicht mehr verwenden). Diese Zeile tauscht man wieder mit der 2. Zeile.
      Danach zeiht man diese Zeile von den darunter ab. Jetzt sind die ersten 2 Zeilen und die ersten 2 Spalten in Diagonalgestalt.
    • Dann sucht man eine Zeile, die an der 3. Position ungleich 0 ist. usw.


    Findet man einmal keine geeignete Zeile, so bedeutet dass, das dieses mind. 1 Gleichung linear von den anderen abhängt und man kann diese Matrix nicht diagonalisieren. Es gibt keine eindeutige Lösung.

    Ich hab mal deinen Code ein wenig umgeschrieben.

    Einmal editiert, zuletzt von Jakube (9. März 2014 um 13:52)

  • Stimmt, du hast volkommen Recht mit deiner Vorgehensweise. Es klingt auch sehr viel logischer als meins:engel:
    Auf jeden Fall funktioniert alles, wenn ich die Zeilen ändere. Vielen Dank nochmal.Ich werd das ganze dann noch mal auf vector ausbauen, dann kann ich (fast) beliebig große Gleichungssysteme einlesen

  • Hab jetzt noch die Option eingefügt, dass man ein eigenes Gleichungssystem eingeben kann, mit dem 2 dimensionalem dynamischen Array war es etwas kompliziert. Jetzt muss ich nur noch die Eingaben überprüfen, dass da nichts falsches eingegeben wird. Vielen vielen Dank nochmals

  • Am Schluss musst du noch die Matrix und den Ergebnis Vektor löschen.
    Also in etwa so

    Code
    for (int i = 0; i < max; i++)
       delete [] Matrix[i];
    delete [] Matrix;
    delete Ergebnis;
  • Code
    for (int i = 0; i < max; i++)
       delete [] Matrix[i];


    Mit diesen Anweisungen werden die Arrays gelöscht, auf die der Zeiger zeigt, nicht?

    Code
    delete [] Matrix;


    Und hier wird der Zeiger auf die Arrays gelöscht
    Nur so, ob ich es verstanden habe, weil das mit den dynamischen mehrdimensionalen Arrays mir neu ist

  • Code
    for (int i = 0; i < max; i++)
       delete [] Matrix[i];


    Mit diesen Anweisungen werden die Arrays gelöscht, auf die der Zeiger zeigt, nicht?

    Ja, stimmt.

    Code
    delete [] Matrix;


    Und hier wird der Zeiger auf die Arrays gelöscht
    Nur so, ob ich es verstanden habe, weil das mit den dynamischen mehrdimensionalen Arrays mir neu ist

    Stimmt fast. Es werden "die" Zeiger auf die Arrays gelöscht. Matrix ist im Grunde ja ein Array, in dem mehrere Zeiger gespeichert sind. Der erste Zeiger zeigt auf die erste Gleichung, der zweite Zeiger auf die 2. Gleichung, ... Dieses Array wird gelöscht.

  • Wenn man bei Google nach linearen Gleichungssystemen sucht findet man auch schnell das Wort Pivotisierung. Das ist doch das Zeilen vertauschen. Damit man das Gleichungssystem lösen kann oder damit die Ergebnisse genauer sind? Ich weiß über Gleichungssysteme nur aus dem letzten Schuljahr bescheid, als ich in der 8. Klasse war, deshalb frage ich lieber hier.

  • Ich hab jetzt ein bisschen noch am Code rumgebastelt, weil ich gelesen habe, dass man beim Zeilentauschen die Zeile mit dem größten Wert für Matrix[i][j] suchen soll, und die dann zum tauschen verwenden soll:


    Das klappt aber nicht immer, zum Beispiel beim folgenden Gleichungssystem nicht:
    2 4 2 1 2
    3 -3 1 0 -6
    1 1 -2 0 8
    4 -2 3 6 -10
    In der letzten Zeile steht als Koeffizient nach dem Diagonalisieren eine 0, das ergibt logischerweise einen Fehler. Wenn ich das Gleichungssystem allerdings so diagonalisiere, dass das erste Vorkommen von Matrix[i][j] != 0 verwendet wird, so wie du es gemacht hast, so klappt das Lösen ohne Probleme. Entweder meine Überlegung ist falsch, oder im Code ist ein offensichtlicher Fehler, den ich nicht sehe, so wie man manchmal den Wald vor lauter Bäumen nicht mehr sieht.

  • Entweder meine Überlegung ist falsch, oder im Code ist ein offensichtlicher Fehler, den ich nicht sehe, so wie man manchmal den Wald vor lauter Bäumen nicht mehr sieht.

    Ich habe ein wenig hinein-gedebuggt und gleich 3 schwere Fehler entdeckt.

    Meine Entdeckungen:

    1) Das Kriterium i=0 ist natürlich nicht ausschlaggebend dafür, dass man nicht Diagonalisieren kann. Es kann ja sein, dass der maximale Wert in der ersten Zeile (i=0) steht. Abbrechen soll das ganze, wenn val=0 ist.

    2) Trotzdem konnte das Programm die Matrix nicht diagonalisieren. Ich habe mir jedes Mal die Matrix ausgegeben, und gesehen, dass in der Schleife bei j=1 nur noch negative Zahlen in der 2. Spalte sehen. Da du nach einem Eintrag suchst, der größer 0 ist, bricht das ganze natürlich ab. Am besten du benutzt die fabs-Funktion. Außerdem kannst du die Abfrage if (Matrix[i][j] != 0) weglassen (stört nicht, bringt aber auch nichts).

    Code
    for (i = j; i < max; i++)
    {
       if (fabs(Matrix[i][j]) > val)
       {
          val = fabs(Matrix[i][j]);
          pos = i;
       }
    }


    Dazu muss man auch die Mathebibliothek einbinden.

    Code
    #include <math.h>


    Nun konnte das Programm die Matrix diagonalisieren, allerdings gab es noch immer falsche Ergebnisse. Mit weiterem Logging fand ich:

    3) Beim Zeilentauschen habe ich die Variable tmp als Integer definiert. Falls in einer zu tauschen Zeile eine Kommazahl steht, wird diese einfach abgeschnitten. Es sollte natürlich

    Code
    float tmp;

    sein.
    Ich muss zugeben, dass ich für diesen Fehler verantwortlich bin ;).
    Lustig dass dieser Fehler nicht früher aufgetreten ist. Man kann nie genug testen!

  • Super vielen Dank, das mit dem int hab ich gar nicht gesehen, obwohl ich mir ganz viele Stellen markiert und mit Kommentaren versehen hatte, hab wohl doch zu oberflächlich gelesen. Mit dem Betrag ist es logisch, da hab ich zu beschränkt gedacht, genauso mit dem Kriterium i = 0, das war husch husch hätte ich eigentlich auch selber drauf kommen können:mad:
    Vielen vielen Dank nochmals, ich benutze zur Zeit Borland C++ Builder 6, welche IDE benutzt du, ich hab mir mal Dev-C++ angeschaut, das war auch ganz gut, fand ich am Anfang aber ein bisschen unübersichtlich, kannst du mir vielleicht noch was empfehlen?


  • So hab jetzt alle Sachen verändert und siehe da, wer hätte es gedacht es funktioniert. Ich hab die gleiche Aufgabe bei einem Onlineprogram zum lösen eingegeben, und die Ergebnisse stimmten überein!!!


  • So hab jetzt alle Sachen verändert und siehe da, wer hätte es gedacht es funktioniert. Ich hab die Aufgabe gleich bei einem Onlineprogramm eingegeben und die Lösungen stimmten überein!!!

  • Ich bin leider kein Informatikstudent, sondern erst in der 9. Klasse:mad:, aber ich lad mir mal eine Testversion von chip herunter und probiere es aus. Ich nehme mal an, du verwendest Linux und g++, nicht?

    2 Mal editiert, zuletzt von henriknikolas (11. März 2014 um 21:45)

  • Ich hab mir jetzt mal eine Klasse zur Bruchrechnung gebastelt, weil die Rechnungen mit Brüchen ja genauer sind. Wenn ich jetzt eine Instanz dieser Klasse erstelle, kann ich Rechnen, die Werte über >> einlesen und über << ausgeben, halt wie auf Papier und so weiter...
    Allerdings funktioniert das Einlesen mit meinem 2-dimensionalen dynamischen Array irgendwie nicht, aber ohne Array funktioniert es. Ich habe im Hauptquellcode einfach alle float durch Bruch, das ist die Klasse für die Bruchrechung ersetzt. Ich schreibe hier nur die Methode fürs Einlesen und die der Hauptdatei, sonst wäre es viel zu lange. Wenn du die ganze Klasse brauchst, kann ich sie dir gerne schicken:

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!