Eliminationsverfahren

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:

	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

	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

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