Характеристическое уравнение матрицы собственный вектор матрицы
Характеристическое уравнение матрицы собственный вектор матрицы
Найдем такие вектора (называются собственными векторами) v и такие числа — значения (называются собственными значениями) l матрицы A, для v, l и A выполняется: A*v = l*v.
Также вычисляется кратность собственных значений и находит характеристическое уравнение матрицы.
определяется как характеристический полином матрицы этого оператора в произвольном базисе линейного пространства, в котором этот оператор задан. Подробнее ☞ ЗДЕСЬ.
Теорема 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_<> $ имеет порядок $ m\times n_<> $, а $ B_<> $ — порядок $ n\times m_<> $. Тогда эти матрицы допускают умножение в любом порядке, т.е. определены $ AB_<> $ и $ BA_<> $ и оба произведения будут квадратными матрицами — порядков $ m_<> $ и $ n_<> $ соответственно. Тогда характеристические полиномы этих произведений различаются лишь на степень $ \lambda_<> $:
определяется для квадратной матрицы $ A_<> $ как произвольный корень ее характеристического полинома $ \det (A_<>-\lambda E) $. Набор всех собственных чисел матрицы $ A_<> $ (с учетом их кратностей) называется спектром матрицы (таким образом спектр матрицы $ A_<> $ порядка $ n_<> $ всегда состоит из $ n_<> $ чисел, часть из которых могут быть одинаковыми). Максимальный из модулей собственных чисел матрицы $ A_<> $ называется ее спектральным радиусом, он иногда обозначается $ \rho(A) $.
$$ g(A)=b_<0>A^m+\dots+b_m E \, . $$ Тогда если $ \<\lambda_<1>,\dots,\lambda_ \> $ — спектр матрицы $ A_<> $, то $ \),\dots,g(\lambda_n) \> $ — спектр матрицы $ g(A_<>) $.
Результат теоремы обобщается и на более широкий класс функций $ g_<>(x) $ — фактически на любую функцию, которая, вместе со своими производными, может быть определена на спектре матрицы $ A_<> $. В частности, если $ \det A_<> \ne 0 $, то спектр матрицы $ A^<-1>_<> $ совпадает с $ \<1/\lambda_j\>_^n $.
Имеет место следующее равенство, связывающее степени матрицы $ A_<> $ с суммами Ньютона ее характеристического полинома:
$$ \operatorname(A^k)=\lambda_1^k+\dots+\lambda_n^k \ . $$ Здесь $ \operatorname_<> $ обозначает след матрицы (т.е. сумму ее диагональных элементов). Утверждение остается справедливым и для отрицательных показателей $ k_<> $ при условии, что $ \det A_<> \ne 0 $.
Имеет место следующее равенство:
$$ \det g(A) = (-1)^ <\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) $.
Теорема 12. [1]. Собственные числа матрицы являются непрерывными функциями ее элементов. Иначе: пусть
$$A=\left[a_ \right]_^n \quad , \quad B=\left[b_ \right]_^n \ . $$ Обозначим $$M= \max_> \left\ <|a_|, |b_ | \right\> \quad , \quad \delta = \frac<1>\sum_^n |a_ — b_ | \ . $$ Тогда любому собственному числу $ \lambda_<\ast>^<> $ матрицы $ A_<> $ можно поставить в соответствие такое собственное число $ \mu_<\ast>^<> $ матрицы $ B_<> $, что $$ |\lambda_<\ast>-\mu_ <\ast>| \le (n+2) M \sqrt[n] <\delta>\ . $$
Собственно факт непрерывной зависимости собственных чисел от элементов матрицы следует из представления характеристического полинома из теоремы ☞ ПУНКТА — коэффициенты этого полинома полиномиально (и, следовательно, непрерывно) зависят от элементов матрицы. Далее используем теорему о непрерывной зависимости корней полинома от его коэффициентов.
Выясним теперь на примере, насколько малым может быть возмущение элементов матрицы чтобы сохранились хотя бы количество вещественных корней ее характеристического полинома.
Пример [Уилкинсон] [2]. Найти собственные числа матрицы
Решение. Характеристический полином $$ \det(A-\lambda E) = \prod_^ <20>(j-\lambda) — 20^ <19> <\color\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_<> $; кроме того, у образовавшихся мнимых корней оказываются достаточно большими мнимые части. В данном примере допустимые возмущения для $ <\color\varepsilon > $, т.е. такие, при которых сохранится свойство вещественности всех корней характеристического полинома, находятся в пределах 3) $$ -8.636174\times 10^<-14>\ ♦
Теорема 13 [Гершгорин]. 4) Обозначим $ \mathbb D_ $ круг на комплексной плоскости $ \mathbb C_<> $ с центром в точке $ a_^<> $ и радиуса
$$ r_j=\sum_<\ell=1 \atop \ell\ne j>^n \left|a_\right| \ .$$ Тогда спектр матрицы $ A_<> $ лежит внутри объединения этих кругов: $$ \ <\lambda_1,\dots, \lambda_n \>\subset \bigcup_^n \mathbb D_j \ . $$ Иными словами: любое собственное число матрицы должно удовлетворять хотя бы одному из неравенств $$ |z- a_ | ☞ ЗДЕСЬ.
Согласно этой теореме, главные миноры матрицы $ A-\lambda\, E $ играют роль системы полиномов Штурма для характеристического полинома симметричной матрицы $ A_<> $.
Если все главные миноры $ A_1,A_2,\dots,A_ $ симметричной матрицы $ A_<> $ отличны от нуля, то число положительных собственных чисел матрицы $ A_<> $ равно числу знакопостоянств, а число отрицательных собственных чисел — числу знакоперемен в ряду $ 1,A_1,\dots,A_n $:
$$ \operatorname \< \det (A-\lambda E) =0 \ | \ \lambda>0 \> = <\mathcal P>(1,A_1,\dots,A_n), $$ $$ \operatorname \ < \det (A-\lambda E) =0 \ | \ \lambda ненулевойстолбец $$ X_<\ast>= \left( \beginx_<1>^ <\ast>\\ \vdots \\ x_^ <\ast>\end \right) \in \mathbb^n $$ такой, что $$ AX_<\ast>=\lambda_ <\ast>X_ <\ast>\quad \iff \quad (A -\lambda_<\ast>E) X_ <\ast>= \mathbb O_ \ . $$ По определению собственного числа, $ \det (A^<> -\lambda_<\ast>E) = 0 $ и, следовательно, система однородных уравнений $ (A -\lambda_<\ast>E) X^<> = \mathbb O $ всегда имеет нетривиальное решение; более того, этих решений бесконечно много. Таким образом, одному и тому же собственному числу матрицы принадлежит бесконечное множество собственных векторов. Эту бесконечность можно описать с помощью фундаментальной системы решений (ФСР).
Пример. Найти собственные векторы матрицы
Решение. Спектр матрицы найден выше. $$(A-0 \cdot E)X=\mathbb O \quad \Longrightarrow \ \mbox< ФСР>= \ \left\< <\mathfrak X>_1=\left(\begin4 \\ -2 \\ 1 \\ 0 \end\right), \ <\mathfrak X>_2=\left(\begin7 \\ -3 \\ 0 \\ 1 \end \right) \right\>.$$ Любой вектор вида $ \alpha_ <1><\mathfrak X>_1 + \alpha_2 <\mathfrak X>_2 $ будет собственным, принадлежащим $ \lambda_<>=0 $. $$ \begin(A- \mathbf i\, \sqrt <83>E)X=\mathbb O \\ \\ \Downarrow \\ \\ <\mathfrak X>_3= \left(\begin1- \mathbf i \, \sqrt <83>\\ 8-2\, \mathbf i \, \sqrt <83>\\ 12 \\ 17+\mathbf i \, \sqrt <83>\end\right) \end \qquad \begin(A+\mathbf i \sqrt <83>E)X=\mathbb O \\ \\ \Downarrow \\ \\ <\mathfrak X>_4= \left(\begin1+\mathbf i \, \sqrt <83>\\ 8+2\mathbf i \, \sqrt <83>\\ 12 \\ 17- \mathbf i \,\sqrt <83>\end\right) \end \ . $$ ♦
Еще один способ нахождения собственного вектора основан на теореме Гамильтона-Кэли.
Теорема 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_ . $$ На основании определения любой ненулевой столбец $ f_<\ast>(A)^<> $ должен быть собственным вектором матрицы $ A_<> $. ♦
Если $ \lambda_<\ast>^<> $ является простым корнем характеристического полинома 5) , то ненулевые столбцы $ f_<\ast>(A)^<> $ будут пропорциональными. Или, что то же, $ \operatorname f_<\ast>(A)^<> = 1 $.
Тогда очевидно, что и строки матрицы $ f_<\ast>(A)^<> $ тоже должны быть пропорциональны!
Доказать, что любая ненулевая строка матрицы $ f_<\ast>(A)^<> $ является собственным вектором матрицы $ A^<^<\top>>_<> $, принадлежащим $ \lambda_<\ast>^<> $. Доказать, что собственный вектор матрицы $ A_<> $ ортогонален собственному вектору матрицы $ A^<\top>_<> $, если эти векторы принадлежат различным собственным числам 6) .
На практике вычисление полинома $ f_<\ast>(\lambda)^<> $ может быть осуществлено с помощью схемы Хорнера.
Решение. Характеристический полином $$ f(\lambda)= -\lambda^3+184\,\lambda^2-14751\,\lambda+611404 $$ имеет единственное вещественное собственное число $ \lambda_ <\ast>\approx 96.8817 $. Составляем схему Хорнера $$ \begin& -1 & 184 & -14751 & 611404 \\ \hline 96.8817 & -1 & 87.1183 & -6310.8310 & -0.0352 \end $$ За счет ошибок округления мы получили ненулевое значение для $ 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-1882.1101 & * & * \\ -2723.2902 & * & * \\ -708.6229 & * & * \end \right) \ .$$ Проверяем: $$ \left( \begin23 & 75 & -92 \\ 6 & 74 & 72 \\ 37 & -23 & 87 \end \right) \left( \begin-1882.1101 \\ -2723.2902 \\ -708.6229 \end \right) — 96.8817 \left( \begin-1882.1101 \\ -2723.2902 \\ -708.6229 \end \right)= \left( \begin0.0356 \\ 0 \\ -0.0002 \end \right) \ . $$ ♦
Можно развить последний метод далее: найти универсальную формулу для собственного вектора как функции ее собственного числа. Действительно, найдем частное от деления характеристического полинома $$ f(\lambda) =a_0\lambda^n+a_0\lambda^+\dots+ a_n, \ \quad a_0=(-1)^n $$ на линейный полином $ \lambda- \lambda_ <\ast>$, где $ \lambda_ <\ast>$ — произвольное число из $ \mathbb C $. С помощью той же схемы Хорнера, получаем $$ q(\lambda)=a_0\lambda^+(a_0\lambda_<\ast>+a_1)\lambda^+(a_0\lambda_<\ast>^2+a_1\lambda_<\ast>+a_2)\lambda^+\dots+ (a_0\lambda_<\ast>^+a_1\lambda_<\ast>^+\dots+a_) \, . $$ Если $ \lambda_ <\ast>$ является собственным числом матрицы $ A_<> $, то любой ненулевой столбец матрицы $$ q(A)= a_0A^+(a_0\lambda_<\ast>+a_1)A^+(a_0\lambda_<\ast>^2+a_1\lambda_<\ast>+a_2)A^+\dots+ (a_0\lambda_<\ast>^+a_1\lambda_<\ast>^+\dots+a_)E $$ будет собственным вектором, принадлежащим $ \lambda_ <\ast>$.
Пример. Найти представление всех собственных векторов матрицы
$$ A=\left( \begin9 & 22 & -6 \\ -1 &-4 & 1 \\ 8 & 16 & -5 \end \right) $$ в виде функции ее собственных чисел.
Теорема 16.Пусть $ g(x)=b_0x^m+\dots+b_ \in <\mathbb C>[x] $ – произвольный полином. Если $ X_<\ast>\in \mathbb C^ $ — собственный вектор матрицы $ 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_^<> $ и просуммируем по $ 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_ <+>$ по абсолютной величине (модулю). Соответствующий этому собственному числу собственный вектор может быть выбран положительным:
Число $ \lambda_ <+>$ из теоремы называется собственным числом Перрона или собственным числом Перрона-Фробениуса матрицы $ A_<> $, а соответствующий ему произвольный положительный собственный вектор — собственным вектором Перрона-Фробениуса матрицы $ A_<> $.
Спектральный радиус положительной матрицы $ A_<> $ совпадает с ее собственным числом Перрона-Фробениуса:
Пример. Найти собственное число и вектор Перрона-Фробениуса для матрицы
Решение. Характеристический полином матрицы $ 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( \begin1 \\ 0.365240 \\ 0.184802 \\ 0.634244 \end \right) \quad \mbox < или >\quad \left( \begin2.737922 \\ 1 \\ 0.505974 \\ 1.736510 \end \right) \quad \mbox < или >\left( \begin5.411185 \\ 1.976383 \\ 1 \\ 3.432010 \end \right) \quad \mbox < или >\quad \left( \begin1.576681 \\ 0.575868 \\ 0.291374 \\ 1 \end \right) \quad \mbox < или >\quad \left( \begin0.798133 \\ 0.291510 \\ 0.147496\\ 0.506210 \end \right) \quad \mbox < или >\dots $$ (напоминаю: собственный вектор определяется с точностью до ненулевого сомножителя!). Последний вектор имеет длину равную $ 1_<> $. ♦
1. Собственное число Перрона-Фробениуса всегда простое для характеристического полинома матрицы $ A_<> $. Отсюда следует, что собственный вектор Перрона-Фробениуса определяется единственным образом — с точностью до домножения на положительный скаляр.
2. Любой собственный вектор положительной матрицы $ A_<> $, не соответствующий собственному числу Перрона-Фробениуса, не может состоять исключительно только из положительных элементов. Иными словами, хотя бы одна компонента такого вектора должна быть либо отрицательной либо мнимой.
3. Для собственного числа Перрона-Фробениуса справедливо неравенство $$ \min_> \sum_^n a_ \le \lambda_ <+>\le \max_> \sum_^n a_ \ . $$
4. Собственное число Перрона-Фробениуса матрицы $ A_<> $ совпадает с собственным числом Перрона-Фробениуса матрицы $ A^ <\top>$.
Какие из перечисленных свойств можно распространить на случай неотрицательных матриц ? Каждую такую матрицу можно рассматривать как предел последовательности (строго) положительных матриц. Воспользовавшись теоремой о непрерывной зависимости собственных чисел матрицы от ее элементов, можем сделать вывод, о том, что для неотрицательной матрицы $ A_<> $ всегда найдется вещественное неотрицательное собственное число, которое будет являться максимальным по модулю среди всех собственных чисел матрицы. Другое дело, что в данном случае — в отличие от случая положительных матриц — такое мажорирующее собственное число может оказаться не единственным.
Пример. Спектр неотрицательной матрицы
$$ A=\left( \begin0 & 1 \\ 1 & 0 \end \right) $$ состоит из чисел $ \lambda_1=+1 $ и $ \lambda_1=-1 $ одинакового модуля. ♦
Однако, по-прежнему, хотя бы одно неотрицательное вещественное число $ \lambda_ <+>$ со свойством $ \rho(A) = \lambda_ <+>$ существовать будет; более того, ему будет соответствовать неотрицательный собственный вектор $ \mathfrak X \ge \mathbb O $. Это число (вектор) по-прежнему называются числом (вектором) Перрона-Фробениуса 7) матрицы $ A_<> $.
Частным случаем неотрицательных матриц являются стохастические матрицы, т.е. неотрицательные матрицы, в которых сумма элементов каждой строки равна $ 1_<> $: $$ P=\left[p_\right]_^n, \\ge 0 \>_^n,\ \sum_^n p_ = 1 \ npu \quad j \in \ <1,2,\dots,n\>\ . $$
Теорема 20.Собственное число Перрона-Фробениуса стохастической матрицы равно $ 1_<> $. Этому собственному числу соответствует собственный вектор $ X=[1,1,\dots,1]^ <\top>$.
Доказательство существования собственного числа равного $ 1_<> $ и соответствующего ему собственного вектора $ X=[1,1,\dots,1]^ <\top>$ следует из равенства $$ P \left( \begin1 \\ 1 \\ \vdots \\ 1 \end \right) = \left( \begin1 \\ 1 \\ \vdots \\ 1 \end\right) \ . $$ Далее, из теоремы Гершгорина следует, что любое собственное число $ \lambda_<>\in \mathbb C $ стохастической матрицы должно удовлетворять неравенству $$|\lambda — p_|\le \sum_ |p_|=1-p_ $$ хотя бы при одном $ j_<> $. Воспользовавшись следствием к неравенству треугольника получаем: $$|\lambda| — |p_|\le |\lambda — p_| \le 1-p_ \ \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 (A^k)=\lambda_1^k+\dots+\lambda_n^k=s_k \ , $$ т.е. след $ k_<> $-й степени матрицы $ A_<> $ равен $ k_<> $-й сумме Ньютона ее характеристического полинома $ f(\lambda)=\det (A-\lambda E ) $. Вычисляем последовательные степени матрицы $ A_<> $: $$s_1=\operatorname (A),\ s_2=\operatorname (A^2),\ \dots, s_n=\operatorname (A^n) \ .$$ Неизвестные коэффициенты $ f(\lambda)=(-1)^n(\lambda^n+a_1\lambda^+ \dots+a_n) $ находим по рекурсивным формулам Ньютона: $$ a_1=-s_1, a_2=-(s_2+a_1s_1)/2, $$ $$ a_k=-(s_+a_1s_+a_2s_+\dots+a_s_1)/k \ npu \ k \le n. $$ Очевидно, что не имеет смысла вычислять все элементы матрицы $ A^ $ — достаточно обойтись лишь элементами ее главной диагонали.
Пример [Леверье]. Найти характеристический полином матрицы
После нахождения коэффициентов характеристического полинома можно найти его корни каким-либо 8) методом. Если $ \lambda_<\ast>^<> $ — одно из собственных чисел, то для нахождения соответствующего собственного вектора воспользуемся алгоритмом из ☞ ПУНКТА. Предположив дополнительно, что это собственное число простое 9) , обозначим $$ f_<\ast>(\lambda)= f(\lambda)/(\lambda-\lambda_<\ast>)=(-1)^n(\lambda^ +p_1\lambda^+\dots+p_\lambda+p_) $$ т.е. частное от деления $ f(\lambda_<>) $ на $ \lambda-\lambda_ <\ast>$. Тогда любой ненулевой столбец матрицы $ f_<\ast>(A)^<> $ будет собственным вектором, принадлежащим $ \lambda_<\ast>^<> $. Как правило, собственным вектором можно взять комбинацию
Степени матрицы $ A_<> $ уже нами посчитаны при вычислении коэффициентов характеристического полинома.
Пример. Для приведенного выше примера находим собственные числа:
$$ \det \left[\beginY_0&Y_<1>&\dots&Y_&Y_\\ 1& \lambda&\dots&\lambda^&\lambda^n \end \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^+a_2 \lambda^+\dots+a_n \ , $$ то по теореме Гамильтона-Кэли: $$ (-1)^n A^n+a_1A^+\dots+a_nE=\mathbb O_ \ . $$ Это равенство останется справедливым и после умножения его на произвольный вектор, в том числе на $ Y_ <0>$: $$ (-1)^n A^n\cdot Y_0+a_1A^ \cdot Y_0 +\dots+a_n\cdot Y_0=\mathbb O_ \iff $$ $$ \iff \quad (-1)^n Y_n+a_1Y_ +\dots+a_nY_0=\mathbb O \ . $$ Последнее равенство представляет линейную систему относительно неизвестных коэффициентов характеристического полинома. Можно решать ее по формулам Крамера, но мы пойдем другим путем. Дополним эту систему тождеством $ f(\lambda)=(-1)^n \lambda^n+a_1 \lambda^+a_2 \lambda^+\dots+a_n $. Рассмотрим получившуюся систему как линейную однородную относительно столбца $ \left[ a_n,a_,\dots,a_1,1\right]^ <\top>$. Поскольку эта система имеет нетривиальное решение, то ее определитель должен равняться нулю: $$ 0=\det \left[\beginY_0&Y_<1>&\dots&Y_&(-1)^nY_\\ 1& \lambda&\dots&\lambda^&(-1)^n\lambda^n-f(\lambda) \end \right]= $$ (представляем последний столбец в виде суммы двух столбцов и используем свойство 5 определителя) $$ =\det \left[\beginY_0&Y_<1>&\dots&Y_&(-1)^nY_\\ 1& \lambda&\dots&\lambda^&(-1)^n\lambda^n \end \right]-f(\lambda) \det \left[\beginY_0&Y_<1>&\dots&Y_ \end \right] \ . $$ Таким образом, $$ f(\lambda)=(-1)^n \frac<\det \left[\beginY_0&Y_<1>&\dots&Y_&Y_\\ 1& \lambda&\dots&\lambda^&\lambda^n \end \right]><\det \left[\beginY_0&Y_<1>&\dots&Y_ \end \right]> \ , $$ если только знаменатель в этой дроби не обратится в нуль. ♦
Пример. Найти характеристический полином матрицы примера Леверье
После нахождения характеристического полинома можно найти его корни каким-либо 10) методом. Пусть $ \lambda_<\ast>^<> $ — одно из собственных чисел, и оно — простое; тогда для нахождения соответствующего собственного вектора можно воспользоваться тем же приемом, что был задействован в предыдущем ПУНКТЕ. Вычислим 11) частное от деления $ f(\lambda_<>) $ на $ \lambda-\lambda_ <\ast>$ $$ f_<\ast>(\lambda)= f(\lambda)/(\lambda-\lambda_<\ast>)=(-1)^n(\lambda^ +p_1\lambda^+\dots+p_\lambda+p_) \ . $$ Тогда любой ненулевой столбец матрицы $ f_<\ast>(A)^<> $ будет собственным вектором, принадлежащим $ \lambda_<\ast>^<> $. Но тогда и произвольная комбинация столбцов этой матрицы тоже будет собственным вектором (если только не обратится в нулевой вектор). В частности, это относится и к комбинации, записываемой в матричном виде $$ (-1)^n f_<\ast>(A) Y_0 = A^Y_0 +p_1A^Y_0+\dots+p_Y_0=Y_+p_1Y_+\dots+p_Y_0 \ . $$ А комбинируемые векторы уже посчитаны.
Теперь обсудим исключительные случаи. При неудачном выборе $ Y_ <0>$ определитель $$ \det \left[\beginY_0&Y_<1>&\dots&Y_ \end \right] $$ может обратиться в нуль. Эта неприятность обязательно произойдет если, например, наш выбор пал на вектор $ Y_0 $, совпадающий с собственным вектором матрицы $ A_<> $. Вероятность такого события — нулевая. В общем же случае, трудно ожидать, чтобы $ n_<> $ почти произвольных столбцов $ Y_0,Y_<1>,\dots,Y_ $ оказались линейно зависимыми — если только сама матрица $ A_<> $ не обладает «скрытым дефектом» — типа рассмотренного в следующем примере.
Пример. Найти характеристический полином матрицы
Решение. При любом выборе $ Y_0 $ векторы $ \ $ оказываются линейно зависимыми: $$ Y_0= \left(\begin1\\ 0\\ 0 \end \right), Y_1= \left(\begin2\\ 1\\ 1 \end \right), Y_2= \left(\begin6\\ 5\\ 5 \end \right),\dots ; Y_0= \left(\begin1\\ 1\\ 1 \end \right),\ Y_1= \left(\begin4\\ 4\\ 4 \end \right),\dots $$ Объяснение этого феномена состоит в том, что для матрицы $ A_<> $ ее аннулирующий полином имеет степень меньшую ее порядка: $$ A^2-5\ A+4 E = \mathbb O \ . $$ Домножение этого равенства на произвольный столбец $ Y_0 $ и доказывает линейную зависимость системы $ \ $. ♦
Такая ситуация возможна только в случае, когда характеристический полином матрицы $ A_<> $ имеет кратные корни (в рассмотренном выше примере $ \lambda_<>=1 $ являлся двойным корнем $ \det (A-\lambda_<> E) $); она исключительно редко встречается на практике.
Поиск всех собственных чисел
Существуют методы нахождения спектра матрицы, не требующие предварительного построения характеристического полинома.
QR-алгоритм
Этот алгоритм основан на 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 $. Утверждается, что бесконечная последовательность матриц $$ \Q_\>_^ <\infty>$$ как правило, сходится к матрице $ A_ <\infty>$, которая будет верхнетреугольной.
Теорема 24 [4].Если все собственные числа матрицы $ A $ различны по модулю, то матрица $ A_ <\infty>$ является верхнетреугольной и на ее главной диагонали стоят собственные числа матрицы $ A $.
Пример. Найти все собственные числа матрицы $$ A=\left(\begin2 & 3 &-1\\ 7 & 3 & 3 \\ -1 & -2 & 4 \end \right) \, . $$
К сожалению условие теоремы достаточно ограничительно: собственные числа вещественной матрицы $ A $ могут оказаться и мнимыми, но тогда они одинаковы по модулю.
Как это обстоятельство сказывается на структуре матрицы $ A_ <\infty>$ и дальнейшее развитие метода ☞ ЗДЕСЬ
Частичная проблема собственных чисел
Задача. Найти максимальное по модулю собственное число матрицы $ A_<> $.
Предположение . Будем считать сначала, что максимальное по модулю собственное число матрицы единственно.
Излагаемый ниже метод поиска этого собственного числа называется методом степенны́х итераций 12) .
Рассмотрим произвольный ненулевой столбец $ Y_0=\left[ y_<1>^<[0]>,\dots,y_^ <[0]>\right]^<^<\top>> \in \mathbb C^n $. Cоставим такую же итерационную векторную последовательность, как и в методе Крылова $$ Y_1=A\cdot Y_0,\ Y_2=A\cdot Y_1, \dots,\ Y_=A\cdot Y_,\dots , $$ (только теперь, в отличие от метода Крылова, считаем ее неограниченно продолжающейся) и выделим последовательность первых элементов этих векторов: $$y_<1>^<[1]>,y_<1>^<[2]>,\dots,y_<1>^<[K]>,\dots $$
Теорема 25.Как правило, предел
$$ \lim_\frac^<[K+1]>>^<[K]>> $$ существует и он равен максимальному по модулю собственному числу матрицы $ A_<> $.
Доказательство. Перенумеруем собственные числа $ \lambda_<1>,\dots,\lambda_n $ матрицы $ A_<> $ так, чтобы $ \lambda_ <1>$ обозначило максимальное по модулю: $$|\lambda_1|= \max_> |\lambda_j| \ , \quad |\lambda_1|>|\lambda_j| \quad npu \quad j\in \ <2,\dots,n\>\ . $$ Очевидно, $$ Y_=A^K\cdot Y_0 \ ; $$ отсюда следует, что любой элемент столбца $ Y_ $ может быть линейно выражен через $ \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 \ . $$ В этом представлении $ \_^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 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 $$ откуда и следует доказываемое равенство.
Во втором случае — когда имеются кратные собственные числа матрицы $ A_<> $ — придется применять «тяжелую артиллерию» в виде жордановой нормальной формы; см. теорему $ 5 $ ☞ ЗДЕСЬ. Для простоты рассуждений, будем в оставшейся части доказательства считать все собственные числа матрицы различными. Имеем тогда $$ \lim_ \frac^<[K+1]>>^<[K]>>= \lim_ \frac <\lambda_1^\left[C_1+ C_2(\lambda_2/\lambda_1)^+\dots+ C_n(\lambda_n/\lambda_1)^ \right]> <\lambda_1^\left[C_1+C_2(\lambda_2/\lambda_1)^+\dots+ C_n(\lambda_n/\lambda_1)^ \right]> =\lambda_1 $$ поскольку $$ \lim_ \left| \frac<\lambda_j> <\lambda_1>\right|^K = 0 \quad npu \quad j\in \ <2,\dots,n\>\ . $$ Исключительным случаем является ситуация $ C_1=0 $, в этом случае утверждение теоремы может оказаться несправедливым 13) . ♦
Как правило, вектор
$$ \left[1, \lim_\frac^<[K]>>^<[K]>>,\dots, \lim_\frac^<[K]>>^<[K]>>\right]^<^<\top>> $$ будет собственным, принадлежащим максимальному по модулю собственному числу матрицы $ A_<> $.
Пример. Для матрицы
$$ A=\left(\begin2 & 3 &-1\\ 7 & 3 & 3 \\ -1 & -2 & -4 \end \right) $$ найти максимальное по модулю собственное число и принадлежащий ему собственный вектор.
1. Нарушение сходимости итерационного процесса за счет неудачного выбора стартового вектора. Если в качестве $ Y_ <0>$ оказался случайно взят собственный вектор $ \mathfrak X_ <\ast>$ матрицы $ A_<> $, принадлежащий произвольному ее собственному числу $ \lambda_ <*>$, то предел последовательности из теоремы будет равен именно этому числу; если при этом $ |\lambda_ <*>| \ne \max_ <1\le j \le n>| \lambda_j | $, то мы выйдем за пределы смысла выражения «как правило». Понятно, что вероятность настолько плохого выбора нулевая, но и выбор $ Y_0 $ вблизи $ \mathfrak X_ <\ast>$ также может существенно замедлить скорость сходимости. Поэтому если возникает ситуация медленной «стабилизации» значащих цифр в десятичном приближении собственного числа, попробуйте сменить начальный вектор.
2. Нарушение условия предположения , выдвинутого в начале пункта: максимальное по модулю собственное число неединственно.
Пример. Найти максимальное по модулю собственное число матрицы примера Леверье
Решение. Для столбца $ Y_0=[1,0,0,0]^<^<\top>> $ имеем $$y_<1>^<[100]>/y_<1>^<[99]>=-17.8_ <\displaystyle 3113>\ ,$$ т.е. на $ 100 $-й итерации получаем лишь $ 3_<> $ истинные десятичные цифры в представлении собственного числа. При этом компонентами векторов $ Y_ $ являются числа порядка $ 10^ <123>$. Если мы посмотрим на ответ примера Леверье, то увидим, что имеются два собственных числа матрицы, близких по модулю. ♦
К сожалению, вероятность того факта, что у случайно выбранной матрицы два ее собственных числа будут иметь одинаковый модуль становится ненулевой если эта матрица выбирается из множества вещественных матриц. Дело в том, что в этом случае ее характеристический полином будет иметь вещественные коэффициенты, а мнимые корни такого полинома всегда пáрные — для любого невещественного корня $ \lambda_<\ast>^<> $ полинома, комплексно сопряженное к нему число $ \overline<\lambda_<\ast>> $ также будет корнем. При этом $ |\lambda_<\ast>|= |\overline<\lambda_<\ast>> | $.
Пример. Для матрицы
Предположение 2 . Пусть два максимальных по модулю собственных числа матрицы разнесены по величине, например $$ |\lambda_1| > | \lambda_2 | > | \lambda_ j | \quad npu \ j \in \ <2,\dots, n \>. $$
Обобщение степенного метода основывается на использовании последовательностей из каких-то двух компонент векторов $ Y_=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 $ для последовательности