Спектральный радиус

Спектральный радиус — понятие в математике, определяемое для квадратной матрицы как максимум абсолютных значений её собственных значений. В более общем случае, спектральный радиус линейного ограниченного оператора — это точная верхняя граница абсолютных значений элементов его спектра. Спектральный радиус часто обозначается Шаблон:Math.

Определение

Матрицы

Пусть Шаблон:Math являются собственными значениями матрицы Шаблон:Math. Спектральный радиус Шаблон:Math определяется как

$\rho (A)=\max \{|{\lambda }_1|,\dots ,|{\lambda }_n|\}.$

Спектральный радиус можно представить как точную нижнюю границу всех норм матрицы. Действительно, с одной стороны, $\rho (A)⩽\Vert A\Vert$ для каждой естественной нормы матрицы $\Vert \cdot \Vert$; а с другой стороны, формула Гельфанда утверждает, что $\rho (A)=\underset{k\to \mathrm{\infty }}{\lim }\Vert A^k{\Vert }^{1/k}$. Оба этих результата показаны ниже.

Однако спектральный радиус не обязательно удовлетворяет $\Vert A𝐯\Vert ⩽\rho (A)\Vert 𝐯\Vert$ для произвольных векторов $𝐯\in {ℂ}^n$. Чтобы понять, почему, пусть $r>1$ будет произвольным, тогда рассмотрим матрицу

$C_r=\left(\begin{array}{cc}0& r^{-1}\\ r& 0\end{array}\right)$.

Характеристический многочлен матрицы $C_r$ — это ${\lambda }^2-1$, поэтому его собственные значения равны $\{-1,1\}$ и, следовательно, $\rho (C_r)=1$. Однако, $C_r{𝐞}_1=r{𝐞}_2$. В результате,

$\Vert C_r{𝐞}_1\Vert =r>1=\rho (C_r)\Vert {𝐞}_1\Vert .$

В качестве иллюстрации формулы Гельфанда заметим, что $\Vert C_r^k{\Vert }^{1/k}\to 1$ при $k\to \mathrm{\infty }$, поскольку $C_r^k=I$, если $k$ — чётное, и $C_r^k=C_r$, если $k$ — нечётное.

Особым случаем, когда $\Vert A𝐯\Vert ⩽\rho (A)\Vert 𝐯\Vert$ для всех $𝐯\in {ℂ}^n$, является ситуация, при которой $A$ — эрмитова матрица и $\Vert \cdot \Vert$ — евклидова норма. Это связано с тем, что любая эрмитова матрица является диагонализируемой унитарной матрицей, а унитарные матрицы сохраняют длину вектора. В результате,

$\Vert A𝐯\Vert =\Vert U^{*}DU𝐯\Vert =\Vert DU𝐯\Vert ⩽\rho (A)\Vert U𝐯\Vert =\rho (A)\Vert 𝐯\Vert .$

Ограниченные линейные операторы

В контексте ограниченного линейного оператора Шаблон:Mvar на банаховом пространстве собственные значения нужно заменить элементами спектра оператора, то есть значениями $\lambda$, для которых $A-\lambda I$ не является биективным. Обозначим спектр через

$\sigma (A)=\{\lambda \in ℂ:A-\lambda I\text{не биективный}\}$.

Спектральный радиус определяется как точная верхняя грань величин элементов спектра:

$\rho (A)=\underset{\lambda \in \sigma (A)}{\sup }|\lambda |.$

Формула Гельфанда, также известная как формула спектрального радиуса, справедлива и для ограниченных линейных операторов: пусть $\Vert \cdot \Vert$ обозначает норму оператора, тогда имеем

$\rho (A)=\underset{k\to \mathrm{\infty }}{\lim }\Vert A^k{\Vert }^{\frac{1}{k}}=\underset{k\in {\mathbb{N}}^{*}}{\inf }\Vert A^k{\Vert }^{\frac{1}{k}}.$

Ограниченный оператор (на комплексном гильбертовом пространстве) называется спектралоидным оператором, если его спектральный радиус совпадает с Шаблон:Iw. Примером такого оператора является нормальный оператор.

Графы

Спектральный радиус конечного графа определяется как спектральный радиус его матрицы смежности.

Это определение распространяется на случай бесконечных графов с ограниченными степенями вершин (то есть существует некоторое вещественное число Шаблон:Mvar такое, что степень каждой вершины графа меньше Шаблон:Mvar). В этом случае, для графа Шаблон:Mvar определяем:

${\ell }^2(G)=\{f:V(G)\to 𝐑:\sum _{v\in V(G)}\Vert f(v{)}^2\Vert <\mathrm{\infty }\}.$

Пусть Шаблон:Mvar — оператор смежности Шаблон:Mvar:

$\{\begin{array}{c}\gamma :{\ell }^2(G)\to {\ell }^2(G)\\ (\gamma f)(v)=\sum _{(u,v)\in E(G)}f(u)\end{array}$

Спектральный радиус Шаблон:Mvar определяется как спектральный радиус ограниченного линейного оператора Шаблон:Mvar.

Верхние границы

Верхние границы спектрального радиуса матрицы

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

Утверждение. Пусть Шаблон:Math со спектральным радиусом Шаблон:Math и согласованной нормой матрицы Шаблон:Math. Тогда, для каждого целого $k⩾1$:

$\rho (A)\le \Vert A^k{\Vert }^{\frac{1}{k}}.$

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

Пусть Шаблон:Math — пара собственного вектора и собственного значения для матрицы A. В силу субмультипликативности нормы матрицы получаем:

$|\lambda {|}^k\Vert 𝐯\Vert =\Vert {\lambda }^k𝐯\Vert =\Vert A^k𝐯\Vert \le \Vert A^k\Vert \cdot \Vert 𝐯\Vert .$

Поскольку Шаблон:Math, мы получаем

$|\lambda {|}^k\le \Vert A^k\Vert$

и поэтому

$\rho (A)\le \Vert A^k{\Vert }^{\frac{1}{k}},$

что и требовалось доказать.

Верхние границы для спектрального радиуса графа

Существует множество верхних границ для спектрального радиуса графа в терминах его количества n вершин и количества m рёбер. Например, если

$\frac{(k-2)(k-3)}{2}\le m-n\le \frac{k(k-3)}{2}$

где $3\le k\le n$ является целым, тогда

$\rho (G)\le \sqrt{2m-n-k+\frac{5}{2}+\sqrt{2m-2n+\frac{9}{4}}}$

Последовательность степеней

Спектральный радиус тесно связан с поведением сходимости последовательности степеней матрицы, как показано в следующей теореме.

Теорема. Пусть Шаблон:Math со спектральным радиусом Шаблон:Math. Тогда Шаблон:Math тогда и только тогда, когда

$\underset{k\to \mathrm{\infty }}{\lim }{A}^k=0.$

С другой стороны, если Шаблон:Math, то $\underset{k\to \mathrm{\infty }}{\lim }\Vert A^k\Vert =\mathrm{\infty }$. Это утверждение верно для любой выбранной нормы матрицы в Шаблон:Math.

Доказательство Допустим, что $A^k$ стремится к нулю, когда $k$ стремится к бесконечности. Мы покажем, что Шаблон:Math. Пусть Шаблон:Math — пара собственного вектора и собственного значения для A. Так как Шаблон:Math, у нас есть следующее:

$\begin{array}{cc}0& =\left(\underset{k\to \mathrm{\infty }}{\lim }{A}^k\right)𝐯\\ & =\underset{k\to \mathrm{\infty }}{\lim }\left(A^k𝐯\right)\\ & =\underset{k\to \mathrm{\infty }}{\lim }{\lambda }^k𝐯\\ & =𝐯\underset{k\to \mathrm{\infty }}{\lim }{\lambda }^k.\end{array}$

Поскольку Шаблон:Math по предположению, то должно выполняться следующее утверждение:

$\underset{k\to \mathrm{\infty }}{\lim }{\lambda }^k=0,$

из чего следует, что |λ| < 1. Поскольку это должно быть верным для любого собственного значения λ, мы можем сделать вывод, что Шаблон:Math.

Теперь предположим, что радиус Шаблон:Mvar меньше Шаблон:Math. Из теоремы о жордановой нормальной форме известно, что для всех Шаблон:Math, существуют Шаблон:Math, где Шаблон:Mvar — невырожденная и Шаблон:Mvar — блочная диагональная, такие что:

$A=VJ{V}^{-1}$

с

$J=\left[\begin{array}{ccccc}{J}_{m_1}({\lambda }_1)& 0& 0& \cdots & 0\\ 0& J_{m_2}({\lambda }_2)& 0& \cdots & 0\\ ⋮& \cdots & \ddots & \cdots & ⋮\\ 0& \cdots & 0& J_{m_{s-1}}({\lambda }_{s-1})& 0\\ 0& \cdots & \cdots & 0& J_{m_s}({\lambda }_s)\end{array}\right]$

где

$J_{m_i}({\lambda }_i)=\left[\begin{array}{ccccc}{\lambda }_i& 1& 0& \cdots & 0\\ 0& {\lambda }_i& 1& \cdots & 0\\ ⋮& ⋮& \ddots & \ddots & ⋮\\ 0& 0& \cdots & {\lambda }_i& 1\\ 0& 0& \cdots & 0& {\lambda }_i\end{array}\right]\in {𝐂}^{m_i\times m_i},1\le i\le s.$

Легко заметить, что

$A^k=V{J}^k{V}^{-1}$

и, поскольку Шаблон:Mvar — блочно-диагональная,

$J^k=\left[\begin{array}{ccccc}{J}_{m_1}^k({\lambda }_1)& 0& 0& \cdots & 0\\ 0& J_{m_2}^k({\lambda }_2)& 0& \cdots & 0\\ ⋮& \cdots & \ddots & \cdots & ⋮\\ 0& \cdots & 0& J_{m_{s-1}}^k({\lambda }_{s-1})& 0\\ 0& \cdots & \cdots & 0& J_{m_s}^k({\lambda }_s)\end{array}\right].$

Теперь стандартный результат Шаблон:Mvar-ой степени блока Жордана размера $m_i\times m_i$ утверждает, что для $k\ge m_i-1$:

$J_{m_i}^k({\lambda }_i)=\left[\begin{array}{ccccc}{\lambda }_i^k& (\genfrac{}{}{0ex}{}{k}{1}){\lambda }_i^{k-1}& (\genfrac{}{}{0ex}{}{k}{2}){\lambda }_i^{k-2}& \cdots & (\genfrac{}{}{0ex}{}{k}{m_i-1}){\lambda }_i^{k-m_i+1}\\ 0& {\lambda }_i^k& (\genfrac{}{}{0ex}{}{k}{1}){\lambda }_i^{k-1}& \cdots & (\genfrac{}{}{0ex}{}{k}{m_i-2}){\lambda }_i^{k-m_i+2}\\ ⋮& ⋮& \ddots & \ddots & ⋮\\ 0& 0& \cdots & {\lambda }_i^k& (\genfrac{}{}{0ex}{}{k}{1}){\lambda }_i^{k-1}\\ 0& 0& \cdots & 0& {\lambda }_i^k\end{array}\right]$

Таким образом, если $\rho (A)<1$, то для всех Шаблон:Mvar верно $|{\lambda }_i|<1$. Следовательно, для всех Шаблон:Mvar у нас есть:

$\underset{k\to \mathrm{\infty }}{\lim }{J}_{m_i}^k=0$,

из чего следует

$\underset{k\to \mathrm{\infty }}{\lim }{J}^k=0.$

Следовательно,

$\underset{k\to \mathrm{\infty }}{\lim }{A}^k=\underset{k\to \mathrm{\infty }}{\lim }V{J}^k{V}^{-1}=V\left(\underset{k\to \mathrm{\infty }}{\lim }{J}^k\right)V^{-1}=0.$

С другой стороны, если $\rho (A)>1$, то по крайней мере один элемент в Шаблон:Mvar не остается ограниченным при увеличении Шаблон:Mvar, что доказывает вторую часть утверждения.

Формула Гельфанда

Формула Гельфанда, названная в честь Израиля Гельфанда, предоставляет спектральный радиус как предел матричных норм.

Теорема

Для любой матричной нормы Шаблон:Math у нас есть

$\rho (A)=\underset{k\to \mathrm{\infty }}{\lim }{\Vert A^k\Vert }^{\frac{1}{k}}$.

Более того, в случае согласованной матричной нормы $\underset{k\to \mathrm{\infty }}{\lim }{\Vert A^k\Vert }^{\frac{1}{k}}$ приближается к $\rho (A)$ сверху (действительно, в этом случае $\rho (A)\le {\Vert A^k\Vert }^{\frac{1}{k}}$ для всех $k$).

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

Для любого Шаблон:Math, определим две следующие матрицы:

$A_{\pm }=\frac{1}{\rho (A)\pm \epsilon }A.$

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

$\rho \left(A_{\pm }\right)=\frac{\rho (A)}{\rho (A)\pm \epsilon },\rho (A_{+})<1<\rho (A_{-}).$

Начнем с применения предыдущей теормы о пределах последовательностей степеней к Шаблон:Math:

$\underset{k\to \mathrm{\infty }}{\lim }{A}_{+}^k=0.$

Это показывает существование Шаблон:Math такого, что для всех Шаблон:Math,

$\Vert A_{+}^k\Vert <1.$

Поэтому,

${\Vert A^k\Vert }^{\frac{1}{k}}<\rho (A)+\epsilon .$

Аналогично, теорема о последовательностях степеней подразумевает, что $\Vert A_{-}^k\Vert$ не ограничена и существует Шаблон:Math такое, что для всех k ≥ N₋,

$\Vert A_{-}^k\Vert >1.$

Следовательно,

${\Vert A^k\Vert }^{\frac{1}{k}}>\rho (A)-\epsilon .$

Пусть Шаблон:Math}. Тогда,

$\mathrm{\forall }\epsilon >0\mathrm{\exists }N\in 𝐍\mathrm{\forall }k\ge N\rho (A)-\epsilon <{\Vert A^k\Vert }^{\frac{1}{k}}<\rho (A)+\epsilon ,$

то есть,

$\underset{k\to \mathrm{\infty }}{\lim }{\Vert A^k\Vert }^{\frac{1}{k}}=\rho (A),$

что и требовалось доказать.

Следствие

Формула Гельфанда даёт оценку спектрального радиуса произведения коммутирующих матриц: если $A_1,\dots ,A_n$ — матрицы, все коммутирующие между собой, то

$\rho (A_1\cdots A_n)\le \rho (A_1)\cdots \rho (A_n).$

Числовой пример

Рассмотрим матрицу

$A=\left[\begin{array}{ccc}9& -1& 2\\ -2& 8& 4\\ 1& 1& 8\end{array}\right],$

собственные значения которой равны Шаблон:Math; по определению, Шаблон:Math. В следующей таблице приведены значения $\Vert A^k{\Vert }^{\frac{1}{k}}$ для четырёх наиболее используемых норм в сравнении с несколькими возрастающими значениями k (обратите внимание, что из-за особой формы этой матрицы, $\Vert .{\Vert }_1=\Vert .{\Vert }_{\mathrm{\infty }}$):

k	$\Vert \cdot {\Vert }_1=\Vert \cdot {\Vert }_{\mathrm{\infty }}$	$\Vert \cdot {\Vert }_F$	$\Vert \cdot {\Vert }_2$
1	14	15.362291496	10.681145748
2	12.649110641	12.328294348	10.595665162
3	11.934831919	11.532450664	10.500980846
4	11.501633169	11.151002986	10.418165779
5	11.216043151	10.921242235	10.351918183
$⋮$	$⋮$	$⋮$	$⋮$
10	10.604944422	10.455910430	10.183690042
11	10.548677680	10.413702213	10.166990229
12	10.501921835	10.378620930	10.153031596
$⋮$	$⋮$	$⋮$	$⋮$
20	10.298254399	10.225504447	10.091577411
30	10.197860892	10.149776921	10.060958900
40	10.148031640	10.112123681	10.045684426
50	10.118251035	10.089598820	10.036530875
$⋮$	$⋮$	$⋮$	$⋮$
100	10.058951752	10.044699508	10.018248786
200	10.029432562	10.022324834	10.009120234
300	10.019612095	10.014877690	10.006079232
400	10.014705469	10.011156194	10.004559078
$⋮$	$⋮$	$⋮$	$⋮$
1000	10.005879594	10.004460985	10.001823382
2000	10.002939365	10.002230244	10.000911649
3000	10.001959481	10.001486774	10.000607757
$⋮$	$⋮$	$⋮$	$⋮$
10000	10.000587804	10.000446009	10.000182323
20000	10.000293898	10.000223002	10.000091161
30000	10.000195931	10.000148667	10.000060774
$⋮$	$⋮$	$⋮$	$⋮$
100000	10.000058779	10.000044600	10.000018232

Литература

• Шаблон:Citation
• Шаблон:Citation