!!§!! Вспомогательная страница к разделу ((:algebra2:charpoly#qr-алгоритм "Характеристический полином, собственные числа, собственные векторы матрицы")).
== QR-алгоритм поиска всех собственных чисел матрицы ==
Этот алгоритм основан на ((:euclid_space#матричный_формализм_алгоритма_грама-шмидтаqr-разложение QR-разложении матрицы)) $ A $.
!!Т!! **Теорема.**// Спектр матрицы// $ A $ //совпадает со спектром матрицы// $ P^{\top} A P $ //при произвольной ортогональной матрице// $ P $.
**Доказательство.**
$$ \det (P^{\top} A P-\lambda E)=\det (P^{\top} A P- \lambda P^{\top} E P)=\det P^{\top} (A -\lambda E ) P =
\det (A -\lambda E ) P P^{\top} = \det (A -\lambda E ) \, .
$$
♦
Пусть QR-разложение матрицы $ A $ имеет вид
$$ A=Q_1R_1 \, , $$
где $ Q_1 $ --- ортогональная, а $ R_1 $ --- верхнетреугольная матрицы. Тогда матрица
$$ A_2=R_1Q_1 $$
имеет тот же спектр, что и матрица $ A $. Действительно, поскольку
$$ A_2=Q_1^{\top} A Q_1 , $$
то сработает предыдущая теорема. Вычислим QR-разложение матрицы $ A_2 $
$$ A_2=Q_2R_2 $$
и переставим местами матрицы этого произведения:
$$ A_3=R_2Q_2 \, . $$
Матрица
$$ A_3= Q_2^{\top} A_2 Q_2=Q_2^{\top} Q_1^{\top} A Q_1 Q_2 $$
продолжает иметь те же собственные числа, что и матрица $ A $. Утверждается, что бесконечная последовательность матриц
$$ \{A_j=R_{j-1}Q_{j-1}\}_{j=1}^{\infty} $$
__как правило__, сходится к матрице $ A_{\infty} $, которая будет верхнетреугольной.
!!Т!! **Теорема ((#источники [1])).** //Если все собственные числа матрицы// $ A $ //различны по модулю, то матрица// $ A_{\infty} $ //является верхнетреугольной и на ее главной диагонали стоят собственные числа матрицы// $ A $.
!!П!! **Пример.** Найти все собственные числа матрицы
$$
A=\left(\begin{array}{rrr}
2 & 3 &-1\\
7 & 3 & 3 \\
-1 & -2 & 4
\end{array}
\right) \, .
$$
**Решение.**
$$
A_1=A\approx
\underbrace{\left(\begin{array}{rrr}
0.272165 & 0.759752 & 0.590511 \\
0.952579 & -0.299517 & -0.053683 \\
-0.136083& -0.577119 & 0.805242
\end{array}
\right)}_{Q_1}
\underbrace{\left(\begin{array}{rrr}
7.348469 & 3.946400 & 2.041241\\
0 & 2.534941 & -3.966781 \\
0 & 0 & 2.469409
\end{array}
\right)}_{R_1}
$$
Теперь переставляем матрицы произведения местами и строим QR-разложение получившейся матрицы:
$$
\quad \Rightarrow \quad A_2 = R_1Q_1\approx
\left(\begin{array}{rrr}
5.481481 & 3.222957 & 5.771191 \\
2.954542 & 1.530046 & -3.3303021 \\
-0.336044 & -1.425143 & 1.988472
\end{array}
\right)\approx
$$
$$
\approx\underbrace{\left(\begin{array}{rrr}
-0.878992 & 0.022595 & 0.476300\\
0.473781 & -0.154267 & -0.867026 \\
0.053886 & -0.987771 & 0.146304
\end{array}
\right)}_{Q_2}
\underbrace{\left(\begin{array}{rrr}
-6.236096& -3.634658 & -3.387848\\
0 & 1.244502 & -1.319999\\
0 & 0 & 5.927198
\end{array}
\right)}_{R_2}
$$
Продолжим процесс:
$$
\quad \Rightarrow \quad A_3 = R_2Q_2\approx
\left(\begin{array}{rrr}
7.020952& 3.766220 & -0.314568\\
-0.660752 & 1.111870 & -1.272137\\
0.319398 & -5.854713 & 0.867177
\end{array}
\right) \approx
$$
$$
\approx
\underbrace{\left(\begin{array}{rrr}
-0.994581 & -0.065879 & 0.080426 \\
0.093601 & -0.230749 & 0.968501 \\
-0.045246 & 0.970780 & 0.235665
\end{array}
\right)}_{Q_3}
\underbrace{\left(\begin{array}{rrr}
-7.059205 & -3.376839 & 0.154554 \\
0 & -6.188319 & 1.156106 \\
0 & 0 & -1.053002
\end{array}
\right)}_{R_3}
$$
Замечаем тенденцию убывания элементов матриц $ \{A_j\} $, стоящих под главной диагональю.
$$
\Rightarrow \dots \Rightarrow A_{10} \approx
\left(\begin{array}{rrr}
\mathbf{6.}_{246022} & 2.758769 & -2.160057\\
-0.0467437 & \mathbf{4.4}_{09292} & -5.341014\\
0.000018 &-0.005924 & \mathbf{-1.6}_{55314}
\end{array}
\right) \approx
$$
$$
\underbrace{\left(\begin{array}{rrr}
-0.999972 & -0.007483 & 0.000007 \\
0.007483 & -0.999971 & 0.001339 \\
-0.000003 & 0.001339 & 0.999999
\end{array}
\right)}_{Q_{10}}
\underbrace{\left(\begin{array}{rrr}
-6.246197 & -2.725694 & 2.120031\\
0 & -4.429817 & 5.354807 \\
0 & 0 & -1.662479
\end{array}
\right)}_{R_{10}} \, .
$$
Матрица $ Q_j $ уже близка к диагональной (с элементами $ \pm 1 $), верхнетреугольность матрицы $ A_j $ также заметна, но точность приближения еще не достаточна.
$$
\Rightarrow \dots \Rightarrow A_{20} \approx
\left(\begin{array}{rrr}
\mathbf{6.17}_{5608} & 2.805821 & -2.020513 \\
-0.001776 & \mathbf{4.48}_{4917} & -5.388407\\
0 & 0 & -\mathbf{1.660525}
\end{array}
\right) \approx
$$
Точность приближения минимильного собственного числа существенно выше точностей приближения остальных чисел.
$$
\Rightarrow \dots \Rightarrow A_{30} \approx
\left(\begin{array}{rrr}
\mathbf{6.172}_{778} & 2.807524 & -2.015076\\
-0.000073 & \mathbf{4.487}_{747} & -5.390442\\
0 & 0 & -\mathbf{1.660525}
\end{array}
\right) \, .
$$
♦
К сожалению условие теоремы достаточно ограничительно: собственные числа вещественной матрицы $ A $ могут оказаться и мнимыми, но тогда они одинаковы по модулю. Посмотрим как это обстоятельство скажется на структуре матрицы $ A_{\infty} $.
!!П!! **Пример.** Вычислить $ A_{\infty} $ для матрицы
$$
A=
\left(\begin{array}{rrrr}
2 & 7 & 18 & 28 \\
1 & 8 & 2 & 8 \\
3 & 1 & 4 & 1 \\
5 & 9 & 26 & 5
\end{array}
\right) \, .
$$
**Решение.** Здесь вычисленная по алгоритму матрица
$$
A_{30} \approx
\left(\begin{array}{rrrr}
\mathbf{25.641949} & 20.992347 & 24.701883 & 6.841640 \\
0 & -10.509149 & 12.631597 & 6.193862 \\
0 & -3.782749 & -2.013392 & -3.393084 \\
0 & 0.000165 & 0.003632 & \mathbf{5.8}_{80591}
\end{array}
\right)
$$
имеет структуру близкую к верхней блочно-треугольной:
$$
\left(\begin{array}{r|rr|r}
{\color{Red}{\star} } & \ast & \ast & \ast \\
\hline
0 & {\color{Red}{\star}} & {\color{Red}{ \star} } & \ast \\
0 & {\color{Red}{\star} } & {\color{Red}{ \star} } & \ast \\
\hline
0 & 0 & 0 & {\color{Red}{ \star} }
\end{array}
\right) \, .
$$
Матрицы порядка $ 1 \times 1 $, появившиеся на диагонали, соответствуют двум вещественным собственным числам матрицы $ A $.
Матрица же второго порядка, стоящая на этой диагонали, имеет своими собственными числами пару комплексно-сопряженных собственных чисел матрицы $ A $. Так, полином
$$
\left|\begin{array}{rr}
-10.509149 -\lambda & 12.631597 \\
-3.782749 & -2.013392 - \lambda
\end{array}
\right| = \lambda^2+12.516007 \lambda+ 69.270982
$$
имеет корнями $ -\mathbf{6.2}_{58004} \pm \mathbf{5.4}_{87109} \mathbf{i} $.
♦
Для симметричных матриц такой ситуации не возникает. Более того, здесь матрица $ A_{\infty} $ будет диагональной, а матрица
$$
\prod_{j=1}^{K} Q_j
$$
при увеличении $ K $ будет состоять из столбцов, сколь угодно близким к собственным векторам
!!§!! Сходимость к пределу у бесконечного произведения не гарантирована.
!!П!! **Пример.** Вычислить $ A_{\infty} $ для матрицы
$$
A=\left(\begin{array}{rrr}
9 & 22 &-6\\
22 & -4 & 1 \\
-6 & 1 & -7
\end{array}
\right) \, .
$$
**Решение.**
$$
A_{30} \approx
\left(\begin{array}{rrr}
\mathbf{25.98}_{2419} & -0.252396 & 0\\
-0.252396 & \mathbf{-21.77}_{8334} & 0\\
0 & 0 & \mathbf{-6.204084}
\end{array}
\right) ; \ \prod_{j=1}^{30} Q_j \approx
\left(\begin{array}{rrr}
-\mathbf{0}._{799024} & -\mathbf{0.59}_{6712} & \mathbf{0.074119}\\
-\mathbf{0.58}_{7209} & \mathbf{0.7}_{47824} & -\mathbf{0.309748} \\
\mathbf{0.12}_{9402} & -\mathbf{0.291}_{021} & -\mathbf{0.947925}
\end{array}
\right) \, .
$$
Точность приближения последнего вектора существенно выше двух первых --- близких по модулю.
$$
\prod_{j=1}^{40} Q_j \approx
\left(\begin{array}{rrr}
-\mathbf{0.80}_{2017} & -\mathbf{0.59}_{2684} & \mathbf{0.074119}\\
-\mathbf{0.583}_{438} & \mathbf{0.750}_{770} & -\mathbf{0.309748} \\
\mathbf{0.12}_{7936} & -\mathbf{0.291}_{668} & -\mathbf{0.947925}
\end{array}
\right) \, .
$$
А вот
$$
\prod_{j=1}^{39} Q_j
$$
будет отличаться от предыдущей матрицы еще и сменой знаков у первых двух столбцов.
♦
При наличии близких по модулю вещественных корней, сходимость к $ A_{\infty} $ становится очень медленной.
!!П!! **Пример.** Для матрицы
$$
A=\left(\begin{array}{rrrr}
4 & -3 & 0 & 0 \\
-3 & 10/3 & -5/3 & 0\\
0 & -5/3 & -33/25 & -68/75\\
0 & 0 & -68/75 & 149/75
\end{array}
\right)
$$
имеем:
$$
A_{20}\approx
\left(\begin{array}{rrrr}
\mathbf{6.844621} & 0 & 0 & 0 \\
0 & 0.159514 & -2.229578 & 0 \\
0 & -2.229578 & -0.088499 & 0.000004 \\
0 & 0 & 0.000004 & \mathbf{1.084364}
\end{array}
\right),
$$
$$
A_{21}\approx
\left(\begin{array}{rrrr}
\mathbf{6.844621} & 0 & 0 & 0 \\
0 & 0.230166 & -2.229578 & 0 \\
0 & 2.224523 & -0.159152 & 0.000002 \\
0 & 0 & 0.000002 & \mathbf{1.084364}
\end{array}
\right) \, .
$$
Здесь два собственных числа однозначно локализуются на главной диагонали, но вот возникающие на ней же $ 2\times 2 $ блоки совершенно друг на друга не похожи. Хотя, если на этих шагах остановить процесс и вычислить
$$
\left|\begin{array}{rr}
0.159514-\lambda & -2.229578 \\
-2.229578 & -0.088499-\lambda
\end{array}\right| \quad \mbox{ и } \quad
\left|\begin{array}{rr}
0.230166 -\lambda & -2.229578 \\
2.2245235 & -0.159152 -\lambda
\end{array}\right|
$$
то эти два полинома оказываются практически идентичными, и их корни $ -2.197517 , 2.268531 $ совпадают с истинными значениями собственных чисел матрицы $ A $ с точностью до $ 10^{-6} $.
♦
==Источники==
[1]. **Хорн Р.**, **Джонсон Ч.** //Матричный анализ//. М.Мир.1989