Pokročilé numerické metody I
Různá témata
Jiří Zelinka
Podzim 2023
12. přednáška
Jiří Zelinka Různá témata 1 / 18
Funkce matice
Odmocnina z matice
Pro pozitivně semidefinitní reálnou matici A hledáme matici B:
B · B = A.
Pak B se nazývá odmocnina z matice A.
Matici A lze diagonalizovat:
A = V · D · V T
pro D = diag(λ1, . . . , λn), λi ≥ 0.
Položíme
√
D = diag(
√
λ1, . . . ,
√
λn). Pak
B = V ·
√
D · V T
Matice B je taky pozitivně semidefinitní a je jediná pozitivně
semidefinitní odmocnina.
Existují odmocniny z jiných matic?
Dají se vypočítat hodnoty jiných funkcí pro matice?
Jiří Zelinka Různá témata 2 / 18
Funkce matice jako řada
P – polynom, P(A) známe (A0
= I).
Funkce jako nekonečná řada (Taylorova):
f (x) =
∞
k=0
akxk
⇒ f (A) =
∞
k=0
akAk
Konverguje řada matic?
1. A je diagonální:
A = diag(λ1, . . . , λn), pak
Ak
= diag(λk
1, . . . , λk
n), odtud
f (A) = diag(
∞
k=0
akλk
1, . . . ,
∞
k=0
akλk
n) =
= diag(f (λ1), . . . , f (λn)).
Jiří Zelinka Různá témata 3 / 18
2. A lze diagonalizovat:
A = V · D · V −1
⇒ Ak
= V · Dk
· V −1
pak
f (A) =
∞
k=0
akAk
= V (
∞
k=0
akDk
)V −1
= V · f (D) · V −1
3. Jordanův kanonický tvar:
A = V · J · V −1
, J = diag(J1, . . . , Jr ). Pak
f (A) = V · f (J) · V −1
, f (J) = diag(f (J1), . . . , f (Jr ))
Jiří Zelinka Různá témata 4 / 18
Funkce Jordanova bloku (řádu n + 1)
Hodnota f (A) je definována, pokud pro vlastní čísla λ matice
A jsou definovány hodnoty f (λ), případně f (i)
(λ) pro derivace
do stupně podle řádu Jordanových bloků.
Jiří Zelinka Různá témata 5 / 18
Definice 1
Spektrem matice A nazýváme množinu uspořádaných dvojic
{[λi , ki ]} pro všechna vlastní čísla λi matice A a ki jejich
násobnost jakožto kořene minimálního polynomu.
Definice 2
Hodnoty funkce f na spektru matice A jsou dány hodnotami
f (j)
(λi ), pro j = 0, . . . , ki − 1 pro všechna vlastní čísla λi
matice A.
Věta 1
Pro libovolné funkce f a g platí f (A) = g(A), pokud f a g
mají stejné hodnoty na spektru matice A.
Důsledek
Pro Hermitův interpolační polynom P funkce f na spektru
matice A platí f (A) = P(A).
Jiří Zelinka Různá témata 6 / 18
Odmocnina z matice – příklad
A =


3 4 0
−1 −1 0
2 4 1

, určete matici B, že B2
= A.
Aplikace
Řešení soustavy obyčejných lineárních diferenciálních rovnic:



y′
1(t)
...
y′
n(t)


 = Y ′
(t) = A · Y (t), Y (t0) = Y0
Řešení: Y (t) = etA
Y0
Jiří Zelinka Různá témata 7 / 18
Řídké matice
Za řídké matice považujeme zpravidla matice, které mají
maximálně 5% nenulových prvků.
Uložení řídkých vektorů
Ukládáme pouze nenulové prvky a jejich indexy.
Př: vektor v = (2, −2, 0, −3, 0, 0, 4, 3, 0, −1) uložíme jako
dvojice hodnot a indexů:
pořadí 1 2 3 4 5 6
val(v) 2 -2 -3 4 3 -1
ind(v) 1 2 4 7 8 10
Při tomto způsobu uložení vektoru nezáleží na pořadí, takže
stejný vektor může reprezentovat také jako:
pořadí 1 2 3 4 5 6
val(v) 3 2 -3 4 -1 -2
ind(v) 8 1 4 7 10 2
Jiří Zelinka Různá témata 8 / 18
Často se používá jako další položka odkaz (link), který
usnadňuje manipulaci s vektorem, například přidat položku na
určité místo bez přesunů v paměti. Je potřeba mít odkaz na
první nenulový prvek (header), 0 značí poslední nenulový prvek.
Předchozí vektor s odkazy na následující nenulovou složku:
pořadí 1 2 3 4 5 6
val(v) 3 2 -3 4 -1 -2
ind(v) 8 1 4 7 10 2
link(v) 5 6 4 1 0 3
header 2
Jiří Zelinka Různá témata 9 / 18
Přidáme hodnotu 5 na pozici 6:
pořadí 1 2 3 4 5 6 7
val(v) 3 2 -3 4 -1 -2 5
ind(v) 8 1 4 7 10 2 6
link(v) 5 6 7 1 0 3 4
header 2
Je možné použít více odkazů pro různé účely (řazení podle
velikosti apod.)
Jiří Zelinka Různá témata 10 / 18
Uložení řídkých matic
Předpokládejme, že matice A je řádu n a má m nenulových
prvků. Pro každý prvek potřebujeme uložit jeho řádkový a
sloupcový index, celkem tedy 3m hodnot.
Ukládaná pole: VA – nenulové hodnoty matice A
CI, RI – sloupcové a řádkové indexy
Příklad
A =






0 0 3 0 0
2 0 0 2 0
0 0 1 0 0
5 0 0 0 2
0 4 0 0 1






VA= {3, 2, 2, 1, 5, 2, 4, 1}
CI= {3, 1, 4, 3, 1, 5, 2, 5}
RI= {1, 2, 2, 3, 4, 4, 5, 5}
Existují úspornější schemata
Jiří Zelinka Různá témata 11 / 18
Schema 1
Matici ukládáme po sloupcích, místo CI ukládáme pole CIP,
které pro každý sloupec udává, kolikátý nenulový prvek ze
všech je jako první v daném sloupci. Schema bývá označováno
CSC (Compressed Sparse Column format). Vyžaduje uložit
2m + n hodnot.
Příklad
A =






0 0 3 0 0
2 0 0 2 0
0 0 1 0 0
5 0 0 0 2
0 4 0 0 1






VA= {2, 5, 4, 3, 1, 2, 2, 1}
RI= {2, 4, 5, 3, 1, 2, 4, 5}
CIP= {1, 3, 4, 6, 7}
Analogicky se definuje CSR uložení.
Jiří Zelinka Různá témata 12 / 18
Schema 2
Matici ukládáme po sloupcích, každý sloupec začíná nulou a
číslem sloupce, pak následuje vždy číslo řádku a příslušný prvek
matice. Data jsou ukončena dvěma nulami. Celkem je potřeba
2m + 2n + 2 = 2(m + n + 1) hodnot. Existuje řádková varianta.
Příklad
A =






0 0 3 0 0
2 0 0 2 0
0 0 1 0 0
5 0 0 0 2
0 4 0 0 1






pA=
{0, 1, 2, 2, 4, 5, 0, 2, 5, 4, 0, 3, 1, 3, 3, 1, 0, 4, 2, 2, 0, 5, 4, 2, 5, 1, 0, 0}
Jiří Zelinka Různá témata 13 / 18
Schema 3
Matici ukládáme po sloupcích, pro každý prvek ai,j uložíme do
pole LD celkové pořadí λ(i, j) v matici A (po sloupcích), tedy
λ(i, j) = i + n(j − 1). Celkem je potřeba 2m hodnot. Opět
existuje řádková varianta.
Příklad
A =






0 0 3 0 0
2 0 0 2 0
0 0 1 0 0
5 0 0 0 2
0 4 0 0 1






VA= {2, 5, 4, 3, 1, 2, 2, 1}
LD= {2, 4, 10, 11, 13, 17, 24, 25}
Jiří Zelinka Různá témata 14 / 18
Schema 4
Používá se pro symetrické pásové matice. Předpokládejme, že
pro každý řádkový index i existuje pi , pi ≪ n, že Ai,j = 0 pro
i.j > pi . Prvky ukládáme po řádcích vždy od prvního
nenulového až po diagonální, můžeme tedy uložit i nějaké nuly.
Do pomocného pole PD ukládáme pozice diagonálních prvnků
ve VA. Celkem potřebujeme pi + n hodnot.
Příklad
A =






2 4 3 0 0
4 1 0 0 0
3 0 1 2 0
0 0 2 3 5
0 0 0 5 1






VA= {2, 4, 1, 3, 0, 1, 2, 3, 5, 1}
PD= {1, 3, 6, 8, 10}
Jiří Zelinka Různá témata 15 / 18
Schema 5
Využívá se pro matice s diagonální strukturou, hlavní diagonále
přidělíme číslo 0, nad ní očíslujeme diagonály kladnými čísly,
pod ní zápornými. Ukládáme jen ty diagonály, kde jsou
nenulové prvky, podle indexu je možné odvodit délku diagonály.
Jiří Zelinka Různá témata 16 / 18
Kombinovaná schemata
Pro některé operaci s maticemi (například násobení) je možné
kombinovat řádkové a sloupcové uložení s využitím odkazů
(linků) nebo pomocných indexů.
Příklad: modifikace schematu 3
Použijeme pomocný index RO, který udává pořadí prvků z VA
bráno po řádcích, a pole LD ve sloupcové i řádkové variantě.
A =






0 0 3 0 0
2 0 0 2 0
0 0 1 0 0
5 0 0 0 2
0 4 0 0 1






VA= {2, 5, 4, 3, 1, 2, 2, 1}
RO= {4, 1, 6, 5, 2, 7, 3, 8}
LDC= {2, 4, 10, 11, 13, 17, 24, 25}
LDR= {3, 6, 9, 12, 16, 20, 22, 25}
Jiří Zelinka Různá témata 17 / 18
Operace s maticemi zachovávající řídkost
Gaussova eliminace pro pásové matice
Gaussova eliminace při vhodné strategii minimalizující
výplň
QR rozklad pro izolované nenulové prvky mimo hlavní
diagonálu
řešení systémů lineárních rovnic: iterační metody
Jiří Zelinka Různá témata 18 / 18