Βασικά στοιχεία γραμμικής άλγεβρας σε

Σχετικά με την έννοια Βασικά στοιχεία γραμμικής άλγεβρας

Τι είναι η "Γραμμική Άλγεβρα";

Υπάρχουν πολλοί τεχνικοί ορισμοί, στη Wikipedia, σε βιβλία και σε εξαιρετικές ιστοσελίδες όπως το 3Blue1Brown, αλλά για τους σκοπούς μας μπορούμε να είμαστε πιο ανεπίσημοι.

Στους συντηρητές της Julia (και της Python) αρέσουν πολύ τέτοια πράγματα. Στη διοίκηση του Exercism, όχι και τόσο.

Αυτή η έννοια θα περιοριστεί στις πιο απλές πτυχές ενός τεράστιου θέματος, αλλά προσοχή: αυτή είναι, αναπόφευκτα, μια αρκετά μαθηματική έννοια.

Τι είναι ένα διάνυσμα;

Εξαρτάται από ποιον ρωτάς, και από το πώς θέλεις να οπτικοποιήσεις κάτι αρκετά αφηρημένο.

• Στη Julia, το Vector{T} είναι απλώς ένα ψευδώνυμο για το Array{T, 1}, και ο eltype T μπορεί να είναι οτιδήποτε.
• Σε (μεγάλο μέρος της) Φυσικής, ένα διάνυσμα είναι ένα βέλος με length και direction σε N-διάστατο χώρο, αλλά χωρίς σταθερή θέση.
• Στη Γραμμική Άλγεβρα, το βέλος των φυσικών είναι σταθεροποιημένο στον χώρο, με την ουρά του στην αρχή των αξόνων. Αυτό κάνει το στέλεχος του βέλους περιττό, οπότε μπορούμε να αναπαραστήσουμε το διάνυσμα ως ένα point στον N-διάστατο χώρο, με τα N στοιχεία να αναπαριστούν την απόσταση από την αρχή κατά μήκος καθενός από τους N άξονες.

Για τις ανάγκες μας, αγνόησε διανύσματα συμβολοσειρών ή χαρακτήρων. Σε αυτή την έννοια θα δουλέψουμε με αριθμητικούς τύπους: Int, Float ή Complex.

Τι είναι ένας πίνακας;

Και πάλι, θα βρεις ποικίλες απαντήσεις.

• Ένας ορθογώνιος δισδιάστατος πίνακας αριθμών (χωρίς κενά στις άκρες). Ο τετραγωνικός πίνακας είναι μια συνηθισμένη ειδική περίπτωση.
• Ένας linear combination διανυσμάτων στηλών, τοποθετημένων ο ένας δίπλα στον άλλο.
• Ένας transformation που μπορεί να εφαρμοστεί σε ένα διάνυσμα, όπως ακριβώς μια function εφαρμόζεται σε άλλους τύπους εισόδου.

Κάποιοι τύποι τετραγωνικών πινάκων είναι αρκετά συνηθισμένοι ώστε να έχουν ειδικά ονόματα.

Διαγώνιος πίνακας: Όλα τα μη μηδενικά στοιχεία βρίσκονται στην main diagonal (από πάνω αριστερά προς τα κάτω δεξιά).

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

Μοναδιαίος πίνακας: Ένας διαγώνιος πίνακας με μόνο άσσους στη διαγώνιο (για λόγους που θα γίνουν πιο σαφείς αργότερα). Συχνά συντομεύεται ως I.

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

Άνω τριγωνικός: Μη μηδενικές τιμές πάνω στη διαγώνιο και πάνω από αυτή, μηδενικά από κάτω. Κάτω τριγωνικός μπορείς να το μαντέψεις.

Αναστροφή πίνακα

Αν θέλεις πραγματικά να ανταλλάξεις γραμμές με στήλες, η συνάρτηση permutedims() θα το κάνει αυτό και θα σου δώσει έναν νέο πίνακα.

Αυτό περιλαμβάνει αντιγραφή, η οποία είναι αργή και απαιτεί πολλή μνήμη όταν δουλεύεις με μεγάλους πίνακες.

Για τους σκοπούς της Γραμμικής Άλγεβρας, η συνάρτηση transpose() είναι πιο χρήσιμη, καθώς δημιουργεί γρήγορα ένα τεμπέλικο περιτύλιγμα γύρω από τον αρχικό πίνακα.

Ακόμη πιο χρήσιμη είναι η συνάρτηση adjoint(), η οποία επίσης αντιστρέφει το πρόσημο του φανταστικού μέρους σε τυχόν μιγαδικούς αριθμούς (αν αναρωτιέσαι γιατί είναι τόσο σημαντική, μια γρήγορη απάντηση είναι η Κβαντομηχανική). Αυτή η πράξη είναι αρκετά συνηθισμένη ώστε να μπορούμε απλώς να προσθέσουμε μια απόστροφο ' στο όνομα της μεταβλητής για να δημιουργήσουμε τον συζυγή ανάστροφο.

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

Πολλαπλασιασμός

Το υπόλοιπο αυτού του κειμένου περιλαμβάνει λειτουργικότητα από τη μονάδα LinearAlgebra. Μια γραμμή using LinearAlgebra θα τη φέρει στον χώρο ονομάτων, αλλά δε θα το επαναλαμβάνουμε συνέχεια στα παραδείγματα (πολύς οπτικός θόρυβος).

Διανύσματα, γινόμενο στοιχείο προς στοιχείο

Αυτό συζητήθηκε στην έννοια Διανυσματικές Πράξεις. Ο τελεστής είναι .*, ο οποίος λειτουργεί στα διανύσματα εισόδου κατά ζεύγη, δίνοντας μια έξοδο με το ίδιο μέγεθος και τύπο όπως οι είσοδοι.

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

Διανύσματα, εσωτερικό γινόμενο

Αυτή η εξαιρετικά συνηθισμένη πράξη γράφεται στα βιβλία ως u ⋅ v και ονομάζεται εσωτερικό γινόμενο.

Ένα εσωτερικό γινόμενο ισοδυναμεί με το άθροισμα του γινομένου στοιχείο προς στοιχείο.

Δύο διανύσματα μπορούν να πολλαπλασιαστούν με τον συνηθισμένο τελεστή *, αλλά μόνο αν το αριστερό διάνυσμα είναι adjoint: γράφεται βολικά u' * v. Αυτό θα γίνει πιο ξεκάθαρο στο επόμενο τμήμα για τον πολλαπλασιασμό πινάκων.

Η ανασηκωμένη (κεντρική) τελεία είναι διαθέσιμη στη Julia (πληκτρολογείται \cdot και μετά tab) ως συντακτική ζάχαρη για τη συνάρτηση dot(). Δε χρειάζεται να προσδιορίσεις τον adjoint, καθώς αυτή η λεπτομέρεια αντιμετωπίζεται αυτόματα.

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

Για διανύσματα με μιγαδικές τιμές, το αριστερό διάνυσμα πρέπει να είναι ο συζυγής (με αντεστραμμένο πρόσημο στο φανταστικό μέρος). Η συνάρτηση dot το κάνει αυτόματα, η σύνταξη u' το κάνει ρητά, αλλά το sum(u .* v) θα αποτύχει αν τα u και v είναι μιγαδικά.

Διανύσματα, διανυσματικό γινόμενο

Λίγη νοσταλγία για όποιον έχει παρακολουθήσει στο παρελθόν μάθημα Ηλεκτρισμού και Μαγνητισμού! Επίσης, για μηχανικούς εξοικειωμένους με τον υπολογισμό ροπών ή διανυσμάτων στροφορμής.

Ενώ το εσωτερικό γινόμενο μετατρέπει δύο διανύσματα σε ένα scalar, το διανυσματικό γινόμενο μετατρέπει δύο τρισδιάστατα διανύσματα σε ένα τρίτο τρισδιάστατο διάνυσμα.

Στη γεωμετρική αναπαράσταση του διανυσματικού χώρου, το νέο διάνυσμα είναι κάθετο στο επίπεδο που περιέχει τα δύο διανύσματα εισόδου. Αν οι δύο είσοδοι είναι παράλληλες (ακόμη και με αντίθετο πρόσημο), δεν ορίζουν επίπεδο, οπότε η έξοδος θα είναι [0, 0, 0].

Η σειρά έχει σημασία: u × v == -(v × u). Αυτός είναι ο διάσημος Κανόνας του Δεξιού Χεριού, που έχει αφήσει πολλούς από εμάς να κοιτάζουμε τον αντίχειρα και τα δύο δάχτυλά μας καθώς τα στριφογυρίζαμε στον χώρο (συχνά με μπερδεμένη έκφραση).

# with \times syntax
julia> [1, 2, 3] × [3, 4, 5]
3-element Vector{Int64}:
 -2
  4
 -2
# with cross()
julia> cross([1, 2, 3], [3, 4, 5])
3-element Vector{Int64}:
 -2
  4
 -2

Παρατήρησε ότι αυτή η πράξη περιορίζεται σε διανύσματα μήκους 3 (ισοδύναμα με τον ευκλείδειο χώρο με ορθογώνιους άξονες x, y, z). Οι μαθηματικοί χαίρονται να ορίζουν την πράξη για άλλες διαστάσεις, με μια ακατανόητη σαλάτα λέξεων (τανυστές ανώτερης τάξης, γινόμενο σφήνας, εξωτερικό γινόμενο, πολυδιανύσματα...) ως αποτέλεσμα. Οι περισσότεροι από εμάς το βάζουμε στα πόδια ή αλλάζουμε γρήγορα θέμα σε αυτό το σημείο!

Νόρμες

Πόσο "μεγάλο" είναι ένα διάνυσμα;

Η norm είναι μια προσπάθεια να αποτυπώσει αυτό, ανάγοντάς το διάνυσμα σε ένα κατάλληλο βαθμωτό μέγεθος.

Ορίζεται μια ολόκληρη οικογένεια νορμών, αλλά μακράν η πιο συνηθισμένη είναι η νόρμα 2, που είναι √(v ⋅ v).

Αυτή η πράξη τετραγωνικής ρίζας του αθροίσματος των τετραγώνων είναι η πυθαγόρεια απόσταση από την αρχή των αξόνων (σε N-διάστατο χώρο). Αν οπτικοποιήσουμε το διάνυσμα ως βέλος, με την ουρά του στην αρχή, η νόρμα 2 είναι το μήκος του βέλους.

Οποιαδήποτε νόρμα p μπορεί να υπολογιστεί δίνοντας το p ως δεύτερο όρισμα. Η νόρμα 1 είναι μερικές φορές χρήσιμη: είναι απλώς το άθροισμα των απόλυτων τιμών των στοιχείων (άρα πολύ γρήγορη και εύκολη στον υπολογισμό).

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

Πολλαπλασιασμός πινάκων

Μερικές φορές φαίνεται πως κάθε εφαρμοσμένος μαθηματικός στον κόσμο έχει περάσει μεγάλο μέρος των τελευταίων 80 χρόνων μετατρέποντας κάθε υπολογισμό σε μια σειρά πολλαπλασιασμών πινάκων.

Αυτή είναι μια πράξη στην οποία οι υπολογιστές είναι πολύ καλοί:

• Είναι εξαιρετικά επαναληπτική.
• Μπορεί να παραλληλοποιηθεί αποδοτικά.
• Έχει αναπτυχθεί πολύ εξειδικευμένο υλικό για να γίνει πιο γρήγορη, από τον Cray-1 των 80 εκατομμυρίων δολαρίων τη δεκαετία του 1970 μέχρι την GPU που είναι πιθανότατα ενσωματωμένη στο laptop σου.

Οι λεπτομέρειες είναι αρκετά απλές, αν και όχι πολύ διαισθητικές με την πρώτη ματιά.

Θεώρησε έναν πίνακα A που πολλαπλασιάζει ένα διάνυσμα v για να δώσει μια έξοδο w (κατά σύμβαση της Γραμμικής Άλγεβρας, χρησιμοποιούμε κεφαλαία γράμματα για τους πίνακες και πεζά για τα διανύσματα).

Η πάνω γραμμή του A πολλαπλασιάζεται εσωτερικά με το v για να προκύψει το πρώτο στοιχείο του w, η δεύτερη γραμμή δίνει το δεύτερο στοιχείο, και ούτω καθεξής προς τα κάτω.

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]

Ο πολλαπλασιασμός πίνακα * πίνακα επεκτείνει αυτό σε όλες τις στήλες του πίνακα στα δεξιά.

Για C = A * B, μπορούμε να θεωρήσουμε ότι το A πολλαπλασιάζει κάθε στήλη του B για να δώσει την αντίστοιχη στήλη του C: μια σειρά πολλαπλασιασμών πίνακα-διανύσματος.

Ισοδύναμα, θα μπορούσαμε να πούμε ότι η πρώτη γραμμή του A πολλαπλασιάζεται εσωτερικά με κάθε στήλη του B για να δώσει την πάνω γραμμή του C, η δεύτερη γραμμή δίνει τη δεύτερη γραμμή, και ούτω καθεξής προς τα κάτω.

Υπάρχουν αρκετές τέτοιες νοητικές αναπαραστάσεις, και όποιος ενδιαφέρεται μπορεί να παρακολουθήσει μια ολόκληρη διάλεξη του MIT που τις συζητά.

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

Όπως φαίνεται στο παραπάνω παράδειγμα, ο πολλαπλασιασμός πινάκων δεν είναι αντιμεταθετικός: δεν υπάρχει απλή σχέση μεταξύ των A*B και B*A.

Ο πολλαπλασιασμός πινάκων είναι μάλλον δύσκολο να οπτικοποιηθεί για όποιον τον συναντά για πρώτη φορά, μόνο διαβάζοντας τις λέξεις. Το YouTube έχει πολλά βίντεο που τον παρουσιάζουν γραφικά, οπότε αναζήτησε "matrix multiplication" και διάλεξε ένα με το στυλ, το επίπεδο λεπτομέρειας και τη γλώσσα που προτιμάς.

Διαστάσεις

Το εσωτερικό γινόμενο δύο διανυσμάτων προϋποθέτει ότι έχουν ίσο μήκος.

Κατ' επέκταση, για τον πολλαπλασιασμό πινάκων ο αριθμός των στηλών του αριστερού πίνακα πρέπει να ταιριάζει με τον αριθμό των γραμμών του δεξιού πίνακα.

Εκφράζοντας τα μεγέθη ως πλειάδες (nrows, ncols), όπως τις δίνει το size(A), έχουμε (a, b) * (b, c) -> (a, c). Οι "εσωτερικές" διαστάσεις, εδώ b και b, είναι συμβατές για τη λήψη εσωτερικών γινομένων. Οι "εξωτερικές" διαστάσεις, εδώ a και c, καθορίζουν τις διαστάσεις της εξόδου.

Ένα παράδειγμα με ορθογώνιους πίνακες:

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

Ο πολλαπλασιασμός ζευγών διανυσμάτων, με τον τρόπο των πινάκων, έχει δύο δυνατότητες.

Κατά σύμβαση, θα χρησιμοποιούσαμε το u' * v ως ισοδύναμο του εσωτερικού γινομένου. Οι διαστάσεις είναι (1, 3) * (3, 1), και η Julia απλοποιεί την έξοδο (1, 1) σε βαθμωτό μέγεθος (σε αντίθεση, για παράδειγμα, με τη R).

Εναλλακτικά, θα μπορούσαμε να χρησιμοποιήσουμε το u * v', με διαστάσεις (3, 1) * (1, 3) -> (3, 3), για να πολλαπλασιάσουμε όλα τα δυνατά ζεύγη στοιχείων και να επεκτείνουμε τα διανύσματα σε έναν πίνακα.

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 ονομάζεται μερικές φορές εσωτερικό γινόμενο.

Το (λιγότερο συνηθισμένο) u * v' είναι αντίστοιχα το εξωτερικό γινόμενο. Αυτό σχετίζεται με το γινόμενο τανυστών, αν και αυτό ξεφεύγει πολύ από το πεδίο μας.

Περιστροφές

Ένας ιδιαίτερα συνηθισμένος τύπος πολλαπλασιασμού πινάκων περιλαμβάνει τους πίνακες περιστροφής.

Στις 2 διαστάσεις, υπάρχει ένας σχετικά απλός πίνακας για να περιστρέψεις ένα διάνυσμα αριστερόστροφα κατά θ ακτίνια.

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

Οι περιστροφές στις 3 διαστάσεις χρειάζονται έναν πιο σύνθετο πίνακα, με δύο γωνίες. Αυτό είναι δύσκολο να απεικονιστεί σε ένα έγγραφο Markdown χωρίς να ενσωματώσεις πολύ LaTeX, οπότε δες τη Wikipedia για τον τύπο.

Για τα τρισδιάστατα γραφικά, όπως το OpenGL και οι διάδοχοί του, η σύμβαση είναι να δουλεύεις με ομογενείς συντεταγμένες.

Κάθε κορυφή αναπαρίσταται από ένα διάνυσμα 4 στοιχείων (ή ισοδύναμα μια στήλη πίνακα): [x, y, z, 1.0] για ένα σημείο στο (x, y, z).

Αυτό επιτρέπει πιο περίπλοκους πίνακες μετασχηματισμού. Η περιστροφή βρίσκεται ακόμα στο A[1:3, 1:3], οι μετατοπίσεις είναι [Δx, Δy, Δz] στο A[1:3, 4], η κλιμάκωση είναι στη διαγώνιο, και υπάρχουν άλλες δυνατότητες για λοξότητα, προοπτική κ.λπ.

Απόδοση

Σε τμήματα Πληροφορικής σε όλο τον κόσμο, υπάρχουν πολλές διδακτορικές διατριβές με ένα ή περισσότερα κεφάλαια για μικρές, σταδιακές βελτιώσεις σε αλγορίθμους πολλαπλασιασμού πινάκων. Αυτό είναι πραγματικά σημαντικό, και διάφοροι οργανισμοί είναι πρόθυμοι να χρηματοδοτήσουν την έρευνα για δικό τους όφελος.

Η απόδοση είναι ένα μεγάλο θέμα στο οποίο δε μπορούμε να εμβαθύνουμε, αλλά για λόγους επίδειξης μπορούμε να δοκιμάσουμε να πολλαπλασιάσουμε τυχαίους πίνακες διάφορων μεγεθών.

Ο παρακάτω κώδικας είναι μια πρόχειρη εκτίμηση (χρησιμοποίησε το BenchmarkTools.jl για μια καλύτερη προσέγγιση).

Το σύστημα που χρησιμοποιήθηκε ήταν ένα μικρό PC των 430 δολαρίων (ΗΠΑ): επεξεργαστής Ryzen 9, 32GB RAM, Linux Mint 22.1, Julia 1.11.6.

julia> mmul(A) = A * A
mmul (generic function with 1 method)
julia> A = rand(Float64, 1_000, 1_000);
julia> @time mmul(A);
  0.011055 seconds (3 allocations: 7.629 MiB)
julia> A = rand(Float64, 10_000, 10_000);
julia> @time mmul(A);
  7.236284 seconds (1.61 k allocations: 763.027 MiB, 17.92% gc time, 0.15% compilation time)

Χονδρικά, ένα ζεύγος πινάκων ενός εκατομμυρίου στοιχείων πήρε μερικά χιλιοστά του δευτερολέπτου, πίνακες 100 εκατομμυρίων στοιχείων πήραν μερικά δευτερόλεπτα. Η προσθήκη αρκετών ακόμη τάξεων μεγέθους θα χρειαστεί καλύτερο υλικό...