Definicje i twierdzenia z zakresu algebry liniowej¶

Podane poniżej definicje zostały zaczerpnięte z [Mostowski1965], [Kostrykin1984], [Gelfand1977].

Definicja 32

Niech $K\in\{\mathbb{R}, \mathbb{C}\}$ będzie zbiorem liczb rzeczywistych lub zespolonych i niech $X$ będzie dowolnym zbiorem niepustym. Niech będą określone dwa działania: dodawanie $+\colon X\times X\to X$ i mnożenie przez liczbę $\cdot\colon K\times X\to X$ , spełniające dla dowolnych $x,y,z\in X$ oraz $a,b\in K$ następujące warunki:

$x+y=y+x$ ,
$x+(y+z)=(x+y)+z$ ,
istnieje element zerowy $\theta\in X$ taki, że dla dowolnego $x\in X$ , $x+\theta=x$ ,
dla każdego $x\in X$ istnieje element przeciwny $-x\in X$ , tzn taki, że $-x+x=\theta$ ,
$a(x+y)=ax+ay$ ,
$(a+b)x=ax+bx$ ,
$a(bx)=(ab)x$ ,
$1\cdot x=x$ .

Zbiór $X$ z działaniami $+$ i $\cdot$ nazywamy przestrzenią wektorową.

Definicja 33

Deltą Kroneckera nazywamy funkcję postaci

$\begin{split}\delta_{ij}=\left\{\begin{array}{ll} 1 & \textrm{ jeśli } i=j\\ 0 & \textrm{ w przeciwnym przypadku} \end{array}\right.\end{split}$

Definicja 34

Iloczynem skalarnym wektorów $x$ oraz $y$ rozmiaru $d\times 1$ nazywamy liczbę

$\left\langle x\cdot y\right\rangle = x^Ty=\sum_{i=1}^dx_iy_i=y^Tx$

Definicja 35

Mówimy, że wektory $x$ oraz $y$ są ortogonalne jeśli $\left\langle x\cdot y\right\rangle =x^T\cdot y=0$ . Mówimy, że zbiór $S=\{x_1,x_2,\ldots,x_n\}$ wektorów z $X$ jest ortonormalny jeśli

$\left\langle x_i\cdot y_j\right\rangle =\delta_{ij} \textrm{ dla dowolnych } i,j\leq n.$

Definicja 36

Normą Euklidesową wektora $x$ nazywamy liczbę

$\|x\|=\sqrt{x^Tx}.$

Definicja 37

Mówimy, że wektor $x$ jest znormalizowany jeśli $\|x\|=1$ .

Definicja 38

Kombinacją liniową wektorów $x_1,\ldots,x_n$ nazywamy wektor x postaci

$x=\alpha_1x_1+\ldots+\alpha_nx_n$

Definicja 39

Mówimy, że zbiór wektorów $\{x_1,x_2,\ldots,x_n\}$ jest liniowo niezależny jeśli żaden wektor ze zbioru nie może być zapisany jako kombinacja liniowa pozostałych wektorów.

Definicja 40

Wyznacznikiem macierzy kwadratowej $A$ stopnia $n$ zawierającej elementy postaci $a_{ij}$ nazywamy liczbę postaci

$\det(A)=\sum_{i=1}^n(-1)^{i+n}a_{in}\det(A_{i,n}),$

gdzie $A_{i,j}$ oznacza macierz stopnia $n-1$ , powstałą z macierzy $A$ poprzez skreślenie $i$ -tego wiersza i $j$ -tej kolumny.

Definicja 41

Śladem macierzy kwadratowej $A$ stopnia $n$ nazywamy wielkość

$\mathop{\rm tr}(A)=\sum_{i=1}^na_{ii}.$

Definicja 42

Wartością własną $\lambda$ macierzy $X\in\mathbb{C}^{n\times n}$ nazywamy każdy z $n$ pierwiastków wielomianu

$p(z)=\det{(zI-X)}.$

nazywanego wielomianem charakterystycznym macierzy $X$ . Zbiór wszystkich wartości własnych oznaczamy poprzez $\lambda(X)=\{\lambda_1,\cdots,\lambda_n\}$ .

Ze wzorów Viette’a wynika następujące twierdzenie:

Twierdzenie 8

Niech $\lambda(X)=\{\lambda_1,\cdots,\lambda_n\}$ będzie zbiorem wartości własnych macierzy $X\in\mathbb{C}^{n\times n}$ . Wówczas

$\det(X)=\lambda_1\lambda_2\cdots\lambda_n$

oraz

$\mathop{\rm tr}(X)=\lambda_1+\cdots+\lambda_n.$

Definicja 43

Macierz $B=[b_{ij}]$ nazywamy macierzą transponowaną macierzy $A=[a_{ij}]$ jeśli

$b_{ij}=a_{ji}$

Definicja 44

Macierz $X$ nazywamy macierzą symetryczną jeśli

$X=X^T$

Definicja 45

Niech $X$ będzie macierzą symetryczną. Mówimy, że macierz $X$ jest dodatnio określona, gdy dla dowolnego wektora $x\neq 0$ zachodzi

$\begin{split}x^TAx> 0.\end{split}$

Twierdzenie 9

Macierz dodatnio określona jest zawsze odwracalna i jej odwrotność jest również dodatnio określona.

Twierdzenie 10

Jeśli macierz jest rzeczywistą, dodatnio określoną, symetryczną macierzą rzędu $n$ to posiada ona $n$ wartości własnych. Co więcej, jej wartości własne są rzeczywiste i dodatnie.

Definicja 46

Rozkładem na wartości własne macierzy kwadratowej $X$ nazywamy rozkład postaci

(1)

$X=V\Lambda V^T$

gdzie $\Lambda=\mathop{\rm diag}(\lambda_1,...,\lambda_n)$ jest macierzą diagonalną z wartościami własnymi na przekątnej uporządkowanymi w porządku malejącym, natomiast $V$ jest macierzą odpowiadających im wektorów własnych.

Twierdzenie 11

Dla każdej symetrycznej macierzy dodatnio określonej istnieje przedstawienie w postaci (1).

Definicja 47

Przestrzeń rozpięta na $l\leq n$ wektorach własnych, odpowiadających $l$ największym wartościom własnym nazywana jest przestrzenią własną. Przestrzeń tę oznaczamy poprzez

$\mathop{\rm lin}(v_1,...,v_n)=\mathcal{E}_{X}$

Twierdzenie

Ślad macierzy symetrycznej dodatnio określonej $Q$ jest sumą wszystkich $n$ wartości własnych i jest niezmienny przy każdej transformacji ortonormalnej, czyli

$\mathop{\rm tr}(Q)=\sum_{i=1}^n\lambda_i.$

Dowód

Niech będą dane macierze $A_{n\times m}$ oraz $B_{m\times n}$ . Wówczas mamy

$\mathop{\rm tr}(AB)=\mathop{\rm tr}(BA).$

Istotnie, zachodzi równość

$\sum_{i=1}^n\sum_{j=1}^ma_{ij}b_{ji}=\sum_{j=1}^n\sum_{i=1}^mb_{ji}a_{ij}$

gdzie $a_{ij}, b_{ji}$ są elementami odpowiednio macierzy $A$ oraz $B$ . Wówczas, na mocy (1)

$\sum_{i=1}^{d}\lambda_i=\mathop{\rm tr}(\Lambda)=\mathop{\rm tr}(w^TQw).$

Ponieważ macierz wartości własnych jest niezmiennicza przy każdej liniowej ortonormalnej transformacji a więc każda funkcja wartości własnych także jest niezmiennicza. Zatem $w^Tw$ jest macierzą jednostkową, a więc

$\mathop{\rm tr}\left(Qw^Tw\right)=\mathop{\rm tr}(Q).$

Algorytm 14 Algorytm obliczania dominującej wartości własnej $\lambda$ i wektora własnego $v$

Dane: $X$ rozmiaru $n\times n$ , $z_0$

Wyniki: dominująca wartość własna $\lambda$ i odpowiadający jej wektor własny $v$

$\mathbf{for} \ k=1,2,\ldots \ \mathbf{do}$
$\qquad$ Oblicz $w_k=Xw_{k-1}$
$\qquad$ Znormalizuj $w_k=w_k\backslash\|w_k\|$
$\qquad$ Testuj zbieżność na $w_k$
$\qquad$ Jeśli zbieżne to $\lambda=\|w_k\|$ oraz $v=Aw_k$

Deflacja¶

Po obliczeniu dominującej wartości własnej i odpowiadającemu jej wektora, możemy usunąć je z macierzy kwadratowej $X$ rozmiaru $n\times n$ w celu uzyskania nowych informacji, bez ryzyka obliczani tych samych wielkości. Przykładowo, po obliczeniu dominującej wartości własnej i wektora własnego, możemy usunąć je z macierzy $X=X_{old}$ uzyskując w ten sposób nową macierz $X_{new}$ i dla nowej macierzy obliczyć dominującą wartość i wektor własny. Technika ta nazywa się deflacją. Nową macierz obliczamy wówczas według następującego wzoru

$X_{new}=X_{old}-\lambda_1v_1v_1^T=\sum_{i=2}^n\lambda_iv_iv_i^T$

Definicje i twierdzenia z zakresu analizy funkcjonalnej¶

Podane poniżej definicje zostały zaczerpnięte z [Kolodziej1970], [Musielak1976].

Definicja 48

Niech $X$ będzie dowolnym zbiorem i niech $d$ będzie funkcją określoną na $X\times X$ o wartościach rzeczywistych, spełniającą następujące warunki:

$d(x,y)=0$ wtedy i tylko wtedy, gdy $x=y$ ,
$d(x,y)=d(y,x)$ ,
$d(x,y)\leq d(x,z)+d(z,y)$ .

Wówczas funkcję $d$ nazywamy metryką.

Definicja 49

Niech $X$ będzie dowolnym zbiorem i niech funkcja $d$ określona na $X\times X$ o wartościach nieujemnych będzie metryką. Wówczas parę $(X,d)$ nazywamy przestrzenią metryczną.

Definicja 50

Niech $X$ będzie przestrzenią liniową nad ciałem $K\in\{\mathbb{R}, \mathbb{C}\}$ liczb rzeczywistych lub zespolonych. Funkcję $x\mapsto\|x\|$ odwzorowującą zbiór $X$ w zbiór liczb nieujemnych nazywamy normą gdy dla dowolnych $x,y\in X$ oraz $a\in K$ spełnia ona następujące warunki:

$\|x\|=0\Rightarrow x=0$ ,
$\|x+y\|\leq\|x\|+\|y\|$ (warunek trójkąta),
$\|ax\|=|a|\cdot\|x\|$ (warunek jednorodności).

Definicja 51

Przestrzeń liniową $X$ wraz z określoną w niej normą $\|\cdot \|$ nazywamy przestrzenią unormowaną, a funkcję $x\mapsto\|x\|$ normą.

Uwaga 1

Funkcja $d(x,y)=\|x-y\|$ jest metryką.

Definicja 52

Niech $X$ będzie przestrzenią nad ciałem $K\in\{\mathbb{R}, \mathbb{C}\}$ liczb rzeczywistych lub zespolonych i niech w $X\times X$ będzie określone odwzorowanie $(x,y)\mapsto(x|y)$ o wartościach w ciele $K$ , spełniające następujące warunki:

$(x+y|z)=(x|y)+(y|z)$
$(ax|y)=a(x|y)$
$(y|x)=\overline{(x|y)}$
$(x|x)>0 \textrm{ dla } x\not=0$

gdzie $x,y,z\in X$ , $a\in K$ oraz $\overline{(x|y)}$ oznacza liczbę sprzężoną do ${(x|y)}$ . Wówczas parę $\langle X, (|)\rangle$ nazywamy przestrzenią unitarną, a funkcję $(x,y)\mapsto(x|y)$ nazywamy iloczynem skalarnym.

Uwaga 2

Funkcja $\|x-y\|=(x-y|x-y)$ jest normą.

Definicja 53

Przestrzeń unitarną $X$ ze zdefiniowanym iloczynem skalarnym $(|)$ nazywamy przestrzenią Hilberta jeśli jest zupełna przy metryce

$d(x,y)=\|x-y\|=(x-y|x-y).$

Definicja 54

Niech $X$ i $Y$ będą przestrzeniami unormowanymi, elementami których są funkcje określone na zbiorze $\Omega$ . Ponadto niech $f$ będzie funkcją określoną na produkcie $\Omega\times \Omega$ mającą tę własność, że dla każdej funkcji $u\in X$ całka

$v(x)=\int_{\Omega}f(x,y)u(y)dy \textrm{ dla } x\in\Omega$

jest dobrze określoną funkcją należącą do przestrzeni $Y$ . Wówczas operatorem całkowym $F$ nazywamy operator $Fu=v$ odwzorowujący przestrzeń $X$ w przestrzeń $Y$ . Ponadto funkcję $f(x,y)$ nazywamy jądrem tego operatora.

Następna część - Definicje z zakresu Teorii Optymalizacji

Definicje i twierdzenia z zakresu algebry liniowej¶

Deflacja¶

Definicje i twierdzenia z zakresu analizy funkcjonalnej¶

Napisz program