A lineáris algebra alapjai ebben a kurzusban:

A(z) A lineáris algebra alapjai fogalomról

Mi az a „lineáris algebra”?

Rengeteg technikai definíció létezik róla a Wikipédián, a tankönyvekben és olyan kiváló oldalakon, mint a 3Blue1Brown, de a mi céljainkra megengedhetünk magunknak egy lazább megfogalmazást.

A Julia (és Python) karbantartói imádják az ilyesmit. Az Exercism vezetősége nem annyira.

Ez a fogalom egy hatalmas témakör egyszerűbb részeire szorítkozik, de legyen egy figyelmeztetés: ez óhatatlanul meglehetősen matematikai fogalom.

Mi az a vektor?

Attól függ, kit kérdezel, és hogyan akarsz megjeleníteni valami meglehetősen absztrakt dolgot.

• Juliában a Vector{T} csupán egy aliasa az Array{T, 1} típusnak, az eltype T pedig bármi lehet.
• A fizika (nagy részében) egy vektor egy nyíl length és direction tulajdonsággal N-dimenziós térben, de rögzített pozíció nélkül.
• A lineáris algebrában a fizikusok nyila rögzítve van a térben, a farka az origóban. Ettől a nyíl szára feleslegessé válik, így a vektort egy point-ként ábrázolhatjuk N-dimenziós térben, ahol az N elem az origótól mért távolságot jelöli az N tengely mindegyike mentén.

A mostani céljainkra hagyjuk figyelmen kívül a stringekből vagy karakterekből álló vektorokat. Ebben a fogalomban numerikus típusokkal fogunk dolgozni: Int, Float vagy Complex.

Mi az a mátrix?

Itt is többféle választ találsz majd.

• Számok téglalap alakú kétdimenziós tömbje (szakadozott szélek nélkül). A négyzetes mátrix gyakori speciális eset.
• Oszlopvektorok linear combination-je, egymás mellé rendezve.
• Egy transformation, amelyet egy vektorra lehet alkalmazni, ahogy egy function-t más bemeneti típusokra alkalmazunk.

A négyzetes mátrixok néhány típusa elég gyakori ahhoz, hogy különleges neve legyen.

Átlós mátrix: Minden nem nulla elem a main diagonal-on van (bal felsőtől jobb alsóig).

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

Egységmátrix: Olyan átlós mátrix, amelynek csak egyesek vannak az átlóján (olyan okokból, amelyek később válnak világosabbá). Gyakran I-vel rövidítik.

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

Felső háromszögmátrix: Nem nulla értékek az átlón és felette, nullák alatta. Alsó háromszögmátrix, ezt kitalálhatod.

Mátrix transzponálása

Ha tényleg sorokat akarsz oszlopokkal felcserélni, a permutedims() függvény megteszi, és egy új mátrixot ad vissza.

Ez másolással jár, ami lassú és memóriaigényes, ha nagy mátrixokkal dolgozol.

Lineáris algebrai szempontból a transpose() függvény hasznosabb, mert gyorsan egy lazy wrappert készít az eredeti mátrix köré.

Még hasznosabb az adjoint() függvény, amely a komplex számok képzetes részének előjelét is megfordítja (ha azon tűnődsz, miért olyan fontos, egy gyors válasz a kvantummechanika). Ez a művelet elég gyakori ahhoz, hogy egyszerűen egy aposztrófot ' tegyünk a változó neve után, és máris megvan az adjungált.

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

Szorzás

A dokumentum hátralévő része a LinearAlgebra modul funkcióit használja. Egy using LinearAlgebra sor behozza a névtérbe, de a példákban nem fogjuk ezt folyton ismételni (túl sok vizuális zaj).

Vektorok, elemenkénti szorzat

Erről a vektorműveletek fogalomban volt szó. Az operátor a .*, amely páronként működik a bemeneti vektorokon, és a bemenetekkel azonos méretű és típusú kimenetet ad.

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

Vektorok, skaláris szorzat

Ezt a rendkívül gyakori műveletet a tankönyvek u ⋅ v alakban írják, és „dot” szorzatnak nevezik.

A skaláris szorzat egyenlő az elemenkénti szorzat összegével.

Két vektor a szokásos * operátorral összeszorozható, de csak akkor, ha a bal oldali vektor egy adjoint: kényelmesen u' * v alakban írva. Ez a mátrixszorzásról szóló későbbi részben válik majd világosabbá.

A kiemelt (középső) pont Juliában (a \cdot és tab billentyűkkel beírva) a dot() függvény szintaktikai cukorkájaként érhető el. Nem kell megadni az adjungáltat, mert ezt a részletet automatikusan kezeli.

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

Komplex értékű vektoroknál a bal oldali vektornak a konjugáltnak kell lennie (a képzetes rész előjele megfordul). A dot függvény ezt automatikusan elvégzi, az u' szintaxis explicit módon, de a sum(u .* v) hibát ad, ha u és v komplex.

Vektorok, vektoriális szorzat

Egy kis nosztalgia mindenkinek, aki valaha járt elektromosságtan és mágnesességtan kurzusra! És azoknak a mérnököknek is, akik ismerik a forgatónyomaték vagy a perdületvektorok számítását.

Míg a skaláris szorzat két vektort egy scalar-rá alakít, addig a vektoriális szorzat két háromelemű vektort egy harmadik háromelemű vektorrá.

A vektortér geometriai ábrázolásában az új vektor merőleges a két bemeneti vektort tartalmazó síkra. Ha a két bemenet párhuzamos (előjelig), nem határoznak meg síkot, így a kimenet [0, 0, 0] lesz.

A sorrend számít: u × v == -(v × u). Ez a híres jobbkézszabály, amely miatt sokan bámultuk a hüvelykujjunkat és két ujjunkat, miközben a térben forgattuk őket (gyakran tanácstalan arckifejezéssel).

# 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

Figyeld meg, hogy ez a művelet a háromelemű vektorokra korlátozódik (ami megfelel az ortogonális x, y, z tengelyű euklideszi térnek). A matematikusok szívesen definiálják a műveletet más dimenziókra is, aminek eredménye egy érthetetlen szóhalmaz (magasabb rendű tenzorok, ékszorzat, külső szorzat, multivektorok...). A legtöbbünk ezen a ponton elfut, vagy gyorsan más témára vált!

Normák

Mennyire „nagy” egy vektor?

A norm erre tesz kísérletet, a vektort egy megfelelő skalárra redukálva.

A normáknak egy egész családja definiált, de messze a leggyakoribb a 2-norma, amely √(v ⋅ v).

Ez a négyzetes közép művelet a pitagoraszi távolság az origótól (N-dimenziós térben). Ha a vektort nyílként ábrázoljuk, a farkával az origóban, a 2-norma a nyíl hossza.

Bármely p-norma kiszámítható úgy, hogy a p-t adjuk meg második argumentumként. Az 1-norma néha hasznos: egyszerűen az elemek abszolút értékeinek összege (tehát nagyon gyorsan és könnyen kiszámítható).

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

Mátrixszorzás

Néha úgy tűnik, mintha a világ minden alkalmazott matematikusa az elmúlt 80 év nagy részét azzal töltötte volna, hogy minden számítást mátrixszorzások sorozatává alakítson.

Ez egy olyan művelet, amiben a számítógépek nagyon jók:

• Nagyon ismétlődő.
• Hatékonyan párhuzamosítható.
• Rengeteg speciális hardvert fejlesztettek ki a gyorsítására, a 70-es évek 80 millió dolláros Cray-1 gépétől a laptopodba valószínűleg beépített GPU-ig.

A részletek meglehetősen egyszerűek, bár első ránézésre nem túl intuitívak.

Tekintsük azt az esetet, amikor egy A mátrix megszoroz egy v vektort, és w kimenetet ad (a lineáris algebra szokása szerint a mátrixokat nagybetűvel, a vektorokat kisbetűvel jelöljük).

Az A legfelső sorát skalárisan megszorozzuk v-vel, így megkapjuk w első elemét, a második sor a második elemet adja, és így tovább lefelé.

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]

A mátrix * mátrix szorzás ezt kiterjeszti a jobb oldali mátrix oszlopaira.

A C = A * B esetében úgy tekinthetjük, hogy A megszorozza B minden oszlopát, és megadja C megfelelő oszlopát: mátrix-vektor szorzások sorozatát.

Ezzel egyenértékűen azt mondhatjuk, hogy A első sorát skalárisan megszorozzuk B minden oszlopával, így megkapjuk C legfelső sorát, a második sor a második sort adja, és így tovább.

Több ilyen gondolati modell is létezik, és az érdeklődő tanulók egy egész MIT-előadást megnézhetnek róluk.

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

Ahogy a fenti példa mutatja, a mátrixszorzás nem kommutatív: nincs egyszerű összefüggés A*B és B*A között.

A mátrixszorzást valószínűleg nehéz megjeleníteni mindenkinek, aki most találkozik vele, pusztán a szöveget olvasva. A YouTube-on rengeteg videó mutatja be grafikusan, ezért keress rá a „matrix multiplication” kifejezésre, és válassz egyet a neked tetsző stílus, részletesség és nyelv szerint.

Dimenziók

Két vektor skaláris szorzata azon alapul, hogy egyenlő hosszúak.

Ezt kiterjesztve, a mátrixszorzásnál a bal oldali mátrix oszlopainak száma meg kell egyezzen a jobb oldali mátrix sorainak számával.

A méreteket (nrows, ncols) tuple-ként kifejezve, ahogy a size(A) kiírja, (a, b) * (b, c) -> (a, c) adódik. A „belső” dimenziók, itt b és b, kompatibilisek a skaláris szorzat képzésével. A „külső” dimenziók, itt a és c, határozzák meg a kimenet méreteit.

Egy példa téglalap alakú mátrixokkal:

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

Vektorok páronkénti szorzásának mátrixos stílusban két lehetősége van.

Szokás szerint u' * v-t használnánk a skaláris szorzat megfelelőjeként. A dimenziók (1, 3) * (3, 1), és a Julia a (1, 1) kimenetet skalárra egyszerűsíti (ellentétben például az R-rel).

Alternatívaként használhatjuk az u * v'-t, (3, 1) * (1, 3) -> (3, 3) dimenziókkal, hogy az elemek összes lehetséges párját megszorozzuk, és a vektorokat mátrixszá bővítsük.

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

Az u' * v-t néha belső szorzatnak nevezik.

A (kevésbé gyakori) u * v' ennek megfelelően a külső szorzat. Ez a tenzorszorzathoz kapcsolódik, bár az messze meghaladja a kereteinket.

Forgatások

A mátrixszorzás egy különösen gyakori típusa a forgatási mátrixok használata.

2D-ben van egy viszonylag egyszerű mátrix, amely egy vektort θ radiánnal az óramutató járásával ellentétes irányba forgat.

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

A 3D-s forgatásokhoz bonyolultabb mátrix kell, két szöggel. Ezt nehéz sok LaTeX beágyazása nélkül megjeleníteni egy Markdown-dokumentumban, ezért a képletért nézd meg a Wikipédiát.

A 3D-s grafikában, például az OpenGL-ben és utódaiban, a szokás a homogén koordinátákkal való munka.

Minden csúcsot egy 4-elemű vektor (vagy ezzel egyenértékűen egy mátrixoszlop) reprezentál: [x, y, z, 1.0] egy (x, y, z) pontban lévő ponthoz.

Ez lehetővé teszi bonyolultabb transzformációs mátrixokat. A forgatás továbbra is az A[1:3, 1:3] helyen van, az eltolások [Δx, Δy, Δz] alakban az A[1:3, 4] helyen, a méretezés az átlón, és más lehetőségek is léteznek nyírásra, perspektívára stb.

Teljesítmény

A világ számítástudományi tanszékein sok doktori disszertáció tartalmaz egy vagy több fejezetet a mátrixszorzó algoritmusok apró, fokozatos fejlesztéseiről. Ez nagyon fontos, és különféle szervezetek hajlandók finanszírozni a kutatást a saját hasznukra.

A teljesítmény nagy téma, amibe nem tudunk mélyen belemenni, de szemléltetésképpen megpróbálhatunk különböző méretű véletlen mátrixokat összeszorozni.

Az alábbi kód egy gyors és durva becslés (jobb megközelítéshez használd a BenchmarkTools.jl csomagot).

A használt rendszer egy kicsi, 430 dolláros (amerikai) PC volt: Ryzen 9 processzor, 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)

Nagyjából az egymillió elemű mátrixok pár ezredmásodpercet vettek igénybe, a százmillió eleműek pár másodpercet. Több nagyságrenddel feljebb már jobb hardverre lesz szükség...