ˇ MA 4 Pˇredmet: Dnešní látka ◮
Lineární (vektorový) prostor
◮
Normovaný lineární prostor
◮
Normy matic a vektoru˚
◮
Symetrické matice, pozitivneˇ definitní matice
◮
ˇ Gaussova eliminaˇcní metoda, podmínenost matic
ˇ Texty o lineární algebˇre (odkazy na webových stránkách Cetba: pˇrednášejícího).
Vektorový (lineární) prostor V : Pro každé u, v ∈ V a každé ˇ prvkem V . Dále α, β ∈ R je lineární kombinace αu + βv opet x +y =y +x
∀x, y ∈ V ,
(1)
x + (y + z) = (x + y) + z ∀x, y, z ∈ V , ˜ = x, ∀x ∈ V , ˜ ∈V x +0 ∃! 0 ˜ ∀x ∈ V ∃! − x ∈ V x + (−x) = 0,
(3)
∀α ∈ R ∀x ∈ V αx ∈ V ,
(5)
1x = x,
(6)
∀α, β ∈ R α(βx) = (αβ)x ,
(7)
α(x + y) = αx + αy ,
(8)
(α + β)x = αx + βx.
(9)
(2) (4)
Vektory (uspoˇrádané n-tice), matice téhož typu, polynomy stupneˇ n, funkce . . . Poznámka: Vektorový prostor nad komplexními cˇ ísly: α, β ∈ C.
Normovaný lineární prostor X Reálný vektorový prostor X se nazývá normovaný lineární prostor, je-li každému x ∈ X pˇriˇrazeno reálné cˇ íslo kxk, které ˇ tyto podmínky: se nazývá norma x, a jsou splneny kxk≥ 0 ∀x ∈ X , kx + yk≤ kxk + kyk
(10) ∀x, y ∈ X ,
(11)
kαxk= |α| kxk
∀x ∈ X , ∀α ∈ R, ˜ kxk= 0 ⇒ x = 0.
(12) (13)
Též platí ku − vk ≤ ku − w k + kw − vk
∀u, v, w ∈ X .
(14)
Nerovnost (11) i (14) se nazývá trojúhelníková nerovnost. Poznámka: Stejná definice normy i pro komplexní vektorový prostor, jen α ∈ C.
Normy vektoru˚ (s reálnými nebo i komplexními složkami) x = (x1 , x2 , . . . , xn ) ∈ Rn , pˇrípadneˇ ∈ Cn
kxk1 =
n X
|xi | (oktaedrická norma),
i=1
kxk2 = kxk∞ =
i=1
!1/2
max
|xi | (max-norma).
n X
|xi |2
i∈{1,2,...,n}
(euklidovská norma),
V dalším se pro jednoduchost omezíme na reálné matice a reálné vektory. (I když uvedená tvrzení platí i pro matice s komplexními prvky.) Norma matice A typu (m, n) generovaná normami vektoru: ˚ kAkYn Xm =
kAxkYm , {x∈Xn : x6=0} kxkXn max
(15)
kde Xn a Ym jsou prostory vektoru˚ s n a m složkami. Jestliže y = Ax, kde x ∈ Xn a y ∈ Ym , pak kykYm ≤ kAkYm Xn kxkXn . Jsou-li v obou prostorech použity normy stejného typu k · kξ , kde ξ odpovídá 1, 2 nebo ∞, pak i normu matice A generovanou normami k · kξ budeme znaˇcit kAkξ . Ve speciálních pˇrípadech se kAkξ nemusí poˇcítat dle (15).
Konkrétneˇ kAk1 =
max
k ∈{1,2,...,n}
m X
i=1 1/2
kAk2 = (̺(AT A))
|aik |,
kAk∞ =
max
i∈{1,2,...,m}
(spektrální norma).
n X
|aik |,
k =1
Pokud A je reálná a symetrická, pak kAk2 =(̺(AT A))1/2 = (̺(A2 ))1/2 = ̺(A).
Frobeniova norma kAkF =
m X n X
i=1 k =1
|aik |2
!1/2
není generovaná.
Platí ̺(A) ≤ kAk pro Frobeniovu i každou generovanou normu. Všechny normy NLP koneˇcné dimenze jsou ekvivalentní, napˇr. ∃c1 , c2 > 0
∀x ∈ Rn
obdobneˇ pro normy matic.
c1 kxk1 ≤ kxk2 ≤ c2 kxk1 ,
ˇ prvku˚ vektorového prostoru V (nad R) Skalární soucin Zobrazení (·, ·) : V × V → R, které dvojicím prvku˚ z V pˇriˇrazuje reálná cˇ ísla, nazveme skalárním souˇcinem na V , pokud pro každé x, y ∈ V a každé α ∈ R platí (y, x) = (x, y),
(16)
(x + z, y) = (x, y) + (z, y), (αx, y) = α(x, y),
(x, αy) = α(x, y),
(17) (18)
(x, x) ≥ 0,
(19)
(x, x) = 0 ⇔ x = 0.
(20)
Navíc pˇredpisem kxk2 =
p
(x, x) je definována norma na V .
Poznámka: Lze definovat skalární souˇcin i pro vektorový prostor nad komplexními cˇ ísly, tj. pak α ∈ C.
ˇ reálných vektoru˚ Skalární soucin Je-li vektorový prostor V tvoˇren uspoˇrádanými n-ticemi reálných cˇ ísel s obvyklým sˇcítáním a násobením reálným cˇ íslem, pak standardneˇ (x, y) =
n X
xk yk ,
(21)
k =1
kde x = (x1 , . . . , xn ) ∈ Rn a y = (y1 , . . . , yn ) ∈ Rn . p Pˇredpisem kxk2 = (x, x) je definována euklidovská norma na Rn . ˇ Poznámka: Definiˇcní požadavky (16)-(20) splnuje i skalární Rb souˇcin funkcí (u, v) = a u(x)v(x) dx, kde u, v ∈ C([a, b]).
Schwarzova (Cauchyova) nerovnost |(x, y)| ≤ kxk2 kyk2
∀x, y ∈ V .
Dukaz: ˚ y = 0 ⇒ tvrzení platí. Jestliže y 6= 0, pak
2
(x, y)
y = 0 ≤ x −
kyk22 2
(x, y) (x, y) y, x − y x− kyk22 kyk22
!
(x, y)2 (x, y)2 (x, y)2 2 kxk − . = kxk22 − 2 + = 2 kyk22 kyk22 kyk22
Poznámka: V dukazu ˚ nebyla použita konkrétní definice skalárního souˇcinu, jen jeho vlastnosti (17)-(18)! Nerovnost tedy platí i pro skalární souˇcin funkcí.
Pozitivneˇ definitní matice Matice A = (aij ) typu (n, n) se nazývá pozitivneˇ definitní, platí-li pro ˇ každý nenulový n-rozmerný reálný vektor x (Ax , x ) > 0, tj.
n X n X
aij xi xj > 0.
i=1 j=1
((Ax , x ) ≥ 0 . . . pozitivneˇ semidefinitní;
> 0, < 0 . . . indefinitní)
Duležité: ˚ Lze ukázat, že symetrická (!) matice A je pozitivneˇ definitní práveˇ tehdy, když všechna vlastní cˇ ísla matice A jsou kladná. Souvislost mezi ˇrešením soustavy rovnic a minimalizací funkce více ˇ promenných; A je symetrická pozitivneˇ definitní matice typu (n, n), b je sloupcový n-složkový vektor: 1 Necht’ g(x ) = (Ax , x ) − (b, x ) a minima funkce g se nabývá v bodeˇ 2 xb, pak platí xb = arg min g(x ) ⇔ grad g(xb ) = 0 ⇔ Axb = b x∈Rn
ˇ metoda Gaussova eliminacní ˇ Rešení soustavy Ax = b pˇrevodem ekvivalentními úpravami na b Zpetný ˇ soustavu s horní trojúhelníkovou maticí U, tj. Ux = b. chod. LU rozklad, tj. LUx = b, kde L je dolní trojúhelníková matice. Pivotace. Je-li matice A pozitivneˇ definitní, jsou prvky na hlavní diagonále nenulové, nebot’ aii = eiT Aei > 0. Navíc A symetrická, pak existuje Choleského rozklad A = LLT , ˇ kde L je dolní trojúhelníková matice (úspora pameti). ˇ Rídká matice: Nejvýše 5% prvku˚ je nenulových. ˇ Zaplnení. Pásovost. Poˇcet operací.
ˇ ˇ Císlo podmínenosti ˇ Necht’ k · k je nejaká generovaná norma a necht’ A je regulární matice. Pak cˇ íslo κ(A) = kAk kA−1 k ˇ se nazývá cˇ íslo podmínenosti matice A vzhledem k normeˇ k · k. Je-li A symetrická a pozitivneˇ definitní a použijeme-li normu k · k2 , je κ(A) = λmax /λmin . Necht’ Ax0 = b0 a Ax1 = b1 , kde b0 6= b1 , pak platí kb1 − b0 k kx1 − x0 k ≤ κ(A) . kx0 k kb0 k
(22)
K A existují b0 6= 0 a b0 6= b1 takové, že v (22) nastane rovnost.
ˇ ˇríkáme, že je O matici, která má velké cˇ íslo podmínenosti, ˇ špatneˇ podmínená. Soustavy lineárních algebraických rovnic se špatneˇ ˇ podmínenou maticí mohou být (a v praxi bývají) numericky ˇ ˇ obtížne rešitelné. Výsledné ˇrešení muže ˚ být znaˇcneˇ nepˇresné, numerická metoda muže ˚ selhat. ˇ ˇ Hrubý odhad cˇ ísla podmínenosti pomocí Geršgorinovy vety, pˇríklady ve sbírce.
Hilbertova matice H(n) 1 , i, j = 1, 2, . . . , n. i +j −1 1 1/2 1/3 Napˇríklad H(3) = 1/2 1/3 1/4 1/3 1/4 1/5 1 ˇ Rešme soustavu H(n)x = ... pro n = 2, 3, . . . , 12. H(n) = (aij ), kde aij =
1
Presne reseni. ||Ax−b||∞ = 0.00E+00 6 4 2 0 −2 1
2 ||presne − numer. res.||
∞
C. podm. = 1.9E+01
||Ax−b|| = 2.22E−16 ∞
−15.1
10
−15.3
10
1
2
Presne reseni. ||Ax−b||∞ = 0.00E+00 40 20 0 −20 −40 1
2 ||presne − numer. res.||
−13
∞
C. podm. = 5.2E+02
3 ||Ax−b|| = 8.88E−16 ∞
10
−14
10
−15
10
1
2
3
Presne reseni. ||Ax−b||∞ = 0.00E+00 200 100 0 −100 −200 1
2 ||presne − numer. res.||
−10
∞
3 C. podm. = 1.6E+04
4 ||Ax−b|| = 3.55E−15 ∞
10
−12
10
−14
10
1
2
3
4
Presne reseni. ||Ax−b||∞ = 0.00E+00 1000 0 −1000 −2000 1
2
3
||presne − numer. res.||
∞
−8
C. podm. = 4.8E+05
4
5
||Ax−b|| = 2.84E−14 ∞
10
−10
10
−12
10
1
2
3
4
5
Presne reseni. ||Ax−b||∞ = 0.00E+00
4
1
x 10
0.5 0 −0.5 −1 1
2
3
||presne − numer. res.||
∞
−6
4
C. podm. = 1.5E+07
5
6
||Ax−b|| = 8.53E−14 ∞
10
−8
10
−10
10
1
2
3
4
5
6
Presne reseni. ||Ax−b||∞ = 0.00E+00
4
4
x 10
2 0 −2 −4 1
2
3
||presne − numer. res.||
∞
0
4
5
C. podm. = 4.8E+08
6
7
||Ax−b|| = 1.25E−12 ∞
10
−5
10
−10
10
1
2
3
4
5
6
7
Presne reseni. ||Ax−b||∞ = 0.00E+00
5
4
x 10
2 0 −2 1
2
3
4
||presne − numer. res.||
∞
0
5
C. podm. = 1.5E+10
6
7
8
||Ax−b|| = 3.64E−12 ∞
10
−5
10
−10
10
1
2
3
4
5
6
7
8
Presne reseni. ||Ax−b||∞ = 0.00E+00
6
2
x 10
1 0 −1 −2 1
2
3
4
||presne − numer. res.||
6
C. podm. = 4.9E+11
∞
5
5
7
8
9
||Ax−b|| = 1.82E−11 ∞
10
0
10
−5
10
1
2
3
4
5
6
7
8
9
Presne reseni. ||Ax−b||∞ = 0.00E+00
7
1
x 10
0.5 0 −0.5 −1 1
2
3
4
||presne − numer. res.||
∞
5
5
6
7
C. podm. = 1.6E+13
8
9
10
||Ax−b|| = 1.02E−10 ∞
10
0
10
−5
10
1
2
3
4
5
6
7
8
9
10
Presne reseni. ||Ax−b||∞ = 0.00E+00
7
5
x 10
0
−5 1
2
3
4
5
||presne − numer. res.||
∞
5
6
7
8
9
10
C. podm. = 5.2E+14
||Ax−b|| = 9.31E−10
5
8
11
∞
10
0
10
−5
10
1
2
3
4
6
7
9
10
11
Presne reseni. ||Ax−b||∞ = 0.00E+00
8
2
x 10
0 −2 −4
1
2
3
4
||presne − numer. res.||
∞
10
5
6
7
8
C. podm. = 1.7E+16
9
10
11
12
||Ax−b|| = 2.79E−09 ∞
10
5
10
0
10
1
2
3
4
5
6
7
8
9
10
11
12
Presne reseni. ||Ax−b||∞ = 0.00E+00
9
2
x 10
1 0 −1 −2
1
2
3
4
5
||presne − numer. res.||
7
8
9
C. podm. = 1.8E+18
∞
10
6
10
11
12
13
||Ax−b|| = 2.51E−08 ∞
10
5
10
0
10
1
2
3
4
5
6
7
8
9
10
11
12
13
Presne reseni. ||Ax−b||∞ = 0.00E+00
10
1
x 10
0.5 0 −0.5 −1
1
2
3
4
5
||presne − numer. res.||
7
8
9
C. podm. = 3.1E+17
∞
10
6
10
11
12
13
14
||Ax−b|| = 1.34E−07 ∞
10
5
10
0
10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
