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


Характеристический полином, собственные числа, собственные векторы матрицы

§

В настоящем разделе n_{} означает порядок квадратной матрицы A_{}.

Характеристический полином

определяется для произвольной квадратной матрицы A_{} как1) \det (A_{}-\lambda E), где E_{}единичная матрица одинакового с A_{} порядка.

П

Пример. Для n=2_{}:

\det (A-\lambda E)= \begin{vmatrix} a_{11}-\lambda & a_{12}\\ a_{21}& a_{22}-\lambda \end{vmatrix}=\lambda^2-(a_{11}+a_{22})\lambda + (a_{11}a_{22}-a_{12}a_{21}) ;

для n=3_{}:

\det (A-\lambda E)= \begin{vmatrix} a_{11}-\lambda & a_{12} & a_{13}\\ a_{21}& a_{22}-\lambda & a_{23} \\ a_{31}& a_{32} & a_{33}-\lambda \end{vmatrix}=
=-\lambda^3+(a_{11}+a_{22}+a_{33})\lambda^2 - \left \{ \begin{vmatrix} a_{11}& a_{12}\\ a_{21}& a_{22} \end{vmatrix} +\begin{vmatrix} a_{22}& a_{23}\\ a_{32}& a_{33} \end{vmatrix}+ \begin{vmatrix} a_{11}& a_{13}\\ a_{31}& a_{33} \end{vmatrix} \right \}\lambda +\det A .

Т

Теорема.

\det (A-\lambda E)= (-1)^n\Big( \lambda^n - \lambda^{n-1}\sum_{1\le j\le n} a_{jj} + \lambda^{n-2}\sum_{1\le j_1< j_2 \le n} \left|\begin{array}{ll} a_{j_1j_1}& a_{j_1j_2}\\ a_{j_2j_1}& a_{j_2j_2} \end{array}\right| - \dots +
+(-1)^k \lambda^{n-k} \sum_{1\le j_1< j_2 < \dots < j_k\le n} \left|\begin{array}{llll} a_{j_1j_1}& a_{j_1j_2} & \dots & a_{j_1j_k}\\ a_{j_2j_1}& a_{j_2j_2} & \dots & a_{j_2j_k}\\ \vdots & & & \vdots \\ a_{j_kj_1}& a_{j_kj_2} & \dots & a_{j_kj_k} \end{array}\right|+ \dots + (-1)^n \det A \Big) \ .

Образно говоря, коэффициент при (-1)^{k}\lambda^{n-k} получается суммированием всех миноров k_{}-го порядка матрицы A_{}, построенных на элементах ее главной диагонали.

!

Результат теоремы имеет исключительно теоретическое значение: практическое вычисление характеристического полинома матрицы большого порядка по этой теореме обычно крайне неэффективно. Методы практического вычисления характеристического полинома разбираются НИЖЕ.

П

Пример. Характеристический полином матрицы Фробениуса

\mathfrak F= \left( \begin{array}{lllllll} 0 & 1 & 0 & 0 & \dots & 0 & 0 \\ 0 & 0 & 1 & 0 & \dots & 0 & 0 \\ 0 & 0 & 0 & 1 & \dots & 0 & 0 \\ \vdots& &&&\ddots & & \vdots \\ 0 & 0 & 0 & 0 & \dots & 0 & 1 \\ a_n & a_{n-1} & a_{n-2} & & \dots & a_2 & a_1 \end{array} \right)_{n \times n}

равен (-1)^n(\lambda^n-a_1\lambda^{n-1}-\dots-a_{n}).

Характеристический полином линейного оператора

определяется как характеристический полином матрицы этого оператора в произвольном базисе линейного пространства, в котором этот оператор задан. Подробнее ЗДЕСЬ.

Характеристический полином линейного однородного разностного уравнения

n_{}-го порядка

x_{n+K}=a_1 x_{n+K-1}+ \dots+ a_n x_K, \quad a_n \ne 0,

определяется как

\lambda^n - a_1 \lambda^{n-1} - \dots - a_n .

Подробнее ЗДЕСЬ.

Свойства

Т

Теорема. Характеристический полином матрицы не меняется

Т

Теорема. Пусть матрица A_{} имеет порядок m\times n_{}, а B_{}порядок n\times m_{}. Тогда эти матрицы допускают умножение в любом порядке, т.е. определены AB_{} и BA_{} и оба произведения будут квадратными матрицами — порядков m_{} и n_{} соответственно. Тогда характеристические полиномы этих произведений различаются лишь на степень \lambda_{}:

\lambda^n \det (AB - \lambda E)\equiv \lambda^m \det (BA - \lambda E) \ .

=>

Если матрицы A_{} и B_{} — квадратные одинакового порядка, то характеристические полиномы матриц AB_{} и BA_{} тождественны.

Т

Теорема. Если характеристический полином матрицы A_{} равен f(\lambda)=(-1)^n \lambda^n+a_1\lambda^{n-1}+\dots+a_{n-1}\lambda+a_n и a_{n} \ne 0, то характеристический полином матрицы A^{-1}_{} равен

f^{\ast}(\lambda)=\frac{(-\lambda)^n}{a_n} f(1/\lambda) = \frac{(-1)^n}{a_n} \left[ (-1)^n+a_1 \lambda + \dots+ a_{n-1}\lambda^{n-1}+a_n\lambda^{n} \right] \ .

Теорема Гамильтона-Кэли

Т

Теорема. Результатом подстановки в характеристический полином \det (A_{}-\lambda E) самой матрицы A_{} будет нулевая матрица:

\det (A-\lambda E)= (-1)^n \lambda^n +a_1 \lambda^{n-1}+\dots+a_{n-1}\lambda+ a_n \ \Rightarrow
\ \Rightarrow \ (-1)^n A^n +a_1 A^{n-1}+\dots+a_{n-1}A+ a_n E = {\mathbb O}_{n\times n} \ .

В литературе эта теорема обычно приводится в иной формулировке:

матрица является корнем своего характеристического полинома.

Доказательство ЗДЕСЬ.

П

Пример. Для n_{}=2:

\left(\begin{array}{ll} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right)^2 - (a_{11}+a_{22})\left(\begin{array}{ll} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right) +
+(a_{11}a_{22}-a_{12}a_{21}) \left(\begin{array}{ll} 1 & 0 \\ 0 & 1 \end{array} \right) = \left(\begin{array}{ll} 0 & 0 \\ 0 & 0 \end{array} \right) \ .

Собственное число

определяется для квадратной матрицы A_{} как произвольный корень ее характеристического полинома \det (A_{}-\lambda E). Набор всех собственных чисел матрицы A_{} (с учетом их кратностей) называется спектром матрицы (таким образом спектр матрицы A_{} порядка n_{} всегда состоит из n_{} чисел, часть из которых могут быть одинаковыми). Максимальный из модулей собственных чисел матрицы A_{} называется ее спектральным радиусом, он иногда обозначается \rho(A).

П

Пример. Найти спектр матрицы

A= \left(\begin{array}{rrrr} 0&1&2&3\\ -1&0&4&7\\ -2&-4&0&2\\ -3&-7&-2&0 \end{array}\right).

Решение. Характеристический полином

\det (A-\lambda E)=\left|\begin{array}{rrrr} -\lambda&1&2&3\\ -1&-\lambda&4&7\\ -2&-4&-\lambda&2\\ -3&-7&-2&-\lambda \end{array}\right|=\lambda^4+ 83\lambda^2

имеет корни \lambda_1=0, \lambda_2 = {\mathbf i}\sqrt{83}, \lambda_3 = - {\mathbf i} \sqrt{83}, причем \lambda_{1} — второй кратности.

Ответ. Спектр матрицы A_{}: \{0,0, {\mathbf i} \sqrt{83},- {\mathbf i} \sqrt {83} \}. Спектральный радиус матрицы A_{}: \rho(A)= \sqrt {83}.

Т

Теорема 1. Если \{\lambda_{1},\lambda_{2},\dots,\lambda_{n} \}спектр матрицы A_{}, то

\lambda_1+\lambda_{2}+\dots+\lambda_n = \operatorname{Sp}(A)=a_{11}+a_{22}+\dots+a_{nn},
\lambda_1\cdot\lambda_{2}\times \dots \times \lambda_n = (-1)^n\det (A) \ .

Доказательство следует из представления характеристического полинома через миноры матрицы и формул Виета.

§

Можно, разумеется, привести еще n-2 зависимостей между собственными числами матрицы и ее минорами, но они редко нужны — а вот равенства из теоремы полезно запомнить.

=>

Для того, чтобы матрица A_{} была неособенной необходимо и достаточно, чтобы среди ее собственных чисел не было нулевого.

Т

Теорема 2. Пусть g(x)=b_{0}x^m+\dots+b_m \in {\mathbb C}[x] — произвольный полином. Вычислим полином от матрицы A_{}: g(A)=b_{0}A^m+\dots+b_m E. Тогда если \{\lambda_{1},\dots,\lambda_{n} \}спектр матрицы A_{}, то \{g(\lambda_{1}),\dots,g(\lambda_n) \}спектр матрицы g(A_{}).

=>

Результат теоремы обобщается и на более широкий класс функций g_{}(x) — фактически на любую функцию, которая может быть определена на спектре матрицы A_{}. В частности, если \det A_{} \ne 0, то спектр матрицы A^{-1}_{} совпадает с \{1/\lambda_j\}_{j=1}^n.

=>

Имеет место следующее равенство, связывающее степени матрицы A_{} с суммами Ньютона ее характеристического полинома:

\operatorname{Sp}(A^k)=\lambda_1^k+\dots+\lambda_n^k \ .

Здесь \operatorname{Sp}_{} обозначает след матрицы (т.е. сумму ее диагональных элементов). Утверждение остается справедливым и для отрицательных показателей k_{} при условии, что \det A_{} \ne 0.

=>

\det g(A) = (-1)^{mn} {\mathcal R}(f,g_{}), где {\mathcal R}(f,g_{}) означает результант полиномов f(x) =\det (A-x_{} E) и g_{}(x).

Т

Теорема 3. Собственные числа вещественной симметричной матрицы A_{} все вещественны.

Доказательство ЗДЕСЬ.

Т

Теорема 4. Собственные числа вещественной кососимметричной матрицы A_{} все мнимы, за исключением, возможно, \lambda_{} = 0.

Доказательство ЗДЕСЬ.

Т

Теорема 5. Собственные числа вещественной ортогональной матрицы все равны 1_{} по абсолютной величине (модулю). Характеристический полином ортогональной матрицы является возвратным если +1 не является его корнем или является корнем четной кратности. Хотя бы одно собственное число ортогональной матрицы нечетного порядка равно +1 или (-1).

Доказательство ЗДЕСЬ.

Т

Теорема 6. Спектр циклической матрицы

\left(\begin{array}{lllll} a_1 & a_2 & a_3 & \dots & a_n \\ a_n & a_1 & a_2 & \dots & a_{n-1} \\ a_{n-1} & a_n & a_1 & \dots & a_{n-2} \\ \vdots & & & & \vdots \\ a_2 & a_3 & a_4 & \dots & a_1 \end{array} \right) \ .

совпадает с набором чисел

\{f(1),f(\varepsilon_1), \dots, f(\varepsilon_{n-1}) \} ,

при

f(x)=a_{1}+a_2x+a_3x^2+\dots+a_nx^{n-1}

и

\varepsilon_k=\cos \frac{2\,\pi k}{n} + {\mathbf i} \sin \frac{2\,\pi k}{n}

корне n-й степени из единицы.

Доказательство ЗДЕСЬ.

Локализация собственных чисел

Т

Теорема. [1]. Собственные числа матрицы являются непрерывными функциями ее элементов. Иначе: пусть

A=\left[a_{jk} \right]_{j,k=1}^n \quad , \quad B=\left[b_{jk} \right]_{j,k=1}^n \ .

Обозначим

M= \max_{j,k\in\{1,\dots,n\}} \left\{|a_{jk} |, |b_{jk} | \right\} \quad , \quad \delta = \frac{1}{nM}\sum_{j,k=1}^n |a_{jk} - b_{jk} | \ .

Тогда любому собственному числу \lambda_{\ast}^{} матрицы A_{} можно поставить в соответствие такое собственное число \mu_{\ast}^{} матрицы B_{}, что

|\lambda_{\ast}-\mu_{\ast} | \le (n+2) M \sqrt[n]{\delta} \ .

Собственно факт непрерывной зависимости собственных чисел от элементов матрицы следует из представления характеристического полинома из теоремы ПУНКТА — коэффициенты этого полинома полиномиально (и, следовательно, непрерывно) зависят от элементов матрицы. Далее используем теорему о непрерывной зависимости корней полинома от его коэффициентов.

Выясним теперь на примере, насколько малым может быть возмущение элементов матрицы чтобы сохранились хотя бы количество вещественных корней ее характеристического полинома.

П

Пример [Уилкинсон] [2]. Найти собственные числа матрицы

A= \left( \begin{array}{cccccc} 20 & 20 & & & & \\ & 19 & 20 & & & \\ & & 18 & 20 & & \\ & & & \ddots & \ddots & \\ & & & & 2 & 20 \\ \varepsilon & & & & & 1 \\ \end{array} \right)_{20\times 20}

при \varepsilon=10^{-10} (все неуказанные элементы матрицы считаются равными нулю).

Решение. Характеристический полином

\det(A-\lambda E) = \prod_{j=1}^{20} (j-\lambda) - 20^{19} \varepsilon =
=\lambda^{20}-{\scriptstyle 210}\,\lambda^{19}+{\scriptstyle 20615}\,\lambda^{18}-{\scriptstyle 1256850}\, \lambda^{17} +{\scriptstyle 53327946}\, \lambda^{16}-{\scriptstyle 1672280820}\, \lambda^{15}+ {\scriptstyle 40171771630}\, \lambda^{14}-{\scriptstyle 756111184500}\, \lambda^{13}+
+{\scriptstyle 11310276995381}\, \lambda^{12} - {\scriptstyle 135585182899530}\, \lambda^{11} +{\scriptstyle 1307535010540395}\, \lambda^{10}-{\scriptstyle 10142299865511450}\, \lambda^9 +
+{\scriptstyle 63030812099294896}\, \lambda^8 - {\scriptstyle 311333643161390640}\, \lambda^7+{\scriptstyle 1206647803780373360}\, \lambda^6 -{\scriptstyle 3599979517947607200}\, \lambda^5 +{\scriptstyle 8037811822645051776}\, \lambda^4-
-{\scriptstyle 12870931245150988800}\, \lambda^3 +{\scriptstyle 13803759753640704000}\, \lambda^2 -{\scriptstyle 8752948036761600000}\,\lambda +{\scriptstyle 2432377720176640000}

очень похож на полином из другого ПРИМЕРА Уилкинсона. Он имеет корни

\lambda_1=0.995754, \ \lambda_2=2.109241,\ \lambda_3=2.574881,
\lambda_{4,5}=3.965331\pm 1.087735\, \mathbf i,\ \lambda_{6,7}=5.893977\pm 1.948530 \, \mathbf i,
\lambda_{8,9}=8.118073 \pm 2.529182 \, \mathbf i,\ \lambda_{10,11}=10.5\pm 2.733397 \, \mathbf i,
\lambda_{12,13}=12.881926\pm 2.529182 \, \mathbf i,\ \lambda_{14,15}=15.106022 \pm 1.948530 \, \mathbf i,
\lambda_{16,17}=17.034669\pm 1.087735 \, \mathbf i,
\lambda_{18}=18.425118,\ \lambda_{19}=18.890758,\ \lambda_{20}=20.004245 \ .

Итак, нановозмущение2) в одном-единственном элементе матрицы приводит к существенному изменению спектра: из 20 вещественных собственных чисел «остаются в живых» только 6_{}; кроме того, у образовавшихся мнимых корней оказываются достаточно большими мнимые части. В данном примере допустимые возмущения для \varepsilon_{}, т.е. такие, при которых сохранится свойство вещественности всех корней характеристического полинома, находятся в пределах3)

-8.636174\times 10^{-14}\ < \ \varepsilon \ \le \frac{685872258640569}{8796093022208000000000000000} \approx +7.797464 \times 10^{-14} \ .

Т

Теорема [Гершгорин].4) Обозначим \mathbb D_{j} круг на комплексной плоскости \mathbb C_{} с центром в точке a_{jj}^{} и радиуса

r_j=\sum_{\ell=1 \atop \ell\ne j}^n \left|a_{j \ell}\right| \ .

Тогда спектр матрицы A_{} лежит внутри объединения этих кругов:

\{\lambda_1,\dots, \lambda_n \} \subset \bigcup_{j=1}^n \mathbb D_j \ .

Иными словами: любое собственное число матрицы должно удовлетворять хотя бы одному из неравенств

|z- a_{jj} | < r_j \ .

П

Пример. Построить круги Гершгорина для матрицы

A=\left( \begin{array}{crr} -1+3\,{\mathbf i} & 2- {\mathbf i} & 3+2\, {\mathbf i} \\ -1+{\mathbf i} & 4+ {\mathbf i} & 3\, {\mathbf i} \\ -1& 2-2\,{\mathbf i}& -2-3\, {\mathbf i} \end{array} \right) .

Решение.

|\lambda + 1 - 3\,{\mathbf i} |\le | 2-{\mathbf i} |+| 3+2\,{\mathbf i} |=\sqrt{5}+\sqrt{13},
|\lambda - 4 - {\mathbf i} |\le 3+\sqrt{2},
|\lambda + 2+ 3\, {\mathbf i} |\le 1 + 2\sqrt{2} \ .

Проверка. Собственные числа матрицы A_{} (на рисунке обозначены красными крестиками):

\{ -2.509081750-3.442241533\,{\mathbf i} ,\ -1.041999986+2.655757676\,{\mathbf i} ,\ 4.551081736+1.786483857\, {\mathbf i} \} .
?

Построить круги Гершгорина для матрицы

A=\left( \begin{array}{rrr} -2 & 4+7\, {\mathbf i} & -3-7 \, {\mathbf i} \\ -1& 6+2\, {\mathbf i} & -5-2\, {\mathbf i} \\ -3& 4+7\, {\mathbf i} &-2-7\, {\mathbf i} \end{array} \right) \ .

Локализация вещественных собственных чисел

Симметричная матрица

Т

Теорема [Коши]. Для вещественной симметричной матрицы A_{} число ее собственных чисел, лежащих на интервале ]a,b_{}[, определяется по формуле:

\operatorname{nrr} \{ \det (A-\lambda E) =0 \ | \ a< \lambda<b \}=
= {\mathcal P}(1, H_1(a), H_2(a),\dots, H_n(a))- {\mathcal P}(1, H_1(b), H_2(b),\dots, H_n(b)) \ .

Здесь H_1(\lambda), H_2(\lambda),\dots, H_n(\lambda)главные миноры матрицы A-\lambda\, E, а {\mathcal P}_{}число знакопостоянств.

Согласно этой теореме, главные миноры матрицы A-\lambda\, E играют роль системы полиномов Штурма для характеристического полинома симметричной матрицы A_{}.

=>

Если все главные миноры A_1,A_2,\dots,A_{n} симметричной матрицы A_{} отличны от нуля, то число положительных собственных чисел матрицы A_{} равно числу знакопостоянств, а число отрицательных собственных чисел — числу знакоперемен в ряду 1,A_1,\dots,A_n:

\operatorname{nrr} \{ \det (A-\lambda E) =0 \ | \ \lambda>0 \} = {\mathcal P}(1,A_1,\dots,A_n),
\operatorname{nrr} \{ \det (A-\lambda E) =0 \ | \ \lambda<0 \}={\mathcal V}(1,A_1,\dots,A_n) \ .

П

Пример. Локализовать собственные числа матрицы

\left( \begin{array}{rrr} 11 & 2 & -8 \\ 2 & 2 & 10 \\ -8 & 10 & 5 \end{array} \right)

Решение.

H_1(\lambda)=11- \lambda, \ H_2(\lambda)=\lambda^2-13\, \lambda+18,
f(\lambda)= H_3(\lambda)=-\lambda^3+18\, \lambda^2 +81\, \lambda -1458 \ .
\lambda 1_{} H_1(\lambda) H_2(\lambda) H_3(\lambda) {\mathcal P} Комментарии
0_{} + + + - 2 число положительных =2
-10 + + + + 3 собственное число
-5 + + + - 2 лежит на ]-10,-5[
5 + + - - 2 собственное число
10 + + - + 1 лежит на ]5,10[
15 + - - + 1 собственное число
20 + - + - 0 лежит на ]15,20[

Проверка. Спектр матрицы: \{-9,9,18 \}.

П

Пример. Локализовать собственные числа матрицы

\left( \begin{array}{rrr} 1 & -2 & 2 \\ -2 & -2 & 4 \\ 2 & 4 & -2 \end{array} \right) \ .

Решение.

H_1(\lambda)=1- \lambda, \ H_2(\lambda)=\lambda^2+\, \lambda-6, \ f(\lambda)=H_3(\lambda)=-\lambda^3-3\, \lambda^2 +24\, \lambda -28 \ .
\lambda_{} 1_{} H_1(\lambda) H_2(\lambda) H_3(\lambda) {\mathcal P} Комментарии
0_{} + + - - 2 число положительных =2
-8 + + + + 3 собственное число
-6 + + + - 2 лежит на ]-8,-6[
1.5 + - - - 2 два собственных числа
3_{} + - + - 0 лежат на ]1.5,3[

Никаким дроблением интервала ]1.5\, , \, 3[ не удается отделить два вещественных собственных числа. Вывод: имеется кратное собственное число.

Проверка. Спектр матрицы: \{-7,2,2 \}.

Произвольная матрица

Собственный вектор

матрицы A_{}, принадлежащий (или соответствующий) ее собственному собственному числу \lambda_{\ast}^{}, определяется как ненулевой столбец

X_{\ast}= \left( \begin{array}{c} x_{1}^{\ast} \\ \vdots \\ x_{n}^{\ast} \end{array} \right) \in \mathbb{C}^n

такой, что

AX_{\ast}=\lambda_{\ast} X_{\ast} \quad \iff \quad (A -\lambda_{\ast}E) X_{\ast} = \mathbb O_{n\times 1} \ .

По определению собственного числа, \det (A^{} -\lambda_{\ast}E) = 0 и, следовательно, система однородных уравнений (A -\lambda_{\ast}E) X^{} = \mathbb O всегда имеет нетривиальное решение; более того, этих решений бесконечно много. Таким образом, одному и тому же собственному числу матрицы принадлежит бесконечное множество собственных векторов. Эту бесконечность можно описать с помощью фундаментальной системы решений (ФСР).

П

Пример. Найти собственные векторы матрицы

A= \left(\begin{array}{rrrr} 0&1&2&3\\ -1&0&4&7\\ -2&-4&0&2\\ -3&-7&-2&0 \end{array}\right).

Решение. Спектр матрицы найден выше.

(A-0 \cdot E)X=\mathbb O \quad \Longrightarrow ФСР= \ \left\{ {\mathfrak X}_1=\left(\begin{array}{r} 4 \\ -2 \\ 1 \\ 0 \end{array}\right), \ {\mathfrak X}_2=\left(\begin{array}{r} 7 \\ -3 \\ 0 \\ 1 \end{array} \right) \right\}.

Любой вектор вида \alpha_{1} {\mathfrak X}_1 + \alpha_2 {\mathfrak X}_2 будет собственным, принадлежащим \lambda_{}=0.

\begin{array}{c} (A- \mathbf i\, \sqrt {83} E)X=\mathbb O \\ \\ \Downarrow \\ \\ {\mathfrak X}_3= \left(\begin{array}{c} 1- \mathbf i \, \sqrt {83} \\ 8-2\, \mathbf i \, \sqrt {83} \\ 12 \\ 17+\mathbf i \, \sqrt {83} \end{array}\right) \end{array} \qquad \begin{array}{c} (A+\mathbf i \sqrt {83} E)X=\mathbb O \\ \\ \Downarrow \\ \\ {\mathfrak X}_4= \left(\begin{array}{c} 1+\mathbf i \, \sqrt {83} \\ 8+2\mathbf i \, \sqrt {83} \\ 12 \\ 17- \mathbf i \,\sqrt {83} \end{array}\right) \end{array} \ .

Еще один способ нахождения собственного вектора основан на теореме Гамильтона-Кэли.

Т

Теорема. Пусть \lambda_{\ast}^{} — собственное число матрицы A_{}. Обозначим частное от деления характеристического полинома на линейный множитель \lambda_{} - \lambda_{\ast} через f_{\ast}(\lambda)^{}:

f_{\ast}(\lambda) \equiv f(\lambda) / (\lambda-\lambda_{\ast}) \ .

Тогда любой ненулевой столбец матрицы f_{\ast}(A)^{} является собственным вектором, принадлежащим \lambda_{\ast}^{}.

Доказательство следует из равенства

(A-\lambda_{\ast} E)f_{\ast}(A)=\mathbb O_{n\times n} .

На основании определения любой ненулевой столбец f_{\ast}(A)^{} должен быть собственным вектором матрицы A_{}.

П

Пример. Найти собственные векторы матрицы

A=\left( \begin{array}{rrr} 9 & 22 & -6 \\ -1 &-4 & 1 \\ 8 & 16 & -5 \end{array} \right) .

Решение.

\det (A-\lambda E)=-\lambda^3+ 7\, \lambda + 6 \equiv -(\lambda_{}-3) (\lambda+2)(\lambda+1) \, .

Пренебрегая знаком – , имеем:

\begin{matrix} f_1(\lambda)=\lambda^2+3\lambda+2 & u & f_1(A)= \left( \begin{array}{rrr} 40 & 80 & -20 \\ 0 &0 & 0 \\ 40 & 80 & -20 \end{array} \right) \ , \\ f_2(\lambda)=\lambda^2-2\lambda-3 & u & f_2(A)= \left( \begin{array}{rrr} -10 & -30 & 10 \\ 5 &15 & -5 \\ 0 & 0 & 0 \end{array} \right) \ , \\ f_3(\lambda)=\lambda^2-\lambda-6 & u & f_3(A)= \left( \begin{array}{rrr} -4 & -8 & 4 \\ 4 & 8 & -4 \\ 8 & 16 & -8 \end{array} \right) \ . \end{matrix}

Ответ. {\mathfrak X}_{1}=[1,0,1]^{^{\top}} принадлежит \lambda_{1}^{}=3, {\mathfrak X}_{2}=[-2,1,0]^{^{\top}} принадлежит \lambda_{2}^{}=-2, {\mathfrak X}_{3}=[-1,1,2]^{^{\top}} принадлежит \lambda_{3}^{}=-1.

=>

Если \lambda_{\ast}^{} является простым корнем характеристического полинома, то ненулевые столбцы f_{\ast}(A)^{} будут пропорциональными.

Рассмотренный только что пример показывает, однако, нечто большее — ненулевые строки матрицы f_{\ast}(A)^{} тоже пропорциональны!

?

Доказать, что любая ненулевая строка матрицы f_{\ast}(A)^{} является собственным вектором матрицы A^{^{\top}}_{}, принадлежащим \lambda_{\ast}^{}. Доказать, что собственный вектор матрицы A_{} ортогонален собственному вектору матрицы A^{\top}_{}, если эти векторы принадлежат различным собственным числам5).

На практике вычисление полинома f_{\ast}(\lambda)^{} может быть осуществлено с помощью схемы Хорнера.

П

Пример. Вычислить собственный вектор матрицы

A=\left( \begin{array}{rrr} 23 & 75 & -92 \\ 6 & 74 & 72 \\ 37 & -23 & 87 \end{array} \right) ,

принадлежащий ее вещественному собственному числу.

Решение. Характеристический полином

f(\lambda)= -\lambda^3+184\,\lambda^2-14751\,\lambda+611404

имеет единственное вещественное собственное число \lambda_{\ast} \approx 96.8817. Составляем схему Хорнера

\begin{array}{c|cccc} & -1 & 184 & -14751 & 611404 \\ \hline 96.8817 & -1 & 87.1183 & -6310.8310 & -0.0352 \end{array}

За счет ошибок округления мы получили ненулевое значение для f(\lambda_{\ast}). В качестве частного от деления f(\lambda) на \lambda-\lambda_{\ast} берем

f_{\ast}(\lambda)= -\lambda^2 + 87.1183\, \lambda - 6310.8310 \ .

Подставляем в него матрицу A_{} и вычисляем первый столбец матрицы

-A^2+87.1183\,A -6310\, E = \left( \begin{array}{rrr} -1882.1101 & * & * \\ -2723.2902 & * & * \\ -708.6229 & * & * \end{array} \right) \ .

Проверяем:

\left( \begin{array}{rrr} 23 & 75 & -92 \\ 6 & 74 & 72 \\ 37 & -23 & 87 \end{array} \right) \left( \begin{array}{r} -1882.1101 \\ -2723.2902 \\ -708.6229 \end{array} \right) - 96.8817 \left( \begin{array}{r} -1882.1101 \\ -2723.2902 \\ -708.6229 \end{array} \right)= \left( \begin{array}{r} 0.0356 \\ 0 \\ -0.0002 \end{array} \right) \ .

Можно развить последний метод далее: найти универсальную формулу для собственного вектора как функции ее собственного числа. Действительно, найдем частное от деления характеристического полинома

f(\lambda) =a_0\lambda^n+a_0\lambda^{n-1}+\dots+ a_n, \ \quad a_0=(-1)^n

на линейный полином \lambda- \lambda_{\ast}, где \lambda_{\ast} — произвольное число из \mathbb C. С помощью той же схемы Хорнера, получаем

q(\lambda)=a_0\lambda^{n-1}+(a_0\lambda_{\ast}+a_1)\lambda^{n-2}+(a_0\lambda_{\ast}^2+a_1\lambda_{\ast}+a_2)\lambda^{n-3}+\dots+ (a_0\lambda_{\ast}^{n-1}+a_1\lambda_{\ast}^{n-2}+\dots+a_{n-1}) \, .

Если \lambda_{\ast} является собственным числом матрицы A_{}, то любой ненулевой столбец матрицы

q(A)= a_0A^{n-1}+(a_0\lambda_{\ast}+a_1)A^{n-2}+(a_0\lambda_{\ast}^2+a_1\lambda_{\ast}+a_2)A^{n-3}+\dots+ (a_0\lambda_{\ast}^{n-1}+a_1\lambda_{\ast}^{n-2}+\dots+a_{n-1})E

будет собственным вектором, принадлежащим \lambda_{\ast}.

П

Пример. Найти представление всех собственных векторов матрицы

A=\left( \begin{array}{rrr} 9 & 22 & -6 \\ -1 &-4 & 1 \\ 8 & 16 & -5 \end{array} \right)

в виде функции ее собственных чисел.

Решение. Характеристический полином матрицы был вычислен выше: f(\lambda)=-\lambda^3+ 7\, \lambda + 6. Имеем,

q(\lambda)=-\lambda^2-\lambda_{\ast}\lambda+(7-\lambda_{\ast}^2)

и

q(A)=-A^2-\lambda_{\ast}A+(7-\lambda_{\ast}^2)E= \left(\begin{array}{ccc} -\lambda_{\ast}^2-9\lambda_{\ast}-4 & -22\lambda_{\ast}-14 & 6\lambda_{\ast}+2 \\ \lambda_{\ast}-3 & -\lambda_{\ast}^2+4\lambda_{\ast}-3 & -\lambda_{\ast}+3 \\ -8\lambda_{\ast}-16 & -16\lambda_{\ast}-32 & -\lambda_{\ast}^2+5\lambda_{\ast}+14 \end{array} \right) \, .

Берем произвольный столбец этой матрицы, например, первый:

X_{\ast}(\lambda_{\ast})= \left(\begin{array}{c} -\lambda_{\ast}^2-9\lambda_{\ast}-4 \\ \lambda_{\ast}-3 \\ -8\lambda_{\ast}-16 \end{array} \right) \, .

Утверждается, что X_{\ast} (\lambda_{\ast}) — универсальное представление всех собственных векторов матрицы. Действительно,

X_{\ast}(-1) = \left(\begin{array}{r} 4 \\ -4 \\ -8 \end{array} \right),\ X_{\ast}(-2) = \left(\begin{array}{r} 10 \\ -5 \\ 0 \end{array} \right),\ X_{\ast}(3) = \left(\begin{array}{r} -40 \\ 0 \\ -40 \end{array} \right) \, .

§

Матрица q(A), которую мы построили для нахождения универсального представления собственного вектора, может быть получена другим способом. В самом деле, поскольку

f(\lambda)\equiv q(\lambda)(\lambda-\lambda_{\ast})+ f(\lambda_{\ast}),

то имеем справедливость матричного равенства:

f(A)\equiv q(A)(A-\lambda_{\ast}E)+ f(\lambda_{\ast})E \, .

Откуда, на основании теоремы Гамильтона-Кэли, получаем равенство

q(A)(A-\lambda_{\ast}E) = - E \det (A-\lambda_{\ast}E) \, .

Это равенство означает, что матрица (- q(A)) является взаимной матрице A-\lambda_{\ast}E. Следовательно, ее выражение (а нам, собственно, нужно только выражение для какого-то ее столбца) может быть получено с помощью алгебраических дополнений элементов матрицы A-\lambda_{\ast}E. Именно такой способ вычисления взаимной матрицы использовался при доказательстве теоремы Гамильтона-Кэли.

Т

Теорема. Пусть g(x)=b_0x^m+\dots+b_{m} \in {\mathbb C}[x] – произвольный полином. Если X_{\ast}\in \mathbb C^{n}собственный вектор матрицы A_{}, соответствующий собственному числу \lambda_{\ast}^{}, то он же будет собственным и для матрицы g(A)^{}, принадлежащим собственному числу g(\lambda_{\ast})^{}.

Доказательство. Домножим равенство A{\mathfrak X}_{\ast}=\lambda_{\ast}^{}{\mathfrak X}_{\ast} слева на матрицу A_{}:

A^2{\mathfrak X}_{\ast}=\lambda_{\ast}A{\mathfrak X}_{\ast}=\lambda_{\ast}^2{\mathfrak X}_{\ast} .

По индукции доказывается и общее равенство:

A^k{\mathfrak X}_{\ast}=\lambda_{\ast}^k{\mathfrak X}_{\ast} .

Домножим его на b_{m-k}^{} и просуммируем по k_{} от 0_{} до m_{}:

g(A){\mathfrak X}_{\ast}=g(\lambda_{\ast}){\mathfrak X}_{\ast} ,

что и доказывает утверждение теоремы.

Т

Теорема. Собственные векторы, принадлежащие различным собственным числам матрицы A_{}, линейно независимы.

Т

Теорема. Собственные векторы, принадлежащие различным собственным числам вещественной симметричной матрицы A_{}, ортогональны, т.е. если \mathfrak X_1 принадлежит собственному числу \lambda_{1}, а \mathfrak X_2 принадлежит собственному числу \lambda_{2} и \lambda_1 \ne \lambda_2, то

(\mathfrak X_1, \mathfrak X_2) =0 \ ,

где ( , ) означает скалярное произведение, определяемое стандартным образом: (X,Y)=x_1y_1+\dots+x_ny_n.

Доказательство ЗДЕСЬ.

Теорема Перрона-Фробениуса

Т

Теорема [Перрон, Фробениус]. Для положительной матрицы A_{} существует положительное собственное число \lambda_{+} такое, что все остальные собственные числа этой матрицы меньше \lambda_{+} по абсолютной величине (модулю). Соответствующий этому собственному числу собственный вектор может быть выбран положительным:

\exists \mathfrak X_{+} > \mathbb O: \quad A \mathfrak X_{+} = \lambda_{+} \mathfrak X_{+} \ .

Число \lambda_{+} из теоремы называется собственным числом Перрона или собственным числом Перрона-Фробениуса матрицы A_{}, а соответствующий ему произвольный положительный собственный вектор — собственным вектором Перрона-Фробениуса матрицы A_{}.

=>

Спектральный радиус положительной матрицы A_{} совпадает с ее собственным числом Перрона-Фробениуса:

\rho(A)=\lambda_{+} \ .

П

Пример. Найти собственное число и вектор Перрона-Фробениуса для матрицы

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_{}

\det(A-\lambda E)=\lambda^4-19\, \lambda^3-175\, \lambda^2-285\, \lambda+10390

имеет корнями

\lambda_{1,2} \approx -6.260463 \pm 5.452465 \mathbf i,\ \lambda_3 \approx 5.878976, \lambda_4 \approx 25.641950 \ .

Числом Перрона-Фробениуса является \lambda_4, а соответствующий ему собственный вектор Перрона-Фробениуса можно взять равным

\left( \begin{array}{c} 1 \\ 0.365240 \\ 0.184802 \\ 0.634244 \end{array} \right) \quad или \quad \left( \begin{array}{c} 2.737922 \\ 1 \\ 0.505974 \\ 1.736510 \end{array} \right) \quad или \left( \begin{array}{c} 5.411185 \\ 1.976383 \\ 1 \\ 3.432010 \end{array} \right) \quad или \quad \left( \begin{array}{c} 1.576681 \\ 0.575868 \\ 0.291374 \\ 1 \end{array} \right) \quad или \quad \left( \begin{array}{r} 0.798133 \\ 0.291510 \\ 0.147496\\ 0.506210 \end{array} \right) \quad или \dots

(напоминаю: собственный вектор определяется с точностью до ненулевого сомножителя!). Последний вектор имеет длину равную 1_{}.

Свойства.

1. Собственное число Перрона-Фробениуса всегда простое для характеристического полинома матрицы A_{}. Отсюда следует, что собственный вектор Перрона-Фробениуса определяется единственным образом — с точностью до домножения на положительный скаляр.

2. Любой собственный вектор положительной матрицы A_{}, не соответствующий собственному числу Перрона-Фробениуса, не может состоять исключительно только из положительных элементов. Иными словами, хотя бы одна компонента такого вектора должна быть либо отрицательной либо мнимой.

3. Для собственного числа Перрона-Фробениуса справедливо неравенство

\min_{j\in\{1,\dots,n\}} \sum_{k=1}^n a_{jk} \le \lambda_{+} \le \max_{j\in\{1,\dots,n\}} \sum_{k=1}^n a_{jk} \ .

4. Собственное число Перрона-Фробениуса матрицы A_{} совпадает с собственным числом Перрона-Фробениуса матрицы A^{\top}.


Какие из перечисленных свойств можно распространить на случай неотрицательных матриц ? Каждую такую матрицу можно рассматривать как предел последовательности (строго) положительных матриц. Воспользовавшись теоремой о непрерывной зависимости собственных чисел матрицы от ее элементов, можем сделать вывод, о том, что для неотрицательной матрицы A_{} всегда найдется вещественное неотрицательное собственное число, которое будет являться максимальным по модулю среди всех собственных чисел матрицы. Другое дело, что в данном случае — в отличие от случая положительных матриц — такое мажорирующее собственное число может оказаться не единственным.

П

Пример. Спектр неотрицательной матрицы

A=\left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)

состоит из чисел \lambda_1=+1 и \lambda_1=-1 одинакового модуля.

Однако, по-прежнему, хотя бы одно неотрицательное вещественное число \lambda_{+} со свойством \rho(A) = \lambda_{+} существовать будет; более того, ему будет соответствовать неотрицательный собственный вектор \mathfrak X \ge \mathbb O. Это число (вектор) по-прежнему называются числом (вектором) Перрона-Фробениуса6) матрицы A_{}.

Частным случаем неотрицательных матриц являются стохастические матрицы, т.е. неотрицательные матрицы, в которых сумма элементов каждой строки равна 1_{}:

P=\left[p_{jk}\right]_{j,k=1}^n, \{p_{jk}\ge 0 \}_{j,k=1}^n,\ \sum_{k=1}^n p_{jk} = 1 \ npu \quad j \in \{1,2,\dots,n\} \ .
Т

Теорема. Собственное число Перрона-Фробениуса стохастической матрицы равно 1_{}. Этому собственному числу соответствует собственный вектор X=[1,1,\dots,1]^{\top}.

Доказательство существования собственного числа равного 1_{} и соответствующего ему собственного вектора X=[1,1,\dots,1]^{\top} следует из равенства

P \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right) = \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array}\right) \ .

Далее, из теоремы Гершгорина следует, что любое собственное число \lambda_{}\in \mathbb C стохастической матрицы должно удовлетворять неравенству

|\lambda - p_{jj}|\le \sum_{k\ne j} |p_{jk}|=1-p_{jj}

хотя бы при одном j_{}. Воспользовавшись следствием к неравенству треугольника получаем:

|\lambda| - |p_{jj}|\le |\lambda - p_{jj}| \le 1-p_{jj} \ \Rightarrow \ |\lambda| \le 1 \ .

§

Численное нахождение собственного числа и собственного вектора Перрона-Фробениуса возможно по методу, разобранному в пункте ЧАСТИЧНАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЧИСЕЛ.

Методы вычисления характеристического полинома

Вычисление коэффициентов характеристического полинома матрицы A_{} непосредственным разложением определителя \det (A-\lambda_{} E) на n!_{} слагаемых — крайне неэффективно. Элементами этого разложения являются выражения, полиномиально зависящие от параметра \lambda_{}. На каждом этапе вычислений мы получаем проблему символьных вычислений: хранения таких полиномов и действий над ними.

Основной метод вычисления числовых определителей — метод Гаусса — также неэффективен в приложении к вычислению определителя, элементы которого зависят от параметра. Источником вычислительных проблем является неудобное расположение переменной \lambda_{} — на главной диагонали матрицы. Первый же шаг метода Гаусса приводит к делению на элемент a_{11} - \lambda, и, в дальнейшем, элементы преобразованной матрицы будут уже не полиномами, а рациональными функциями относительно \lambda_{}. Следующие шаги метода приводят к возрастанию степеней знаменателей. Необходимость в организации хранения рациональных функций и программировании действий с ними кажется тем более неоправданной, если вспомнить, что окончательный ответ — выражение для \det (A-\lambda_{} E) — должно быть полиномом по \lambda_{}; т.е. знаменатели дробей в конечном ответе сократятся.

А в качестве усугубляющего положение обстоятельства «на заднем плане» маячит проблема точности вычислений коэффициентов характеристического полинома — чувствительность его корней к возмущению его коэффициентов бывает весьма высокой.

Какой выход предлагается? — Предварительно преобразовать определитель \det (A-\lambda_{} E) к виду, когда переменная \lambda_{} оказывается «выметенной» с диагонали на крайний ряд (в столбец или в строку). При этом допускается увеличение размеров (порядка) определителя. Такое представление дает возможность разложения определителя по этому исключительному ряду, и, тем самым, позволяет свести задачу к вычислению числовых определителей — а уж для этой задачи применение метода Гаусса вполне эффективно.

Метод Леверье

Метод основан на формуле (см. следствие к теореме 2 ЗДЕСЬ ):

\operatorname{Sp} (A^k)=\lambda_1^k+\dots+\lambda_n^k=s_k \ ,

т.е. след k_{}-й степени матрицы A_{} равен k_{}-й сумме Ньютона ее характеристического полинома f(\lambda)=\det (A-\lambda E ). Вычисляем последовательные степени матрицы A_{}:

s_1=\operatorname{Sp} (A),\ s_2=\operatorname{Sp} (A^2),\ \dots, s_n=\operatorname{Sp} (A^n) \ .

Неизвестные коэффициенты f(\lambda)=(-1)^n(\lambda^n+a_1\lambda^{n-1}+ \dots+a_n) находим по рекурсивным формулам Ньютона:

a_1=-s_1, a_2=-(s_2+a_1s_1)/2,
a_k=-(s_{k}+a_1s_{k-1}+a_2s_{k-2}+\dots+a_{k-1}s_1)/k \ npu \ k \le n.

Очевидно, что не имеет смысла вычислять все элементы матрицы A^{n} — достаточно обойтись лишь элементами ее главной диагонали.

П

Пример [Леверье]. Найти характеристический полином матрицы

A=\left(\begin{array}{rrrr} -5.509882&1.870086&0.422908&0.008814 \\ 0.287865&-11.811654&5.711900&0.058717 \\ 0.049099&4.308033&-12.970687&0.229326 \\ 0.006235&0.269851&1.397369&-17.596207 \end{array} \right) \ .

Решение.

A^2=\left(\begin{array}{rrrr} 30.91795128&-30.56848188&2.878480155&0.0031325713\\ -4.705449283&164.6764010&-141.3504639&-0.4143169528\\ 0.3341843103&-106.6094396&193.1869924& -6.756396001\\ 0.0022236138&-1.904168948&-41.16923134& 309.9628536 \end{array} \right),
A^3=\left(\begin{array}{rrrr} -179.0125092&431.2849919&-198.8601505& -0.9173897610\\ 66.38829278&-2562.954533& 2771.458834& -15.49709921\\ -23.08728044&2090.291485&-3124.010318& 156.9329019\\ -0.649145142&-71.21907809&956.2502143& -5463.723497 \end{array} \right),
A^4=\left(\begin{array}{cccc} 1100.720103& \ast& \ast& \ast \\ \ast& 42332.23816& \ast& \ast \\ \ast& \ast& 52669.62534& \ast \\ \ast& \ast& \ast& 96355.91518 \end{array} \right) \ .

Вычисляем следы матриц:

s_1=-47.888430,\ s_2=698.7441983,\ s_3=-11329.70086,\ s_4= 192458.4988 \ ,

и по формулам Ньютона получаем:

a_1= 47.888430,\ a_2 = 797.278764_{\displaystyle 8} ,\ a_3 = 5349.45551_{\displaystyle 3},\ a_4 = 12296.550_{\displaystyle 68} \ .

После нахождения коэффициентов характеристического полинома можно найти его корни каким-либо7) методом. Если \lambda_{\ast}^{} — одно из собственных чисел, то для нахождения соответствующего собственного вектора воспользуемся алгоритмом из ПУНКТА. Предположив дополнительно, что это собственное число простое8), обозначим

f_{\ast}(\lambda)= f(\lambda)/(\lambda-\lambda_{\ast})=(-1)^n(\lambda^{n-1} +p_1\lambda^{n-2}+\dots+p_{n-2}\lambda+p_{n-1})

т.е. частное от деления f(\lambda_{}) на \lambda-\lambda_{\ast}. Тогда любой ненулевой столбец матрицы f_{\ast}(A)^{} будет собственным вектором, принадлежащим \lambda_{\ast}^{}. Как правило, собственным вектором можно взять комбинацию

Степени матрицы A_{} уже нами посчитаны при вычислении коэффициентов характеристического полинома.

П

Пример. Для приведенного выше примера находим собственные числа:

\lambda_1=-17.86326,\ \lambda_2=-17.15242,\ \lambda_3=-7.57404,\ \lambda_4= -5.29869 \ .

Коэффициенты f_1(\lambda) можно определить по схеме Хорнера:

\begin{array}{r|r|r|r|r|r} &1 & 47.888430 & 797.2787648 & 5349.455513 & 12296.55068 \\ \hline -17.86326 & 1 & \underbrace{30.025170}_{p_{_1}}& \underbrace{260.9313465}_{p_{_2}} &\underbrace{688.371028}_{p_{_3}}& \approx 0 \\ \end{array}

Собственным вектором, принадлежащим \lambda_{1}, будет

\left[ -0.0256_{\displaystyle 67},\ 0.21938_{\displaystyle 0},\ -0.24187_{\displaystyle 1},\ 1.044526 \right]^{^{\top}} \ .

Т

Теорема. Характеристический полином явно выражается через суммы Ньютона с помощью следующего представления:

f(\lambda)=\frac{1}{n!}\left| \begin{array}{llllll} s_1 &1 & & & &\\ s_2&s_1& 2 & &\mathbb O & \\ s_3&s_2&s_1&3& & \\ \vdots& & & \ddots &\ddots & \\ s_n&s_{n-1}& s_{n-2} & \dots &s_1&n \\ \lambda^n&\lambda^{n-1}&\lambda^{n-2}& \dots &\lambda&1 \end{array} \right|_{(n+1)\times (n+1)} \ .

§

Этот определитель имеет порядок больший, чем исходный \det (A_{}-\lambda E), однако в нем все включения переменной \lambda_{} локализованы в одной строке — именно такое размещение трактовалось как «хорошее» в смысле вычисления определителя в ВЫШЕ.

И

Биографические заметки о Леверье ЗДЕСЬ.

§

Существует модификация метода Леверье, позволяющая организовать одновременное вычисление как самого характеристического полинома матрицы A_{}, так и матрицы взаимной к матрице A_{}-\lambda E (что делает возможным получение универсальной формулы для всех собственных векторов матрицы A_{}); этот метод известен как метод Леверье-Фаддеева.

Метод Крылова

Рассмотрим произвольный ненулевой столбец Y_0=\left[ y_{1}^{[0]},\dots,y_{n}^{[0]} \right]^{^{\top}} \in \mathbb C^n. Cоставим итерационную векторную последовательность

Y_1=A\cdot Y_0,\ Y_2=A\cdot Y_1, \dots,\ Y_{n}=A\cdot Y_{n-1} \ .
Т

Теорема. Определитель

\det \left[\begin{array}{c|c|c|c|c} Y_0&Y_{1}&\dots&Y_{n-1}&Y_{n}\\ 1& \lambda&\dots&\lambda^{n-1}&\lambda^n \end{array} \right]_{(n+1)\times (n+1)}

совпадает — с точностью до постоянного множителя — с характеристическим полиномом матрицы A_{}. Здесь |_{} означает конкатенацию.

Доказательство. Легко видеть, что

Y_K=A^KY_0 \quad npu \quad K \in \{1,\dots,n\} \ .

Если

f(\lambda)=\det(A-\lambda E) =(-1)^n \lambda^n+a_1 \lambda^{n-1}+a_2 \lambda^{n-2}+\dots+a_n \ ,

то по теореме Гамильтона-Кэли:

(-1)^n A^n+a_1A^{n-1}+\dots+a_nE=\mathbb O_{n \times n} \ .

Это равенство останется справедливым и после умножения его на произвольный вектор, в том числе на Y_{0}:

(-1)^n A^n\cdot Y_0+a_1A^{n-1} \cdot Y_0 +\dots+a_n\cdot Y_0=\mathbb O_{n \times 1} \iff
\iff \quad (-1)^n Y_n+a_1Y_{n-1} +\dots+a_nY_0=\mathbb O \ .

Последнее равенство представляет линейную систему относительно неизвестных коэффициентов характеристического полинома. Можно решать ее по формулам Крамера, но мы пойдем другим путем. Дополним эту систему тождеством f(\lambda)=(-1)^n \lambda^n+a_1 \lambda^{n-1}+a_2 \lambda^{n-2}+\dots+a_n. Рассмотрим получившуюся систему как линейную однородную относительно столбца \left[ a_n,a_{n-1},\dots,a_1,1\right]^{\top}. Поскольку эта система имеет нетривиальное решение, то ее определитель должен равняться нулю:

0=\det \left[\begin{array}{c|c|c|c|c} Y_0&Y_{1}&\dots&Y_{n-1}&(-1)^nY_{n}\\ 1& \lambda&\dots&\lambda^{n-1}&(-1)^n\lambda^n-f(\lambda) \end{array} \right]=

(представляем последний столбец в виде суммы двух столбцов и используем свойство 5 определителя)

=\det \left[\begin{array}{c|c|c|c|c} Y_0&Y_{1}&\dots&Y_{n-1}&(-1)^nY_{n}\\ 1& \lambda&\dots&\lambda^{n-1}&(-1)^n\lambda^n \end{array} \right]-f(\lambda) \det \left[\begin{array}{c|c|c|c} Y_0&Y_{1}&\dots&Y_{n-1} \end{array} \right] \ .

Таким образом,

f(\lambda)=(-1)^n \frac{\det \left[\begin{array}{c|c|c|c|c} Y_0&Y_{1}&\dots&Y_{n-1}&Y_{n}\\ 1& \lambda&\dots&\lambda^{n-1}&\lambda^n \end{array} \right]}{\det \left[\begin{array}{c|c|c|c} Y_0&Y_{1}&\dots&Y_{n-1} \end{array} \right]} \ ,

если только знаменатель в этой дроби не обратится в нуль.

П

Пример. Найти характеристический полином матрицы примера Леверье

A=\left(\begin{array}{rrrr} -5.509882&1.870086&0.422908&0.008814 \\ 0.287865&-11.811654&5.711900&0.058717 \\ 0.049099&4.308033&-12.970687&0.229326 \\ 0.006235&0.269851&1.397369&-17.596207 \end{array} \right) \ .

Решение. Возьмем Y_0=\left[ 1,0,0,0 \right]^{\top}. Имеем

\begin{array}{cccc} Y_1=A Y_0= & Y_2=AY_1= & Y_3=AY_2= & Y_4=AY_3= \\ \left(\begin{array}{r} -5.509882\\ 0.287865 \\ 0.049099 \\ 0.006235 \end{array} \right), & \left(\begin{array}{r} 30.917951\\ -4.705449 \\ 0.334184 \\ 0.002223 \end{array} \right), & \left(\begin{array}{r} -179.012509\\ 66.388293 \\ -23.087280\\ -0.649145 \end{array} \right), & \left(\begin{array}{r} 1100.720101\\ -967.597333\\ 576.522644\\ -4.040153 \end{array} \right)\ . \end{array}
\det \left[\begin{array}{c|c|c|c|c} Y_0&Y_{1}&Y_2& Y_{3}& Y_{4}\\ 1& \lambda&\lambda^2 &\lambda^{3}&\lambda^4 \end{array} \right]= \left| \begin{array}{rrrrr} 1 & -5.509882 & 30.917951 & -179.012509 & 1100.720101 \\ 0 & 0.287865 & -4.705449 & 66.388293 & -967.597333\\ 0 & 0.049099 & 0.334184 & -23.087280 & 576.522644\\ 0 & 0.006235 & 0.002223 & -0.649145 & -4.040153 \\ 1 & \lambda & \lambda^2 & \lambda^3 & \lambda^4 \end{array} \right|=
=0.348621 \lambda^4+16.694915\lambda^3+277.948166\lambda^2+1864.932835\lambda+4286.836454 =
=0.348621 \left(\lambda^4+47.888430\lambda^3+797.27876_{\displaystyle 3}\lambda^2+5349.4555_{\displaystyle 0}\lambda+12296.550_{\displaystyle 5} \right) \ .

После нахождения характеристического полинома можно найти его корни каким-либо9) методом. Пусть \lambda_{\ast}^{} — одно из собственных чисел, и оно — простое; тогда для нахождения соответствующего собственного вектора можно воспользоваться тем же приемом, что был задействован в предыдущем ПУНКТЕ. Вычислим10) частное от деления f(\lambda_{}) на \lambda-\lambda_{\ast}

f_{\ast}(\lambda)= f(\lambda)/(\lambda-\lambda_{\ast})=(-1)^n(\lambda^{n-1} +p_1\lambda^{n-2}+\dots+p_{n-2}A+p_{n-1}) \ .

Тогда любой ненулевой столбец матрицы f_{\ast}(A)^{} будет собственным вектором, принадлежащим \lambda_{\ast}^{}. Но тогда и произвольная комбинация столбцов этой матрицы тоже будет собственным вектором (если только не обратится в нулевой вектор). В частности, это относится и к комбинации, записываемой в матричном виде

(-1)^n f_{\ast}(A) Y_0 = A^{n-1}Y_0 +p_1A^{n-2}Y_0+\dots+p_{n-1}Y_0=Y_{n-1}+p_1Y_{n-2}+\dots+p_{n-1}Y_0 \ .

А комбинируемые векторы уже посчитаны.

Теперь обсудим исключительные случаи. При неудачном выборе Y_{0} определитель

\det \left[\begin{array}{c|c|c|c} Y_0&Y_{1}&\dots&Y_{n-1} \end{array} \right]

может обратиться в нуль. Эта неприятность обязательно произойдет если, например, наш выбор пал на вектор Y_0, совпадающий с собственным вектором матрицы A_{}. Вероятность такого события — нулевая. В общем же случае, трудно ожидать, чтобы n_{} почти произвольных столбцов Y_0,Y_{1},\dots,Y_{n-1} оказались линейно зависимыми — если только сама матрица A_{} не обладает «скрытым дефектом» — типа рассмотренного в следующем примере.

П

Пример. Найти характеристический полином матрицы

A=\left( \begin{array}{ccc} 2&1&1 \\ 1&2&1 \\ 1&1&2 \end{array} \right) \ .

Решение. При любом выборе Y_0 векторы \{Y_0,Y_1,Y_2 \} оказываются линейно зависимыми:

Y_0= \left(\begin{array}{r} 1\\ 0\\ 0 \end{array} \right), Y_1= \left(\begin{array}{r} 2\\ 1\\ 1 \end{array} \right), Y_2= \left(\begin{array}{r} 6\\ 5\\ 5 \end{array} \right),\dots ; Y_0= \left(\begin{array}{r} 1\\ 1\\ 1 \end{array} \right),\ Y_1= \left(\begin{array}{r} 4\\ 4\\ 4 \end{array} \right),\dots

Объяснение этого феномена состоит в том, что для матрицы A_{} ее аннулирующий полином имеет степень меньшую ее порядка:

A^2-5\ A+4 E = \mathbb O \ .

Домножение этого равенства на произвольный столбец Y_0 и доказывает линейную зависимость системы \{Y_0,Y_1,Y_2\}.

Такая ситуация возможна только в случае, когда характеристический полином матрицы A_{} имеет кратные корни (в рассмотренном выше примере \lambda_{}=1 являлся двойным корнем \det (A-\lambda_{} E)); она исключительно редко встречается на практике.

Частичная проблема собственных чисел

Задача. Найти максимальное по модулю собственное число матрицы A_{}.

Предположение . Будем считать сначала, что максимальное по модулю собственное число матрицы единственно.

Рассмотрим произвольный ненулевой столбец Y_0=\left[ y_{1}^{[0]},\dots,y_{n}^{[0]} \right]^{^{\top}} \in \mathbb C^n. Cоставим такую же итерационную векторную последовательность, как и в методе Крылова

Y_1=A\cdot Y_0,\ Y_2=A\cdot Y_1, \dots,\ Y_{K}=A\cdot Y_{K-1},\dots ,

(только теперь, в отличие от метода Крылова, считаем ее неограниченно продолжающейся) и выделим последовательность первых элементов этих векторов:

y_{1}^{[1]},y_{1}^{[2]},\dots,y_{1}^{[K]},\dots
Т

Теорема. Как правило, предел

\lim_{K\to +\infty}\frac{y_{1}^{[K+1]}}{y_{1}^{[K]}}

существует и он равен максимальному по модулю собственному числу матрицы A_{}.

Доказательство. Перенумеруем собственные числа \lambda_{1},\dots,\lambda_n матрицы A_{} так, чтобы \lambda_{1} стало максимальным по модулю:

|\lambda_1|= \max_{j\in \{1,\dots,n\}} |\lambda_j| \ , \quad |\lambda_1|>|\lambda_j| \quad npu \quad j\in \{2,\dots,n\} \ .

Очевидно,

Y_{K}=A^K\cdot Y_0 \ ;

отсюда следует, что любой элемент столбца Y_{K} может быть линейно выражен через \lambda_{1}^K,\dots,\lambda_n^K. В частности, это справедливо и для первого элемента:

y_{1}^{[K]}=C_1\lambda_1^K+C_2\lambda_2^K+\dots+C_n\lambda_n^K \ .

В этом представлении \{C_j\}_{j=1}^n — будут константами из \mathbb C_{} в случае если все собственные числа являются простыми, и полиномами из \mathbb C[K] в случае, если имеются кратные собственные числа. Действительно, в первом случае существует базис пространства \mathbb C^n, состоящий из собственных векторов матрицы A_{}:

A{\mathfrak X}_j=\lambda_j{\mathfrak X}_j \quad npu \quad j\in \{1,\dots,n\} .

Вектор Y_0 можно разложить по этому базису:

Y_0=\alpha_1{\mathfrak X}_1+\dots+\alpha_n{\mathfrak X}_n \ .

Тогда последовательным домножением на матрицу A_{} получаем :

\begin{matrix} Y_1=AY_0&=& \alpha_1 \lambda_1{\mathfrak X}_1+\dots+\alpha_n\lambda_n{\mathfrak X}_n, \\ \dots & & \dots \\ Y_K=A^KY_0&=& \alpha_1 \lambda_1^K{\mathfrak X}_1+\dots+\alpha_n\lambda_n^K{\mathfrak X}_n \end{matrix}

откуда и следует доказываемое равенство.

Во втором случае — когда имеются кратные собственные числа матрицы A_{} — придется применять «тяжелую артиллерию» в виде жордановой нормальной формы, но этот материал еще в разработке… Для простоты рассуждений, будем в оставшейся части доказательства считать все собственные числа матрицы различными. Имеем тогда

\lim_{K \to +\infty} \frac{y_{1}^{[K+1]}}{y_{1}^{[K]}}= \lim_{K \to +\infty} \frac{\lambda_1^{K+1} \left[C_1+ C_2(\lambda_2/\lambda_1)^{K+1}+\dots+ C_n(\lambda_n/\lambda_1)^{K+1} \right]} {\lambda_1^{K} \left[C_1+C_2(\lambda_2/\lambda_1)^{K}+\dots+ C_n(\lambda_n/\lambda_1)^{K} \right]} =\lambda_1

поскольку

\lim_{K \to +\infty} \left| \frac{\lambda_j}{\lambda_1} \right|^K = 0 \quad npu \quad j\in \{2,\dots,n\} \ .

Исключительным случаем является ситуация C_1=0, в этом случае утверждение теоремы может оказаться несправедливым11).

=>

Как правило, вектор

\left[1, \lim_{K\to +\infty}\frac{y_{2}^{[K]}}{y_{1}^{[K]}},\dots, \lim_{K\to +\infty}\frac{y_{n}^{[K]}}{y_{1}^{[K]}}\right]^{^{\top}}

будет собственным, принадлежащим максимальному по модулю собственному числу матрицы A_{}.

П

Пример. Для матрицы

A=\left(\begin{array}{rrr} 2 & 3 &-1\\ 7 & 3 & 3 \\ -1 & -2 & -4 \end{array} \right)

найти максимальное по модулю собственное число и принадлежащий ему собственный вектор.

Решение. Возьмем в качестве стартового столбца Y_0=[1,0,0]^{^{\top}}. Имеем:

Y_1=AY_0=\left( \begin{array}{r} 2 \\ 7 \\ -1 \end{array} \right),\ Y_2=AY_1=\left( \begin{array}{r} 26 \\ 32 \\ -12 \end{array} \right),\ Y_3=AY_2=\left( \begin{array}{r} 160 \\ 242 \\ -42 \end{array} \right),\dots,
Y_{19}=\left( \begin{array}{r} {\scriptstyle 4259667747238636} \\ {\scriptstyle 6435097324667832} \\ {\scriptstyle -1571397155909260} \end{array} \right),\ Y_{20}=AY_{19}=\left( \begin{array}{r} {\scriptstyle 29396024624390028} \\ {\scriptstyle 44408774736946168} \\ {\scriptstyle -10844273772937260} \end{array} \right)

Смотрим на отношения первых элементов векторов:

\begin{array}{c|c|c|c|c|c|c|c|c|c} K & 1 & 2 & 3 & 4 & 5 & \dots & 15 & \dots & 19 \\ \hline y_{1}^{[K+1]}/y_{1}^{[K]} & 2 & 13 & 6.153846 & 6.8 & 7.180147 & \dots & 6.900726 & \dots & \mathbf{6.90101}_{\displaystyle 3} \end{array}

Далее, в соответствии со следствием, собственный вектор, принадлежащий найденному числу

\approx \left[1, \frac{y_{2}^{[20]}}{y_{1}^{[20]}},\frac{y_{3}^{[20]}}{y_{1}^{[20]}}\right]^{^{\top}} \approx \left[1, 1.51070_{\displaystyle 6}, -0.368902 \right]^{^{\top}}

§

Результат теоремы представляет собой обобщение метода Бернулли поиска максимального по модулю корня полинома. Если в качестве матрицы A_{} взять матрицу Фробениуса

\mathfrak F= \left( \begin{array}{lllllll} 0 & 1 & 0 & 0 & \dots & 0 & 0 \\ 0 & 0 & 1 & 0 & \dots & 0 & 0 \\ 0 & 0 & 0 & 1 & \dots & 0 & 0 \\ \vdots& &&&\ddots & & \vdots \\ 0 & 0 & 0 & 0 & \dots & 0 & 1 \\ a_n & a_{n-1} & a_{n-2} & & \dots & a_2 & a_1 \end{array} \right)_{n \times n} \ ,

то равенство

X_K=\mathfrak F X_{K-1} \ npu \ K\in \{1,2,\dots \}

определяет — при задании (произвольным образом) чисел x_0,x_1,\dots,x_{n-1} — линейную рекуррентную последовательность порядка n_{}:

x_{n+K}=a_1 x_{n+K-1}+ \dots+ a_n x_K \ .

Здесь столбцы X_K определяются формулами

X_0=\left( \begin{array}{l} x_0 \\ x_1 \\ \vdots \\ x_{n-1} \end{array} \right),\ X_1=\left( \begin{array}{l} x_1 \\ x_2 \\ \vdots \\ x_{n} \end{array} \right),\ X_2=\left( \begin{array}{l} x_2 \\ x_3 \\ \vdots \\ x_{n+1} \end{array} \right),\ \dots, X_K=\left( \begin{array}{l} x_K \\ x_{K+1} \\ \vdots \\ x_{K+n-1} \end{array} \right),\dots ;

Характеристический полином последовательности совпадает с характеристическим полиномом матрицы \mathfrak F, т.е. с \lambda^n-a_1 \lambda^{n-1} -a_2 \lambda^{n-2} -\dots - a_n.


Теперь обсудим исключительные случаи алгоритма.

1. Нарушение сходимости итерационного процесса за счет неудачного выбора стартового вектора. Если в качестве Y_{0} оказался случайно взят собственный вектор \mathfrak X_{\ast} матрицы A_{}, принадлежащий произвольному ее собственному числу \lambda_{*}, то предел последовательности из теоремы будет равен именно этому числу; если при этом |\lambda_{*} | \ne \max_{1\le j \le n} | \lambda_j |, то мы выйдем за пределы смысла выражения «как правило». Понятно, что вероятность настолько плохого выбора нулевая, но и выбор Y_0 вблизи \mathfrak X_{\ast} также может существенно замедлить скорость сходимости. Поэтому если возникает ситуация медленной «стабилизации» значащих цифр в десятичном приближении собственного числа, попробуйте сменить начальный вектор.

2. Нарушение условия предположения , выдвинутого в начале пункта: максимальное по модулю собственное число неединственно.

П

Пример. Найти максимальное по модулю собственное число матрицы примера Леверье

A=\left(\begin{array}{rrrr} -5.509882&1.870086&0.422908&0.008814 \\ 0.287865&-11.811654&5.711900&0.058717 \\ 0.049099&4.308033&-12.970687&0.229326 \\ 0.006235&0.269851&1.397369&-17.596207 \end{array} \right) \ .

Решение. Для столбца Y_0=[1,0,0,0]^{^{\top}} имеем

y_{1}^{[100]}/y_{1}^{[99]}=-17.8_{\displaystyle 3113} \ ,

т.е. на 100-й итерации получаем лишь 3_{} истинные десятичные цифры в представлении собственного числа. При этом компонентами векторов Y_{K} являются числа порядка 10^{123}. Если мы посмотрим на ответ примера Леверье, то увидим, что имеются два собственных числа матрицы, близких по модулю.

К сожалению, вероятность того факта, что у случайно выбранной матрицы два ее собственных числа будут иметь одинаковый модуль становится ненулевой если эта матрица выбирается из множества вещественных матриц. Дело в том, что в этом случае ее характеристический полином будет иметь вещественные коэффициенты, а мнимые корни такого полинома всегда пáрные — для любого невещественного корня \lambda_{\ast}^{} полинома, комплексно сопряженное к нему число \overline{\lambda_{\ast}} также будет корнем. При этом |\lambda_{\ast}|= |\overline{\lambda_{\ast}} |.

П

Пример. Для матрицы

A=\left(\begin{array}{rrr} 3 & 2 &7\\ -2 & -8 & 2 \\ 5 & -3 & -2 \end{array} \right)

итерационная последовательность из теоремы ведет себя хаотически: при выборе Y_0=[1,0,0]^{\top} получим

\left\{\frac{y_{1}^{[K+1]}}{y_{1}^{[K]}}\right\}_{K=1}^{\infty} = 3; 13.3333; 5.9250; 4.6455; 15.9273; 0.8546; 68.0186; 0.4543; 91.7873; \dots

Спектр матрицы: \{ 6.9363, -6.9682\pm 3.0186 \mathbf i\}, и максимальное по модулю собственное число неединственно.

§

Существуют приемы, позволяющие модифицировать метод на случай когда два числа спектра матрицы близки по модулю к максимальному; они подробно обсуждаются в [3].

.

Задачи

ЗДЕСЬ.

Источники

[1]. Островский А.М. Решение уравнений и систем уравнений. М. ИЛ, 1963, c. 137-142

[2]. Уилкинсон Дж.Х. Алгебраическая проблема собственных значений. М.Наука. 1970, с.93-94

[3]. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. М.ГИФМЛ. 1960

1) По традиции, идущей из XIX века, переменную характеристического полинома обозначают через \lambda_{}.
2) \nu \tilde \alpha \nu o \varsigma (др.греч.) — гном, карлик. Приставка нано- в системе СИ означает 10^{-9}.
3) Просчитаны мною. au
4) Гершгорин Семён Аронович (1901-1933) — советский математик, выпускник петроградского Технологического института. Биография ЗДЕСЬ (англ.)
5) Здесь предполагается, что скалярное произведение вещественных векторов X=(x_1,x_2,\dots)^{\top} и Y=(y_1,y_2,\dots)^{\top} определяется стандартным образом: (X,Y)= X^{\top} Y = \sum_j x_jy_j; впрочем, при таком определении данное конкретное утверждение будет справедливо даже для собственных векторов, имеющих мнимые координаты!
6) В отечественных источниках фамилию Перрона часто опускают — пусть это будет на совести их авторов!
7) , 9) Как правило, приближенным
8) А вероятность противоположного события — нулевая.
10) Например, по схеме Хорнера
11) Именно эта ситуация скрывалась в формулировке теоремы под словами «как правило».

2017/03/16 08:55 редактировал au