Implementierung des Eliminationsverfahrens

Aus EINI
Wechseln zu: Navigation, Suche

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.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
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:

?
1
2
3
4
5
6
7
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.

Von „https://ls14-eini.cs.tu-dortmund.de/index.php?title=Implementierung_des_Eliminationsverfahrens&oldid=2303“