Этот алгоритм основан на 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