Übung Numerik (02)

In dieser Übung sollen drei Ziele erricht werden:

1. Vektoren und Matrizen in Java verwenden und Arithmetik darauf anwenden;
2. Anwendung der Algorithmen auf konkrete Daten.
3. Wieder Laufzeitbetrachtungen anstellen und einordnen können.

Ausgabe : 15.11.2024

Abgabe : 22.11.2024

Komplexitätsanalyse

Aufgabe 1. Was bedeutet die O-Notation?

Aufgabe 2. Was ist der Unterschied zwischen Big-O und Littel-o Notation?

Aufgabe 3. Welche berechnten Laufzeiten (Aufwand S) sind gleich oder kleiner O(n²)?

Vektoren und Matrizen

Vektoren und Matrizen

sind die wichtigsten Datenstrukturen in der Matheamatik und Numerik.

Für Matrixalgebra brauchen wir Vektoren und Matrizen. In Java können diese mittels der Array Klasse von einem beliebigen Datentyp direkt erzeugt werden. Matrizen sind im Grunde Arrays von (eindimensionalen) Arrays.

• In unseren Numerikaufgaben verwenden wir für Vektoren und Matrizen den Datentyp float bzw double.
• Java ist beim Datentyp float zickig was Literalwerte angeht (z.B. 0.001 wird als double typisiert, will man es einer float Variable zuweisen muss ein (float) casting erfolgen), der Transpiler nicht.

Es können aber auch initialierte Arrays (oder Arrays von Arrays, also Matrizen) erzeugt werden. Das wird nachfolgend gezeigt.

Im folgenden sollen diese nativen Arrays (oder Arrays von Arrays als Matrizen) in komfortable Vektor- und Matrixklassen in Java eingebettet werden, mit einer Reihe von Operationen der linearen Vektor- und Matrixalgebra.

Matrix Numerik Klasse

Aufgabe 4. Lese das Modul B Abschnitt Vektor- und Matrixalgebra. Erstelle eine Vektor und Matrix Klasse die die Operationen +,-*,/ und Negieren von Vektoren und Matrizen (elementweise) implementieren sowie das Skalarprodukt und das Matrixprodukt. Dabei soll es in-place (Nutzung der Quellmatrix) und out-of-place (neue Ergebnismatrix) möglich sein diese Operationen durchzuführen. Es wird in beiden Fällen die Zielmatrix (oder der Zielvektor) zurück gegeben. Weiterhin muss die Konstruktorfunktion und eine Print Methode erstellt werden. Die diagonal Methode erzeugt eine Einheitsmatrix. Die data Methode gibt das reine Datenarray zurück. Die Vector und Matrix Klassen sollen jeweils die Metadaten als Klassenvariablen implementieren (nrow,ncol) sowie die Daten mittels data. Die fehlen in den Templates noch. Zuletzt soll es eine fromArray Methode geben, die vor allem für die Initialisierung mit Konstantwert Arrays verwendet werden soll (also z.B. beim Vektor new float[]{1,2,3,4}, bei Matrix new float[][]{{1,2},{3,4}}).

cHVibGljIGNsYXNzIE1hdHJpeCAgewogIGludCBuY29sOwogIGludCBucm93OwogIGZsb2F0IFtdW10gZGF0YTsKICBwdWJsaWMgTWF0cml4KGludCBucm93LCBpbnQgbmNvbCwgZmxvYXQgaW5pdCkgewogICAgdGhpcy5uY29sPW5jb2w7CiAgICB0aGlzLm5yb3c9bnJvdzsKICAgIHRoaXMuZGF0YT1uZXcgZmxvYXRbbnJvd11bbmNvbF07CiAgICBmb3IoaW50IGk9MDtpPG5yb3c7aSsrKSAKICAgICAgZm9yKGludCBqPTA7ajxuY29sO2orKykgCiAgICAgICAgdGhpcy5kYXRhW2ldW2pdPWluaXQ7CiAgfQogIHB1YmxpYyBNYXRyaXggZnJvbUFycmF5KGZsb2F0IFtdW10gYSkgewogICAgZm9yKGludCBpPTA7aTxucm93O2krKykgCiAgICAgIGZvcihpbnQgaj0wO2o8bmNvbDtqKyspIAogICAgICAgIHRoaXMuZGF0YVtpXVtqXT1hW2ldW2pdOwogICAgcmV0dXJuIHRoaXM7CiAgfQogIHB1YmxpYyBNYXRyaXggYWRkKE1hdHJpeCBiLCBCb29sIGlucGxhY2UpIHsKICAgIE1hdHJpeCB0YXJnZXQ9dGhpczsKICAgIGlmICghaW5wbGFjZSkgewogICAgICB0YXJnZXQ9bmV3IE1hdHJpeCh0aGlzLm5yb3csdGhpcy5uY29sLDBmKTsKICAgIH0KICAgIGZvcihpbnQgaT0wO2k8bnJvdztpKyspIAogICAgICBmb3IoaW50IGo9MDtqPG5jb2w7aisrKSAKICAgICAgICB0YXJnZXRbaV1bal09dGhpcy5kYXRhW2ldW2pdK2IuZGF0YVtpXVtqXTsKICAgIHJldHVybiB0YXJnZXQ7CiAgfQogIHB1YmxpYyBNYXRyaXggc3ViKE1hdHJpeCBiLCBCb29sIGlucGxhY2UpIHsKICB9CiAgcHVibGljIE1hdHJpeCBtdWwoTWF0cml4IGIsIEJvb2wgaW5wbGFjZSkgewogIH0KICBwdWJsaWMgTWF0cml4IGRpdihNYXRyaXggYiwgQm9vbCBpbnBsYWNlKSB7CiAgfQogIHB1YmxpYyBNYXRyaXggbmVnKEJvb2wgaW5wbGFjZSkgewogIH0KICBwdWJsaWMgTWF0cml4IHByb2QoTWF0cml4IGIsIEJvb2wgaW5wbGFjZSkgewogIH0KICBwdWJsaWMgTWF0cml4IGRpYWdvbmFsKGZsb2F0IHZhbHVlLEJvb2wgaW5wbGFjZSkgewogIH0KICBwdWJsaWMgZmxvYXQgW11bXSBkYXRhKCkgewogIH0KICBwdWJsaWMgdm9pZCBwcmludCgpIHsKICAgIFN0cmluZyBsaW5lID0gIiI7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG5yb3c7IGkrKykgewogICAgICAgIGxpbmUgKz0gIlsiOwogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgbmNvbDsgaisrKSB7CiAgICAgICAgICAgIGlmKGo9PW5jb2wtMSl7CiAgICAgICAgICAgICAgICBsaW5lICs9IGRhdGFbaV1bal0rIl1cbiI7CiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICBsaW5lICs9IGRhdGFbaV1bal0rIiAiOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgU3lzdGVtLm91dC5wcmludGxuKGxpbmUpOwogIH0KfSAKcHVibGljIGNsYXNzIFRlc3QgewogIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgIE1hdHJpeCBxID0gbmV3IE1hdHJpeCgzLDMsMCk7CiAgICBNYXRyaXggciA9IG5ldyBNYXRyaXgoMywzLDApOwogICAgcS5mcm9tQXJyYXkobmV3IGZsb2F0IFtdW117ezMsMiw1fSx7NCw2LDd9LHs1LC0xLC0yfX0pOwogICAgci5mcm9tQXJyYXkobmV3IGZsb2F0IFtdW117ezEzLDEsNX0sezQsMiwtN30sezEsMSwyfX0pOwogICAgcS5wcmludCgpOwogICAgci5wcmludCgpOwogIH0KfQ==

Aufgabe 5. Teste nachfolgende mathematische Rechnungen (jede Zeile ist eine Aufgabe, ⊙ ist das Skalar- oder Matrixprodukt.

Tipp: Initialisiere die Matrizen folgendermaßen:

    float [][] qI = {{1,2,3},{4,5,6},{7,8,9}};
    float [][] rI = {{1,2,3},{4,5,6},{7,8,9}};
    Matrix q = new Matrix(3,3,0);
    Matrix r = new Matrix(3,3,0);
    q.fromArray(qI);
    r.fromArray(rI);

Man könnte alternativ q.fromArray(new float[][]{{3,2,...},..,{}}) verwenden, jedoch führt das zu sehr hohen Parsingzeiten (Ursache liegt im extrem schlechten Design des verwendeten Parser, Performanzschwäche ist nicht behebar). Verfahre ähnlich bei Vektoren.

Aufgabe 6. Die Lösungen sind als Tex/AsciiMath in korrekter mathematischer Notation hier einzutragen (auf das Doppelquadrat klicken und ein Editor öffnet sich):

AsciiMath Syntax:

Vector: v=((1),(2),(..),(4))
Matrix: m=((1,2,3),(3,4,5),(6,7,8))

VEJB