\documentclass[10pt,a4paper,polish]{article}

%% Polonizacja
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage{polski}
\usepackage{indentfirst}

%% Wzorki matematyczne
\usepackage{amsmath,amsfonts}
\usepackage{latexsym}

%% Inne
%\usepackage{varioref}

%% Twierdzenia
\newtheorem{thm}{Twierdzenie}[section]
\newtheorem{df}{Definicja}[section]

\DeclareMathOperator{\sign}{sign}

\numberwithin{equation}{subsection}

\newcommand*{\n}[1][n]{$#1$\nobreakdash-\hspace{0pt}}
\newcommand*{\abs}[1]{\ensuremath{\lvert #1 \rvert}}
\newcommand*{\norm}[1]{\ensuremath{\lVert #1 \rVert}}
\newcommand*{\ABS}[1]{\ensuremath{\left\lvert #1 \right\rvert}}
\newcommand*{\NORM}[1]{\ensuremath{\left\lVert #1 \right\rVert}}
\newcommand*{\vect}[1]{\ensuremath{\mathbf{#1}}}
\newcommand*{\matr}[1]{\ensuremath{\mathbf{#1}}}
\newcommand*{\dfequ}[1][df]{\stackrel{\text{#1}}{=}}
\newcommand*{\bra}[1]{\ensuremath{\langle #1 \rvert}}
\newcommand*{\ket}[1]{\ensuremath{\lvert #1 \rangle}}
\newcommand*{\braket}[2]{\ensuremath{\langle #1 | #2 \rangle}}



\begin{document}

\newcounter{seria}
\setcounter{seria}{5}
% 1 - sortowanie
% 2 - układy równań
% 3 - układy równań: iteracyjnie
% 4 - wartości własne metodą potęgową
% 5 - wartości własne przez diagonalizację
\newcommand*{\preparedby}{Paweł Jankowski, Jakub Narębski}
\input{naglowek2.tex}




\section{Znajdowanie wartości własnych macierzy metodami opartymi na podobieństwie}
\label{sec:podobienstwo}

Jak łatwo udowodnić macierz $\matr{A}$ i~macierz do niej
\emph{podobna} ($\matr{U}^{\dag} \matr{A} \matr{U}$, gdzie $\matr{U}$
unitarna tzn. $\matr{U}^{\dag} \matr{U} = 1$ dla macierzy zespolonych;
$\matr{Q}^{T} \matr{A} \matr{Q}$, gdzie $\matr{Q}$ ortogonalna tzn.
$\matr{Q}^{T} \matr{Q} = 1$ dla macierzy rzeczywistych) mają te same
wartości własne.  Aby zatem znaleźć wszystkie wartości własne macierzy
należy sprowadzić ją za pomocą transformacji podobieństwa do macierzy
diagonalnej (jeśli się da) lub do macierzy szczególnej postaci, której
wartości własne łatwo znajdować (np. postaci Hessenberga dla
$\matr{A}$ dowolnej, co dla macierzy symetrycznej $\matr{A} =
\matr{A}^T$ sprowadza się do postaci trójdiagonalnej symetrycznej).

Załóżmy, że macierz $\matr{A}$ jest symetryczna, rzeczywista.
Będziemy szukali takiej transformacji ortogonalnej $\matr{Q}$, żeby
\begin{equation}
  \label{eq:podob-do-diag}
  \matr{Q}^T \matr{A} \matr{Q} = \matr{D},
\end{equation}
gdzie macierz $\matr{D}$ jest diagonalna (i~ma na diagonali wartości
własne macierzy $\matr{A}$).  Kolumnami $\matr{Q}$ będą wektory własne
(unormowane).  Opłaca się to dokonywać w~dwu krokach: zredukować
macierz najpierw do macierzy trójdiagonalnej, symetrycznej i~ją
następnie zdiagonalizować.


\subsection{Przekształcenie Householdera}
\label{sec:Householder}

\emph{Przekształceniem Householdera} nazywamy przekształcenie
(macierz) postaci
\begin{equation}
  \label{eq:Householder}
  \matr{H} 
  = \matr{1} - 2\, \vect{u} \vect{u}^T 
  = \matr{1} - 2\, \ket{\vect{u}}\bra{\vect{u}}, 
\end{equation}
gdzie $\vect{u}$ jest wektorem (kolumnowym) unormowanym
($\norm{\vect{u}}_2 = 1$), zaś $\vect{u}^T$ oznacza jego transpozycję;
$\vect{u} \vect{u}^T$ to macierz będąca \emph{iloczynem zewnętrznym}
o~elementach $[\vect{u} \vect{u}^T]_{ij} = u_i u_j$.  Jak łatwo
sprawdzić, przekształcenie to jest hermitowskie $\matr{H} =
\matr{H}^{\dag}$ i~unitarne $\matr{H}^{\dag} = \matr{H}^{-1}$
(w~przypadku rzeczywistym symetryczne $\matr{H} = \matr{H}^T$
i~ortogonalne $\matr{H}^T = \matr{H}^{-1}$) oraz jest idempotentne
$\matr{H}^2 = \matr{H}$. Odwzorowanie $\matr{H}$ jest zatem rzutem
ortogonalnym.  

\emph{Uwaga:} Dalej będziemy rozpatrywać tylko macierze rzeczywiste.

Podstawowym zastosowaniem przekształcenia Householdera jest
konstrukcja transformacji unitarnej przeprowadzającej dany wektor
$\vect{z} \neq 0$ na kierunek zadanego wektora $\vect{e} \neq 0$
(np. wektora jednostkowego $\vect{e}_1 = [1,0,0,\dots,0]^T$).
Wprowadzając oznaczenia
\begin{equation}
  \label{eq:Householder:zast:u}
  \vect{u} \dfequ \vect{z} - \alpha\,\vect{e},\quad
  \tau \dfequ \frac{\norm{\vect{u}}^2_2}{2},
\end{equation}
możemy przekształcenie Householdera zapisać wzorem
\begin{equation}
  \label{eq:Householder:zast:ogolne}
  \matr{H} 
  = \matr{1} - \frac{1}{\tau} \vect{u} \vect{u}^T
  = \matr{1} = \frac{1}{\tau} \ket{\vect{u}}\bra{\vect{u}}, 
\end{equation}
gdzie liczba $\alpha$ zadana jest wzorem
\begin{equation}
  \label{eq:Householder:zast:alpha}
  \alpha = 
  \begin{cases}
    - \frac{\vect{e}^{T}\vect{z}}{\abs{\vect{e}^{T}\vect{z}}}
    \frac{\norm{\vect{z}}_2}{\norm{\vect{e}}_2}
    = - \frac{\braket{\vect{e}}{\vect{z}}}{\abs{\braket{\vect{e}}{\vect{z}}}}
    \frac{\norm{\vect{z}}_2}{\norm{\vect{e}}_2},
    & \text{gdy\ } \vect{e}^{T}\vect{z} = \braket{\vect{e}}{\vect{z}} \neq 0\\[0.7 ex]
    - \frac{\norm{\vect{z}}_2}{\norm{\vect{e}}_2},
    & \text{gdy\ } \vect{e}^{T}\vect{z} = \braket{\vect{e}}{\vect{z}} = 0
  \end{cases}
\end{equation}

W~najczęściej spotykanym przypadku przekształcenie Householdera będzie
dobierane w~ten sposób, aby pierwszych $k-1$ współrzędnych wektora
$\vect{z}$ nie ulegało zmianie pod wpływem transformacji a~pozostałe
$n-k+1$ współrzędnych $\vect{z}^{(k)} = [z_k, z_{k+1}, \dots, z_n]^T$
przechodziło na kierunek wersora $\vect{e}^{(k)}_1 = [1,0\dots,0]^T$.
W~takim przypadku macierz przekształcenia Householdera można zapisać
w~postaci blokowej
\begin{equation}
  \label{eq:Householder:blokowa}
  \matr{H}^{(k)} =
  \left[
    \begin{array}{c|c} 
      \matr{1}  & 0 \\
      \hline
      0         &\tilde{\matr{H}}^{(k)} \vphantom{\bigg|}
    \end{array}
  \right]
  \!\!
  \begin{array}{l} 
    \}      \: k-1 \\
    \bigg\} \, n-k+1
  \end{array}
\end{equation}
gdzie $\tilde{\matr{H}}^{(k)}$ jest macierzą Householdera dla
$\vect{z}^{(k)}$ i~$\vect{e}^{(k)}_1$.  Dla takiego wyboru wektorów
$\vect{z}$ i~$\vect{e}$ możemy dla zagadnienia rzeczywistego uprościć
wzór~\eqref{eq:Householder:zast:u}:
\begin{equation}
  \label{eq:Householder:uproszcz:rzeczyw}
  \begin{aligned}
    u_k &= 
    \begin{cases}
      z_k + \norm{\vect{z}^{(k)}}_2, & \text{gdy\ } z_k \geq 0 \\
      z_k - \norm{\vect{z}^{(k)}}_2, & \text{gdy\ } z_k < 0 
    \end{cases}\\
    u_i &= a_i \qquad \text{dla\ } i = k+1, k+2, \dots, n\\
    \tau &= \norm{\vect{z}^{(k)}}^2_2 + \abs{z_k} \norm{\vect{z}^{(k)}}_2
  \end{aligned}
\end{equation}

Należy zwrócić uwagę, że aby uzyskać wynik mnożenia dowolnego wektora
$\vect{y}$ przez macierz transformacji Householdera $\matr{H}$
wystarczy skorzystać z~równości
\begin{equation}
  \label{eq:Householder:mnozenie}
  \matr{H}\,\vect{y} 
  = \vect{y} - \left(\frac{1}{\tau} \vect{u}^{T} \vect{y}\right) \vect{u} 
  = \vect{y} - \frac{\langle \vect{u} | \vect{y} \rangle}{\tau} \vect{u} 
\end{equation}



\subsection{Redukcja macierzy symetrycznej do postaci trójdiagonalnej}
\label{sec:symetr-do-tridiag}

Do sprowadzenia macierzy symetrycznej do postaci trójdiagonalnej
możemy zastosować transformację Householdera.  W~\n[k]tym kroku
eliminujemy z~\n[k]tej kolumny elementy pod drugą diagonalą $k+1, k+2,
\dots, n$.

Aby zredukować symetryczną macierz $A$ do postaci trójdiagonalnej wybieramy
jako wektor $\vect{z}$ dla pierwszej macierzy Householdera wektor zbudowany z $n-1$
dolnych elementów pierwszej kolumny $\matr{A}$: $\vect{z}^{(1)} =
[a_{21}, a_{31}, \dots, a_{n1}]^T$.  Wtedy jej dolne $n-2$ elementów zostanie wyzerowanych

\newcommand*{\HH}[1]{\tilde{\matr{H}}^{(#1)}}
\newcommand*{\sth}{\text{coś}}
\begin{equation*}
  \begin{split}
    \matr{A}^{(1)} 
    &= \matr{H}^{(1)}\matr{A}\bigl(\matr{H}^{(1)}\bigr)^{-1} 
    = \matr{H}^{(1)}\matr{A}\matr{H}^{(1)}
    = \\
    &=
    \left[
      \begin{array}{c|ccc} 
        1       & 0 & \cdots & 0 \\
        \hline
        0       &   &        &   \\
        0       &   & \HH{1} &   \\
        \vdots  &   &        &   \\
        0       &   &        &   \\
      \end{array}
    \right] 
    \left[
      \begin{array}{c|ccc} 
        a_{11}  & a_{12} & \cdots & a_{1n} \\
        \hline
        a_{21}  &        &        &        \\
        a_{31}  &        &  \sth  &        \\
        \vdots  &        &        &        \\
        a_{n1}  &        &        &        \\
      \end{array}
    \right] 
    \left[
      \begin{array}{c|ccc} 
        1       & 0 & \cdots & 0 \\
        \hline
        0       &   &        &   \\
        0       &   & \HH{1} &   \\
        \vdots  &   &        &   \\
        0       &   &        &   \\
      \end{array}
    \right] = \\
    &=
    \left[
      \begin{array}{c|ccc} 
        a_{11}  & a_{12} & \cdots & a_{1n} \\
        \hline
        k       &        &        &        \\
        0       &        & \sth   &        \\
        \vdots  &        &        &        \\
        0       &        &        &        \\
      \end{array}
    \right] 
    \left[
      \begin{array}{c|ccc} 
        1       & 0 & \cdots & 0 \\
        \hline
        0       &   &        &   \\
        0       &   & \HH{1} &   \\
        \vdots  &   &        &   \\
        0       &   &        &   \\
      \end{array}
    \right] = \\
    &=
    \left[
      \begin{array}{c|ccc} 
        a_{11}  & k      & \cdots & 0      \\
        \hline
        k       &        &        &        \\
        0       &        & \sth   &        \\
        \vdots  &        &        &        \\
        0       &        &        &        \\
      \end{array}
    \right] 
  \end{split}
\end{equation*}
gdzie $\HH{1}$ to macierz Householdera o rozmiarze $(n-1)\times
(n-1)$, zaś $k$ jest równe $\HH{1} \vect{z}^{(1)} = \pm
\norm{\vect{z}^{(1)}}$. 
  
Widać, że $\HH{1} \matr{A} \HH{1}$ zaczyna być trójdiagonalne.
Wykonując w~analogiczny sposób dalsze kroki iteracji po $n-2$ krokach
dostaniemy macierz trójdiagonalną z~macierzą podobieństwa $\matr{Q} =
\HH{1} \dots \HH{n-2}$. Jeżeli znajdziemy wektory własne macierzy
$\matr{A}' = \matr{Q}^T \matr{A} \matr{Q}$ przemnożenie ich przez
$\matr{Q}$ da nam wektory własne $\matr{A}$.


Zamiast mnożenia $\matr{H} \matr{A}\matr{H}$ wygodniej wpierw
obliczyć wektory pomocnicze
\begin{subequations}
\label{eq:Householder-symetr:HAH:wekt}
\begin{align}
  \label{eq:Householder-symetr:HAH:wekt:w}
  \vect{w} &= \frac{\matr{A} \vect{u}}{\tau}, \\
  \label{eq:Householder-symetr:HAH:wekt:v}
  \vect{v} &= \vect{w} - \frac{\vect{u}^T \vect{w}}{2 \tau} \vect{u}
            = \vect{w} - \frac{\braket{\vect{u}}{\vect{w}}}{2 \tau} \vect{u},
\end{align}
\end{subequations}
a~następnie skorzystać ze wzoru
\begin{equation}
  \label{eq:Householder-symetr:HAH}
   \matr{H}\matr{A}\matr{H} 
   = \matr{A} - \vect{u}\vect{v}^T - \vect{v}\vect{u}^T
   = \matr{A} - \ket{\vect{u}}\bra{\vect{v}} - \ket{\vect{v}}\bra{\vect{u}}
\end{equation}


\subsection{Wektory i~wartości własne macierzy trójdiagonalnej}


Macierz trójdiagonalną symetryczną $\matr{T}$ 
\begin{equation*}
  \matr{T} =
  \begin{bmatrix}
    a & b & \dots \\
    b & c & \dots \\
    \vdots &  &       
  \end{bmatrix}
\end{equation*}
możemy sprowadzić do postaci diagonalnej mnożąc ją przez macierze obrotu
\begin{multline}
  \left[
    \begin{array}{cr} 
      \cos \phi & -\sin \phi \\
      \sin \phi & \cos \phi  \\
    \end{array}
  \right]
  \left[
    \begin{array}{cc} 
      a & b \\
      b & c \\
    \end{array}
  \right] 
  \left[
    \begin{array}{rc} 
      \cos \phi  & \sin \phi  \\
      -\sin \phi & \cos \phi \\
    \end{array}
  \right] 
  = \\
  =
  \left[
    \begin{array}{cc} 
      \text{jakaś wartość} & b( \cos^2 \phi - \sin^2 \phi) + (a-c)\sin \phi \cos \phi \\
      b( \cos^2 \phi - \sin^2 \phi) + (a-c)\sin \phi \cos \phi & \text{jakaś wartość} \\
    \end{array}
  \right] 
\end{multline}
i~dobierając kąt $\phi$ tak, aby elementy niediagonalne wyniku
znikały, czyli by
\begin{equation}
  \frac{\cos^2\phi - \sin^2\phi}{\sin \phi \cos \phi} = \frac{c-a}{b}
\end{equation}
Ale
\begin{equation}
  \frac{\cos^2\phi - \sin^2\phi}{\sin \phi \cos \phi} = 
  \frac{1-\tan^2 \phi}{2\tan \phi} = \Theta,
\end{equation}
gdzie oznaczyliśmy $\Theta=\dfrac{c-a}{b}$.  Wprowadzając zmienną $\tan
\phi = t$ możemy zapisać równanie na nią
\begin{equation}
  t^2+2\,\Theta\, t-1 = 0
\end{equation}

Z wzorów Viete'a widać, że $t_1 t_2 = -1$, a zatem jeden z pierwiastków spełnia
$|t_i| < 1$.  Ze względów numerycznych wybieramy właśnie ten pierwiastek.  
\begin{equation}
  t = \frac{\text{sgn} (\Theta)}{\abs{\Theta}+\sqrt{1+\Theta^2}} = \tan \phi
\end{equation}
i ostatecznie
\begin{subequations}
\begin{align}
  \cos \phi &= \frac{1}{\sqrt{1+t^2}} \\
  \sin \phi &= t \cdot \cos \phi = \frac{t}{\sqrt{1+t^2}} 
\end{align}  
\end{subequations}

W~kolejnych krokach eliminujemy kolejne elementy pozadiagonalne.
Ostatecznie otrzymamy macierz diagonalną.  Macierze obrotów są
ortogonalne, ich złożenie jest szukana transformacją podobieństwa.

%%
\input{podpis.tex}

\end{document}

