\myAddDate{13}{03}{09}
    
    Свойства оператора H:
    
    \begin{enumerate}
      \item \( H^T=H \)
      \item \( H^{-1} = H^T \)
    \end{enumerate}
    
    Докажем второе свойство, то есть что \(H\) является ортогональной матрицей.
    \begin{proof}
      \[ 
        H^TH = 
        H^2 = 
        \left( E - 2\frac{VV^T}{||V||^2} \right)\left( E -
        2\frac{VV^T}{||V||^2} \right) =
      \]
      
      \[
        E - 4\frac{VV^T}{||V||^2} + 4\frac{V(V^TV)V^T}{||V||^4}
      \]
      
      Используя свойство \( V^TV = ||V||^2 \), сократим в последнем
      соотношении дроби и получим, что
      \[
        H^TH = E
      \]
      Значит, матрица H является ортогональной.
    \end{proof}
    
   Сформулируем и докажем свойство 3.
  \begin{myUnnumberedTheorem}
    Для любого вектора
      \(x\):
    \[ x =    
        \left(
            \begin{smallmatrix}
                x_1 \\
                x_2 \\
                x_3 \\
                \vdots \\
                x_m
            \end{smallmatrix}            
        \right)
     \]
     можно выбрать такой вектор \( V = (v_1, v_2, \ldots, v_m) \), что        
     
     \[ Hx =        
        \left(
            \begin{smallmatrix}
            -\sigma \\
            0 \\
            0 \\
            \vdots \\
            0
            \end{smallmatrix}
        \right)             
    \]
    
    где \( \sigma = ||x|| \), то есть преобразование H подавляет все координаты
    вектора кроме первой.
  \end{myUnnumberedTheorem}
  \begin{proof}
    Выберем \( V \) в виде:
    \[ V = x + \sigma z, ~ \sigma \in 
\mathbb{R},
	z = (1,0,0, \ldots, 0)^T \]
    
    \[ Hx = x - 2\frac{ (x+\sigma z)(x + \sigma z)^T }{ (x+\sigma z)^T(x+\sigma
    z) }x =
    \]
    
    \[
      x - (x+\sigma z) \frac{ 2(x+\sigma z)^Tx }{ (x+\sigma z)^T(x+\sigma z) }
    \]
    
    Для дальнейшего преобразования воспользуемся свойствами 1 и 2 :

  \[ (x+\sigma z)^Tx = ||x||^2 + \sigma x_1 \]
    
   \[ (x+\sigma z)^T(x+\sigma z) = ||x||^2 + \sigma x_1 + \sigma x_1 +
   {\sigma}^2 =
   \]
   \[ ||x||^2 + 2\sigma x_1 + {\sigma}^2 \]
   
   Положим \( \sigma = ||x|| \). Тогда получим:
   \[ x - (x+\sigma z) \frac{ 2(x+\sigma z)^Tx }{ (x+\sigma z)^T(x+\sigma z) }
   = \]
   
   \[ x - (x+\sigma z)\frac{ \left( ||x||^2 + 2\sigma x_1 + {\sigma}^2 \right) +
   ||x||^2 - {\sigma}^2 }{||x||^2 + 2\sigma x_1 + {\sigma}^2} = 
   x - x - \sigma z =   
      \left(
        \begin{smallmatrix}
            -\sigma \\
            0 \\
            0 \\
            \vdots \\
            0
        \end{smallmatrix}
      \right)      
   \]
  \end{proof}

Полученные 3 свойства мы будем применять при приведении матрицы к верхней почти
треугольной форме.\\

Пусть дана произвольная матрица \(A\) порядка \(m \times m \):

\[ 
A = \begin{pmatrix}
        a_{11} & a_{12} & \ldots & a_{1m} \\
        a_{21} & a_{22} & \ldots & a_{2m} \\
        \hdotsfor{4}\\
        a_{m1} & a_{m2} & \ldots & a_{mm}     
    \end{pmatrix}
\] 

Представим ее в виде блочной матрицы следующего вида:

\[
    A = \begin{pmatrix}
        a_{11} & y_{m-1} \\
        x_{m-1} & A_{m-1} \\     
    \end{pmatrix} 
\]

где \[y_{m-1} = (a_{12}, a_{13}, \ldots, a_{1m})\]
    \[ x_{m-1} = (a_{21}, a_{31}, \ldots, a_{m1})^T \]
    а матрица \(A_{m-1}\)
    получается из матрицы \(A\) удалением первого столбца и первой строки.

Воспользуемся свойством 3:

\[
    H_{m-1}x_{m-1} = \begin{pmatrix}
                        -||x_{m-1}|| \\
                        0 \\
                        \vdots \\
                        0
                     \end{pmatrix}
\]
    
    Рассмотрим матрицу \(U_1\) порядка \(m \times m\) вида:
    \[
        U_1 = \begin{pmatrix}
                 1 & 0_{12} \\
                 0_{21} & H_{m-1}        
              \end{pmatrix}
    \]
    
    Очевидно, \( U_1 = U_1^T \), значит:
    \[
        U_1^2 = \begin{pmatrix}
                    1 & 0_{12} \\
                    0_{21} & H_{m-1}
                \end{pmatrix}
                \begin{pmatrix}
                    1 & 0_{12} \\
                    0_{21} & H_{m-1}
                \end{pmatrix} = 
                \begin{pmatrix}
                    1 & 0_{12} \\
                    0_{21} & H_{m-1}^2
                \end{pmatrix} = E
    \]
    
    Последнее равенство верно в силу того, что \( H^2_{m-1}=E \) 
    Таким образом, мы получили что матрица \(U_1\) - ортогональная.\\
    Обозначим \(C_1 = U_1^{-1} A U_1 \)
    
    \[
        C_1 = \begin{pmatrix}
                 a_{11} & c_{12}^{(1)} & \ldots\\
                 -{\sigma}_1 z_{m-1} & c_{22}^{(2)} & \ldots\\
                 0 & c_{32}^{(1)} &  c_{ij}^{(1)}\\
                 \vdots & \vdots & \ldots\\
                 0 & c_{m2}^{(1)} & \ldots\\
              \end{pmatrix}
    \]
    
    Таким образом, структуру матрицы можно представить так:
    \[        \begin{pmatrix}
                 \times & \times & \ldots & \times \\
                 \times & \times & \ldots & \times \\
                 0      & \times & \ldots & \times \\
                 0      & \times & \ldots & \times \\
                 \vdots & \vdots & \ddots & \vdots \\
                 0      & \times & \ldots & \times 
              \end{pmatrix}              
    \]
    
    Возьмем вектор \( x_{m-2} = \begin{pmatrix}
                                   c_{32}^{(1)} \\
                                   \vdots \\
                                   c_{m2}^{(1)} \\
                                \end{pmatrix}\) \\

    По свойству 3, можно построить такой оператор \( H_{m-2} \), что:
   \[
        H_{m-2}x_{m-2} = \begin{pmatrix}
                            -||x_{m-2}|| \\
                            0 \\
                            0 \\
                            \vdots \\
                            0
                         \end{pmatrix}   
   \]
   
   Рассмотрим матрицу \( U_2 \), построенную аналогично матрице \( U_1 \)
   \[ U_2 = \begin{pmatrix}
                E_2    & 0_{12} \\
                0_{21} & H_{m-2}          
            \end{pmatrix} \]

   где    \( E_2 =    \bigl(\begin{smallmatrix}
1 & 0\\0 & 1
\end{smallmatrix}\bigr) \) \\
   \\
   Свойства матрицы \( U_2 \):
   \begin{enumerate}
     \item \( U_2 = U_2^T \)
     \item \( U_2 = U_2^{-1} \) - ортогональная матрица
   \end{enumerate}
   
   Аналогично, обозначим \( C_2 \):
   
   \[
        C_2 = U_2^{-1}C_1U_2 = U_2^{-1}U_1^{-1}AU_1U_2
   \]
   
   Посмотрим на структуру матрицы \( C_2 \):
   \[
     C_2 = \begin{pmatrix}
              \times & \times & \times & \ldots & \times \\
              \times & \times & \times & \ldots & \times \\
              0 & \times & \times & \ldots & \times \\
              0 & 0 & \times & \ldots & \times \\
              \vdots & \vdots & \vdots & \ddots & \vdots \\
              0 & 0 & \times & \ldots & \times \\
           \end{pmatrix}
   \]
   
   Очевидно, что сделав таким образом m-2 шага, мы придем к верхней почти
   треугольной форме. В итоге мы получим:
   \[ C =  
   U^{-1}_{m-2}
   U^{-1}_{m-3}
   \ldots
   U^{-1}_{2}
   U^{-1}_{1}
   A
   U_{1}
   U_{2}
   \ldots
   U_{m-3}
   U_{m-2} =\]
   
   \[
    = \begin{pmatrix}
        \times & \times & \times & \ldots & \times \\
        \times & \times & \times & \ldots & \times \\
        0      & \times & \times & \ldots & \times \\
        0      &      0 & \times & \ldots & \times \\
        \vdots & \vdots & \vdots & \ddots & \vdots \\
        0      & 0      & 0      & \times & \times \\
      \end{pmatrix}
        \mbox{~-ВПТФ}
   \]
   
   Обозначим \( U = U_1U_2 \ldots U_{m-2} \)
   \[
    U^T = U^T_{m-2}U^T_{m-3} \ldots U^T_{2}U^T_{1} =
    U^{-1}_{m-2}U^{-1}_{m-3}\ldots U^{-1}_{2}U^{-1}_{1} = U^{-1}
   \]
   
   Следовательно, матрица U - ортогональна.\\
   \[ C = U^{-1}AU \Rightarrow C \sim A \]
   Причем подобие выполняется с помощью ортогональной матрицы \(U\)\\
   Элементы матрицы C имеют вид:
   \[ c_{ij} = 0, ~ i \geq j+2, ~ j=1,2,\ldots,m-2 \]
   
   \begin{myUnnumberedNote}
       Собственные значения матрицы A совпадают с собственными значениями
       матрицы C, т.е.:
       \[ \lambda_k^A = \lambda_k^C, ~ k=\overline{1,m} \]
   \end{myUnnumberedNote}
   \begin{proof}
    \[ Ax = \lambda x , x \neq 0 \]
    \[ U^{-1}Ax = \lambda U^{-1}x, \mbox{обозначим} U^{-1}x = y \neq 0 
    \Rightarrow x = Uy\]
    
    \[ U_{-1}AUy = \lambda y, ~ y \neq 0 \]
    \[ Cy = \lambda y \]
   \end{proof}

   \begin{myUnnumberedNote}
     Если \(A=A^T\), то \( C = C^T \)
   \end{myUnnumberedNote}
   \begin{proof}
     \[ C^T = (U^{-1}AU)^T = U^TA^T(U^{-1})^T = U^{-1}AU = C\] 
   \end{proof}

\section{Понятие о QR-алгоритме. Решение полной проблемы собственных значений.}
Изученные в предыдущем параграфе свойства позволят нам представить матрицу
\(A\) в виде:
    \begin{equation}
        \label{eq_1_11_1}
        A = QR
    \end{equation}
    где \( Q^{-1} = Q^T \) - ортогональная матрица, а \( R\) имеет
    верхнетреугольную форму.
    
    Возьмем вектор \( x=(a_{11}, a_{21}, \ldots ,a_{m1} ) \). Для него
    существует такая ортогональная матрица \( H_1 = E - 2\frac{VV^T}{||V||^2}\),
    которая ``подавляет'' все координаты вектора \( x \), кроме первой. \\
    Матрица \( H_1A \) имеет вид: 
     \[ H_1A =
    \begin{pmatrix} \times & \times & \ldots & \times \\
                 0 & \times & \ldots & \times \\
                 0 & \times & \ldots & \times \\
                 \vdots & \vdots & \ddots & \vdots \\
                 0 & \times & \ldots & \times \\          
              \end{pmatrix} 
    \]
    
    Построим матрицу \( H_2 = \bigl(\begin{smallmatrix}
                                1 & 0 \\
                                0 & H
                              \end{smallmatrix} \bigr) \) порядка \( m \times m
                              \),такую, что
                              
    \[
        H_2H_1A = \begin{pmatrix}
                    \times & \times & \times & \ldots & \times \\
                    0      & \times & \times & \ldots & \times \\
                    0      & 0      & \times & \ldots & \times \\
                    \vdots & \vdots & \vdots & \ddots & \times \\
                    0      & 0      & \times & \ldots & \times \\
                  \end{pmatrix}
    \]
    
    Очевидно, что за (m-1) шаг мы обнулим все элементы под главной диагональю:
    \[ H_{m-1}H_{m-2} \ldots H_{2}H_{1}A = R = 
        \left(\begin{smallmatrix}
           \times & \times & \ldots & \times \\
             0    & \times & \ldots & \times \\
           \vdots & \vdots & \ddots & \times \\
             0    & 0      & \ldots & \times
        \end{smallmatrix} \right) - \mbox{~ ВТФ}
    \]
    
    Построим матрицу Q следующим образом:
    \[ Q = H_1H_2 \ldots H_{m-1} \]
    Найдем \( Q^T \):
    \[ Q^T = H^T_{m-1}H^T_{m-2} \ldots H^T_{2}H^T_{1} =
    H^{-1}_{m-1}H^{-1}_{m-2} \ldots H^{-1}_{1} = Q^{-1}\]
    Следовательно, матрица Q ортогональна.\\
    Таким образом, мы получили разложение матрицы A.
   \begin{myUnnumberedNote}
        При факторизации в виде QR:
        \begin{enumerate}
          \item Для произвольной матрицы \(A\) требуется \(O(m^3)\) действий.
          \item Для матрицы \(A\) вида ВПТФ требуется \(O(m^2)\) действий.
          \item Для трехдиагональной матрицы \(A\) требуется \(O(m)\)
          действий.
        \end{enumerate}
   \end{myUnnumberedNote} 

\subsection{QR-алгоритм}
Возьмем матрицу \(A_0\). Представим ее в виде \( A_0 = Q_0R_0\), где \(
Q_0^T=Q_0^{-1}\), R - матрица ВТФ.\\

Положим 
 \begin{equation}
 	\label{eq_1_11_3}
 	A_1 = R_0Q_0	
 \end{equation}

 \[ R_0 = Q_0^{-1}A_0 \]
 \[ A_1 = Q_0^{-1}A_0Q_0 \]
 Таким образом, матрицы \( A_1\) и \( A_0 \) подобны с ортогональной матрицей.\\
 Аналогично, сделаем следующие шаги:
 \[ A_1 = Q_1R_1, ~ Q_1^T = Q_1^{-1}, R_1 - \mbox{ВТФ}  \]
 \[ \ldots \]
 \begin{equation}
 	\label{eq_1_11_4}
 	A_k = Q_kR_k, ~ k=0,1,\ldots
 \end{equation}
 \begin{equation}
 	\label{eq_1_11_5}
 	A_{k+1} = R_kQ_k
 \end{equation}

 Устремим \( k \rightarrow \infty \), тогда:
 \[ 
 	A_k \rightarrow \begin{pmatrix}
                     	\times & \times & \ldots & \times \\
                     	0      & \times & \ldots & \times \\
                     	\vdots & \vdots & \ddots & \times \\
                     	0      & 0      & \ldots & \times
                     \end{pmatrix}
 \]
 Где на главной диагонали будут стоять собственные значения матриц \( A_0, A_1,
 \ldots \) (спектры этих матриц совпадают).\\
 Заметим, что под главной диагональю могут и не получаться нули в математическом смысле. 
 Достаточно, чтобы значения под главной диагональю были
 по модулю меньше некоторого числа (т.н. машинный ноль), определяющего точность
 вычислений.\\
 Если у \( A_k \) комплексные собственные значения, то в матрице на главной
диагонали будут появляться квадраты \( 2 \times 2\),  она будет иметь вид:
 \[
 	A_k \rightarrow \begin{pmatrix}
                     	\times &        &            &             &  X \\
                     	       & \times &            &             &    \\
                     	       &        & \lambda_0  &  \lambda_1  &    \\
                     	       &        & -\lambda_1 &  \lambda_0  &    \\
                     	 0     &        &            &             &  \ddots\\
                     \end{pmatrix}
 \]
    
 Перечислим основные плюсы и минусы QR-алгоритма:\\
 \begin{enumerate}
   \item (+) Для любой матрицы можно найти весь спектр.
   \item (-) Во время вычислений нужно держать всю матрицу в памяти.
   \item (-) Если собственные значения комплексны, то появляются клетки 2го
   порядка, которые при последующих итерациях не будут сходиться к 0.
 \end{enumerate}
