Как найти характеристические числа матрицы

Содержание

§

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

определяется для произвольной квадратной матрицы $ A_{} $ как¹⁾
$ 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 .
$$

Т

Теорема 1.

$$ det (A-lambda E)=
(-1)^nBigg(
lambda^n — lambda^{n-1}sum_{1le jle n} a_{jj}
+ lambda^{n-2}sum_{1le 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_{1le j_1< j_2 < dots < j_kle 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
Bigg) .
$$
Образно говоря, коэффициент при $ (-1)^{k}lambda^{n-k} $ получается
суммированием всех миноров $ k_{} $-го порядка матрицы $ A_{} $, построенных на
элементах, стоящих в строках и столбцах с одинаковыми номерами..

Такой минор матрицы
$$
left|begin{array}{cccc}
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 & & ddots & vdots \
a_{j_kj_1} & a_{j_kj_2} & dots & a_{j_kj_k}
end{array}
right|
, quad 1le j_1<j_2< dots < j_k le n
$$
в настоящем ресурсе называется ведущим минором ($k$-го порядка). См. замечание о терминологии

☞

ЗДЕСЬ.

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

☟

НИЖЕ.

П

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

$$
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_1lambda^{n-1}-dots-a_{n}) $.

Т

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

1.

при ее транспонировании:
$$ det (A-lambda E) = det (A^{top}-lambda E_{}) , ;$$

2.

при переходе к подобной матрице: если $ B=C^{-1}AC^{} $ при произвольной неособенной матрице $ C_{} $, то
$$ det (A-lambda E) equiv det (B-lambda E_{}) , . $$

Т

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

$$
lambda^n det (AB — lambda E_{m times m})equiv lambda^m det (BA — lambda E_{n times n}) .
$$

=>

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

Т

Теорема 4. Если характеристический полином матрицы $ A_{} $ равен

$$ f(lambda)=(-1)^n lambda^n+a_1lambda^{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_nlambda^{n} right] . $$

Т

Теорема 5. Результатом подстановки в характеристический полином $ 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}_{ntimes 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) $. Уравнение
$$
det(A-lambda E)=0
$$
называется характеристическим уравнением матрицы $ A $.

И

Понятие характеристического уравнения было введено Коши в 1840 г. В литературе XIX века известно также как вековое уравнение.

Набор всех собственных чисел матрицы $ 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+
83lambda^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} $.

Т

Теорема 6. Если $ {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_1cdotlambda_{2}times dots times lambda_n = (-1)^ndet (A) . $$

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

♦

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

=>

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

Т

Теорема 7. Пусть $ 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) $.

Т

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

Доказательство

☞

ЗДЕСЬ.

Т

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

Доказательство

☞

ЗДЕСЬ.

Т

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

Доказательство

☞

ЗДЕСЬ.

Т

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

$$
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-й степени из единицы.

Доказательство

☞

ЗДЕСЬ.

Т

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

$$A=left[a_{jk} right]_{j,k=1}^n quad , quad B=left[b_{jk} right]_{j,k=1}^n
.
$$
Обозначим
$$M= max_{j,kin{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 \
{color{Red} varepsilon } & & & & & 1 \
end{array}
right)_{20times 20}
$$
при $ {color{Red} varepsilon }=10^{-10} $
(все неуказанные элементы матрицы считаются равными нулю).

Решение. Характеристический полином
$$
det(A-lambda E) = prod_{j=1}^{20} (j-lambda) — 20^{19} {color{Red} 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.965331pm 1.087735, mathbf i, lambda_{6,7}=5.893977pm 1.948530 , mathbf i,
$$
$$
lambda_{8,9}=8.118073 pm
2.529182 , mathbf i,
lambda_{10,11}=10.5pm 2.733397 , mathbf i,
$$
$$
lambda_{12,13}=12.881926pm 2.529182 , mathbf i, lambda_{14,15}=15.106022 pm 1.948530
, mathbf i, $$
$$
lambda_{16,17}=17.034669pm 1.087735 , mathbf i,
$$
$$
lambda_{18}=18.425118, lambda_{19}=18.890758, lambda_{20}=20.004245 .
$$
Итак, нановозмущение⁵⁾ в одном-единственном элементе матрицы приводит к существенному изменению спектра: из $ 20 $ вещественных собственных чисел «остаются в живых» только $ 6_{} $; кроме того, у образовавшихся мнимых корней оказываются достаточно большими мнимые части. В данном примере допустимые возмущения для $ {color{Red} varepsilon } $, т.е. такие, при
которых сохранится
свойство вещественности всех корней характеристического полинома, находятся в пределах⁶⁾
$$ -8.636174times 10^{-14} < {color{Red} varepsilon } le frac{685872258640569}{8796093022208000000000000000} approx +7.797464 times 10^{-14} .$$

♦

Т

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

$$ r_j=sum_{ell=1 atop ellne 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 + 2sqrt{2} . $$

Проверка. Собственные числа матрицы $ A_{} $ (на рисунке обозначены красными крестиками):
$$ { -2.509081750-3.442241533,{mathbf i} , -1.041999986+2.655757676,{mathbf i} , 4.551081736+1.786483857, {mathbf i} } .$$

Т

Теорема 14 [Коши].
Для вещественной симметричной матрицы $ 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
.
$$

Проверка. Спектр матрицы: $ {-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
.
$$

Никаким дроблением интервала $ ]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_{ntimes 1} . $$
По определению собственного числа, $ det (A^{} -lambda_{ast}E) = 0 $ и, следовательно,
система однородных уравнений $ (A -lambda_{ast}E) X^{} = mathbb O $ всегда имеет нетривиальное решение; более того, этих решений бесконечно много. Таким образом, одному и тому же собственному числу матрицы принадлежит бесконечное множество собственных векторов. Эту бесконечность можно описать с помощью фундаментальной системы решений (ФСР).

Строго говоря, только что введено определение правого собственного вектора матрицы $ A $. Потому как для
этой же матрицы определяется и левый собственный вектор — как строка $ Y_{ast}=(y_1^{ast},dots, y_n^{ast}) ne mathbb O $, такая, что
$$ Y_{ast} A= mu_{ast} A quad mbox{ при некотором } mu_{ast} in mathbb C , . $$
Очевидно, что $ Y_{ast} $ является левым собственным вектором $ A $ тогда и только тогда, когда столбец $ Y_{ast}^{top} $ является правым собственным вектором матрицы $ A^{^{top}} $. Кроме того, поскольку спектры матриц $ A $ и $ A^{^{top}} $ совпадают, то все результаты, полученные для правых собственных векторов, автоматически переносятся и на левые. Традиционно принято рассматривать правые собственные векторы; в этом случае слово «правый» опускают.

П

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

$$
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 mbox{ ФСР}=
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+2mathbf i , sqrt {83} \ 12 \ 17- mathbf i ,sqrt {83}
end{array}right)
end{array} .
$$

♦

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

Т

Теорема 15. Пусть $ 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_{ntimes 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+3lambda+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-2lambda-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)^{} $ будут пропорциональными. Или, что то же, $ operatorname{rank} f_{ast}(A)^{} = 1 $.

Тогда очевидно, что и строки матрицы $ f_{ast}(A)^{} $ тоже должны быть пропорциональны!

На практике вычисление полинома $ 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_0lambda^n+a_0lambda^{n-1}+dots+ a_n, quad a_0=(-1)^n $$
на линейный полином $ lambda- lambda_{ast} $, где $ lambda_{ast} $ — произвольное число из $ mathbb C $. С помощью той же схемы Хорнера, получаем
$$ q(lambda)= $$
$$
=a_0lambda^{n-1}+(a_0lambda_{ast}+a_1)lambda^{n-2}+(a_0lambda_{ast}^2+a_1lambda_{ast}+a_2)lambda^{n-3}+dots+ (a_0lambda_{ast}^{n-1}+a_1lambda_{ast}^{n-2}+dots+a_{n-1}) , .
$$
Если $ lambda_{ast} $ является собственным числом матрицы $ A_{} $, то любой ненулевой столбец матрицы
$$ q(A)= $$
$$
=a_0A^{n-1}+(a_0lambda_{ast}+a_1)A^{n-2}+(a_0lambda_{ast}^2+a_1lambda_{ast}+a_2)A^{n-3}+dots+ (a_0lambda_{ast}^{n-1}+a_1lambda_{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-9lambda_{ast}-4 & -22lambda_{ast}-14 & 6lambda_{ast}+2 \
lambda_{ast}-3 & -lambda_{ast}^2+4lambda_{ast}-3 & -lambda_{ast}+3 \
-8lambda_{ast}-16 & -16lambda_{ast}-32 & -lambda_{ast}^2+5lambda_{ast}+14
end{array} right) , .
$$
Берем произвольный столбец этой матрицы, например, первый:
$$
X_{ast}(lambda_{ast})=
left(begin{array}{c}
-lambda_{ast}^2-9lambda_{ast}-4 \
lambda_{ast}-3 \ -8lambda_{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 $:
$$ — q(A)=operatorname{adj}(A-lambda_{ast}E) , . $$
Следовательно, ее выражение (а нам, собственно, нужно только выражение для какого-то ее столбца)
может быть получено с помощью алгебраических дополнений элементов матрицы $ A-lambda_{ast}E $. Именно такой способ вычисления взаимной матрицы использовался при доказательстве теоремы Гамильтона-Кэли.

Т

Теорема 16. Пусть $ 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^{-1} $. В частности, собственные векторы $ A^{-1} $ совпадают с собственными векторами матрицы $ A $.

Т

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

Т

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

$$ langle mathfrak X_1, mathfrak X_2 rangle =0 , $$
где $ langle , rangle $ означает скалярное произведение, определяемое стандартным образом: $ langle X,Y rangle =x_1y_1+dots+x_ny_n $.

Доказательство

☞

ЗДЕСЬ.

Т

Теорема 19 [Перрон, Фробениус]. Для положительной матрицы $ 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 mbox{ или } quad
left(
begin{array}{c}
2.737922 \ 1 \ 0.505974 \ 1.736510
end{array}
right) quad mbox{ или }
left(
begin{array}{c}
5.411185 \ 1.976383 \ 1 \ 3.432010
end{array}
right) quad mbox{ или } quad
left(
begin{array}{c}
1.576681 \ 0.575868 \ 0.291374 \ 1
end{array}
right) quad mbox{ или } quad
left(
begin{array}{r}
0.798133 \
0.291510 \
0.147496\
0.506210
end{array}
right) quad mbox{ или } dots
$$
(напоминаю: собственный вектор определяется с точностью до ненулевого сомножителя!). Последний вектор имеет длину равную $ 1_{} $.

♦

Свойства.

1.

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

2.

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

3.

Для собственного числа Перрона-Фробениуса справедливо неравенство
$$ min_{jin{1,dots,n}} sum_{k=1}^n a_{jk} le lambda_{+} le max_{jin{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 $. Это число (вектор) по-прежнему называются числом (вектором) Перрона-Фробениуса¹⁰⁾ матрицы $ A_{} $.

Частным случаем неотрицательных матриц являются стохастические матрицы, т.е. неотрицательные матрицы, в которых сумма элементов
каждой строки равна $ 1_{} $:
$$
mathfrak 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} .
$$

Т

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

Доказательство существования собственного числа равного $ 1_{} $ и соответствующего ему собственного вектора $ X=[1,1,dots,1]^{top} $ следует из равенства
$$mathfrak 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_{kne 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_{} $ оказывается «выметенной» с диагонали на крайний ряд (в столбец или в строку). При этом допускается увеличение размеров (порядка) определителя. Такое представление дает возможность разложения определителя по этому исключительному ряду, и, тем самым, позволяет свести задачу к вычислению числовых
определителей — а уж для этой задачи применение метода Гаусса вполне эффективно.

Метод основан на формуле (см. следствие к теореме $ 7 $

☞

ЗДЕСЬ ):
$$ 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_1lambda^{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} . $$

♦

После нахождения коэффициентов характеристического полинома можно найти его корни каким-либо¹¹⁾ методом. Если $ lambda_{ast}^{} $ — одно
из собственных чисел, то для нахождения соответствующего собственного
вектора воспользуемся алгоритмом из

☞

ПУНКТА. Предположив дополнительно, что это собственное число простое¹²⁾, обозначим
$$
f_{ast}(lambda)= f(lambda)/(lambda-lambda_{ast})=(-1)^n(lambda^{n-1}
+p_1lambda^{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}} .$$

♦

Т

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

$$
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=Acdot Y_0, Y_2=Acdot Y_1, dots, Y_{n}=Acdot Y_{n-1} .
$$

Т

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

$$
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^ncdot Y_0+a_1A^{n-1} cdot Y_0 +dots+a_ncdot 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,1right]^{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)^nlambda^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)^nlambda^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.694915lambda^3+277.948166lambda^2+1864.932835lambda+4286.836454 =
$$
$$
=0.348621 left(lambda^4+47.888430lambda^3+797.27876_{displaystyle 3}lambda^2+5349.4555_{displaystyle 0}lambda+12296.550_{displaystyle 5} right) .
$$

♦

После нахождения характеристического полинома можно найти его корни каким-либо¹³⁾ методом. Пусть $ lambda_{ast}^{} $ — одно из собственных чисел, и оно —
простое; тогда для нахождения соответствующего собственного вектора можно воспользоваться тем же приемом, что был задействован в предыдущем ПУНКТЕ. Вычислим¹⁴⁾ частное от деления $ f(lambda_{}) $ на $ lambda-lambda_{ast} $
$$
f_{ast}(lambda)= f(lambda)/(lambda-lambda_{ast})=(-1)^n(lambda^{n-1}
+p_1lambda^{n-2}+dots+p_{n-2}lambda+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) $); она исключительно редко встречается на практике.

Этот алгоритм основан на QR-разложении матрицы $ A $.

Т

Теорема 23. Спектр матрицы $ 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} $, которая будет верхнетреугольной.

Т

Теорема 24 [4]. Если все собственные числа матрицы $ A $ различны по модулю, то матрица $ A_{infty} $ является верхнетреугольной и на ее главной диагонали стоят собственные числа матрицы $ A $.

П

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

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

Решение.
$$
A_1=Aapprox
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_1approx
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
$$
$$
approxunderbrace{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_2approx
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_{} $.

Предположение

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

Излагаемый ниже метод поиска этого собственного числа называется методом степенны́х итераций¹⁵⁾.

Рассмотрим произвольный ненулевой столбец $ Y_0=left[ y_{1}^{[0]},dots,y_{n}^{[0]} right]^{^{top}} in mathbb C^n $. Cоставим такую же итерационную векторную
последовательность, как и в методе Крылова
$$
Y_1=Acdot Y_0, Y_2=Acdot Y_1, dots, Y_{K}=Acdot Y_{K-1},dots ,
$$
(только теперь, в отличие от метода Крылова, считаем ее неограниченно продолжающейся) и выделим последовательность первых элементов этих векторов:
$$y_{1}^{[1]},y_{1}^{[2]},dots,y_{1}^{[K]},dots $$

Т

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

$$
lim_{Kto +infty}frac{y_{1}^{[K+1]}}{y_{1}^{[K]}}
$$
существует и он равен максимальному по модулю собственному числу матрицы $ A_{} $.

Доказательство. Перенумеруем собственные числа $ lambda_{1},dots,lambda_n $ матрицы $ A_{} $ так, чтобы $ lambda_{1} $ обозначило максимальное по модулю:
$$|lambda_1|= max_{jin {1,dots,n}} |lambda_j| , quad |lambda_1|>|lambda_j| quad npu quad jin {2,dots,n} . $$
Очевидно,
$$
Y_{K}=A^Kcdot Y_0 ;
$$
отсюда следует, что любой элемент столбца $ Y_{K} $ может быть линейно выражен через $ lambda_{1}^K,dots,lambda_n^K $.
В частности, это справедливо и для первого элемента:
$$
y_{1}^{[K]}=C_1lambda_1^K+C_2lambda_2^K+dots+C_nlambda_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 jin {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_nlambda_n{mathfrak X}_n, \
dots & & dots \
Y_K=A^KY_0&=& alpha_1 lambda_1^K{mathfrak X}_1+dots+alpha_nlambda_n^K{mathfrak X}_n
end{matrix}
$$
откуда и следует доказываемое равенство.

Во втором случае — когда имеются кратные собственные числа матрицы $ A_{} $ — придется применять «тяжелую артиллерию» в виде жордановой нормальной формы; см. теорему $ 5 $

☞

ЗДЕСЬ. Для простоты рассуждений, будем в оставшейся части доказательства считать все собственные числа матрицы различными. Имеем тогда
$$
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 jin {2,dots,n} .
$$
Исключительным случаем является ситуация $ C_1=0 $, в этом случае утверждение теоремы может оказаться несправедливым¹⁶⁾.

♦

=>

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

$$
left[1, lim_{Kto +infty}frac{y_{2}^{[K]}}{y_{1}^{[K]}},dots,
lim_{Kto +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 Kin {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 $.

Метод степенных итераций используется в поисковике Google для вычисления PageRank.

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

1.

Нарушение сходимости итерационного процесса за счет неудачного выбора стартового вектора. Если в качестве $ Y_{0} $ оказался случайно взят собственный вектор $ mathfrak X_{ast} $ матрицы $ A_{} $, принадлежащий произвольному ее собственному числу $ lambda_{*} $, то предел последовательности из теоремы будет равен именно этому числу; если при этом $ |lambda_{*} | ne max_{1le 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.9682pm 3.0186 mathbf i} $, и максимальное по модулю собственное число неединственно.

♦

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

Предположение 2

. Пусть два максимальных по модулю собственных числа матрицы разнесены по величине, например
$$ |lambda_1| > | lambda_2 | > | lambda_ j | quad npu j in {2,dots, n } . $$

Обобщение степенного метода основывается на использовании последовательностей из каких-то двух компонент векторов $ Y_{K+1}=AY_K $, например, наряду с уже использованной выше последовательностью первых компонент
$$y_{1}^{[1]},y_{1}^{[2]},dots,y_{1}^{[K]},dots $$
возьмем еще и аналогичную для вторых:
$$y_{2}^{[1]},y_{2}^{[2]},dots,y_{2}^{[K]},dots $$

Т

Теорема 26 [Эйткен]. При практически любом выборе стартового вектора $ Y_0 ne mathbb O $ для последовательности

$$
Y_1=Acdot Y_0, Y_2=Acdot Y_1, dots, Y_{K}=Acdot Y_{K-1},dots ,
$$
имеет место равенство
$$
lambda_1 lambda_2 = lim_{Kto +infty} frac{left|begin{array}{ll} y_1^{[K+1]} & y_1^{[K+2]} \ y_2^{[K+1]} & y_2^{[K+2]} end{array} right|}
{left|begin{array}{ll} y_1^{[K]} & y_1^{[K+1]} \ y_2^{[K]} & y_2^{[K+1]} end{array} right|} , .
$$

Доказательство. Построим квадратное уравнение
$$ p_0x^2+p_1x+p_2 = 0 $$
имеющее корнями $ lambda_1 $ и $ lambda_2 $.
Если существует базис рпостранства $ mathbb C^n $
$$Y_0=alpha_1{mathfrak X}_1+alpha_2{mathfrak X}_2+dots+alpha_n{mathfrak X}_n .$$
Тогда последовательным домножением на матрицу $ A_{} $ получаем :
$$begin{array}{llll}
Y_K=& alpha_1 lambda_1^K{mathfrak X}_1 &+alpha_2 lambda_2^K{mathfrak X}_2+dots &+alpha_nlambda_n^K{mathfrak X}_n, \
Y_{K+1}=& alpha_1 lambda_1^{K+1}{mathfrak X}_1 &+alpha_2 lambda_2^{K+1}{mathfrak X}_2+dots &+alpha_nlambda_n^{K+1}{mathfrak X}_n,\
Y_{K+2}=& alpha_1 lambda_1^{K+2}{mathfrak X}_1 & +alpha_2 lambda_2^{K+2}{mathfrak X}_2+dots &+alpha_nlambda_n^{K+2}{mathfrak X}_n.
end{array}
$$
Отбрасываем из правых частей равенств слагаемые порядков возрастания ниже, чем $ lambda_2^K, lambda_2^{K+1}, lambda_2^{K+2} $ соответственно, домножаем получившиеся приближенные равенства
$$begin{array}{lll|l}
Y_K & approx alpha_1 lambda_1^K{mathfrak X}_1 &+alpha_2 lambda_2^K{mathfrak X}_2, & color{Red} times p_2 \
Y_{K+1}& approx alpha_1 lambda_1^{K+1}{mathfrak X}_1 &+alpha_2 lambda_2^{K+1}{mathfrak X}_2, & color{Red} times p_1\
Y_{K+2} & approx alpha_1 lambda_1^{K+2}{mathfrak X}_1 & +alpha_2 lambda_2^{K+2}{mathfrak X}_2, & color{Red} times p_0
end{array}
$$
и складываем:
$$ p_2 Y_K + p_1Y_{K+1} + p_0 Y_{K+2} approx mathbb O , . $$
В получившемся векторном равенстве выбираем первые две компоненты:
$$
left{
begin{array}{ll}
p_2 y_1^{[K]} + p_1 y_1^{[K+1]} + p_0 y_1^{[K+2]} approx 0 , , \
p_2 y_2^{[K]} + p_1 y_2^{[K+1]} + p_0 y_2^{[K+2]} approx 0 , ,
end{array}
right.
$$
которые и позволят определить приближенное значение набора $ p_0,p_1,p_2 $. С точностью до числового сомножителя, искомый полином можно представить в виде определителя
$$
p_0x^2+p_1x+p_2 approx
left|begin{array}{lll}
y_1^{[K]} & y_1^{[K+1]} & y_1^{[K+2]} \
y_2^{[K]} & y_2^{[K+1]} & y_2^{[K+2]} \
1 & x & x^2
end{array}
right| , .
$$
Формулы Виета завершат доказательство.

♦

=>

При выполнении условия

предположения 2

имеет место равенство

$$ lambda_2 =
lim_{Kto +infty} frac{left|begin{array}{ll} y_1^{[K+1]} & y_1^{[K+2]} \ y_2^{[K+1]} & y_2^{[K+2]} end{array} right| y_{1}^{[K+1]}}
{left|begin{array}{ll} y_1^{[K]} & y_1^{[K+1]} \ y_2^{[K]} & y_2^{[K+1]} end{array} right| y_{1}^{[K+2]} } , .
$$

П

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

$$
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=left( begin{array}{r} 2 \ 7 \ -1 end{array} right),
Y_2=left( begin{array}{r} 26 \ 32 \ -20 end{array} right), dots,
$$
$$
Y_{18}=left( begin{array}{r} {scriptstyle 164983395620948} \ {scriptstyle 156537857759336} \ -{scriptstyle 219402049179956} end{array} right),
Y_{19}=left( begin{array}{r} {scriptstyle 1018982413699860} \ {scriptstyle 966291195084776} \ -{scriptstyle 1355667307859444} end{array} right),
Y_{20}=left( begin{array}{r} {scriptstyle 6292505720513492} \ {scriptstyle 5964748557575016} \ -{scriptstyle 8374234035307188} end{array} right), .
$$
Таким образом,
$$
lambda_1 approx frac{y_1^{[20]}}{y_1^{[19]}}= frac{1573126430128373}{254745603424965} approx mathbf{6.17}_5 ,
$$
$$
lambda_2 approx
frac{left|begin{array}{ll} y_1^{[19]} & y_1^{[20]} \ y_2^{[19]} & y_2^{[20]} end{array} right| y_{1}^{[19]}}
{left|begin{array}{ll} y_1^{[18]} & y_1^{[19]} \ y_2^{[18]} & y_2^{[19]} end{array} right| y_{1}^{[20]} }=
frac{300892177677465751832368453246033765185}{67074186846991590001957412392957971737 }
approx mathbf{4.48}_5
$$

♦

Обобщение этого подхода для поиска следующих по убыванию модулей собственных чисел проводится по аналогии с деления-вычитания вычисления корня полинома. Кстати, теоретически можно довести этот метод и до построения характеристического (точнее, минимального аннулирующего) полинома матрицы: при любом $ K in {0,1,2,dots } $ определитель
$$
left|begin{array}{llll}
y_1^{[K]} & y_1^{[K+1]} & dots & y_1^{[K+n]} \
y_2^{[K]} & y_2^{[K+1]} & dots & y_2^{[K+n]} \
vdots & vdots & & vdots \
y_n^{[K]} & y_n^{[K+1]} & dots & y_n^{[K+n]} \
1 & lambda & dots & lambda^n
end{array}
right|=
det left[begin{array}{c|c|c|c|c}
Y_K&Y_{K+1}&dots&Y_{K+n-1}&Y_{K+n}\
1& lambda&dots&lambda^{n-1}&lambda^n
end{array}
right]
$$
совпадает — с точностью до числового сомножителя — с $ det (A-lambda E) $. И мы вернулись к

☝

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

Для случая симметричной матрицы альтернативное обобщение степенного метода для поиска ранжированных по убыванию модулей собственных чисел и соответствующих им собственных векторов разбирается

☞

ЗДЕСЬ.

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

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

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

[4]. Хорн Р., Джонсон Ч. Матричный анализ. М.Мир.1989