Eliminationsverfahren - Versionsgeschichte

Elias am 9. März 2020 um 21:36 Uhr

2020-03-09T21:36:11Z

Elias am 9. März 2020 um 21:22 Uhr

2020-03-09T21:22:01Z

Elias am 9. März 2020 um 21:19 Uhr

2020-03-09T21:19:36Z

Elias am 9. März 2020 um 21:14 Uhr

2020-03-09T21:14:45Z

Elias: /* Pivotsuche */

2020-03-09T21:07:18Z

‎Pivotsuche

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…“

2020-03-09T20:29:32Z

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…“

Neue Seite

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

@@ 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.
-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:
+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">
@@ Zeile 22: / Zeile 22: @@
 ==Pivotierung und Elimination==
 <source lang="java">
@@ Zeile 66: / Zeile 70: @@
 ==Rückwärtseinsetzen==
 <source lang="java">
@@ Zeile 94: / Zeile 101: @@
+	}
 </source>

@@ Zeile 5: / Zeile 5: @@
 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>
+<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
@@ Zeile 22: / Zeile 19: @@
 		return argmax;
+	}
 </source>
 ==Pivotierung und Elimination==
-<source lang=Java>
+<source lang="java">
-package Gauß;
-−
-public class LGS {
 	public static void ZeilenTauschen (double[][] A, double[] b, int zeile1, int zeile2){
 		int n=b.length;
@@ Zeile 71: / Zeile 63: @@
 		b[a]=b[a]+c*b[Pivotindize];
+	}
 </source>
 ==Rückwärtseinsetzen==
-<source lang=Java>
+<source lang="java">
-package Gauß;
-−
-public class LGS {
 	public static double[] LGSloesen (double[][] A ,double[] b) {
 		//loest regulaeres LGS Ax=b
@@ Zeile 105: / Zeile 93: @@
 		return x;
+	}
 </source>

@@ Zeile 29: / Zeile 29: @@
 <source lang=Java>
 	public static void ZeilenTauschen (double[][] A, double[] b, int zeile1, int zeile2){
 		int n=b.length;
@@ Zeile 68: / Zeile 71: @@
 		b[a]=b[a]+c*b[Pivotindize];
+	}
 </source>
@@ Zeile 73: / Zeile 77: @@
 <source lang=Java>
 	public static double[] LGSloesen (double[][] A ,double[] b) {
 		//loest regulaeres LGS Ax=b
@@ Zeile 98: / Zeile 105: @@
 		return x;
+	}
 </source>

@@ Zeile 9: / Zeile 9: @@
 public class LGS {
 	public static int Pivotindize (double[][] A, int Spalte) {
 		//findet Indize, der >= Spaltenindizee ist, mit groesstem Eintrag in gegebener Spalte
@@ Zeile 81: / Zeile 23: @@
+	}
 	public static void ZeilenTauschen (double[][] A, double[] b, int zeile1, int zeile2){
 		int n=b.length;
@@ Zeile 120: / Zeile 68: @@
 		b[a]=b[a]+c*b[Pivotindize];
+	}
+</source>
 </source>

← Nächstältere Version		Version vom 9. März 2020, 21:07 Uhr
Zeile 4:		Zeile 4:

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