1. Domácí úkol: Gauss

Úvod

Prvním domácím úkolem se vrátíme k studentům velmi dobře známému lineárně-algebraickému algoritmu, ke Gaussově eliminační metodě (GEM). Obsahem tohoto úkolu cílíme zejména na následující body:

Carl Friedrich Gauss byl jedním z největších matematiků a na jeho jméno narazíte ve spoustě matematických partií. V případě GEM nelze tvrdit, že by byl jejím prvním objevitelem. Jisté verze GEM existovaly již dříve a stopy vedou až k čínským matematikům do doby před naším letopočtem. Pravdou ovšem zůstává, že Gauss se touto metodou zabýval systematicky a to včetně důkazů. V literatuře občas také narazíte na alternativní název "Gauss–Jordanova eliminace."

Teoretický background

Implementační cíle úkolu jsou tři:

Všechny z uvedených metod budou moci pracovat s různými číselnými datovými typy (strojová čísla, komplexní čísla, racionální čísla, modulární aritmetika). Podrobně jsou tyto metody popsány dále v textu. V implementaci funkcí inverse a solve půjde přirozeně využít funkci echelon_form!.

Svůj kód umístěte do souboru gauss.jl, kde je i předpřipravena nekompletní šablona. V tomto souboru můžete (a je to velmi vhodné) definovat i další pomocné metody. Případně můžete přidat i další testy do adresáře test, viz sekci Lokální spouštění testů.

Než se pustíme do formálního popisu zadání, rychle připomeneme/představíme matematické pozadí problému.

[
  0 1 0 0 3 0
  0 0 1 0 2 0
  0 0 0 1 1 0
  0 0 0 0 0 1
  0 0 0 0 0 0
]

Implementační pokyny

Naše implementace musí zvládnout pracovat s maticemi s prvky minimálně následujících typů

Pokud to bude možné, tak se budeme snažit počítat v exaktní aritmetice.

Vaše implementace by ale měla fungovat i s dalšími podobnými typy. Nezapomínejte, že máte k dispozici abstraktní typy jako AbstractFloat nebo Integer.

julia> A = [1 2 3; 4 5 6];

julia> echelon_form!(A)
2×3 Matrix{Rational{Int64}}:
 1//1  0//1  -1//1
 0//1  1//1   2//1

julia> A = [1.0 1.0 -1.0; 1.0 -1.0 1.0; -1.0 1.0 1.0];

julia> inverse(A)
3×3 Matrix{Float64}:
 0.5  0.5  0.0
 0.5  0.0  0.5
 0.0  0.5  0.5

julia> A = [1.0 1.0 -1.0; 1.0 -1.0 1.0; -1.0 1.0 1.0];

julia> b = [1.0, 1.0, 1.0];

julia> solve(A, b)
3-element Vector{Float64}:
 1.0
 1.0

Lokální spouštění testů

Toto zadání je úmyslně vytvořeno lehce "na koleni" a nevyužívá například moduly nebo Julia projekty ke správě závislostí (látka, ke které se dostaneme později během semestru).

K lokálnímu spuštění budete proto pravděpodobně potřebovat doinstalovat balíčky Glob a GaloisFields.

import Pkg; Pkg.add("Glob"); Pkg.add("GaloisFields")

Poté v kořenovém adresáři tohoto zadání stačí z příkazové řádky spustit

$ julia --color=yes test/runtests.jl

Tímto příkazem spustíte všechny test v souborech test/test_*.jl. Případně tak do adresáře test můžete snadno přidat i další pomocné vlastní testy vlastních pomocných metod, jen je musíte pojmenovat ve tvaru test_*.jl.

Pokud vše dopadne dobře, měli byste vidět následující standardní výstup:

$ julia test/runtests.jl
┌ Info: Running tests in test_echelon_form.jl...
└ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Test Summary:                                                | Pass  Total
echelon_form!: integer and trivial examples                  |    8      8
Test Summary:                                                | Pass  Total
echelon_form!: over rational numbers                         |    4      4
Test Summary:                                                | Pass  Total
echelon_form!: GaloisField, GF(5)                            |    4      4
Test Summary:                                                | Pass  Total
echelon_form!: Float64                                       |    3      3
Test Summary:                                                | Pass  Total
echelon_form!: BigFloat                                      |    3      3
┌ Info: Running tests in test_inverse.jl...
└ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Test Summary:                                                | Pass  Total
inverse: non-invertible matrices                             |    3      3
Test Summary:                                                | Pass  Total
inverse: computation over rational field, small examples     |    3      3
Test Summary:                                                | Pass  Total
inverse: computation in floating point arithmetic            |    2      2
┌ Info: Running tests in test_other.jl...
└ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
...
...
...
┌ Info: Running tests in test_solve.jl...
└ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Test Summary:                                                | Pass  Total
solve: non-solvable examples                                 |    2      2
Test Summary:                                                | Pass  Total
solve: simple solvable examples                              |    4      4
Test Summary:                                                | Pass  Total
solve: a badly conditioned system                            |    1      1
Test Summary:                                                | Pass  Total
solve: randomized tests                                      |    3      3

V opačném případě dostanete od Julia vynadáno!

Řešení a odevzdání

Opět vytvořte větev odvozenou z větve assignment/01-gauss a nezvěte ji například solution/01-gauss. Do solution/01-gauss vložte své řešení editací souboru gauss.jl případně přidáním testů do složky test. Až budete se svým řešením spokojeni, vytvořte MR (to můžete i dříve, aspoň uvidíte výsledek testů, pokud je nespouštíte lokálně) a přiřaďte mě k němu jako assignee. Tímto aktem úkol odevzdáte.

Poznámky

julia> using GaloisFields; import GaloisFields: AbstractGaloisField

julia> Z5 = GaloisField(5)
𝔽₅

julia> m1 = Z5[1 2; 3 4]
2×2 Matrix{𝔽₅}:
 1  2
 3  4

julia> m1 * m1
2×2 Matrix{𝔽₅}:
 2  0
 0  2

julia> m1 + m1
2×2 Matrix{𝔽₅}:
 2  4
 1  3

julia> Z5 <: AbstractGaloisField
true