Gauß-Seidel Verfahren, logischer Fehler

[ludden]

Hallo java-forum,
ich soll ein Gauß-Seidel Verfahren implementieren. Ist auch eigentlich ganz einfach. Hab den Pseudocode und hab ihn auch umgesetzt. Aber irgendwo ist ein logischer Fehler drinn und mein "Programm" zählt immer weiter hoch und nähert sich nicht den Werten an sonder sie Explodieren nach -unendlich und +unendlich. Aber jenachdem wie ich meinen Startwähle kommt auch das richtige Ergebnis raus irgendwo hab ich da also was falsch gemacht.

Hier mal noch der Link zum Algorithmus, er ist auch auf Wikipedia zu finden, aber dort finde ich ihn nicht so einfach erklärt.

Ich hoffe jmd kann den Fehler finden, sonst hab ich ein Problem
Vielen dank schonmal im Vorraus für die Hilfe.

public static void main(String[] args)
    {
        int n=3;
        double A[][]=new double [n][n];
        double b[]= new double[n];
        double x[]= new double[n];
        double x0[] = new double[n];
        double eps=0.1;

	//MATRIX
        A[0][0]=1;
        A[0][1]=2;
        A[0][2]=3;

        A[1][0]=4;
        A[1][1]=5;
        A[1][2]=6;

        A[2][0]=7;
        A[2][1]=8;
        A[2][2]=10;

        b[0]=1;
        b[1]=1;
        b[2]=1;
	
	//Startwert, frei Wählbar
        x0[0]=1;
        x0[1]=1;
        x0[2]=1;

	//Anzahl der Iterationsschritte
        int Nmax=300;

        for(int k=0;k<=Nmax;k++)
        {

            for(int i=0;i<n;i++)
            {
                double sum1=0;
                double sum2=0;
		//Erste Summe ausrechnen
                for(int j=0;j<i;j++)
                {
                    sum1 += A[i][j]*x[j];
                }
		//Zweite Summe ausrechnen
                for(int j=i+1;j<n;j++)
                {
   	                sum2 += A[i][j]*x0[j];

                }
		//x[i] mit den Zwei Summen berechnen
                x[i] = (-sum1 - sum2 + b[i])/A[i][i];

            }
	     //x0=x 
             for(int l=0;l<n;l++)
                {
                        double foo=x[l];
                        x0[l] = foo;
                }
             //Abbruchbedingung fällt aus Testzwecken weg
                            

        }
        System.out.println("x[0]="+x[0]+" x[1]= "+x[1]+" x[2]="+x[2]+"\n" );
    }

 

[Marco13]

Nachdem ich jetzt ca. eine Stunde gesucht habe, habe ich keinen Fehler gefunden, und das Thema mal abonniert, weil ich mich zusammen mit dir ärgern will, wenn jemand postet "In Zeile X muss nur statt des Y ein Z stehen, dann geht's". Andernfalls (d.h. bis mir jemand das Gegenteil beweist) bin ich jetzt erstmal davon überzeugt, dass das Gauss-Seidel-Verfahren in dieser Form (d.h. so wie es überall beschrieben ist) nicht funktioniert. (Jaja, nennt es meinetwegen "Provokation"...)

 

[bone2]

x = x0 fehlt am anfang
k soll mit 1 starten nicht mit 0

und du hast die if then abbruchbedingung nicht drinne, das ergbnis wird direkt beim schleifen abbruch ausgegeben

wo bei dir:

System.out.println("x[0]="+x[0]+" x[1]= "+x[1]+" x[2]="+x[2]+"\n" );

steht sollte eigentlich

System.out.println("failed");

stehen und nicht das nun wieder falsch gewordene ergebnis

 

[Marco13]

Hast du es getestet bzw. so geändert, dass es funktioniert?

 

[bone2]

ich weiß ja nicht was rauskommen soll

was ist das || x - x0|| ? betrag hat doch nur 1 |


was mich auch noch stört, die for shcleife im pseudocode geht bis n, das if darunter hat kein n, was ist n?

 

[frnky]

Also ich seh das so:

x muss beim ersten Durchlauf nicht belegt sein,da die Schleife dann nicht darauf zugreift.
Beim ersten Zugriff wurde x dann schon belegt.

Es ist praktisch egal, ob k bei 0 oder 1 startet.
So wird nur eine Abbruchbedningung erzeugt,damit keine endlosschleife entsteht.

Ohne if then Abbruchbedingung müsste das Ergebnis praktisch nur genauer werden und
wird dann am Ende der ersten for-Schleife für k>Nmax ausgegeben.

Auch die Implementierung mit if-then-Bedingung hat bei mir nicht zum richitgen Ergebnis geführt.

Mit ||x-x0|| ist eine allgemeine Norm gemeint.
Meines Wissen müsste eine Addition der Beträge der einzelnen Komponenten als Norm ausreichen.


Und die lezte Zeile ist nur Formsache.Die Ergebnisse werden halt zur Überprüfung ausgegeben.

Die Lösung sollte -1,1,0 ergeben

 

[ludden]

Sorry, dass es solange dauert bis ich schreibe , war noch unterwegs!

Nachdem ich jetzt ca. eine Stunde gesucht habe, habe ich keinen Fehler gefunden, und das Thema mal abonniert, weil ich mich zusammen mit dir ärgern will, wenn jemand postet "In Zeile X muss nur statt des Y ein Z stehen, dann geht's". Andernfalls (d.h. bis mir jemand das Gegenteil beweist) bin ich jetzt erstmal davon überzeugt, dass das Gauss-Seidel-Verfahren in dieser Form (d.h. so wie es überall beschrieben ist) nicht funktioniert. (Jaja, nennt es meinetwegen "Provokation"...)

Ja, ich habe auch die Vermutung, dass es nicht funktioniert, zumindest wenn ich es wie bei Wikipedia oder dem Skript gemäß umsetze, wegen den Änderungen siehe bei dem Zitat unten drunter. Diese dürften eigentlich keine Auswirkung haben!

Also ich seh das so:

x muss beim ersten Durchlauf nicht belegt sein,da die Schleife dann nicht darauf zugreift.
Beim ersten Zugriff wurde x dann schon belegt.

Es ist praktisch egal, ob k bei 0 oder 1 startet.
So wird nur eine Abbruchbedningung erzeugt,damit keine endlosschleife entsteht.

Ohne if then Abbruchbedingung müsste das Ergebnis praktisch nur genauer werden und
wird dann am Ende der ersten for-Schleife für k>Nmax ausgegeben.

Auch die Implementierung mit if-then-Bedingung hat bei mir nicht zum richitgen Ergebnis geführt.

Mit ||x-x0|| ist eine allgemeine Norm gemeint.
Meines Wissen müsste eine Addition der Beträge der einzelnen Komponenten als Norm ausreichen.


Und die lezte Zeile ist nur Formsache.Die Ergebnisse werden halt zur Überprüfung ausgegeben.

Die Lösung sollte -1,1,0 ergeben

Ja diese Lösung habe ich mit Matlab auch errechnet, aber es kommen ganz andere Werte raus. Ist die Umsetzung mit Java vlt nicht möglich? Ich kann ja jetzt schlecht zu meinem Prof gehen und sagen "hei gauß-seidel funktioniert nicht, ich will trotzdem die punkte" ! Vlt hat ja jmd einen funktionierenden Algorithmus
PS: ||x-x0|| ist wirklich die 2 Norm und wird mit sqrt(x1²+x2²+...xn²) errechnet

 

[bone2]

PS: ||x-x0|| ist wirklich die 2 Norm und wird mit sqrt(x1²+x2²+...xn²) errechnet

mist höhere mathematik...
kansnt du das für dieses beispiel in java ausdrücken?

    public static void main(String[] args)
    {
        int n=3;
        double A[][]=new double[n][n];
        double b[]= new double[n];
        double x[]= new double[n];
        double x0[] = new double[n];
        double eps=0.1;

    //MATRIX
        A[0][0]=1;
        A[0][1]=2;
        A[0][2]=3;

        A[1][0]=4;
        A[1][1]=5;
        A[1][2]=6;

        A[2][0]=7;
        A[2][1]=8;
        A[2][2]=10;

        b[0]=1;
        b[1]=1;
        b[2]=1;

    //Startwert, frei Wählbar
        x0[0]=1;
        x0[1]=1;
        x0[2]=1;

        x[0]=x0[0];
        x[1]=x0[1];
        x[2]=x0[2];

    //Anzahl der Iterationsschritte
        int Nmax=500;

        for(int k=1; k<=Nmax; k++) {

            for(int i=0;i<n;i++) {
                double sum1=0;
                double sum2=0;

                for(int j=0; j<i; j++) {
                    sum1 += A[i][j]*x[j];
                }

                //Zweite Summe ausrechnen
                for(int j=i+1;j<n;j++) {
                    sum2 += A[i][j]*x0[j];
                }

                //x[i] mit den Zwei Summen berechnen
                x[i] = (-sum1 - sum2 + b[i])/A[i][i];
            }
            for(int l=0; l<n; l++) {
//                if (/* || x[l]- x0[l] || < esp */) {
//                    System.out.println("x["+l+"]="+x[l]);
//                    // break;
//                }

                x0[l] = x[l];
            }
        }

        System.out.println("failed");
    }

 

[ludden]

mist höhere mathematik...
kansnt du das für dieses beispiel in java ausdrücken?

hast ein Array x[3]={1,23} dann ist die Norm
erg=Math.sqrt(Math.Pow(x[0],2)+Math.Pow(x[1],2)+Math.Pow(x[2],2))

 

[Marco13]

Natürlich "geht" es in Java, genau wie in jeder anderen Programmiersprache. Aber wenn ich heute mittag nicht vollkommen auf dem Schlauch stand, war das, was du gepostet hast, und was ich ausprobiert und durch mehrfaches Lesen verifiziert hatte, genau das, was auf allen Seiten als das Gauss-Seidel-Verfahren beschrieben ist, und was demnach (egal in welcher Spache) Mist liefert. der Gegenbeweis steht noch aus. Deinen Prof wird das nicht überzeugen. Aber vielleicht kannst du dann die Musterlösung hier posten. Wenn sie weniger als 20 Zeilen hat, kann man sie sich ja mal ansehen. Wenn sie mehr als 20 Zeilen hat, gehe ich davon aus, dass es nicht Gauss-Seidel ist, bzw. die Seiten, die die clevere, hübsche Iterationsformel von Wikipedia kopiert haben, schlicht etwas verschweigen, was mich im Detail dann aber auch nicht so brennend interessiert. Dass man so ein LGS mit der LU-Zerlegung lösen kann, ist auch klar, aber auf Basis dessen, was auf den Seiten steht, sehe ich keinen Grund, warum es notwendig sein sollte, die zu erstellen. A ist A und nicht U, L, L* oder L*^-1....

 

[Marco13]

Gauss-Seidel Method -- from Wolfram MathWorld sagt:
The Gauss-Seidel method is applicable to strictly diagonally dominant, or symmetric positive definite matrices A.

Dass dass sonst nirgendwo steht ist irritierend.

Mit

        double [][] A={{3,1,1},{1,5,2},{1,2,5}};
        double []   b={10, 21, 30};

findet er die richtige Lösung (1,2,5).

 

[ludden]

Gauss-Seidel Method -- from Wolfram MathWorld sagt:
The Gauss-Seidel method is applicable to strictly diagonally dominant, or symmetric positive definite matrices A.

Dass dass sonst nirgendwo steht ist irritierend.

Mit

        double [][] A={{3,1,1},{1,5,2},{1,2,5}};
        double []   b={10, 21, 30};

findet er die richtige Lösung (1,2,5).

Hm die Matrix, welche ich verwende wurde aber vorgegeben, vlt ist dem Prof da ein Fehler unterlaufen.
Muss ich mal nachhorchen. Könnte wirklich die Fehlerquelle sein!

Danke!

 

[henpara]

und? ist es die Fehlerquelle?

 

[ludden]

und? ist es die Fehlerquelle?

Kann ja eigentlich nur so sein, weil alle Matrzien die die Bedingung erfüllen, funktionieren. Die frage ist ob mein Prof das auch so anerkennt

 

[frnky]

ok,habs jetzt. spiel mal ein bisschen an den indizes!

 

[Marco13]

Poste mal ein bißchen code.

 

[ludden]

Ja das wäre mal ganz Interessant! Finde den Fehler nicht!