EINI - Benutzerbeiträge [de]

Eliminationsverfahren

2020-03-09T21:36:11Z

Elias:

==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:

<source lang="java">
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;
}
</source>

==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){
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];
}
</source>

==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) {
//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;
}
</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.

Eliminationsverfahren

2020-03-09T21:22:01Z

Elias:

==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. Eine Implementierung könnte zum Beispiel folgend aussehen:

<source lang="java">
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;
}
</source>

==Pivotierung und Elimination==

<source lang="java">
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];
}
</source>

==Rückwärtseinsetzen==

<source lang="java">
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;
}
</source>

Eliminationsverfahren

2020-03-09T21:19:36Z

Elias:

==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. Eine Implementierung könnte zum Beispiel folgend aussehen:

<source lang=java>
package Gauß;

public class LGS {
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;
}

}
</source>

==Pivotierung und Elimination==

<source lang=Java>
package Gauß;

public class LGS {
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];
}
}
</source>

==Rückwärtseinsetzen==

<source lang=Java>
package Gauß;

public class LGS {
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;
}
}
</source>

Eliminationsverfahren

2020-03-09T21:14:45Z

Elias:

==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. Eine Implementierung könnte zum Beispiel folgend aussehen:

<source lang=java>
package Gauß;

public class LGS {
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;
}

}
</source>

==Pivotierung und Elimination==

<source lang=Java>
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];
}
</source>

==Rückwärtseinsetzen==

<source lang=Java>
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;
}
</source>

Implementierung des Eliminationsverfahrens

2020-03-09T21:08:01Z

Elias:

Wir testen den zuvor beschriebenen Algorithmus mit Hilfe folgender Implementierung, welche das Eliminationsverfahren mit Spaltenpivotierung an einem Beispiel anwendet. Hier können natürlich auch andere reguläre LGS, eventuell anderer Größe, gelöst werden.

<source lang="java">
package Gauß;

public class LGS {

public static void main (String[] args) {
double[][] A= {{3,1,6},{2,1,3},{1,1,1}};
double[] b= {2,7,4};
print2D(A);
System.out.println();
printVektor(b);
System.out.println();
printVektor(LGSloesen (A ,b));
}

public static void printVektor(double[] array) {
// gibt Array in Vektorschreibweise aus
System.out.print("(");
for(int i=0; i<array.length-1; i++) {
System.out.print(array[i] + ",");
}
System.out.print(array[array.length-1]);
System.out.println(")^T");
}

public static void print2D(double[][] A) {
// gibt quadr. 2D Array aus
int n=A.length;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
System.out.print(A[i][j] + " ");
}
System.out.println();
}
}

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;
}

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;
}

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];
}
}
</source>

Insgesamt liefert unser Programm die Ausgabe:

<source lang="java">
3.0 1.0 6.0
2.0 1.0 3.0
1.0 1.0 1.0

(2.0,7.0,4.0)^T

(19.0,-6.999999999999998,-8.0)^T

</source>

Hierbei handelt es sich zunächst um die Koeffizientenmatrix A, dann die rechte Seite b und zuletzt die errechnete Lösung x des LGS Ax=b. Auffällig ist, dass durch Rundungsfehler der Maschine der zweite Eintrag der errechneten Lösung von dem exakten Eintrag -7 abweicht.

Um entsprechende Rundungsfehler zu reduzieren, kann das System bereits vor dem Lösen verändert werden, sogenanntes Vorkonditionieren. Auch können Nachiterationen den Fehler reduzieren. Da Rundungsfehler jedoch aufgrund der Rechengenauigkeit im Allgemeinen jedoch nicht vollkommen verhindert werden können, spielen auch Algorithmen eine Rolle, die bei steigender Anzahl an Iterationen eine Konvergenz gegen die Lösung liefern können und dabei wesentlich schneller sind. Auch können bestimmte Matrixstrukturen wie Smmetrie und viele Nulleinträge genutzt werden. Solche iterative Löser und deren Fehlerabschätzungen werden in der Numerik, einem Bereich der Mathematik, eräutert. Dort gibt es viele weitere Anwendungsmöglichkeiten der Programmierung mit Java und dieses Beispiel sollte einen Einblick in die Anwendungsmöglichkeiten bieten.

Eliminationsverfahren

2020-03-09T21:07:18Z

Elias: /* Pivotsuche */

==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. Eine Implementierung könnte zum Beispiel folgend aussehen:

<source lang=java>
package Gauß;

public class LGS {

public static void main (String[] args) {
double[][] A= {{3,1,6},{2,1,3},{1,1,1}};
double[] b= {2,7,4};
print2D(A);
System.out.println();
printVektor(b);
System.out.println();
printVektor(LGSloesen (A ,b));
}

public static void printVektor(double[] array) {
// gibt Array in Vektorschreibweise aus
System.out.print("(");
for(int i=0; i<array.length-1; i++) {
System.out.print(array[i] + ",");
}
System.out.print(array[array.length-1]);
System.out.println(")^T");
}

public static void print2D(double[][] A) {
// gibt quadr. 2D Array aus
int n=A.length;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
System.out.print(A[i][j] + " ");
}
System.out.println();
}
}

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;
}

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;
}

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];
}
}
</source>

Implementierung des Eliminationsverfahrens

2020-03-09T21:00:08Z

Elias:

Wir testen den zuvor beschriebenen Algorithmus mit Hilfe folgender Implementierung, welche das Eliminationsverfahren mit Spaltenpivotierung an einem Beispiel anwendet. Hier können natürlich auch andere reguläre LGS, eventuell anderer Größe, gelöst werden.

<source lang="java">
package Gauß;

public class LGS {

public static void main (String[] args) {
double[][] A= {{3,1,6},{2,1,3},{1,1,1}};
double[] b= {2,7,4};
print2D(A);
System.out.println();
printVektor(b);
System.out.println();
printVektor(LGSloesen (A ,b));
}

public static void printVektor(double[] array) {
// gibt Array in Vektorschreibweise aus
System.out.print("(");
for(int i=0; i<array.length-1; i++) {
System.out.print(array[i] + ",");
}
System.out.print(array[array.length-1]);
System.out.println(")^T");
}

public static void print2D(double[][] A) {
// gibt quadr. 2D Array aus
int n=A.length;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
System.out.print(A[i][j] + " ");
}
System.out.println();
}
}

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;
}

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=A[Spalte][Spalte];
for(int i=Spalte+1;i<n;i++) {
if(A[i][Spalte]>max) {
max=A[i][Spalte];
argmax=i;
}
}
return argmax;
}

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];
}
}
</source>

Insgesamt liefert unser Programm die Ausgabe:

<source lang="java">
3.0 1.0 6.0
2.0 1.0 3.0
1.0 1.0 1.0

(2.0,7.0,4.0)^T

(19.0,-6.999999999999998,-8.0)^T

</source>

Hierbei handelt es sich zunächst um die Koeffizientenmatrix A, dann die rechte Seite b und zuletzt die errechnete Lösung x des LGS Ax=b. Auffällig ist, dass durch Rundungsfehler der Maschine der zweite Eintrag der errechneten Lösung von dem exakten Eintrag -7 abweicht.

Um entsprechende Rundungsfehler zu reduzieren, kann das System bereits vor dem Lösen verändert werden, sogenanntes Vorkonditionieren. Auch können Nachiterationen den Fehler reduzieren. Da Rundungsfehler jedoch aufgrund der Rechengenauigkeit im Allgemeinen jedoch nicht vollkommen verhindert werden können, spielen auch Algorithmen eine Rolle, die bei steigender Anzahl an Iterationen eine Konvergenz gegen die Lösung liefern können und dabei wesentlich schneller sind. Auch können bestimmte Matrixstrukturen wie Smmetrie und viele Nulleinträge genutzt werden. Solche iterative Löser und deren Fehlerabschätzungen werden in der Numerik, einem Bereich der Mathematik, eräutert. Dort gibt es viele weitere Anwendungsmöglichkeiten der Programmierung mit Java und dieses Beispiel sollte einen Einblick in die Anwendungsmöglichkeiten bieten.

Implementierung des Eliminationsverfahrens

2020-03-09T20:32:14Z

Elias: Die Seite wurde neu angelegt: „<source lang="java"> package Gauß; public class LGS { public static void main (String[] args) { double[][] A= {{3,1,6},{2,1,3},{1,1,1}}; double[] b= {2…“

<source lang="java">
package Gauß;

public class LGS {

public static void main (String[] args) {
double[][] A= {{3,1,6},{2,1,3},{1,1,1}};
double[] b= {2,7,4};
print2D(A);
System.out.println();
printVektor(b);
System.out.println();
printVektor(LGSloesen (A ,b));
}

public static void printVektor(double[] array) {
// gibt Array in Vektorschreibweise aus
System.out.print("(");
for(int i=0; i<array.length-1; i++) {
System.out.print(array[i] + ",");
}
System.out.print(array[array.length-1]);
System.out.println(")^T");
}

public static void print2D(double[][] A) {
// gibt quadr. 2D Array aus
int n=A.length;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
System.out.print(A[i][j] + " ");
}
System.out.println();
}
}

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;
}

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=A[Spalte][Spalte];
for(int i=Spalte+1;i<n;i++) {
if(A[i][Spalte]>max) {
max=A[i][Spalte];
argmax=i;
}
}
return argmax;
}

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];
}
}

</source>

Eliminationsverfahren

2020-03-09T20:29:32Z

Elias: Die Seite wurde neu angelegt: „==Pivotsuche== Da wir nur ein allgemeines reguläres quadratisches lineares Gleichungssystem der Form Ax=b betrachten, können auf der Hauptdiagonalen von A N…“

Motivation

2020-03-09T19:07:17Z

Elias:

==Einleitung==

Viele Probleme in der Mathematik lassen sich auf lineare Gleichungssysteme zurückführen. Im Folgenden wollen wir uns daher damit beschäftigen, wie man entsprechende LGS mithilfe eines Eliminationsverfahrens mit Spaltenpivotierung lösen kann und wollen insbesondere auf die Implementierung in Java eingehen. Diese Anwendung soll hierbei nur die Möglichkeiten von Java verdeutlichen und nicht auf eine Optimierung der Laufzeit oder Ausnutzung spezieller Besetzungsstrukturen von Matrizen beruhen.

Wir wollen letztlich eine Implementierung einer direkten Lösungsmethode für (reguläre, reelle) quadratische lineare Gleichungssysteme erstellen und diese anwenden. Die Implementierung basiert im Wesentlichen auf dem Gaußschen Eliminationsverfahren, welches durch diverse Veranstaltungen bekannt ist.

==Gestaffelte Systeme==

Wenn wir eine obere Dreiecksmatrix A als Koeffizientmatrix unseres regulären LGS haben, lässt sich dies leicht durch rückwärts einsetzen lösen:
In der letzten Zeile ist nur eine unbekannte Komponente des Vektors in einer linearen Gleichung, in der vorletzten Zeile gibt es nur zwei Unbekannte, wobei wir eine der Unbekannten schon durch vorherige bestimmen können und damit diese Gleichung uns durch Umstellen noch eine Unbekannte bestimmen lässt. So erhalten wir für Systeme der Form

a_11*x_1 + a_12*x_2 + ... + a_1n*x_n = b_1
a_22*x_2 + ... + a_2n*x_n = b_2
...
a_nn*x_n = b_n

folgenden Algorithmus:

==Sukzessives Rückwärtseinsetzen==

Da wir nur reguläre Systeme betrachten, müssen die Diagonaleinträge der oberen Dreiecksmatrix stets ungleich 0 nach Grundkenntnissen der Linearen Algebra sein. somit können wir durch Umstellen und Dividieren eine Lösung erhalten:

x_n = b_n / a_nn
x_j = (b_j- (a_j(j+1)*x_j+1 ... a_jn*x_n) )/a_jj

==Anwendung bei allgemeiner Koeffizientenmatrix==

Nach Grundkenntnissen der Linearen Algebra wissen wir, dass wir bei einem LGS folgende Rechenschritte vornehmen können, ohne die Lösung zu verändern:

(1) Wir können Zeilen vertauschen. Hierbei wird stets eine ganze Zeile der Matrix und der rechte entsprechende Vektoreintrag mit einer anderen Zeile und einem Vektoreintrag getauscht.
(2) Wir können alle Einträge der Matrix und des Vektors mit einer reellen Zahl ungleich 0 multiplizieren.
(3) Wir können zu einer Zeile eine andere hinzuaddieren.

Mit diesen Umformungen ist es stets möglich, ein reguläres LGS in die Form zu bringen, dass die Koeefizientenmatrix eine obere Dreiecksmatrix ist. Dieses Umformen bezeichnet man als Eliminationsverfahren, da wir so unter der Hauptdiagonalen die Elemente "eliminieren".
Anschließend können wir das LGS dann durch Rückwärtseinsetzen lösen.

Motivation

2020-03-09T18:53:50Z

Elias: /* Sukzessives Rückwärtseinsetzen */

Motivation

2020-03-09T18:26:21Z

Elias:

Beispiele

2020-03-09T18:15:15Z

Elias: /* Lösung von Gleichungssystemen */

=Übersicht über alle Beispiele=
Dieser Abschnitt enthält alle Beispeile aus dem EINI-Wiki.

==Lösung von Gleichungssystemen==
*[[Motivation]]
*[[Eliminationsverfahren]]
*[[Implementierung des Eliminationsverfahrens]]

Motivation

2020-03-09T18:10:06Z

Elias: /* Einführung in die Notation */

Motivation

2020-03-09T17:55:36Z

Elias: /* Einleitung */

Motivation

2019-12-02T12:59:40Z

Elias: Die Seite wurde neu angelegt: „==Einleitung== Viele Probleme in der Mathematik lassen sich auf lineare Gleichungssysteme zurückführen. Im Folgenden wollen wir uns daher damit beschäftige…“

Beispiele

2019-12-02T12:24:45Z

Elias: /* Lösung von Gleichungssystemen */

Beispiele

2019-12-02T12:22:22Z

Elias: /* Lösung von Gleichungssystemen */

=Übersicht über alle Beispiele=
Dieser Abschnitt enthält alle Beispeile aus dem EINI-Wiki.

==Lösung von Gleichungssystemen==
*[[Motivation]]
*[[Eliminationsverfahren]]
*[[Beispiel]]

Beispiele

2019-12-02T12:00:06Z

Elias:

=Übersicht über alle Beispiele=
Dieser Abschnitt enthält alle Beispeile aus dem EINI-Wiki.

==Lösung von Gleichungssystemen==
*[[Einfaches Beispiel]]

Beispiele

2019-12-02T11:59:18Z

Elias:

=Übersicht über alle Beispiele=
Dieser Abschnitt enthält alle Beispeile aus dem EINIWiki.

==Lösung von Gleichungssystemen==
*[[Einfaches Beispiel]]

Beispiele

2019-12-02T11:58:23Z

Elias: Die Seite wurde neu angelegt: „=Übersicht über alle Beispiele= ==Lösung von Gleichungssystemen== *Einfaches Beispiel“

=Übersicht über alle Beispiele=

==Lösung von Gleichungssystemen==
*[[Einfaches Beispiel]]

Hauptseite

2019-12-02T11:57:07Z

Elias:

<div id=mainpage_topbox>
<div id=mainpage_title>
<span>Willkommen im</span> EINI-Wiki
</div>
<div id=mainpage_title_text>
Eine Wiki zur Veranstaltung "Einführung in die Informatik für Logistiker, Wirtschaftsmathematiker und -ingenieure" der TU Dortmund
</div>
</div>

<div style="display:flex">
<div style="border: solid 1px #AAA; width:100%; margin-top: 0.5em; margin-right: 0.5em;">
<div class="box_head">
Übersicht
</div>
<div class="box_content" style="margin:0 ; padding: 0;">
{| class = "wikitable" width=100%
|+ Themenübersicht
! Thema !! Vorlesung !! Inhalt
|-
| rowspan="2" | Rechensysteme & Datendarstellung
| Vorlesung 1 (Kapitel 0)
| Einführung und Organisation
|-
| Vorlesung 2 (Kapitel 1)
| [[Dezimal- und Binärsystem|Dezimal- und Binärzahlen]], Darstellung von Zahlen, Darstellung von Zeichen, Darstellung logischer Werte, Umrechnung, Rechensysteme
|-
| Spezifikation - Algorithmus - Syntax & Semantik
| Vorlesung 3 (Kapitel 2)
| Entwurf, [[Probleme#Spezifikation|Spezifikation]], [[Algorithmus]], [[Syntax und Semantik]]
|-
| rowspan="3" | Kern imperativer Programmiersprachen
| Vorlesung 4 (Kapitel 3.1)
| [[Variable | Variablen]], [[Zuweisung|Zuweisungen]], [[Datentyp|primitive Datentypen]], [[Operator|Operatoren]]
|-
| Vorlesung 5 (Kapitel 3.2)
| [[Kontrollstrukturen]]: [[Sequenz|Sequenzen]], [[Block|Blöcke]], [[Fallunterscheidung]], [[Schleife|Schleifen]]: [[while]], [[do-while]]
|-
| Vorlesung 6 (Kapitel 3.3)
| [[Schleifen]]: [[for]], [[continue]], [[break]]
|-
| Funktion - Prozedur - Methode - Rekursion
| Vorlesung 7 (Kapitel 4)
| [[Unterprogramm|Unterprogramme]], [[Funktion|Funktionen]], [[Funktion|Aufruf]], [[Rekursion]]
|-
| rowspan="2" | Arrays - Internes Sortieren - Rekursive Datenstrukturen
| Vorlesung 8 (Kapitel 5.1)
| [[Array|Arrays]], [[Sortieren|Internes Sortieren]], Rekursive Datenstrukturen ([[Baum|Binär-Baum]], [[Heap]])
|-
| Vorlesung 9 (Kapitel 5.2)
| Abstrakte Datentypen am Beispiel des [[Heap]], [[Heapsort]]
|-
| rowspan="1" | Objektorientierte Programmierung - Einführung
| Vorlesung 10 (Kapitel 6)
| Aufbau eines [[Java]]-[[Programm]]s, [[Klasse|Klassen]], [[Objekt|Objekte]], Details zu [[Konstruktor|Konstruktoren]], [[Referenz|Referenzen]], [[Garbage Collector|Garbage Collection]], Übergabe von [[Parameter|Parametern]], [[Attribut|Klassenattribute]]
|-
| rowspan="2" | Objektorientierte Programmierung - Vererbung
| Vorlesung 11 (Kapitel 7)
| rowspan="2" | [[Vererbung]], [[Attribut|Attribute]] & [[Methode|Methoden]]: [[Sichtbarkeit|Zugriffsrechte]], Überschreiben, [[abstract|Abstrakte Klassen/Methoden]], Polymorphie
|-
| Vorlesung 12 (Kapitel 7)
|-
| rowspan="2" | Dynamische Datenstrukturen
| Vorlesung 13 (Kapitel 8.1)
| einfache [[Liste|Listen]], sortierte Liste, Doppelt verkettete Liste
|-
| Vorlesung 14 (Kapitel 8.2)
| [[Baum#Suchbaum | Binärer Suchbaum]], Vollständige Induktion, Operationen in einem binärem Suchbaum, Durchlaufstrategien für einen binären Suchbaum
|}

=Wichtige Übersichtsseiten=

* Unter [[Basisvokabular]] findet sich eine Liste mit in der Informatik häufig verwendeten Begriffen. Anregungen für Ergänzungen sind erwünscht.

* Unter [[Schlüsselwort]] findet sich eine Liste mit allen Schlüsselwörtern in Java und weiterführenden Links.

* In dem Artikel [[Syntaxdiagramm]]e wird erklärt, wie diese zu lesen sind.

</div>
</div>
<div style="border: solid 1px #AAA; width:50%; margin-top: 0.5em; margin-left: 0.5em;">
<div class="box_head">
Glossar
</div>
<div class="box_content">
zu: '''[[Glossar (vorlesungsorientiert)|vorlesungsorientiert]]''' / '''[[Glossar (alphabetisch)|alphabetisch]]'''

*[[Stack | Abarbeitung von Funktionsaufrufen]]
*[[Algorithmus]]
*[[Array]]
*[[Ausdruck]]
*[[Beispiele]]
*[[Bit]]
*[[Dezimal-_und_Binärsystem | Binärzahlen]]
*[[Boolesche Algebra]]
*[[Boolean]]
*[[Block]]
*[[Alternative | Bedingte Anweisung]]
*[[Baum | binärer Baum]]
*[[Char]]
*[[call by value]]
*[[call by reference]]
*[[Darstellung natürlicher Zahlen]]
*[[Darstellung ganzer Zahlen]]
*[[Deklaration]]
*[[Datentyp]]
*[[do-while | do-while-Schleife]]
*[[Datenstruktur]]
*[[Dynamische Datenstruktur]]
*[[Ein- und Ausgabe]]
*[[Elementaroperationen]]
*[[Einfache Grundoperationen]]
*[[Festpunktzahlen]]
*[[Float]]
*[[for | for-Schleife]]
*[[Funktion]]
*[[Gleitpunktzahlen]]
*[[globale Variablen]]
*[[Hexadezimalzahlen]]
*[[Heap]]
*[[if]]
*[[Initialisierung]]
*[[Integer]]
*[[Schleife | Iteration]]
*[[Objekt | Instanz]]
*[[Java]]
*[[Kurzformen]]
*[[Kontrollstruktur]]
*[[Klasse]]
*[[Liste | lineare Liste]]
*[[Methode]]
*[[main | main-Methode]]
*[[new | new-Operator]]
*[[null]]
*[[Objektorientierte Programmierung]]
*[[Operation]]
*[[Objekt]]
*[[Programmierung]]
*[[Primitive Datentypen]]
*[[Operatoren#Prioritäten | Prioritäten von Operatoren]]
*[[Parameter]]
*[[public]]
*[[private]]
*[[protected]]
*[[Punkt-Operator]]
*[[Rechensysteme]]
*[[Rückgabewert]]
*[[Rekursive Funktion]]
*[[Referenzen]]
*[[Syntax]]
*[[Semantik]]
*[[Sortieren]]
*[[Suchen]]
*[[Syntaxdiagramm]]
*[[switch]]
*[[Schleife]]
*[[static]]
*[[Schlüsselwörter]]
*[[Teile und herrsche]]
*[[Terminierung]]
*[[this]]
*[[Variable]]
*[[Vererbung]]
*[[while | while-Schleife]]
*[[Zweierkomplement]]
*[[Zuweisung]]

</div>
</div>
</div>