Επανάσταση των ρομπότ

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

Υπάρχουν πολλοί τεχνικοί ορισμοί, στη [Wikipedia][linalg-wiki], σε εγχειρίδια και σε εξαιρετικές ιστοσελίδες όπως το [3Blue1Brown][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 θα τη φέρει στον χώρο ονομάτων, αλλά δεν θα το επαναλαμβάνουμε στα παραδείγματα (πολύς οπτικός θόρυβος).

Διανύσματα, γινόμενο κατά στοιχείο

Αυτό συζητήθηκε στην έννοια [Vector Operations][vector-ops]. Ο τελεστής είναι .*, ο οποίος δρα στα διανύσματα εισόδου ανά ζεύγη, δίνοντας μια έξοδο ίδιου μεγέθους και τύπου με τις εισόδους.

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

Διανύσματα, βαθμωτό γινόμενο

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

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

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

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

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 είναι μιγαδικά.

Νόρμες

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

Η 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 χρόνων μετατρέποντας κάθε υπολογισμό σε μια σειρά από πολλαπλασιασμούς μητρών.

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

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

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

Θεώρησε μια μήτρα 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, η δεύτερη γραμμή δίνει τη δεύτερη γραμμή, και ούτω καθεξής προς τα κάτω.

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

Περιστροφές

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

Στις 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