Revolução dos robôs

O que é a "Álgebra Linear"?

Há imensas definições técnicas, na [Wikipédia][linalg-wiki], em manuais e em sites excelentes como o [3Blue1Brown][3blue1brown], mas para o que nos interessa podemos ser mais informais.

Os responsáveis do Julia (e do Python) adoram este tipo de coisas. A direção do Exercism, nem tanto.

Este Conceito vai limitar-se aos aspetos mais simples de um tema enorme, mas fica avisado: isto é, inevitavelmente, um conceito bastante matemático.

O que é um vetor?

Depende de quem perguntas e de como queres visualizar algo bastante abstrato.

• Em Julia, Vector{T} é apenas um alias para Array{T, 1}, e o eltype T pode ser qualquer coisa.
• Em (grande parte da) Física, um vetor é uma seta com um length e uma direction no espaço N-dimensional, mas sem posição fixa.
• Em Álgebra Linear, a seta dos físicos está fixa no espaço, com a cauda na origem. Isto torna a haste da seta redundante, por isso podemos representar o vetor como um point no espaço N-dimensional, em que os N elementos representam a distância à origem ao longo de cada um dos N eixos.

Para o que aqui nos interessa, ignora vetores de strings ou carateres. Neste Conceito vamos trabalhar com tipos numéricos: Int, Float ou Complex.

O que é uma matriz?

Mais uma vez, vais encontrar respostas variadas.

• Um array retangular 2-D de números (sem linhas irregulares). Uma matriz quadrada é um caso especial comum.
• Uma linear combination de vetores coluna, empilhados lado a lado.
• Uma transformation que pode ser aplicada a um vetor, tal como uma function é aplicada a outros tipos de entrada.

Alguns tipos de matriz quadrada são suficientemente comuns para terem nomes especiais.

Matriz diagonal: Todas as entradas não nulas estão na main diagonal (do canto superior esquerdo ao canto inferior direito).

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

Matriz identidade: Uma matriz diagonal com apenas uns na diagonal (por razões que se tornarão mais claras mais adiante). Muitas vezes abreviada como 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

Triangular superior: Valores não nulos sobre a diagonal e acima dela, zeros abaixo. Triangular inferior já podes adivinhar.

Transpor uma matriz

Se quiseres mesmo trocar linhas por colunas, a função permutedims() faz isso e devolve-te uma nova matriz.

Isto implica uma cópia, o que é lento e consome muita memória quando trabalhas com matrizes grandes.

Para efeitos de Álgebra Linear, a função transpose() é mais útil, pois cria rapidamente um wrapper lazy em torno da matriz original.

Ainda mais útil é a função adjoint(), que também inverte o sinal da parte imaginária em quaisquer números complexos. Esta operação é suficientemente comum para que possamos simplesmente acrescentar um apóstrofo ' ao nome da variável para criar o 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

Multiplicação

O resto deste documento inclui funcionalidades do módulo LinearAlgebra. Uma linha using LinearAlgebra traz isso para o namespace, mas não vamos repetir isto nos exemplos (demasiada poluição visual).

Vetores, produto elemento a elemento

Isto foi abordado no Conceito [Operações com Vetores][vector-ops]. O operador é .*, que opera sobre os vetores de entrada aos pares, dando origem a uma saída com o mesmo tamanho e tipo dos vetores de entrada.

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

Vetores, produto escalar

Esta operação extremamente comum é escrita nos manuais como u ⋅ v e é chamada produto escalar.

Um produto escalar é equivalente à soma do produto elemento a elemento.

Dois vetores podem ser multiplicados com o operador * habitual, mas apenas se o vetor da esquerda for um adjoint: convenientemente escrito u' * v. Isto ficará mais claro mais à frente, na secção sobre multiplicação de matrizes.

O ponto elevado (ao centro) está disponível em Julia (escreve-se \cdot e prime-se tab) como açúcar sintático para a função dot(). Não é preciso especificar o adjoint, pois este detalhe é tratado automaticamente.

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

Para vetores com valores complexos, o vetor da esquerda tem de ser o conjugado (sinal invertido na parte imaginária). A função dot faz isto automaticamente, a sintaxe u' fá-lo explicitamente, mas sum(u .* v) falha se u e v forem complexos.

Normas

Quão "grande" é um vetor?

A norm é uma tentativa de captar isso, reduzindo o vetor a um escalar apropriado.

Está definida toda uma família de normas, mas de longe a mais comum é a norma 2, que é √(v ⋅ v).

Esta operação de raiz quadrada da soma dos quadrados é a distância pitagórica à origem (no espaço N-dimensional). Se visualizarmos o vetor como uma seta, com a cauda na origem, a norma 2 é o comprimento da seta.

Qualquer norma p pode ser calculada fornecendo p como segundo argumento. A norma 1 é por vezes útil: é simplesmente a soma dos valores absolutos das entradas (por isso é muito rápida e fácil de calcular).

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

Multiplicação de matrizes

Por vezes parece que todos os matemáticos aplicados do mundo passaram grande parte dos últimos 80 anos a transformar todos os cálculos numa série de multiplicações de matrizes.

Esta é uma operação em que os computadores são muito bons:

• É altamente repetitiva.
• Pode ser paralelizada de forma eficiente.
• Foi desenvolvido muito hardware especializado para a tornar mais rápida, incluindo a GPU que provavelmente está integrada no teu portátil.

Os detalhes são bastante simples, embora não muito intuitivos à primeira vista.

Considera uma matriz A a multiplicar um vetor v para dar uma saída w (por convenção da Álgebra Linear, usamos letras maiúsculas para matrizes e minúsculas para vetores).

Faz-se o produto escalar da primeira linha de A com v para obter o primeiro elemento de w, a segunda linha dá o segundo elemento, e assim sucessivamente, linha a linha.

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]

Uma multiplicação matriz * matriz estende isto às colunas da matriz da direita.

Para C = A * B, podemos considerar que A multiplica cada coluna de B para dar a coluna correspondente de C: uma série de multiplicações matriz-vetor.

De forma equivalente, podemos dizer que se faz o produto escalar da primeira linha de A com cada coluna de B para dar a primeira linha de C, a segunda linha dá a segunda linha, e assim sucessivamente.

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

Como mostra o exemplo acima, a multiplicação de matrizes não é comutativa: não há uma relação simples entre A*B e B*A.

A multiplicação de matrizes é provavelmente difícil de visualizar só pela leitura das palavras, para quem está a contactar com ela pela primeira vez. O YouTube tem imensos vídeos que a demonstram graficamente, por isso pesquisa por "multiplicação de matrizes" e escolhe um com o estilo, o nível de detalhe e a língua que preferires.

Dimensões

O produto escalar de dois vetores depende de ambos terem o mesmo comprimento.

Por extensão, na multiplicação de matrizes o número de colunas da matriz da esquerda tem de coincidir com o número de linhas da matriz da direita.

Se expressarmos os tamanhos como tuplos (nrows, ncols), tal como são devolvidos por size(A), temos (a, b) * (b, c) -> (a, c). As dimensões "internas", aqui b e b, são compatíveis com o cálculo de produtos escalares. As dimensões "externas", aqui a e c, determinam as dimensões da saída.

Um exemplo com matrizes retangulares:

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

Multiplicar pares de vetores, ao estilo matricial, tem duas possibilidades.

Convencionalmente, usaríamos u' * v como equivalente ao produto escalar. As dimensões são (1, 3) * (3, 1), e o Julia simplifica a saída (1, 1) para um escalar (ao contrário, por exemplo, do R).

Em alternativa, poderíamos usar u * v', com dimensões (3, 1) * (1, 3) -> (3, 3), para multiplicar todos os pares possíveis de elementos e expandir os vetores numa matriz.

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 é por vezes chamado de produto interno.

Rotações

Um tipo particularmente comum de multiplicação de matrizes envolve matrizes de rotação.

Em 2D, existe uma matriz relativamente simples para rodar um vetor no sentido contrário ao dos ponteiros do relógio em θ radianos.

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