	\myAddDate{06}{03}{09}
	
	Обозначим через \(x_{n+1}^{(i)}\) \(i\)-ую координату вектора \(x_{n+1}\). Тогда:
	\[x_{n+1}^{(i)}=c_1\lambda_1^{n+1}e_1^{(i)} + c_2\lambda_2^{n+1}e_2^{(i)} + \dots + c_m \lambda_m^{n+1} e_m^{(i)}\]
	\[x_n^{(i)}=c_1 \lambda_{1}^n e_1^{(i)} + c_2\lambda_2^n e_2^{(i)} + \dots + c_m\lambda_m^n e_m^{(i)}\]
	Поделим 	\(x_{n+1}^{(i)}\) на \(x_{n}^{(i)}\):
	\[\frac{x_{n+1}^{(i)}}{x_{n}^{(i)}}=\frac{c_m\lambda_m^{n+1}e_m^{(i)}\left(1 +  \frac{c_{m-1}}{c_m}\frac{e_{m-1}^{(i)}}{e_m^{(i)}}\left(\frac{\lambda_{m-1}}{\lambda_m}\right)^{n+1} + \dots + \frac{c_1}{c_m}\frac{e_1^{(i)}}{e_m^{(i)}}\left(\frac{\lambda_1}{\lambda_m}\right)^{n+1}\right)}   {c_m\lambda_m^n e_m^{(i)}\left(1 +  \frac{c_{m-1}}{c_m}\frac{e_{m-1}^{(i)}}{e_m^{(i)}}\left(\frac{\lambda_{m-1}}{\lambda_m}\right)^n + \dots + \frac{c_1}{c_m}\frac{e_1^{(i)}}{e_m^{(i)}}\left(\frac{\lambda_1}{\lambda_m}\right)^n\right)} =\]
\[= \lambda_m + O\left(\left(\frac{\lambda_{m-1}}{\lambda_{m}}\right)^n\right) = \lambda_m^{(n)}\]
	Таким образом, \(\lambda_m^{(n)} - \lambda_m = O\left(\left(\frac{\lambda_{m-1}}{\lambda_{m}}\right)^n\right)\), то есть мы решили задачу нахождения максимального по модулю собственного значения.
	Сформулируем соответсвующее утверждение:
\begin{myUnnumberedStatement}
	Пусть выполнены следующие предположения:
\begin{enumerate}
	\item (A) Матрица A имеет базис из собственных векторов \(\left\{e_i \right\}_{i=1}^{i=m}\)
	\item (B) \(|\frac{\lambda_{m-1}}{\lambda_m}| < 1\)
	\item (С) \(x_0 = c_1e_1 + c_2e_2 + \dots + c_me_m\), где \(c_m \neq 0\)
\end{enumerate}
Тогда \(x_n \rightarrow e_m\) (по направлению) при \(n \rightarrow \infty \), где \(e_m\) - собственный вектор, отвечающий наибольшему по модулю собственному значению \(\lambda_m\), а \(\lambda_m^{(n)} = \frac{x_{n+1}^{(i)}}{x_{n}^{(i)}} = \lambda_m + O\left(\left(\frac{\lambda_{m-1}}{\lambda_{m}}\right)^n\right)\).
\end{myUnnumberedStatement}

\begin{myUnnumberedNote}
Условия (A) и (B) несколько ограничивают класс задач, к которым
применим этот метод, хотя он все равно остается достаточно широким.
\end{myUnnumberedNote}

\begin{myUnnumberedNote}
	Найти \(\lambda_m^{(n)}\) можно также по формуле: 
\[\lambda_m^{(n)} = \frac{\left(x_{n+1}, x_n\right)}{\left(x_n, x_n\right)} = \frac{\left(Ax_n, x_n\right)}{\left(x_n, x_n\right)}\].
\end{myUnnumberedNote}

Рассмотрим два случая:

	1. Пусть \(A = A^*\). Тогда \(\exists \left\{e_i \right\}_{i=1}^{i=m}\) - ортонормированный базис из собственных векторов матрицы A:
\[Ae_k = \lambda_k e_k, \quad k = 1, \dots, m,\quad e_k \neq 0\] 
\[\left(e_i, e_j\right) = \delta_{ij}\] 
	\[x_{n+1}=c_1\lambda_1^{n+1}e_1 + c_2\lambda_2^{n+1}e_2 + \dots + c_m \lambda_m^{n+1} e_m\]
	\[x_n=c_1 \lambda_{1}^n e_1 + c_2\lambda_2^n e_2 + \dots + c_m\lambda_m^n e_m\]
Найдем \(\lambda_m^{(n)}\):
\[\lambda_m^{(n)} = \frac{\left(x_{n+1}, x_n\right)}{\left(x_n, x_n\right)} = \frac{c_1^2\lambda_1^{2n+1} + c_2^2\lambda_2^{2n+1} + \dots + c_m^2\lambda_m^{2n+1}}{c_1^2\lambda_1^{2n} + c_2^2\lambda_2^{2n} + \dots + c_m^2\lambda_m^{2n}} =\] 
\[= \frac{c_m^2\lambda_m^{2n+1}\left(1 + \left(\frac{c_{m-1}}{c_m}\right)^2\left(\frac{\lambda_{m-1}}{\lambda_m}\right)^{2n+1} + \dots + \left(\frac{c_1}{c_m}\right)^2\left(\frac{\lambda_1}{\lambda_m}\right)^{2n+1}\right)}   {c_m^2\lambda_m^{2n}\left(1 + \left(\frac{c_{m-1}}{c_m}\right)^2\left(\frac{\lambda_{m-1}}{\lambda_m}\right)^{2n} + \dots + \left(\frac{c_1}{c_m}\right)^2\left(\frac{\lambda_1}{\lambda_m}\right)^{2n}\right)} = \]
\[= \lambda_m + O\left(\left(\frac{\lambda_{m-1}}{\lambda_{m}}\right)^{2n}\right)\]
Таким образом, при \(A = A^*\) получили более быструю сходимость.

	2. Пусть \(\exists \left\{e_i \right\}_{i=1}^{i=m}\) - базис из собственных векторов (ортонормированность не предполагается). Тогда:
\[\lambda_m^{(n)} = \frac{\left(x_{n+1}, x_n\right)}{\left(x_n, x_n\right)} = \frac{\sum \limits_{i,j = 1}^{m}c_i c_j \lambda_i^{n+1}\lambda_j^n\left(e_i, e_j\right)}{\sum \limits_{i,j = 1}^{m}c_i c_j \lambda_i^n\lambda_j^n\left(e_i, e_j\right)} = \]
\[= \frac{c_m^2\lambda_m^{2n+1}\left(e_m, e_m\right)\left(1 +  \frac{c_{m-1}}{c_m}\frac{\left(e_m, e_{m-1}\right)}{\left(e_m, e_m\right)}\left(\frac{\lambda_{m-1}}{\lambda_m}\right)^n + \dots + \left(\frac{c_1}{c_m}\right)^2\frac{\left(e_1, e_1\right)}{\left(e_m, e_m\right)}\left(\frac{\lambda_1}{\lambda_m}\right)^{2n+1}\right)}   {c_m^2\lambda_m^{2n}\left(e_m, e_m\right)\left(1 +  \frac{c_{m-1}}{c_m}\frac{\left(e_m, e_{m-1}\right)}{\left(e_m, e_m\right)}\left(\frac{\lambda_{m-1}}{\lambda_m}\right)^n + \dots + \left(\frac{c_1}{c_m}\right)^2\frac{\left(e_1, e_1\right)}{\left(e_m, e_m\right)}\left(\frac{\lambda_1}{\lambda_m}\right)^{2n}\right)} = \]
\[= \lambda_m + O\left(\left(\frac{\lambda_{m-1}}{\lambda_{m}}\right)^n\right)\]
\[\lambda_m^{(n)} - \lambda_m = O\left(\left(\frac{\lambda_{m-1}}{\lambda_{m}}\right)^n\right)\]
\subsection{Метод обратных итераций}
	Пусть матрица \(A\) (m x m) такова, что \(\exists A^{-1}\). Рассмотрим итерационный степенной метод решения частичной проблемы собственных значений:
\[Ax_{n+1} = x_n, \quad n = 0, 1, \dots, \quad x_0 \text{ --- задан.}\]
	Домножим обе части слева на \(A^{-1}\):
\[x_{n+1} = A^{-1}x_n, \quad n = 0, 1, \dots, \quad x_0 \text{ --- задан.}\]
	Получили степенной метод для обратной матрицы. Пусть верны следующие предположения:
\begin{enumerate}
	\item (A) Матрица A имеет базис из собственных векторов \(\left\{e_i \right\}_{i=1}^{i=m}\)
	\item (B) \(|\frac{\lambda_1}{\lambda_2}| < 1\)
	\item (С) \(x_0 = c_1e_1 + c_2e_2 + \dots + c_me_m\), где \(c_1 \neq 0\)
\end{enumerate}
	Тогда:
\[x_n=c_1 \lambda_{1}^{-n} e_1 + c_2\lambda_2^{-n} e_2 + \dots + c_m\lambda_m^{-n} e_m\]
\[\lambda_1^n x_n=c_1 e_1 + c_2 \left(\frac{\lambda_1}{\lambda_2}\right)^n e_2 + \dots + c_m \left(\frac{\lambda_1}{\lambda_m}\right)^n e_m\]
	Таким образом, \(x_n \rightarrow e_1 \) (по направлению) при \(n \rightarrow \infty\).
\begin{myUnnumberedTask}
Пусть выполнены условия (A), (B) и (C). Тогда метод обратных итераций позволяет найти собственное значение \(\lambda_1^{(n)} = \lambda_1 + O\left(\left(\frac{\lambda_1}{\lambda_2}\right)^n\right)\), где \(\lambda_1^{(n)} = \frac{x_n^{(i)}}{x_{n+1}^{(i)}}\).
\end{myUnnumberedTask}
\begin{proof}
	Выпишем выражения для \(x_{n}^{(i)}\) и \(x_{n+1}^{(i)}\):
	\[x_n^{(i)}=c_1 \lambda_{1}^{-n} e_1^{(i)} + c_2\lambda_2^{-n} e_2^{(i)} + \dots + c_m\lambda_m^{-n} e_m^{(i)}\]
	\[x_{n+1}^{(i)}=c_1 \lambda_{1}^{-n-1} e_1^{(i)} + c_2\lambda_2^{-n-1} e_2^{(i)} + \dots + c_m\lambda_m^{-n-1} e_m^{(i)}\]
	Теперь поделим  \(x_{n}^{(i)}\) на \(x_{n+1}^{(i)}\):
	\[\frac{x_{n}^{(i)}}{x_{n+1}^{(i)}}=\frac{c_1\lambda_1^{-n}e_1^{(i)}\left(1 + \frac{c_2}{c_1}\frac{e_2^{(i)}}{e_1^{(i)}}\left(\frac{\lambda_2}{\lambda_1}\right)^{-n} + \dots + \frac{c_m}{c_1}\frac{e_m^{(i)}}{e_1^{(i)}}\left(\frac{\lambda_m}{\lambda_1}\right)^{-n}\right)}   {c_1\lambda_1^{-n-1} e_1^{(i)}\left(1 + \frac{c_2}{c_1}\frac{e_2^{(i)}}{e_1^{(i)}}\left(\frac{\lambda_2}{\lambda_1}\right)^{-n-1} + \dots + \frac{c_m}{c_1}\frac{e_m^{(i)}}{e_1^{(i)}}\left(\frac{\lambda_m}{\lambda_1}\right)^{-n-1}\right)} =\]
\[= \lambda_1 + O\left(\left(\frac{\lambda_1}{\lambda_2}\right)^n\right) = \lambda_1^{(n)}\]
\end{proof}
	Пусть теперь \(A = A^*\). Тогда \(\exists \left\{e_i \right\}_{i=1}^{i=m}\) - ортонормированный базис из собственных векторов матрицы A. Найдем \(\lambda_1^{(n)}\):
\[\lambda_m^{(n)} = \frac{\left(x_n, x_n\right)}{\left(x_{n+1}, x_n\right)} = \frac{c_1^2\lambda_1^{-2n} + c_2^2\lambda_2^{-2n} + \dots + c_m^2\lambda_m^{-2n}}{c_1^2\lambda_1^{-2n+1} + c_2^2\lambda_2^{-2n-1} + \dots + c_m^2\lambda_m^{-2n-1}} =\] 
\[= \frac{c_1^2\lambda_1^{-2n}\left(1 + \left(\frac{c_2}{c_1}\right)^2\left(\frac{\lambda_2}{\lambda_1}\right)^{-2n} + \dots + \left(\frac{c_m}{c_1}\right)^2\left(\frac{\lambda_m}{\lambda_1}\right)^{-2n}\right)}   {c_1^2\lambda_1^{-2n-1}\left(1 + \left(\frac{c_2}{c_1}\right)^2\left(\frac{\lambda_2}{\lambda_1}\right)^{-2n-1} + \dots + \left(\frac{c_m}{c_1}\right)^2\left(\frac{\lambda_m}{\lambda_1}\right)^{-2n-1}\right)} = \]
\[= \lambda_1 + O\left(\left(\frac{\lambda_{1}}{\lambda_{2}}\right)^{2n}\right)\]
Таким образом, при \(A = A^*\) снова имеем более быструю сходимость.
\begin{myUnnumberedTask}
Пусть \(\exists \left\{e_i \right\}_{i=1}^{i=m}\) - базис из собственных векторов матрицы A. Тогда \(\lambda_1^{(n)} = \lambda_1 + O\left(\left(\frac{\lambda_1}{\lambda_2}\right)^n\right)\).
\end{myUnnumberedTask}
\begin{proof}
\[\lambda_1^{(n)} = \frac{\left(x_n, x_n\right)}{\left(x_{n+1}, x_n\right)} = \frac{\sum \limits_{i,j = 1}^{m}c_i c_j \lambda_i^{-n}\lambda_j^{-n}\left(e_i, e_j\right)}{\sum \limits_{i,j = 1}^{m}c_i c_j \lambda_i^{-n-1}\lambda_j^{-n}\left(e_i, e_j\right)} = \]
\[= \frac{c_1^2\lambda_1^{-2n}\left(e_1, e_1\right)\left(1 +  \frac{c_2}{c_1}\frac{\left(e_1, e_2\right)}{\left(e_1, e_1\right)}\left(\frac{\lambda_2}{\lambda_1}\right)^{-n} + \dots + \left(\frac{c_m}{c_1}\right)^2\frac{\left(e_m, e_m\right)}{\left(e_1, e_1\right)}\left(\frac{\lambda_m}{\lambda_1}\right)^{-2n}\right)}   {c_1^2\lambda_1^{-2n-1}\left(e_1, e_1\right)\left(1 +  \frac{c_2}{c_1}\frac{\left(e_1, e_2\right)}{\left(e_1, e_1\right)}\left(\frac{\lambda_2}{\lambda_1}\right)^{-n} + \dots + \left(\frac{c_m}{c_1}\right)^2\frac{\left(e_m, e_m\right)}{\left(e_1, e_1\right)}\left(\frac{\lambda_m}{\lambda_1}\right)^{-2n-1}\right)} = \]
\[= \lambda_1 + O\left(\left(\frac{\lambda_1}{\lambda_2}\right)^n\right)\]
\[\lambda_1^{(n)} - \lambda_1 = O\left(\left(\frac{\lambda_1}{\lambda_2}\right)^n\right)\]
\end{proof}
Сформулируем еще одно утверждение:
\begin{myUnnumberedStatement}
Если есть хотя бы одно комплексное собственное значение \(\lambda_k = \lambda_0 + i\lambda_1\), \(\lambda_1 \neq 0\), то и отвечающий ему собственный вектор должен быть комплексным, и начальное приближение для него должно быть комплексным.
\end{myUnnumberedStatement}
\begin{proof}
	Пусть \(x_k = \mu_0 + i\mu_1\) - собственный вектор матрицы A, отвечающий собственному значению \(\lambda_k = \lambda_0 + i\lambda_1\). Тогда:
\[Ax_k = A(\mu_0 + i\mu_1) = (\lambda_0 + i\lambda_1)(\mu_0 + i\mu_1) = \lambda_0\mu_0 - \lambda_1\mu_1 + i(\lambda_0\mu_1 + \lambda_1\mu_0)\]
В силу линейности:
\[A\mu_0 = \lambda_0\mu_0 - \lambda_1\mu_1\]
\[A\mu_1 = \lambda_0\mu_1 + \lambda_1\mu_0\]
Предположим, что \(\mu_1 = 0\). Тогда \(\lambda_1\mu_0 = 0\), \(\mu_0 = 0\), откуда следует, что \(x_k = 0\), а это противоречит тому, что x - ненулевой вектор. 
\end{proof}
\subsection{Метод обратных итераций со сдвигом}
	Иногда бывает нужно найти собственное значение из внутренней части спектра. Рассмотрим метод обратных итераций со сдвигом:
\[(A - \alpha E)x_{n+1} = x_n, \alpha \in \mathbb{R}, n \in \mathbb{N}\]
\[n = 0, 1, \dots, \quad x_0 \text{ --- задан.}\]
Пусть существует \((A - \alpha E)^{-1} = B\), тогда получим степенной метод для матрицы B:
\[x_{n+1} = Bx_n, \quad n = 0, 1, \dots, \quad x_0 \text{ --- задан.}\]
Собственные значения матрицы B:
\[\lambda_k^B = \frac{1}{\lambda_k^{A} - \alpha}\]
Тогда \(x_n \rightarrow e_l\) (по направлению), где l таково, что:
\[\lambda_l^B = \max_{k = 1, \dots, m} \frac{1}{\lambda_k^A - \alpha} = \frac{1}{\lambda_l^{A} - \alpha}\]
\begin{myUnnumberedNote}
Если известно приближенное значение какого-то собственного значения, а мы хотим его уточнить, то можно использовать этот метод. Найти весь спектр этим методом практически невозможно.
\end{myUnnumberedNote}
\section{Приведение матрицы к верхней почти треугольной форме (ВПТФ)}
	Легче всего найти собственные значения у диагональной или треугольной
матрицы. Наша задача - привести матрицу A (m x m) к треугольной. Однако, приведение матрицы A к треугольной форме методом Гаусса
не сохраняет спектр матрицы. Спектр матрицы сохраняется при преобразовании подобия:
\[C = Q^{-1}AQ\]
Если матрица Q - ортогональна (унитарна), то сохраняется симметрия.
\begin{myUnnumberedDefinition}
	Матрица находится в верхней почти треугольной форме (ВПТФ), если она имеет вид (ненулевые элементы обозначены через x):
\[ A =
 		\begin{pmatrix}
			x & x & x & \cdots & x & x & x \\
			x & x & x & \cdots & x & x & x \\
			0 & x & x & \cdots & x & x & x \\
			\vdots & \vdots & \vdots  & \ddots & \vdots & \vdots & \vdots  \\
			0 & 0 & 0 & \cdots & x & x & x \\
			0 & 0 & 0 & \cdots & 0 & x & x
		\end{pmatrix} \]
\end{myUnnumberedDefinition}
	Рассмотрим вектор-столбец \(\nu\):
\[\nu = (\nu_1, \nu_2, \dots, \nu_m)^T\]
\[\nu^T = (\nu_1, \nu_2, \dots, \nu_m)\]
\begin{myUnnumberedDefinition}
Элементарным отражением, соответствующим вектору \(\nu\), называется преобразование, задаваемое матрицей:
\[H = E - 2\frac{\nu \nu^T}{||\nu||^2}\]
\end{myUnnumberedDefinition}
\begin{myUnnumberedNote}
\[\nu^T \nu = \nu_1^2 + \nu_2^2 + \dots + \nu_m^2 = ||\nu||^2\]
\[\nu \nu^T =
 		\begin{pmatrix}
			\nu_1^2 & \nu_1 \nu_2 & \cdots & \nu_1 \nu_m \\
			\nu_2 \nu_1 & \nu_2^2 & \cdots & \nu_2 \nu_m \\
			\vdots & \vdots  & \ddots & \vdots \\
			\nu_m \nu_1 & \nu_m \nu_2 & \cdots & \nu_m^2
		\end{pmatrix} \]
Матрица \(\nu \nu^T\) - симметричная.
\end{myUnnumberedNote}
