Least Squares Approximation

[WiggidyWaste]

Hallo Community,

Ich habe momentan einige Probleme bei einer Programmierarbeit.
Es soll auf Basis von Daten aus einem Excel-Sheet eine Approximationsfunktion dritten Grades erzeugt werden. Diese Approximationsfunktion soll danach dann an beliebigen Stellen ausgegeben und eventuell noch geplottet bzw. wiederum in einem Excel-Sheet ausgegeben werden.
Nun steh ich ein bisschen wie der Ochs vorm Berg. Ich habe damals in der Schule Java im Informatikunterricht gelernt, danach aber Jahre lang nichts mehr gemacht - Dementsprechend sind meine Kenntnisse zu Staub zerfallen.

Es fängt schon damit an, dass Java anscheinend nicht direkt aus Excel-Dateien lesen bzw. in sie schreiben kann. Da scheint es ja einige APIs zu geben, allerdings hab ich es nicht geschafft diese unter Mac OS zum laufen zu bekommen - Aber ich denke das bekomme ich alleine noch irgendwie hin.

Als Beispiel hab ich mir einfach mal ein paar Werte ausgedacht:

Wenn ich nun das mit Excel zum Laufen bringe, hatte ich vor die Messwerte aus Excel in ein zweidimensionales Array zu schreiben - in etwa so:

int[][] wertetabelle = {
   {0,1},
   {1,2},
   {2,1},
   {3,3},
   {4,2},
   {5,2},
   };

Allerdings hakt es jetzt beim erstellen der Matrix für die Koeffizientenberechnung.
Die Matrix muss dann ja folgendermaßen aussehen:

Hierbei ist n dann die Anzahl der Wertepaare (im Beispiel oben 6) und m die Anzahl der Koeffizienten ai (beim kubischen Polynom a0, a1, a2 und a3).

Per Hand bekomme ich sie locker gerechnet:

Aber ich bekomme sie auf Teufel komm raus nicht in Java hin! Wahrscheinlich liegt es daran, dass ich mich mit den vielen Schleifen verhaspel und ich mit den Array-Indizes komplett durcheinander komme. Mit Arrays stand ich schon damals auf dem Kriegsfuß und mit mehrdimensionalen Arrays erst recht. Wenn ich mit Worten erklären müsste, was zu machen ist, wär es absolut kein Problem. Allerdings scheiter ich gnadenlos an der Implementierung. Wenn ich die Matrix irgendwie hinbekommen würde, dann wäre der Rest glaube ich auch kein Problem mehr.

Wäre wirklich dankbar, wenn mir jemand zumindest ein paar Brocken hinwerfen könnte, an denen ich mich festhalten kann.

Mit freundlichen Grüßen,

Thomas

 

[XHelp]

Hm. Ich denke ich fange mit der Berechnung an. Generell ist die nicht schwer, die könnte wie folgt aussehen:

public static void printMatrix(int[][] werte) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			int sum = 0;
			for (int k = 0; k < werte.length; k++) {
				sum += (int) (Math.pow(werte[k][0], j) * Math.pow(werte[k][0], i));
			}
			System.out.print(sum + "\t");
		}
		System.out.println();
	}
}

Darüber hinaus glaube ich, dass besser ist sich eigene Klassen zu machen um die Daten zu speichern. 2d-Array zu benutzen ist hier imho ungünstig.
Vllt fällt es dir leichter erstmal Pseudocode zu erstellen, z.B.:
- gehe alle m durch
- - gehe alle m durch
- - - gehe alle Elemente durch... usw.
und dann daraus deinen Code zu schreiben.

 

[Marco13]

Es würde vermutlich übersichtlicher und leichter handhabbar, wenn man sich für die Berechnung der Einträge einzelne Methoden machen würde

private double berechneEintrag(int r, int c)
{
    double sum = 0;
    for (int i=0; i<n; i++) { sum += wertetabelle[i][0]; }
    return sum;
}

oder so. Und wenn die 2D-Arrays für Verwirrung sorgen ... .... ... (dann schreib ein Programm mit 10D-Arrays wie float[][][][][][][][][][] - zur Abhärtung ) ... könntest du, wie XHelp schon gesagt hat, versuchen die zu vermeiden. Ob man dafür nun eine eigene Klasse braucht... weiß ich nicht. Aber ein

float tArray[] = new float[] { 0,1,2,3,4,5 };
float fArray[] = new float[] { 1,2,1,3,2,2 };

würde das vielleicht schon übersichtlicher machen.

 

[XHelp]

Vermutlich sollte die Methode eher

for (int i=r; i<c; i++)

sein? Anders kann ich mir nicht vorstellen, wozu die Parameter gut sind.

 

[WiggidyWaste]

Hey ihr beiden,

Wow. Schon 2 Antworten! Das ist ja wirklich super
Ihr seid also beide der Meinung, dass es für die Übersicht und generell für die Handhabung günstiger wäre, wenn ich die Werte für t und f jeweils in ein eigenes Array schreibe und dann gesondert auf beide zugreife? Scheint mir jetzt im Nachhinein auch um einiges einfacher - Zumal ich ja für die große und unübersichtliche Matrix eigentlich nur die t-Werte und nicht die f-Werte brauche. Die brauch ich ja erst für den Ergebnisvektor, aber da der ja als eindimensionales Array darstellbar ist, müsste das eigentlich auch machbar sein.

Wie ich die einzelnen Werte jetzt berechne hab ich endlich geschnallt. Ich hatte mir sowas ähnliches wie die Dreifachschleife von XHelp zusammengebastelt, allerdings bin ich da irgendwann mit den Indizes durcheinandergekommen und dann wars vermurkst. Ich werde es dann wohl auch so versuchen, wie XHelp es schon gepostet hat, allerdings dann erstmal nur mit einem eindimensionalen Array. Somit scheint die Berechnung der einzelnen Werte abgeschlossen.

Allerdings brauche ich doch jetzt wieder so eine Monsterschleife um die Werte, die ich ja jetzt berechnen kann, wieder in die Berechnungsmatrix einzusetzen!? Oder habe ich im Code irgendwas übersehen, was das Schreiben in die neue Matrix vorsieht.

Könnte man hier bereits vorher die Ergebnismatrix definieren und in die schon vorhandene Schleife soetwas einbauen wie:

int[4][4]ergebnismatrix;

public static void printMatrix(int[]tWerte) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            int sum = 0;
            for (int k = 0; k < tWerte.length; k++) {
                sum += (int) (Math.pow(tWerte[k], j) * Math.pow(tWerte[k], i));
            }
            System.out.print(sum + "\t");
            ergebnismatrix[i][j] = sum
        }
        System.out.println();
    }
}

Ich vermute mal, dass ich mir das nur so einfach vorstelle und es so nicht funktionieren wird, aber die Hoffnung stirbt wohlbekanntlich ja zuletzt

Vielen Dank schonmal für eure Tips!

mfG, Thomas

 

[Marco13]

Oh ja, was die Parameter da sollten weiß ich auch nicht mehr - die sollten wohl nur andeuten, dass man damit den entsprechenden Eintrag aus der Tabelle berechnet. Also sowas wie

int[4][4]ergebnismatrix;
 
public static void printMatrix(int[]tWerte) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            ergebnismatrix[i][j] = berechneEintrag(i,j);
        }
        System.out.println();
    }
}

 

[XHelp]

Allerdings brauche ich doch jetzt wieder so eine Monsterschleife um die Werte, die ich ja jetzt berechnen kann, wieder in die Berechnungsmatrix einzusetzen!? Oder habe ich im Code irgendwas übersehen, was das Schreiben in die neue Matrix vorsieht.

Naja, du kannst es ja statt dem Ausgeben auch speichern. Vor allem würde es sich, glaube ich, anbieten keine void-Methode dazu benutzen, sondern eben deine errechnete Matrix zurückgeben. So ist die Methode mehr souverän.

 

[Landei]

Naja, du kannst es ja statt dem Ausgeben auch speichern. Vor allem würde es sich, glaube ich, anbieten keine void-Methode dazu benutzen, sondern eben deine errechnete Matrix zurückgeben. So ist die Methode mehr souverän.

Sehr richtig! Um das "souverän" zu konkretisieren: Es gibt ein wichtiges Design-Prinzip namens Seperation of Concerns. Dabei geht es darum, dass jedes Stück Code genau eine Verantwortwortlichkeit hat (berechnen und ausgeben sind schon zwei). Wie soll man z.B. eine Methode testen, die nichts hinterläßt außer Pixeln auf der Konsole (natürlich kann man das, aber man macht sich das Leben unnötig schwer)? Was wenn man stattdessen in eine Datei schreiben oder HTML erzeugen will?

 

[WiggidyWaste]

Hey ihr,

Echt super, dass mir so viele zu helfen versuchen!

Ich werd mich erstmal mit dieser Informationsflut hinsetzen und versuchen was auf die Beine zu stellen. Kaum zu glauben, dass von 3 Jahren Leistungskurs in der Schule nach 2 Jahren nichts tun einfach nichts mehr übrig ist... Wenn das mein Lehrer von damals wüsste.

Naja - Noch ist ja jede Menge Zeit. Ich wusste insgeheim schon, dass nich mehr viel von meinen Kenntnissen übrig sein würde und hab mich dementsprechend früh hingesetzt. Ich hoffe bis November bekomm ich es hin

Darf ich euch nochmal nerven, falls ich wieder Fragen habe - Was mit ziemlich hoher Wahrscheinlichkeit passieren wird.

mfG, Thomas

 

[WiggidyWaste]

Hallo nochmal,

ich hab mich jetzt wieder mal etwas intensiver in Java eingelesen und hab jetzt einige Fragen ganz gut alleine klaeren koennen - entschuldigt bitte die ausgeschriebenen Umlaute, ich sitze gerade in Kreta an einem Hotspot und habe deshalb nur griechische Tastatur zur Verfuegung.
Ein paar Fragen habe ich allerdings noch:

Und zwar habe ich jetzt angefangen die Regel von Sarrus zu programmieren. Das funktioniert soweit ich das getestet habe auch schon, allerdings brauche ich dafuer eine vorgegebene Matrix. Ich hatte ja im Voraus schonmal gefragt, wie sich die hier beschriebene Matrix berechnen liesse. Das habe ich soweit auch schon verstanden. Allerdings weiss ich nicht, wie ich diese Matrix dann nach dem Berechnen noch irgendwo zwischenspeichern kann um sie danach zur Berechnung zu benutzen. Waere super, wenn mir dort nochmal jemand behilflich sein koennte.
Zur Sarrusregel habe ich auch noch eine Frage. Ich habe sie jetzt fuer den Koeffizienten a0 programmiert und das funktioniert auch. Allerdings faende ich es wesentlich eleganter, wenn ich dies nun auch fuer den Koeffizienten ai realisieren koennte. Hier hatte ich aber Probleme, weil sich die Parameter wieder in 2 Richtungen nach vorne und nach hinten veraendern. Ich wuerde euch ja gerne ne Zeichnung dazu hochladen, aber die Moeglichkeit habe ich hier leider nicht. Wenn jemand verstanden hat, was ich meine, dann waere ich auch hier fuer Tips dankbar.
Ich werde die Tage nochmal hier reinschauen, waere cool, wenn jemand was hat. Ansonsten melde ich mich nach dem Urlaub nochmal!
Viele Gruesse, Thomas

 

[WiggidyWaste]

Ich bins mal wieder,

Mittlerweile bin ich aus dem Urlaub zurück und hab mich nochmal ein bisschen an die Arbeit gemacht. Allerdings bin ich bei der Problemlösung noch nicht wirklich weitergekommen. Mein Hauptproblem ist wohl das:

  // Berechnung des Ergebnisvektors

    public static void printSolutionVector (double [] tValues, double [] fValues) {
        for (int i = 0; i < 4; i++) {
            double solution = 0;
            for (int j = 0; j < tValues.length; j++) {
                solution += (double) (Math.pow(tValues[j], i) * fValues[j]);
            }
            System.out.print(solution + "\t");
        }
    System.out.println();
    }[/Java]

das hier ist jetzt zum Beispiel die Methode, die den Ergebnisvektor berechnet. Funktionieren tut sie an sich einwandfrei, allerdings würde ich hier gerne noch etwas dran tüfteln. Und zwar wäre es wichtig, dass die Methode mir den Ergebnisvektor irgendwie in einem Array hinterlegen kann, da ich den Vektor später zum Weiterrechnen benötige. Ich habe es schon mit einer einfachen Zuweisung in der Schleife versucht:

[code=Java]  // Berechnung des Ergebnisvektors

    public static void printSolutionVector (double [] tValues, double [] fValues) {
        for (int i = 0; i < 4; i++) {
            double solution = 0;
            for (int j = 0; j < tValues.length; j++) {
                solution += (double) (Math.pow(tValues[j], i) * fValues[j]);
            }
            System.out.print(solution + "\t");
            solutionVector [i] = solution        // das war mein Versuch
        }
    System.out.println();
    }[/Java]

Allerdings hat das nur zu wirrem Zeichenchaos geführt, als ich mir den so "erzeugten" Vektor dann ausgeben lassen wollte. Gibt es irgendeine Möglichkeit aus einer Schleife direkt in ein Array zu schreiben? Wenn es eine gäbe, wäre ich für einen kleinen Tipp dankbar!


Mein zweites "Problem" ist eher ein ästhetisches. Hier geht es um die Sarrus'sche Regel:

[code=Java]    // Bestimmung der Koeffizienten a0, a1, a2 und a3

    public static void getCoefficientA0 (double[][] matrix, double[] solutionVector) {
	a0 = (solutionVector[0] * matrix[1][1] * matrix[2][2] * matrix[3][3])
           + (matrix[0][1] * matrix[1][2] * matrix[2][3] * solutionVector[3])
           + (matrix[0][2] * matrix[1][3] * solutionVector[2] * matrix[3][1])
           + (matrix[0][3] * solutionVector[1] * matrix[2][1] * matrix[3][2])
           - (solutionVector[3] * matrix[2][1] * matrix[1][2] * matrix[0][3])
           - (matrix[3][1] * matrix[2][2] * matrix[1][3] * solutionVector[0])
           - (matrix[3][2] * matrix[2][3] * solutionVector[1] * matrix[0][1])
           - (matrix[3][3] * solutionVector[2] * matrix[1][1] * matrix[0][2]);
    }
    
    public static void printCoefficientA0 () {
        getCoefficientA0 (matrix, solutionVector);
        System.out.println ("a0 = " + a0);
    }

    public static void getCoefficientA1 (double[][] matrix, double[] solutionVector) {
	a1 = (solutionVector[0] * matrix[1][2] * matrix[2][3] * matrix[3][0])
           + (matrix[0][2] * matrix[1][3] * matrix[2][0] * solutionVector[3])
           + (matrix[0][3] * matrix[1][0] * solutionVector[2] * matrix[3][2])
           + (matrix[0][0] * solutionVector[1] * matrix[2][2] * matrix[3][3])
           - (solutionVector[3] * matrix[2][2] * matrix[1][3] * matrix[0][0])
           - (matrix[3][2] * matrix[2][3] * matrix[1][0] * solutionVector[0])
           - (matrix[3][3] * matrix[2][0] * solutionVector[1] * matrix[0][2])
           - (matrix[3][0] * solutionVector[2] * matrix[1][2] * matrix[0][3]);
    }

    public static void printCoefficientA1 () {
        getCoefficientA1 (matrix, solutionVector);
        System.out.println ("a1 = " + a1);
    }

    public static void getCoefficientA2 (double[][] matrix, double[] solutionVector) {
	a2 = (solutionVector[0] * matrix[1][3] * matrix[2][0] * matrix[3][1])
           + (matrix[0][3] * matrix[1][0] * matrix[2][1] * solutionVector[3])
           + (matrix[0][0] * matrix[1][1] * solutionVector[2] * matrix[3][3])
           + (matrix[0][1] * solutionVector[1] * matrix[2][3] * matrix[3][0])
           - (solutionVector[3] * matrix[2][3] * matrix[1][0] * matrix[0][1])
           - (matrix[3][3] * matrix[2][0] * matrix[1][1] * solutionVector[0])
           - (matrix[3][0] * matrix[2][1] * solutionVector[1] * matrix[0][3])
           - (matrix[3][1] * solutionVector[2] * matrix[1][3] * matrix[0][0]);
    }

    public static void printCoefficientA2 () {
        getCoefficientA2 (matrix, solutionVector);
        System.out.println ("a2 = " + a2);
    }

    public static void getCoefficientA3 (double[][] matrix, double[] solutionVector) {
	a3 = (solutionVector[0] * matrix[1][0] * matrix[2][1] * matrix[3][2])
           + (matrix[0][0] * matrix[1][1] * matrix[2][2] * solutionVector[3])
           + (matrix[0][1] * matrix[1][2] * solutionVector[2] * matrix[3][0])
           + (matrix[0][2] * solutionVector[1] * matrix[2][0] * matrix[3][1])
           - (solutionVector[3] * matrix[2][0] * matrix[1][1] * matrix[0][2])
           - (matrix[3][0] * matrix[2][1] * matrix[1][2] * solutionVector[0])
           - (matrix[3][1] * matrix[2][2] * solutionVector[1] * matrix[0][0])
           - (matrix[3][2] * solutionVector[2] * matrix[1][0] * matrix[0][1]);
    }

    public static void printCoefficientA3 () {
        getCoefficientA3 (matrix, solutionVector);
        System.out.println ("a3 = " + a3);
    }[/Java]

Gibt es hier eine Möglichkeit den "i-ten" Koeffizienten zu berechnen? Damit würde man sich wohl eine Menge Code sparen. Außerden wäre man dann flexibler, falls die Arbeit irgendwann mal erweitert werden soll und man ein Polynom höheren Grades erzeugen soll. Bei der Matrix handelt es sich momentan immer um eine 4x4 Matrix. Der Vektor hat immer 4 Komponenten. Ich habs mit einer Schleife versucht, allerdings war hier das Problem, dass ich bei der Änderung der Indizes kein wirkliches System ausmachen konnte. Wenn hier jemand einen Rat hätte, wäre ich ebenfalls sehr dankbar!

mfG, Thomas

 

[Marco13]

Das Zeichenchaos könnte man wohl mit
System.out.println(Arrays.toString(derArray));
verhindern.

Das andere... als Sarrusregel kenne ich nur Regel von Sarrus ? Wikipedia . Du könntest dir mal den modulo-Operator ansehen
int rest = a % b;
gibt den Rest der division zurück. Wenn man z.B. eine Schleife hat, die von 0 bis 6 läuft, hat man bei

for (int i=0; i<6; i++)
{
    int rest = i % 3;
    System.out.println(rest);
}

die Ausgabe
[c]0 1 2 0 1 2[/c]
was sich als indizes für eine 3x3-Matrix eignen könnte.
Aber was der Ergebnisvektor da verloren hat ist mir nicht klar.

 

[WiggidyWaste]

Das mit dem Arrays.toString war genau das, was ich brauchte! Tausend Dank. Ich hab allerdings wieder ein kleines Problem. Für meinen Vektor funktioniert das Umwandeln in den String einwandfrei, allerdings wird bei der Matrix wieder nur Kauderwelsch ausgegeben. Liegt das daran, dass diese Umwandlung für zweidimensionale Felder unzulässig ist, oder gibts hier auch wieder einen Trick?!

Edit:// Kollege Google hat geholfen. Arrays.deepToString(array) funktioniert einwandfrei!

mfG, Thomas

 

[WiggidyWaste]

Aber was der Ergebnisvektor da verloren hat ist mir nicht klar.

Also wenn ich nicht vollkommen falsch liege oder in der Mathevorlesung geschlafen habe, dann sollten sich doch so die Koeffizienten ai bestimmen lassen. Für den Koeffizienten a0 setzt man einfach den Ergebnisvektor anstelle der ersten Spalte der Matrix ein und rechnet dann die Determinante der "neuen Matrix" aus. Analog geht das dann auch für a1, wenn man den Vektor mit der zweiten Spalte tauscht und so weiter.

Es kann allerdings auch sein, dass du Recht hast und da wirklich etwas nicht stimmt. Wenn ich die Koeffizienten von meinem Programm rechnen lasse, werden unmögliche Werte ausgespuckt. Daraufhin hab ich das ganze nochmal über 3 verschiedene online-Rechner für Determinanten probiert, welche mir alle ein gleiches Ergebnis liefern. Das ist allerdings nicht das, welches mein Programm liefert.

Habe ich bei der Rechnung einfach generell einen Denkfehler? Ich war mir felsenfest sicher, dass der Rechenweg so in Ordnung wäre!

Edit:// Oh mann... Jetzt weiß ich, was ihr meint. Also das ganze ist natürlich nicht die Regel nach Sarrus, sondern die Cramer'sche Regel. Allerdings habe ich da ja nur die halbe Cramer'sche Regel stehen - Es muss ja noch durch die Determinante der "normalen Matrix" geteilt werden. Das werde ich wohl erstmal beheben.
Danke für den Hinweis!

mfG, Thomas

 

[XHelp]

Du musst doch noch das Ergebnis von deinen

getCoefficientAX

durch die Determinante der Ursprungsmatrix teilen:

. Soviel dazu... die Sarrus-Regel zieht allerdings nur bis 3x3 Matritzem., also kommst du hier nicht wirklich weiter, bei 4x4 geht die nicht mehr.
Ich weiß nicht wie oft du es brauchst, aber du könntest überlegen Gauß, Entwicklungssatz von Laplace oder Leibnitz-Formel angucken, wobei du mit Laplace imho an günstigsten fährst.

 

[WiggidyWaste]

Oh mann, dann habe ich da ja totalen Mist verzapft Dann werden Sarrus und Cramer erstmal über Bord geworfen. Dann werde ich mich mal in die drei von dir genannten Methoden einlesen und schauen, welche davon wohl am einfachsten zu implementieren ist.

Tausend dank nochmal, dass ihr mir so super unter die helft! Ich glaube ohne euch wäre ich hier komplett aufgeschmissen.

mfG, Thomas

 

[XHelp]

Cramer sollte eigentlich hinhauen (zumindestmal fällt mir jetzt nicht ein, was dagegen sprechen sollte). Es ging nur um die Sarrus-Regel.

 

[WiggidyWaste]

Hey ihr,

Vielen Dank nochmal an alle, die geholfen haben. Es scheint so als hätte ich das ganze Thema so eben abgeschlossen. Mit Laplace und Cramer funktionieren jetzt auch die Determinantenberechnungen und somit kann ich an die kleinen Details gehen. Ich denke mal, dass die letzten 20% der Arbeit wieder 80% der Zeit in Anspruch nehmen, aber das Grundgerüst fürs Programm steht jetzt und funktionsfähig ist es auch. Alles was jetzt kommt ist die Kür!

Nochmal vielen Dank an alle, die mitgeholfen haben!

mfG, Thomas