Řešení soustav lineárních rovnic v SageMath

SageMath je open-source počítačový algebraický systém využívající programovací jazyk Python. Tento příspěvek stručně ukazuje, jak lze SageMath využít při řešení té nejčastější úlohy v příkladech lineární algebry: řešení soustavy lineárních rovnic. V textu se dotkneme jen úplných základů, zvídavý čtenář nalezne více ukázek použití v tomto repozitáři. Ukážeme si ale, jak řešit soustavy i v konečných číselných tělesech.

Příklad

Vyřešme jeden z úvodních příkladů z prvního cvičení BI-LIN: nalezněte průnik následujících dvou rovin v $\mathbb{R}^3$, \[ r: \ x+y=0, \quad s: \ z = x - 2y + 3. \]

Začněme nejprve přímočarým postupem bez použití pojmů lineární algebry. Nejprve vytvoříme symbolické proměnné $x$, $y$ a $z$ reprezentující neznámé:

var('x,y,z')

K řešení (nejen) soustav lineárních rovnic lze v SageMath použít příkaz solve. Prvním argumentem tohoto příkazu je list (nebo tuple) rovnic a druhým argumentem pak list (nebo tuple) neznámých. V našem konkrétním příkladě proto provedeme

solve([x + y == 0, z == x - 2*y + 3], [x, y, z])

Odpovědí SageMath bude:

[[x == 1/3*r1 - 1, y == -1/3*r1 + 1, z == r1]]

Zde r1 je nová symbolická proměnná. Jinak řečeno, množina všech řešení naší soustavy je parametrizována jedním parametrem $r_1$ a tvoří proto přímku v $\mathbb{R}^3$. Výše uvedený výsledek není nic jiného než parametrické rovnice této přímky.

Maticová notace

Výše uvedený přístup lze přirozeně rozšířit na libovolnou jinou soustavu lineárních rovnic. Stačí jen vytvořit příslušné symbolické proměnné (neznámé), sepsat rovnice, a pak použít funkci/příkaz solve. Tento přístup ale není příliš šikovný, zejména z následujících důvodů:

• Sepisovat takto ručně rovnice je náchylné na vytvoření chyby.
• S výsledkem v parametrickém tvaru se špatně dále pracuje.

Z přednášek lineární algebry již jistě víte, že libovolnou soustavu $m$ lineárních rovnic o $n$ neznámých můžete zapsat v kompaktním maticovém tvaru \[ \mathbb{A} x = b, \] kde $\mathbb{A}$ je matice soustavy typu $m \times n$, $x$ je vektor neznámých o $n$ složkách a $b$ je vektor pravých stran o $m$ složkách. Složky této matice a vektorů patří do jistého tělesa $T$, v kterém se celý náš výpočet odehrává (typicky racionální čísla, reálná čísla, komplexní čísla nebo prvky zvoleného konečného tělesa).

Příklad znovu

Vraťme se k příkladu uvedenému výše. Zaveďme matici příslušné soustavy a vektor pravých stran,

A = matrix(QQ, [
    [1,  1,  0],
    [1, -2, -1]
])
b = vector(QQ, [0, -3])

show(A)

\[ \left(\begin{array}{rrr} 1 & 1 & 0 \\ 1 & -2 & -1 \end{array}\right) \]

K vytvoření matice používáme funkci matrix, které lze předat matici ve tvaru vnořených listů (tento zápis je prakticky totožný s Mathematica) a jako nepovinný parametr číselné těleso, nad kterým matici konstruujeme. V tomto případě jsme zvolili nejmenší možné těleso racionálních čísel ($\mathbb{Q}$ v SageMath skryté pod QQ; to nám na většinu výpočtů stačí, protože v GEM pouze sčítáme, odčítáme, násobíme a dělíme, čímž množinu racionálních čísel neopustíme). K vytvoření vektoru používáme funkci vector, jejíž syntaxe je podobná.

Před vlastním řešením soustavy si dovolme drobnou odbočku. Na objektu typu matice můžeme volat celou řadu užitečnách metod (můžete je prozkoumat stistknutím tabulátoru za A.). Například hodnost matice A je rovna dvěma, jak se snadno přesvědčíme pomocí metody rank (což je anglicky hodnost),

A.rank()

Řešení

Přistupme nyní k samotnému řešení naší soustavy. Nejprve nalezneme partikulární řešení soustavy $\mathbb{A} x = b$. K tomu lze použít metodu solve_right

vp = A.solve_right(b)
show(vp)

\[ \left(-1,\,1,\,0\right) \]

Ověřme, že se skutečně jedná o řešení: příkaz

A * vp == b

skutečně vrací True.

Abychom nalezli všechna řešení naší soustavy $\mathbb{A} x = b$, musíme ještě nalézt všechna řešení příslušné homogenní (s nulovou pravou stranou) soustavy. K tomu slouží metoda right_kernel, provedením

S0 = A.right_kernel()
S0

SageMath vypíše

Vector space of degree 3 and dimension 1 over Rational Field
Basis matrix:
[ 1 -1  3]

To nás nepřekvapuje, neboť víme, že množina všech řešení homogenní soustavy tvoří vektorový prostor. Také jeho dimenze není překvapivá, již jsme nalezli hodnost matice ($2$), známe dimenzi $\mathbb{R}^3$ a proto je dimenzí prostoru všech řešení $1 = 3 - 2$.

Množina všech řešení naší soustavy je dána součtem $v_p + S_0$.

Poznámky

Bázi podprostoru $S_0$ lze získat pomocí metody basis. Příkaz

S0.basis()

v tomto případě vrací list obsahující jeden bazický vektor (dimenze $S_0$ je $1$)

[
(1, -1, 3)
]

Snadno tak můžeme množinu všech řešení naší soustavy parametrizovat:

var('t')
vp + t * S0.basis()[0]

vrací

(t - 1, -t + 1, 3*t)

Porovnávání

Všimněte si, že výše získané výsledky se liší. To je v lineární algebře celkem častá situace. Ačkoliv množina všech řešení je dána jednoznačně, její vyjádření jednoznačné zdaleka není.

V předcházejícím textu jsme zjistili, že tato množina je dána jako $v_p + S_0$ a současně jako množina všech vektorů tvaru $(1/3 r_1 - 1, \ -1/3 r_1 + 1, \ r_1)$, kde $r_1 \in \mathbb{R}$ je parametr. Jinak řečeno, v druhém případě vidíme, že množina všech řešení je dána jako součet $w_p + T_0$, kde

wp = vector(QQ, [-1, 1, 0])
T0 = (QQ^3).span([vector([1/3, -1/3, 1])])

Množiny $v_p + S_0$ a $w_p + T_0$ jsou totožné, právě když $S_0 = T_0$ a $v_p - w_p \in S_0$. O tom se snadno přesvědčíme,

S0 == T0

vrací True, stejně jako

vp - wp in S0

Příklad v modulární aritmetice

V Příkladě 1.8 na cvičení jsme měli vyřešit soustavu \begin{align*} v_1 + v_3 &= 1, \\ v_1 + v_2 + v_4 + v_5 &= 1, \\ v_3 + v_4 &= 1, \\ v_2 + v_4 &= 1, \\ v_2 + v_5 &= 1, \end{align*} kde neznámé $v_1,v_2,\ldots,v_5$ patří do $\mathbb{Z}_2 = \{0,1\}$ a počítáme modulo $2$.

V SageMath můžeme tento problém řešit úplně stejně jako výše. Maticí soustavy a vektorem pravých stran jsou (GF(2) v SageMath představuje konečné těleso o dvou prvcích; *Galois field*)

A = matrix(GF(2), [
    [1, 0, 1, 0, 0],
    [1, 1, 0, 1, 1],
    [0, 0, 1, 1, 0],
    [0, 1, 0, 1, 0],
    [0, 1, 0, 0, 1]
])

b = vector(GF(2), [1, 1, 1, 1, 1])

show(A)

\[ \left(\begin{array}{rrrrr} 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \end{array}\right) \]

Nalezneme partikulární řešení

vp = A.solve_right(b)
show(vp)

\[ \left(0,\,1,\,1,\,0,\,0\right) \]

Dále nalezneme množinu řešení homogenní soustavy

S0 = A.right_kernel()
S0

Vector space of degree 5 and dimension 1 over Finite Field of size 2
Basis matrix:
[1 1 1 1 1]

Tudíž, množina všech řešení je dvouprvková ($S_0$ je jednodimenzionální a konečné těleso $GF(2)$ má dva prvky):

[vp + u for u in S0]

[(0, 1, 1, 0, 0), (1, 0, 0, 1, 1)]