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