Eliminationsverfahren: Unterschied zwischen den Versionen
Elias (Diskussion | Beiträge) |
Elias (Diskussion | Beiträge) |
||
(Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt) | |||
Zeile 3: | Zeile 3: | ||
Da wir nur ein allgemeines reguläres quadratisches lineares Gleichungssystem der Form Ax=b betrachten, können auf der Hauptdiagonalen von A Nulleinträge vorkommen. Aus vorherigem Abschnitt wissen wir, dass wir das LGS so umformen wollen, dass die Koeffizientenmatrix eine obere Dreiecksmatrix ist. Diese hat wegen der Regularität nur Einträge ungleich 0 auf der Diagonalen. | Da wir nur ein allgemeines reguläres quadratisches lineares Gleichungssystem der Form Ax=b betrachten, können auf der Hauptdiagonalen von A Nulleinträge vorkommen. Aus vorherigem Abschnitt wissen wir, dass wir das LGS so umformen wollen, dass die Koeffizientenmatrix eine obere Dreiecksmatrix ist. Diese hat wegen der Regularität nur Einträge ungleich 0 auf der Diagonalen. | ||
− | Wir wollen deshalb eine sogenannte Spaltenpivotierung durchführen. Hierbei wird zunächst ein Pivotelement in der Spalte gesucht, das betragsmäßig möglichst groß ist. Hierfür werden wird das Argmax der Beträge aller Einträge in der Spalte mit Zeilenindizes, die größer oder gleich dem Spaltenindize sind, bestimmt. Wegen Regularität ist dieser Eintrag stets ungleich 0. | + | Wir wollen deshalb eine sogenannte Spaltenpivotierung durchführen. Hierbei wird zunächst ein Pivotelement in der Spalte gesucht, das betragsmäßig möglichst groß ist. Hierfür werden wird das Argmax der Beträge aller Einträge in der Spalte mit Zeilenindizes, die größer oder gleich dem Spaltenindize sind, bestimmt. Wegen Regularität ist dieser Eintrag stets ungleich 0. Wir betrachten ein Beispiel für eine Implementierung durch Funktionen: |
− | <source lang=java> | + | <source lang="java"> |
− | + | ||
− | + | ||
− | + | ||
public static int Pivotindize (double[][] A, int Spalte) { | public static int Pivotindize (double[][] A, int Spalte) { | ||
//findet Indize, der >= Spaltenindizee ist, mit groesstem Eintrag in gegebener Spalte | //findet Indize, der >= Spaltenindizee ist, mit groesstem Eintrag in gegebener Spalte | ||
Zeile 22: | Zeile 19: | ||
return argmax; | return argmax; | ||
} | } | ||
− | |||
− | |||
</source> | </source> | ||
==Pivotierung und Elimination== | ==Pivotierung und Elimination== | ||
− | + | Anschließend vertauschen wir die Zeile mit dem Pivotelemt, sodass dieses auf der Hauptdiagonalen liegt. Hierbei ist zu beachten, dass zum System neben der Matrix die rechte Seite ebenfalls umgeformt werden muss. | |
− | + | ||
+ | Nun können wir die sogenannte Elimination durchführen, hierbei wird das c-fache der Zeile mit dem Pivotelement zu den Zeilen dadrunter addiert mit einem c, das so gewählt ist, dass bis auf Rechengenauigkeit unter dem Pivotelement sämtliche Einträge zu Nulleinträgen werden. Durch diese Nulleinträge können wir die gewünschte Struktur einer oberen Dreiecksmatrix erreichen. Wir betrachten ein Beispiel für eine Implementierung durch Funktionen: | ||
− | + | <source lang="java"> | |
public static void ZeilenTauschen (double[][] A, double[] b, int zeile1, int zeile2){ | public static void ZeilenTauschen (double[][] A, double[] b, int zeile1, int zeile2){ | ||
int n=b.length; | int n=b.length; | ||
Zeile 71: | Zeile 67: | ||
b[a]=b[a]+c*b[Pivotindize]; | b[a]=b[a]+c*b[Pivotindize]; | ||
} | } | ||
− | |||
</source> | </source> | ||
==Rückwärtseinsetzen== | ==Rückwärtseinsetzen== | ||
− | + | Wenn wir nun für jede Spalte außer die letzte obige Pivotierung und Elimination anwenden, erhalten wir ein neues LGS mit einer oberen Dreiecksmatrix als Systemmatrix wie gewünscht. Nun können wir leicht eine Lösung durch Rückwärtseinsetzen bestimmen, wie in der Motivation schon erklärt wurde. | |
− | + | Wir betrachten ein Beispiel für eine Implementierung durch Funktionen: | |
− | + | <source lang="java"> | |
public static double[] LGSloesen (double[][] A ,double[] b) { | public static double[] LGSloesen (double[][] A ,double[] b) { | ||
//loest regulaeres LGS Ax=b | //loest regulaeres LGS Ax=b | ||
Zeile 105: | Zeile 100: | ||
return x; | return x; | ||
} | } | ||
− | |||
</source> | </source> | ||
+ | |||
+ | Insgesamt können wir mit den obigen Funktionen also reguläre quadratische LGS beliebiger Größe lösen. Eine vollständige Implementierung mit Test an einem Beispiel folgt im letzten Abschnitt. |
Aktuelle Version vom 9. März 2020, 22:36 Uhr
Pivotsuche
Da wir nur ein allgemeines reguläres quadratisches lineares Gleichungssystem der Form Ax=b betrachten, können auf der Hauptdiagonalen von A Nulleinträge vorkommen. Aus vorherigem Abschnitt wissen wir, dass wir das LGS so umformen wollen, dass die Koeffizientenmatrix eine obere Dreiecksmatrix ist. Diese hat wegen der Regularität nur Einträge ungleich 0 auf der Diagonalen.
Wir wollen deshalb eine sogenannte Spaltenpivotierung durchführen. Hierbei wird zunächst ein Pivotelement in der Spalte gesucht, das betragsmäßig möglichst groß ist. Hierfür werden wird das Argmax der Beträge aller Einträge in der Spalte mit Zeilenindizes, die größer oder gleich dem Spaltenindize sind, bestimmt. Wegen Regularität ist dieser Eintrag stets ungleich 0. Wir betrachten ein Beispiel für eine Implementierung durch Funktionen:
public static int Pivotindize (double[][] A, int Spalte) { //findet Indize, der >= Spaltenindizee ist, mit groesstem Eintrag in gegebener Spalte int n =A.length; int argmax=Spalte; double max=Math.abs(A[Spalte][Spalte]); for(int i=Spalte+1;i<n;i++) { if(Math.abs(A[i][Spalte])>max) { max=Math.abs(A[i][Spalte]); argmax=i; } } return argmax; }
Pivotierung und Elimination
Anschließend vertauschen wir die Zeile mit dem Pivotelemt, sodass dieses auf der Hauptdiagonalen liegt. Hierbei ist zu beachten, dass zum System neben der Matrix die rechte Seite ebenfalls umgeformt werden muss.
Nun können wir die sogenannte Elimination durchführen, hierbei wird das c-fache der Zeile mit dem Pivotelement zu den Zeilen dadrunter addiert mit einem c, das so gewählt ist, dass bis auf Rechengenauigkeit unter dem Pivotelement sämtliche Einträge zu Nulleinträgen werden. Durch diese Nulleinträge können wir die gewünschte Struktur einer oberen Dreiecksmatrix erreichen. Wir betrachten ein Beispiel für eine Implementierung durch Funktionen:
public static void ZeilenTauschen (double[][] A, double[] b, int zeile1, int zeile2){ int n=b.length; //temporäre Hilfsvariablen double [] Azeile1vorher =new double[n]; for(int j=0;j<n;j++) { Azeile1vorher[j]=A[zeile1][j]; } double bzeile1vorher = b[zeile1]; //tauschen for(int j=0;j<n;j++) { A[zeile1][j]=A[zeile2][j]; A[zeile2][j]=Azeile1vorher[j]; } b[zeile1]=b[zeile2]; b[zeile2]=bzeile1vorher; //keine Rückgabe, da Arrays nicht primitiv } public static void PivotierungElimination (double[][] A, double[] b, int Spalte) { //Pivotelement soll vor Elimination auf der Diagonalen liegen int pivot=Pivotindize (A, Spalte); if(pivot>Spalte) { ZeilenTauschen (A, b, Spalte, pivot); } //Elimination: zu jeder Zeile mit Zeilenindize>Spaltenidize wird das c-fache der durch "Spalte" vorgegebenen Zeile addiert //c wird hierbei stets so gewaehlt, dass unter dem Pivotelement nur Nullen sind for(int i=Spalte+1;i<b.length;i++) { ZeileAddieren(A,b, -A[i][Spalte]/A[Spalte][Spalte] ,Spalte,i); } } public static void ZeileAddieren(double[][] A, double[] b, double c, int Pivotindize, int a) { // addiert das c-fache der Zeile mit Pivotelement zu Zeile a //(beachte, dass bei der Elimination das Pivotelement auf der Diagonalen liegt) for(int j=0;j<b.length;j++) { A[a][j]=A[a][j]+c*A[Pivotindize][j]; } b[a]=b[a]+c*b[Pivotindize]; }
Rückwärtseinsetzen
Wenn wir nun für jede Spalte außer die letzte obige Pivotierung und Elimination anwenden, erhalten wir ein neues LGS mit einer oberen Dreiecksmatrix als Systemmatrix wie gewünscht. Nun können wir leicht eine Lösung durch Rückwärtseinsetzen bestimmen, wie in der Motivation schon erklärt wurde. Wir betrachten ein Beispiel für eine Implementierung durch Funktionen:
public static double[] LGSloesen (double[][] A ,double[] b) { //loest regulaeres LGS Ax=b //umformen, sodass eine obere Dreiecksmatrix die Koeffizientenmatrix ist. for(int j=0;j<b.length-1;j++) { PivotierungElimination (A,b,j); } //nutze Algorithmus für LGS mit oberer Dreiecksmatrix als Koeffizientenmatrix double[] x=LGSobereDreiecksmatrix(A,b); return x; } public static double[] LGSobereDreiecksmatrix(double[][] A, double[] b) { //setze Werte rueckwaerts ein int n=b.length; double[] x=new double[n]; x[n-1]=b[n-1]/A[n-1][n-1]; for(int j= n-2;j>=0;j--) { double sum=0; for(int k=j+1;k<n;k++) { sum=sum+A[j][k]*x[k]; } x[j]=(b[j]-sum)/A[j][j]; } return x; }
Insgesamt können wir mit den obigen Funktionen also reguläre quadratische LGS beliebiger Größe lösen. Eine vollständige Implementierung mit Test an einem Beispiel folgt im letzten Abschnitt.