Roboterrevolution

Was ist „Lineare Algebra“?

Es gibt reichlich technische Definitionen, auf [Wikipedia][linalg-wiki], in Lehrbüchern und auf hervorragenden Websites wie [3Blue1Brown][3blue1brown], aber für unsere Zwecke können wir es lockerer angehen.

Die Julia- (und Python-)Maintainer lieben solche Sachen. Das Exercism-Management eher weniger.

Dieses Konzept beschränkt sich auf die einfacheren Aspekte eines riesigen Themas, aber sei gewarnt: das ist zwangsläufig ein ziemlich mathematisches Konzept.

Was ist ein Vektor?

Das hängt davon ab, wen man fragt und wie man etwas ziemlich Abstraktes veranschaulichen möchte.

• In Julia ist Vector{T} nur ein Alias für Array{T, 1}, und der eltype T kann alles Mögliche sein.
• In (einem Großteil) der Physik ist ein Vektor ein Pfeil mit einer length und einer direction im N-dimensionalen Raum, aber ohne feste Position.
• In der Linearen Algebra ist der Pfeil der Physiker im Raum fixiert, mit seinem Fuß im Ursprung. Dadurch wird der Schaft des Pfeils überflüssig, und wir können den Vektor als point im N-dimensionalen Raum darstellen, wobei die N Elemente den Abstand vom Ursprung entlang jeder der N Achsen angeben.

Für unsere Zwecke ignorieren wir Vektoren aus Strings oder Zeichen. In diesem Konzept arbeiten wir mit numerischen Typen: Int, Float oder Complex.

Was ist eine Matrix?

Auch hier findest du eine Vielzahl von Antworten.

• Ein rechteckiges 2D-Array aus Zahlen (ohne ausgefranste Ränder). Eine quadratische Matrix ist ein häufiger Sonderfall.
• Eine linear combination von Spaltenvektoren, nebeneinander gestapelt.
• Eine transformation, die auf einen Vektor angewendet werden kann, so wie eine function auf andere Eingabetypen angewendet wird.

Manche Arten quadratischer Matrizen sind so verbreitet, dass sie eigene Namen haben.

Diagonalmatrix: Alle Nicht-Null-Einträge stehen auf der main diagonal (von oben links nach unten rechts).

julia> [1 0 0; 0 2 0; 0 0 3]
3×3 Matrix{Int64}:
 1  0  0
 0  2  0
 0  0  3

# a convenient shortcut
julia> diagm(1:3)
3×3 Matrix{Int64}:
 1  0  0
 0  2  0
 0  0  3

Einheitsmatrix: Eine Diagonalmatrix mit nur Einsen auf der Diagonalen (aus Gründen, die später klarer werden). Oft als I abgekürzt.

julia> Matrix{Float64}(I, 3, 3)
3×3 Matrix{Float64}:
 1.0  0.0  0.0
 0.0  1.0  0.0
 0.0  0.0  1.0

Obere Dreiecksmatrix: Nicht-Null-Werte auf und über der Diagonalen, Nullen darunter. Untere Dreiecksmatrix kannst du dir selbst denken.

Transponieren einer Matrix

Wenn du wirklich Zeilen mit Spalten vertauschen willst, erledigt das die Funktion permutedims() und liefert dir eine neue Matrix.

Dabei wird kopiert, was bei großen Matrizen langsam ist und viel Speicher braucht.

Für Zwecke der Linearen Algebra ist die Funktion transpose() nützlicher, denn sie erzeugt schnell einen Lazy-Wrapper um die ursprüngliche Matrix.

Noch nützlicher ist die Funktion adjoint(), die zusätzlich das Vorzeichen des Imaginärteils bei komplexen Zahlen umdreht. Diese Operation ist so verbreitet, dass wir einfach einen Apostroph ' an den Variablennamen hängen können, um die Adjungierte zu erzeugen.

julia> m
2×3 Matrix{Int64}:
 1  2  3
 4  5  6

# new, full copy
julia> permutedims(m)
3×2 Matrix{Int64}:
 1  4
 2  5
 3  6

# lazy version
julia> transpose(m)
3×2 transpose(::Matrix{Int64}) with eltype Int64:
 1  4
 2  5
 3  6

julia> mc = [1+2im 2+3im; 3+2im 1+2im]
2×2 Matrix{Complex{Int64}}:
 1+2im  2+3im
 3+2im  1+2im

# lazy conjugate transpose
julia> adjoint(mc)
2×2 adjoint(::Matrix{Complex{Int64}}) with eltype Complex{Int64}:
 1-2im  3-2im
 2-3im  1-2im

# syntactic sugar for adjoint
julia> mc'
2×2 adjoint(::Matrix{Complex{Int64}}) with eltype Complex{Int64}:
 1-2im  3-2im
 2-3im  1-2im

Multiplikation

Der Rest dieses Dokuments verwendet Funktionalität aus dem Modul LinearAlgebra. Eine Zeile using LinearAlgebra bringt es in den Namensraum, aber wir werden das in den Beispielen nicht ständig wiederholen (zu viel visueller Ballast).

Vektoren, elementweises Produkt

Das wurde im Konzept [Vektoroperationen][vector-ops] besprochen. Der Operator ist .*, der die Eingabevektoren paarweise verarbeitet und eine Ausgabe liefert, die dieselbe Größe und denselben Typ wie die Eingaben hat.

julia> [1, 2] .* [3, 4]
2-element Vector{Int64}:
 3
 8

Vektoren, Skalarprodukt

Diese extrem verbreitete Operation wird in Lehrbüchern als u ⋅ v geschrieben und „Skalarprodukt“ genannt.

Ein Skalarprodukt entspricht der Summe des elementweisen Produkts.

Zwei Vektoren können mit dem üblichen *-Operator multipliziert werden, aber nur, wenn der linke Vektor ein adjoint ist: praktischerweise geschrieben als u' * v. Das sollte im späteren Abschnitt über Matrixmultiplikation klarer werden.

Der hochgestellte (mittige) Punkt ist in Julia verfügbar (eingegeben als \cdot und Tab) und ist syntaktischer Zucker für die Funktion dot(). Es ist nicht nötig, die Adjungierte anzugeben, da dieses Detail automatisch behandelt wird.

julia> using LinearAlgebra

# with element-wise syntax
julia> sum([1, 2] .* [3, 4])
11

# with u' * v syntax
julia> [1, 2]' * [3, 4]
11

# with dot()
julia> dot([1, 2], [3, 4])
11

# with \cdot syntax
julia> [1, 2] ⋅ [3, 4]
11

Bei komplexwertigen Vektoren muss der linke Vektor die Konjugierte sein (das Vorzeichen des Imaginärteils umgedreht). Die Funktion dot erledigt das automatisch, die Syntax u' macht es explizit, aber sum(u .* v) schlägt fehl, wenn u und v komplex sind.

Normen

Wie „groß“ ist ein Vektor?

Die norm ist der Versuch, das zu erfassen, indem der Vektor auf einen passenden Skalar reduziert wird.

Es ist eine ganze Familie von Normen definiert, aber die mit Abstand gebräuchlichste ist die 2-Norm, also √(v ⋅ v).

Diese Operation des quadratischen Mittels ist der Pythagoreische Abstand vom Ursprung (im N-dimensionalen Raum). Wenn wir uns den Vektor als Pfeil mit seinem Fuß im Ursprung vorstellen, ist die 2-Norm die Länge des Pfeils.

Jede p-Norm lässt sich berechnen, indem man p als zweites Argument angibt. Die 1-Norm ist manchmal nützlich: Sie ist einfach die Summe der Absolutbeträge der Einträge (also sehr schnell und einfach zu berechnen).

# defaults to the 2-norm
julia> norm([1, 2, 3])
3.7416573867739413
# the 1-norm
julia> norm([1, -2, 3], 1)
6.0

Matrixmultiplikation

Manchmal scheint es, als hätte jeder angewandte Mathematiker der Welt einen Großteil der letzten 80 Jahre damit verbracht, jede Rechnung in eine Reihe von Matrixmultiplikationen zu verwandeln.

Das ist eine Operation, in der Computer sehr gut sind:

• Sie ist stark repetitiv.
• Sie lässt sich effizient parallelisieren.
• Es wurde viel spezialisierte Hardware entwickelt, um sie schneller zu machen, darunter die GPU, die wahrscheinlich in deinem Laptop steckt.

Die Details sind recht einfach, wenn auch auf den ersten Blick nicht sehr intuitiv.

Betrachte eine Matrix A, die einen Vektor v multipliziert und eine Ausgabe w ergibt (nach Konvention der Linearen Algebra verwenden wir Großbuchstaben für Matrizen, Kleinbuchstaben für Vektoren).

Die oberste Zeile von A wird mit v skalar multipliziert, um das erste Element von w zu erhalten, die zweite Zeile ergibt das zweite Element, und so weiter nach unten.

julia> A = [1 2; 3 4]
2×2 Matrix{Int64}:
 1  2
 3  4
julia> v = [5, 6]
2-element Vector{Int64}:
 5
 6
julia> A * v
2-element Vector{Int64}:
 17  # equals [1, 2] ⋅ [5, 6]
 39  # equals [3, 4] ⋅ [5, 6]

Eine Matrix-mal-Matrix-Multiplikation erstreckt dies über die Spalten der Matrix auf der rechten Seite.

Für C = A * B können wir uns vorstellen, dass A jede Spalte von B multipliziert und die entsprechende Spalte von C ergibt: eine Reihe von Matrix-Vektor-Multiplikationen.

Gleichwertig könnten wir sagen, dass die erste Zeile von A mit jeder Spalte von B skalar multipliziert wird, um die oberste Zeile von C zu ergeben, die zweite Zeile die zweite Zeile ergibt, und so weiter nach unten.

julia> A
2×2 Matrix{Int64}:
 1  2
 3  4

julia> B = [5 7; 6 8]
2×2 Matrix{Int64}:
 5  7
 6  8

# left column is the same as A*v previously
julia> A * B
2×2 Matrix{Int64}:
 17  23
 39  53
 
julia> B * A
2×2 Matrix{Int64}:
 26  38
 30  44

Wie im obigen Beispiel gezeigt, ist die Matrixmultiplikation nicht kommutativ: Es gibt keine einfache Beziehung zwischen A*B und B*A.

Matrixmultiplikation ist wahrscheinlich für jeden, der neu darin ist, allein vom Lesen der Worte her schwer zu veranschaulichen. YouTube hat viele Videos, die sie grafisch demonstrieren, also suche nach „Matrixmultiplikation“ und wähle eines mit deinem bevorzugten Stil, Detaillierungsgrad und deiner Sprache.

Dimensionen

Das Skalarprodukt zweier Vektoren setzt voraus, dass sie gleich lang sind.

In der Erweiterung muss für die Matrixmultiplikation die Anzahl der Spalten der linken Matrix mit der Anzahl der Zeilen der rechten Matrix übereinstimmen.

Schreiben wir die Größen als (nrows, ncols)-Tupel, wie sie size(A) ausgibt, so gilt (a, b) * (b, c) -> (a, c). Die „inneren“ Dimensionen, hier b und b, sind mit der Bildung von Skalarprodukten kompatibel. Die „äußeren“ Dimensionen, hier a und c, bestimmen die Dimensionen der Ausgabe.

Ein Beispiel mit rechteckigen Matrizen:

julia> D = reshape(1:6, 2, 3)
2×3 reshape(::UnitRange{Int64}, 2, 3) with eltype Int64:
 1  3  5
 2  4  6

julia> E = reshape(1:12, 3, 4)
3×4 reshape(::UnitRange{Int64}, 3, 4) with eltype Int64:
 1  4  7  10
 2  5  8  11
 3  6  9  12

julia> D * E
2×4 Matrix{Int64}:
 22  49   76  103
 28  64  100  136

# (3, 4) * (2, 3) not possible
julia> E * D
ERROR: DimensionMismatch: matrix A has axes (Base.OneTo(3),Base.OneTo(4)), matrix B has axes (Base.OneTo(2),Base.OneTo(3))

Vektorpaare im Matrixstil zu multiplizieren, hat zwei Möglichkeiten.

Üblicherweise würden wir u' * v als Äquivalent zum Skalarprodukt verwenden. Die Dimensionen sind (1, 3) * (3, 1), und Julia vereinfacht die Ausgabe (1, 1) zu einem Skalar (anders als zum Beispiel R).

Alternativ könnten wir u * v' verwenden, mit den Dimensionen (3, 1) * (1, 3) -> (3, 3), um alle möglichen Elementpaare zu multiplizieren und die Vektoren zu einer Matrix zu erweitern.

julia> u = [1, 2]
2-element Vector{Int64}:
 1
 2
julia> v = [3, 4]
2-element Vector{Int64}:
 3
 4
julia> u' * v
11
julia> u * v'
2×2 Matrix{Int64}:
 3  4
 6  8

u' * v wird manchmal das innere Produkt genannt.

Rotationen

Eine besonders verbreitete Art der Matrixmultiplikation betrifft Rotationsmatrizen.

In 2D gibt es eine relativ einfache Matrix, um einen Vektor um θ Radiant gegen den Uhrzeigersinn zu drehen.

julia> rot2d(θ, vec) = [cos(θ) -sin(θ); sin(θ) cos(θ)] * vec
rot2d (generic function with 1 method)

# unit vector in the x direction
julia> i_hat = [1, 0]
2-element Vector{Int64}:
 1
 0

# rotate 45 degrees
julia> rot2d(π/4, i_hat)
2-element Vector{Float64}:
 0.7071067811865476
 0.7071067811865475

# rotate 90 degrees -> unit vector in the y direction, j_hat
julia> rot2d(π/2, i_hat)
2-element Vector{Float64}:
 6.123233995736766e-17  # zero, within numerical error
 1.0