Lekce 2 - Matice a základní operace s nimi, nejen v kódu

V minulé lekci, Faktoriál, jsme si ukázali algoritmus pro výpočet faktoriálu včetně popisu a zdrojového kódu bez rekurze i s rekurzí.

Dnes se zaměříme na seznámení s pojmem matice a vysvětlíme si základních matematické operace včetně ukázky převedení do kódu.

Motivace

S maticemi jste se již možná někdy v matematice setkali, a tak víte, že se běžně používají k řešení soustav lineárních rovnic. Mnohem zajímavější tak může být fakt, že mají dobré využití také například v počítačové grafice či kryptografii. V počítačové grafice se matice používají například k lineárním transformacím jako posunutí, rotace, škálování a zkosení nebo převodu mezi soustavnými systémy. V kryptografii matice využívá například tzv. Hillova šifra vynalezena v roce 1929.

Co jsou to matice?

Jsou to čtvercová či obdélníková schémata složená z prvků. Například tedy z čísel, uspořádaných do m řádků a n sloupců (pro čtvercovou matici tedy platí m = n). Prvky matice jsou značeny jako a_ij, kde i označuje řádek a j sloupec v matici. Například prvek a_15 se tedy nachází v pátém sloupci prvního řádku:

Příklady matic

Pro ukázku si ukážeme čtvercovou a obdélníkovou matici:

Čtvercová matice.

Obdélníková matice

Druhy matic

Matice máme:

• diagonální,
• trojúhelníkové,
• řádkové
• a sloupcové.

Všechny si teď postupně probereme

Diagonální

Matice, která obsahuje nenulové prvky pouze na diagonále, se nazývá diagonální. Musí tedy platit:

• a_ij = 0 pro i ≠ j
• a a_ij ≠ 0 pro i = j.

Speciálním případem diagonální matice je tzv. jednotková matice. Ta musí mít na diagonále samé jedničky, tedy a_ij = 1 pro i = j:

Trojúhelníkové

Pro trojúhelníkovou matici platí, že má pod diagonálou všechny prvky rovny nule - horní trojúhelníková (vlevo), nebo nad diagonálou - dolní trojúhelníková (vpravo):

Řádková matice/vektor

Matice může mít mít samozřejmě jeden z rozměrů roven i 1. Pokud je typu 1 × n, hovoříme o tzv. řádkové matici:

Sloupcový matice/vektor

V opačném případě, kdy má matice rozměry m × 1, se jedná o sloupcovou matici:

Jak reprezentovat matice v kódu

Matici si můžeme představit jako tabulku prvků, pro její reprezentaci můžeme tedy využít dvourozměrné pole. Pro opakovanou práci s maticemi se nám bude hodit udělat si nějaký objekt, který je bude reprezentovat a bude na něm možné používat operace zmíněné dále v článku. Vytvoříme si tedy jednoduchou strukturu reprezentující matici, v které si uložíme rozměry a hodnoty. Na uložení hodnot použijeme již zmíněné dvourozměrné pole:

public struct Matrix
    {
        public int rows { get; private set; }
        public int columns { get; private set; }
        public double[,] data { get; private set; }

        /// <param name="m">number of rows</param>
        /// <param name="n">number of columns</param>
        public Matrix(int m, int n, Queue<double> values)
        {
            rows = m;
            columns = n;
            data = new double[m, n];

            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    data[i, j] = values.Dequeue();
        }
    }

Základní operace s maticemi

Jelikož v maticích máme zaznamenané hodnoty či data, s kterými pravděpodobně chceme nadále pracovat, potřebujeme se naučit aplikovat matematické operace.

Negace

Někdy se nám hodí umět znegovat hodnotu, u matic to samozřejmě jde také. Stačí pro každý prvek matice otočit znaménko a výsledná matice bude negací původní:

V kódu by to vypadalo takto:

public static Matrix operator -(Matrix A)
        {
            Queue<double> results = new Queue<double>();
            for (int i = 0; i < A.rows; i++)
                for (int j = 0; j < A.columns; j++)
                    results.Enqueue(-A.data[i, j]);

            return new Matrix(A.rows, A.columns, results);
        }

Sčítání/odčítání

Sčítání a odčítání jsou velmi jednoduché operace. Obě fungují na stejném principu, a to sečtení/odečtení prvku na stejných pozicích v maticích. Vezmeme si tedy matici A typu 2 × 2 a matici B typu 2 × 2, jednoduše pak pro každé i a j uděláme operaci a_ij + b_ij. Jelikož a_ij i b_ij jsou již normální číselné hodnoty, můžeme je spolu sečíst/odečíst. Vznikne nám tedy nová matice C, kde každý prvek je výsledkem zmíněné operace. Někteří již možná postřehli, že abychom mohli operaci sčítání/odčítání provést, musí byt matice stejného typu. Nejde tedy sečíst například matici typu 2 × 3 s maticí 2 × 2.

Pro maticové sčítání navíc platí, že je komutativní a asociativní.

Příklad sčítání a odčítání matic A a B:

Sčítání v kódu:

public static Matrix operator + (Matrix A, Matrix B)
        {
            if (A.rows != B.rows || A.columns != B.columns)
                throw new InvalidOperationException("Matrices are not of the same type");

            Queue<double> results = new Queue<double>();
            for (int i = 0; i < A.rows; i++)
                for (int j = 0; j < A.columns; j++)
                    results.Enqueue(A.data[i,j] + B.data[i,j]);

            return new Matrix(A.rows, A.columns, results);
        }

Odčítání by bylo naprosto totožné, s pouhou změnou operátoru + na -. Abychom zbytečně neopakovali kód, můžeme využít implementace negace matice a přepsat odčítání jako přičtení negace, tedy A + (-B):

public static Matrix operator -(Matrix A, Matrix B)
        {
            return A + (-B);
        }

Násobení skalárem

Další velmi jednoduchá operace je násobení skalárem. V případě, že chceme celou matici vynásobit nějakou hodnotou n, je to to stejné, jako kdybychom n těchto matic k sobě přičetli. Platí tedy, že ve výsledné matici B je každý prvek b_ij výsledkem operace n × a_ij:

V kódu by to mohlo vypadat takto:

public static Matrix operator *(double multiplier, Matrix A)
        {
            Queue<double> results = new Queue<double>();
            for (int i = 0; i < A.rows; i++)
                for (int j = 0; j < A.columns; j++)
                    results.Enqueue(A.data[i, j] * multiplier);

            return new Matrix(A.rows, A.columns, results);
        }

Násobení matice maticí

Nejtěžší ze zmíněných základních operací je určitě násobení matice maticí. Mějme matice A typu m × n a B typu k × l, které spolu chceme vynásobit. Abychom tuto operaci mohli provést, musí platit, že počet sloupců matice A je roven počtu řádků matice B - tedy n = k. Výsledná matice C má pak rozměry m x l. Jak tedy vypočteme prvky výsledné matice? Ukážeme si to na jednoduchém příkladu:

Jak vidíme na obrázku, ve výsledné matici C je například prvek c_11 roven výsledku a_11*b_11 + a_12*b_21 + ... + a_1n*b_n1. Platí tedy, že prvek c_ij je výsledkem skalárního součinu i-tého řádku matice A a j-tého sloupce matice B.

Doplníme zbytek řádku a stejně spočítáme zbytek hodnot v dalším řádku:

Násobení matic je asociativní, ale není komutativní. Neplatí tedy, že A × B = B × A. Pokud matici A k-krát vynásobíme sama sebou, získáme matici A^k.

Násobení matic by v kódu mohlo vypadat následovně:

public static Matrix operator *(Matrix A, Matrix B)
        {
            if (A.columns != B.rows)
                throw new InvalidOperationException("Matrices cannot be multiplied");

            Queue<double> results = new Queue<double>();
            for (int i = 0; i < A.rows; i++)
                for (int j = 0; j < B.columns; j++)
                {
                    double value = 0; ;
                    for (int k = 0; k < A.columns; k++)
                        value += A.data[i, k] * B.data[k, j];

                    results.Enqueue(value);
                }

            return new Matrix(A.rows, B.columns, results);
        }

Transpozice matice

Tato unární operace spočívá v prohození řádků a sloupců matice. Vezmeme-li matici A typu m × n a transponujeme ji na matici, platí, že a_ij = b_ji. Jednodušeji řečeno, řádky původní matice přepíšeme jako sloupce do výsledné matice. Ta se nazývá transponovaná a má rozměry n × m:

Transpozice matice by vypadalo v C# takto:

public Matrix Transpose()
        {
            Queue<double> results = new Queue<double>();
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < columns; j++)
                    results.Enqueue(data[j, i]);

            return new Matrix(columns, rows, results);
        }

V další lekci, Gaussova eliminace a Gauss-Jordanova eliminace, se podíváme již na lehce pokročilejší pojmy jako Gaussovou a Gauss-Jordanovou eliminaci.