Révolution des robots

Qu'est-ce que l'« algèbre linéaire » ?

Il existe de nombreuses définitions techniques, sur [Wikipédia][linalg-wiki], dans les manuels et sur d'excellents sites comme [3Blue1Brown][3blue1brown], mais pour ce qui nous intéresse, on peut rester plus informels.

Les mainteneurs de Julia (et de Python) adorent ce genre de choses. La direction d'Exercism, beaucoup moins.

Ce concept se limitera aux aspects les plus simples d'un vaste sujet, mais attention : c'est inévitablement un concept assez mathématique.

Qu'est-ce qu'un vecteur ?

Cela dépend à qui on pose la question, et de la façon dont on veut visualiser quelque chose d'assez abstrait.

• En Julia, Vector{T} n'est qu'un alias de Array{T, 1}, et l'eltype T peut être n'importe quoi.
• En physique (en grande partie), un vecteur est une flèche avec une length et une direction dans un espace à N dimensions, mais sans position fixe.
• En algèbre linéaire, la flèche des physiciens est fixée dans l'espace, sa queue posée à l'origine. Le corps de la flèche devient alors redondant, ce qui permet de représenter le vecteur comme un point dans un espace à N dimensions, les N éléments représentant la distance à l'origine le long de chacun des N axes.

Pour ce qui nous concerne ici, on ignore les vecteurs de strings ou de caractères. Dans ce concept, on travaillera avec des types numériques : Int, Float ou Complex.

Qu'est-ce qu'une matrice ?

Là encore, les réponses varient.

• Un tableau 2D rectangulaire de nombres (sans bords irréguliers). Une matrice carrée en est un cas particulier courant.
• Une linear combination de vecteurs colonnes, empilés côte à côte.
• Une transformation que l'on peut appliquer à un vecteur, tout comme une function s'applique à d'autres types d'entrées.

Certains types de matrices carrées sont assez courants pour porter des noms particuliers.

Matrice diagonale : tous les coefficients non nuls se trouvent sur la main diagonal (du coin supérieur gauche au coin inférieur droit).

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

Matrice identité : une matrice diagonale dont la diagonale ne contient que des uns (pour des raisons qui deviendront plus claires par la suite). Souvent abrégée en 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

Triangulaire supérieure : des valeurs non nulles sur la diagonale et au-dessus, des zéros en dessous. Triangulaire inférieure, tu devineras.

Transposer une matrice

Si tu veux vraiment échanger les lignes et les colonnes, la fonction permutedims() s'en charge et te renvoie une nouvelle matrice.

Cela implique une copie, ce qui est lent et gourmand en mémoire lorsqu'on travaille avec de grandes matrices.

Pour les besoins de l'algèbre linéaire, la fonction transpose() est plus utile, car elle crée rapidement une enveloppe paresseuse autour de la matrice d'origine.

Encore plus utile, la fonction adjoint() inverse aussi le signe de la partie imaginaire des nombres complexes. Cette opération est si courante qu'on peut simplement ajouter une apostrophe ' au nom de la variable pour créer la matrice adjointe.

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

Multiplication

Le reste de ce document fait appel à des fonctionnalités du module LinearAlgebra. Une ligne using LinearAlgebra les fera entrer dans l'espace de noms, mais on ne va pas le répéter dans les exemples (trop de bruit visuel).

Vecteurs, produit élément par élément

Cela a été abordé dans le concept [Opérations sur les vecteurs][vector-ops]. L'opérateur est .*, qui agit sur les vecteurs d'entrée paire par paire et produit une sortie de même taille et de même type que les entrées.

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

Vecteurs, produit scalaire

Cette opération extrêmement courante s'écrit u ⋅ v dans les manuels et s'appelle le produit « scalaire ».

Un produit scalaire équivaut à la somme du produit élément par élément.

On peut multiplier deux vecteurs avec l'opérateur habituel *, mais seulement si le vecteur de gauche est un adjoint : ce qu'on écrit commodément u' * v. Cela deviendra plus clair dans la section suivante sur la multiplication matricielle.

Le point surélevé (centré) est disponible en Julia (saisi avec \cdot puis tabulation) comme sucre syntaxique pour la fonction dot(). Pas besoin de préciser la matrice adjointe, car ce détail est géré automatiquement.

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

Pour les vecteurs à valeurs complexes, le vecteur de gauche doit être le conjugué (signe inversé sur la partie imaginaire). La fonction dot s'en charge automatiquement, la syntaxe u' le fait explicitement, mais sum(u .* v) échouera si u et v sont complexes.

Normes

Quelle est la « taille » d'un vecteur ?

La norm est une tentative de rendre compte de cela, en réduisant le vecteur à un scalaire approprié.

Toute une famille de normes est définie, mais de loin la plus courante est la 2-norme, qui vaut √(v ⋅ v).

Cette opération de moyenne quadratique correspond à la distance pythagoricienne à l'origine (dans un espace à N dimensions). Si on visualise le vecteur comme une flèche dont la queue est posée à l'origine, la 2-norme est la longueur de la flèche.

On peut calculer n'importe quelle p-norme en passant p comme 2e argument. La 1-norme est parfois utile : c'est simplement la somme des valeurs absolues des coefficients (donc très rapide et facile à calculer).

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

Multiplication matricielle

On a parfois l'impression que tous les mathématiciens appliqués du monde ont passé une bonne partie des 80 dernières années à transformer chaque calcul en une série de multiplications matricielles.

C'est une opération dans laquelle les ordinateurs excellent :

• Elle est extrêmement répétitive.
• Elle peut être parallélisée efficacement.
• Beaucoup de matériel spécialisé a été conçu pour l'accélérer, y compris le GPU probablement intégré à ton ordinateur portable.

Les détails sont assez simples, même si ce n'est pas très intuitif au premier abord.

Considérons une matrice A qui multiplie un vecteur v pour produire une sortie w (par convention en algèbre linéaire, on utilise des majuscules pour les matrices et des minuscules pour les vecteurs).

La première ligne de A fait l'objet d'un produit scalaire avec v pour obtenir le premier élément de w, la deuxième ligne donne le deuxième élément, et ainsi de suite vers le bas.

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]

Une multiplication matrice * matrice étend cela à toutes les colonnes de la matrice de droite.

Pour C = A * B, on peut considérer que A multiplie chaque colonne de B pour donner la colonne correspondante de C : une série de multiplications matrice-vecteur.

De façon équivalente, on pourrait dire que la première ligne de A fait l'objet d'un produit scalaire avec chaque colonne de B pour donner la première ligne de C, la deuxième ligne donne la deuxième ligne, et ainsi de suite vers le bas.

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

Comme le montre l'exemple ci-dessus, la multiplication matricielle n'est pas commutative : il n'existe pas de relation simple entre A*B et B*A.

La multiplication matricielle est probablement difficile à visualiser pour qui y est nouveau, rien qu'en lisant le texte. YouTube regorge de vidéos qui la démontrent graphiquement : cherche « multiplication matricielle » et choisis celle dont le style, le niveau de détail et la langue te conviennent.

Dimensions

Le produit scalaire de deux vecteurs suppose qu'ils aient la même longueur.

Par extension, pour la multiplication matricielle, le nombre de colonnes de la matrice de gauche doit correspondre au nombre de lignes de la matrice de droite.

En exprimant les tailles sous forme de tuples (nrows, ncols), comme les renvoie size(A), on a (a, b) * (b, c) -> (a, c). Les dimensions « internes », ici b et b, sont compatibles pour le calcul des produits scalaires. Les dimensions « externes », ici a et c, déterminent les dimensions de la sortie.

Un exemple avec des matrices rectangulaires :

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

Multiplier des paires de vecteurs à la manière d'une matrice offre deux possibilités.

Par convention, on utiliserait u' * v comme équivalent du produit scalaire. Les dimensions sont (1, 3) * (3, 1), et Julia simplifie la sortie (1, 1) en un scalaire (contrairement, par exemple, à R).

Sinon, on pourrait utiliser u * v', de dimensions (3, 1) * (1, 3) -> (3, 3), pour multiplier toutes les paires d'éléments possibles et transformer les vecteurs en une matrice.

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 est parfois appelé le produit intérieur.

Rotations

Un type particulièrement courant de multiplication matricielle fait intervenir des matrices de rotation.

En 2D, il existe une matrice relativement simple pour faire tourner un vecteur de θ radians dans le sens antihoraire.

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