УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу "Характеристический полином, собственные числа, собственные векторы матрицы".


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}, которая будет верхнетреугольной.

Т

Теорема [4]. Если все собственные числа матрицы 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{RubineRed} \star } & \ast & \ast & \ast \\ \hline 0 & {\color{RubineRed} \star } & {\color{RubineRed} \star } & \ast \\ 0 & {\color{RubineRed} \star } & {\color{RubineRed} \star } & \ast \\ \hline 0 & 0 & 0 & {\color{RubineRed} \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 и \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}.


2017/11/16 09:33 редактировал au