Implementierung des Eliminationsverfahrens: Unterschied zwischen den Versionen

Aktuelle Version vom 9. März 2020, 22:08 Uhr

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.

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

Insgesamt liefert unser Programm die Ausgabe:

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

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.