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