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:

  1. \(x+y=y+x\),
  2. \(x+(y+z)=(x+y)+z\),
  3. istnieje element zerowy \(\theta\in X\) taki, że dla dowolnego \(x\in X\), \(x+\theta=x\),
  4. dla każdego \(x\in X\) istnieje element przeciwny \(-x\in X\), tzn taki, że \(-x+x=\theta\),
  5. \(a(x+y)=ax+ay\),
  6. \((a+b)x=ax+bx\),
  7. \(a(bx)=(ab)x\),
  8. \(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\)

  1.  \(\mathbf{for} \ k=1,2,\ldots \ \mathbf{do}\)
  2.  \(\qquad\) Oblicz \(w_k=Xw_{k-1}\)
  3.  \(\qquad\) Znormalizuj \(w_k=w_k\backslash\|w_k\|\)
  4.  \(\qquad\) Testuj zbieżność na \(w_k\)
  5.  \(\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:

  1. \(d(x,y)=0\) wtedy i tylko wtedy, gdy \(x=y\),
  2. \(d(x,y)=d(y,x)\),
  3. \(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:

  1. \(\|x\|=0\Rightarrow x=0\),
  2. \(\|x+y\|\leq\|x\|+\|y\|\) (warunek trójkąta),
  3. \(\|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:

  1. \((x+y|z)=(x|y)+(y|z)\)
  2. \((ax|y)=a(x|y)\)
  3. \((y|x)=\overline{(x|y)}\)
  4. \((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