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

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

%% Wzorki matematyczne
\usepackage{amsmath,amsfonts}

%% Inne
%\usepackage{varioref}
\usepackage{latexsym}

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

\DeclareMathOperator{\sign}{sign}

\numberwithin{equation}{section}

\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}}}





\begin{document}

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

\section{Zagadnienie własne}
\label{sec:zagadnienie-wlasne}

Wektor $\vect{x} \neq \vec{0}$ nazywamy \textbf{wektorem własnym}
macierzy $\matr{A}$, jeśli istnieje liczba $\lambda$ taka, że
\begin{equation}
  \label{eq:rown-wlasne:1}
  \matr{A}\,\vect{x} = \lambda\,\vect{x}, \quad \vect{x} \neq \vect{0}
\end{equation}
czyli
\begin{equation}
  \label{eq:rown-wlasne:2}
  (\matr{A} - \lambda\,\matr{I})\vect{x} = 0 
  \implies  \det(\matr{A} - \lambda\matr{I}) = 0,
\end{equation}
gdzie $\matr{I}$ oznacza macierz jednostkową.  Wielomian 
\begin{math}
  w_{\matr{A}}(\lambda) = \det(\matr{A} - \lambda\matr{I})  
\end{math}
nazywamy wielomianem charakterystycznym macierzy $\matr{A}$.

Jeśli $\vect{x}$ jest wektorem własnym, to $k\,\vect{x}$ też jest
wektorem własnym z~tą samą wartością własną.



\section{Metoda potęgowa}
\label{sec:metoda-potegowa}

Niech $\matr{A}$ rozmiaru $n \times n$ będzie macierzą
diagonalizowalną.  Istnieje wtedy $n$ liniowo niezależnych wektorow
własnych $\vect{v}_1, \vect{v}_2, \dots, \vect{v}_n$ odpowiadajacych
wartościom własnym $\lambda_1,\lambda_2,\dots, \lambda_n$.  Zakładamy,
że $\lambda_1$ jest wartościa dominującą co do modułu, tzn.
$\abs{\lambda_1} > \abs{\lambda_i}$ dla każdego $i \neq 1$.

\emph{Metoda potegowa} wyznaczająca $\lambda_1$ i~kierunek wektora
$v_1$, polega na konstrukcji ciągu wektorów $\vect{x}^{(k)}$, gdzie
$\vect{x}^{(0)}$ jest danym wektorem poczatkowym, za pomocą wzoru
iteracyjnego
\begin{equation}
  \label{eq:metoda-potegowa:1}
  \vect{x}^{(k+1)} = \matr{A}\,\vect{x}^{(k)}
  = \matr{A}^{k+1} \, \vect{x}^{(0)}, \quad k=0,1,2,\dots
\end{equation}
Elementy $\vect{x}^{(k)}$ zbiegają do wektora odpowiadającego
najwiekszej wartości własnej.  Poniżej podano uzasadnienie tego faktu.


Każdy wektor początkowy $\vect{x}^{(0)}$ można (przy naszych
założeniach) przedstawić jako kombinację liniową wektorów własnych
$\vect{v}_i$ (gdyż tworzą one bazę).  Niech $\vect{x}^{(0)} = c_1
\vect{v}_1 + \dots + c_n \vect{v}_n$.  Dla $k= 1, 2, \dots$
otrzymujemy wtedy zależność
\begin{equation}
  \label{eq:metoda-potegowa:wyjasnienie}
  \begin{split}
    \vect{x}^{(k)} &= \matr{A}^k\,\vect{x}^{(0)} 
    = \sum_{i=1}^n c_i\,\, \matr{A}^k\,\vect{v}_i 
    = \sum_{i=1}^n c_i \lambda_i^k \,\vect{v}_i =\\
    %%
    &= \lambda_1^k 
    \left(
      c_1 \vect{v}_1 + 
      \sum_{i=2}^{n} c_i \left(\frac{\lambda_i}{\lambda_1}\right)^k \vect{v}_i
    \right)
  \end{split}
\end{equation}
Ponieważ dla $i \geq 2$ mamy $\ABS{{\lambda_i}/{\lambda_1}}<1$, to
przy zalożeniu, że $c_1 \neq 0$, ciąg wektorów $\vect{x}^{(k)}$ dąży do
kierunku wektora własnego $\vect{v}_1$.  

Wielkości $\abs{\lambda_1}^k$ dążą do zera, gdy $\abs{\lambda_1} < 1$
lub do nieskończoności, gdy $\abs{\lambda_1}>1$.  Dla uniknięcia
niedomiaru lub nadmiaru w rachunku numerycznym konieczne jest więc
normowanie wektorow $\vect{x}^{(k)}$.  Jeśli robimy to w każdym kroku,
to metoda potęgowa ma postać:
\begin{equation}
  \label{eq:metoda-potegowa:2}
  \begin{aligned}
    \vect{y} &:= \matr{A}\,\vect{x};\\
    \vect{x} &:= \vect{y}/\norm{\vect{y}};
  \end{aligned}
\end{equation}

Przybliżenia dominującej wartości własnej $\lambda_1$ wyznacza sie z tzw.
\emph{ilorazow Rayleigha}
\begin{equation}
  \label{eq:metoda-potegowa:wartosc-wlasna}
  \sigma^{(k)} 
  = 
  \frac{\vect{x}^{(k)T}\,\matr{A}\,\vect{x}^{(k)}}
       {\vect{x}^{(k)T}\,\vect{x}^{(k)}}
  =
  \frac{(\vect{x}^{(k)}|\matr{A}\vect{x}^{(k)})}
       {(\vect{x}^{(k)}|\vect{x}^{(k)})}
  ,\quad k=0,1,\dots
\end{equation}
co wynika z przemnożenia równania \eqref{eq:rown-wlasne:1} z lewej
strony przez $\vect{x}^{(k)T}$.  $\vect{x}^T$ oznacza transpozycję
wektora $\vect{x}$.

\emph{Uwaga:} powinniśmy badać zbieżność ciągu $\vect{x}^{(0)},
\vect{x}^{(2)}, \vect{x}^{(4)},\dots$ ze względu na możliwość $\lambda
< 0$ (wtedy ciąg $\vect{x}^{(i)}$ oscyluje).



\section{Odwrotna metoda potęgowa}
\label{sec:odwr-metoda-poteg}

Stosujac metode potęgowa do macierzy {$\matr{A}^{-1}$} możemy
wyznaczyć najmniejszą co do modułu wartość własna $\matr{A}$ gdyż:
\begin{equation}
  \label{eq:odwr-metoda-poteg:wyjasnienie}
  \matr{A}\vect{x} = \lambda\vect{x} \iff
  \matr{A}^{-1} \matr{A}\vect{x} = \lambda \matr{A}^{-1}\vect{x} \iff 
  \matr{A}^{-1}\vect{x} = \lambda^{-1} \vect{x}
\end{equation}
Ogólniej stosując metodę potęgową do macierzy $(\matr{A} - \lambda^*
\matr{I})^{-1}$, gdzie $\lambda^*$ jest ustaloną liczbą, możemy
znaleźć wartość własną macierzy $\matr{A}$ najbliższą $\lambda^*$.
Metodę tę można wprost zapisać wzorem:
\begin{equation}
  \label{eq:odwr-metoda-poteg}
  \vect{x}^{(k+1)} 
  = (\matr{A} - \lambda^* \matr{I})^{-1}\,\vect{x}^{(k)}
  = (\matr{A} - \lambda^* \matr{I})^{-(k+1)}\,\vect{x}^{(0)}, 
  \quad k=0,1,2,\dots
\end{equation}
ale zamiast obliczać macierz odwrotną lepiej jest rozwiązywać w~każdym
kroku układ równań, co prowadzi do (równoważnego)wzoru
\begin{equation}
  \label{eq:odwr-metoda-poteg}
  (\matr{A} - \lambda^* \matr{I})\, \vect{x}^{(k+1)} 
  = \vect{x}^{(k)},\quad k=0,1,2,\dots
\end{equation}
Ponieważ w~każdym kroku rozwiązujemy układ równań z~tą samą macierzą
a~różnym wektorem prawych stron, warto skorzystać z~rozkładu
$\matr{L}\matr{U}$ macierzy $(\matr{A} - \lambda^* \matr{I})$ do
rozwiązywania wielokrotnie tego układu.

Tak określona metoda nazywana jest \emph{odwrotną metodą potęgową} lub
\emph{metodą Wielandta}.  Ciag ilorazów Rayleigha dąży do wartości
własnej macierzy $(\matr{A} - \lambda^* \matr{I})^{-1}$, czyli
$\dfrac{1}{\lambda-\lambda^*}$.

Analogicznie jak w~metodzie potęgowej w~celu uniknięcia nadmiaru lub
niedomiaru w~obliczeniach numerycznych należy normalizować wektory.



\section{Zadanie domowe}
\label{sec:zad-dom}

Napisać procedurę (funkcję) znajdująca wektor własny odpowiadający
największej co do modułu wartości własnej oraz tę wartość własną.
Jako parametry funkcja powinna przyjmować macierz oraz wektor
początkowy oraz maksymalną liczbę iteracji.

Napisać procedurę (funkcję) znajdującą wartość własną macierzy
$\matr{A}$ najbliższą zadanej wartości $\lambda^*$.  Funkcja może
nadpisywać macierz $\matr{A}$ jej rozkładem $\matr{L}\matr{U}$.
Funkcja powinna reagować na błędy obliczeń (typu wartość $\lambda^*$
równa którejś z~wartości własnych).

Przetestować obie funkcje znajdując wszystkie wartości i~wektory
własne macierzy o~znanych jednokrotnych wartościach własnych.
Przykładem może być macierz:
\begin{equation*}
  \begin{bmatrix}
    2 & 3 & 3 \\
    0 & 5 & 3 \\
    0 & 0 & 8 
  \end{bmatrix}
\end{equation*}
o~wartościach własnych $2, 5, 8$., lub macierz
\begin{equation*}
  \begin{bmatrix}
    11 &  0 &  5 &  0 &  0 \\
     0 &  7 &  0 &  3 &  0 \\
     5 &  0 & 11 &  0 &  0 \\
     0 &  3 &  0 &  7 &  0 \\
     0 &  0 &  0 &  0 &  1
  \end{bmatrix}
\end{equation*}
o~wartościach własnych $1, 2, 3, 5, 8$, czy też macierz
\begin{equation*}
  \begin{bmatrix}
     4 & -1 &  0 &  0 &  0 \\
    -1 &  4 & -1 &  0 &  0 \\
     0 & -1 &  4 & -1 &  0 \\
     0 &  0 & -1 &  4 & -1 \\
     0 &  0 &  0 & -1 &  4 \\
  \end{bmatrix}
\end{equation*}
o~wartościach własnych $3, 4, 5, 4 - \sqrt{3}, 4+ \sqrt{3}$, czy też
macierz
\begin{equation*}
  \begin{bmatrix}
     12 & 1 & 0 & 0 & 0 \\
      1 & 9 & 1 & 0 & 0 \\
      0 & 1 & 6 & 1 & 0 \\
      0 & 0 & 1 & 3 & 1 \\
      0 & 0 & 0 & 1 & 0 \\
  \end{bmatrix}
\end{equation*}
o~wartościach własnych
\begin{math}
  6,
  6 \pm \frac{1}{2}\,\sqrt {98 \pm 2\,\sqrt {949}}
  \simeq
  -1.316875950, 2.983863699, 6, 9.016136308, 12.31687596
\end{math}


%%% 
\input{podpis.tex}

\end{document}

