Aktuálně: Postihly zákazy tvou profesi? Poptávka po ajťácích prudce roste, využij slevové akce 50% výuky zdarma!
Pouze tento týden sleva až 80 % na e-learning týkající se Javy
Discount week - May - 50

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

Čtvercová matice.

Obdélníková 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:

Diagonální matice

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

Horní a dolní trojúhelníková

Řádková matice/vektor

Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

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:

Řádková matice

Sloupcový matice/vektor

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

Sloupcová matice

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í:

Negace

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í a odčítání

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:

Násobení skalárem

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:

Násobení

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í

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 Ak.

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

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.


 

Předchozí článek
Faktoriál
Všechny články v sekci
Matematické algoritmy
Článek pro vás napsala Eresiel
Avatar
Jak se ti líbí článek?
1 hlasů
Aktivity (7)

 

 

Komentáře

Avatar
Lukáš Vejsada:7. dubna 21:45

Ahoj,

využil jste někdo matice v reálném projektu?

Díky

 
Odpovědět
7. dubna 21:45
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
DarkCoder
Člen
Avatar
Odpovídá na Lukáš Vejsada
DarkCoder:7. dubna 23:24

Ano. Jak už je v úvodu článku zmíněno, v počítačové grafice se matice využívají hojně. Budeš-li chtít si například vytvořit nějaký 3D projekt v OpenGL, je použití matic patrné na každém kroku. Při práci s kamerou - nastavení perspektivní nebo ortogonální kamery, při transformování objektů - rotace, posun, zkosení, změna měřítka, při práci s texturami, shadery..

Matice tak mají praktické využití a jejich znalost Ti může v lecčem usnadnit práci.

Odpovědět
7. dubna 23:24
"„Učíš-li se proto, aby sis zapamatoval, zapomeneš. Učíš-li se proto, abys porozuměl, zapamatuješ si."
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 2 zpráv z 2.