Степенной метод и теорема Перрона для импримитивных матриц

[wormer]

Господа, доброго времени суток!

Вопрос касается теории неотрицательных (положительных) матриц. Теорема Перрона для положительных матриц допускает следующую переформулировку в терминах сходимости.

Утверждение.
Пусть $A$ - положительная матрица порядка $n$. Существует положительный вектор $\vec{z}_0$ такой, что для любого неотрицательного ненулевого вектора $\vec{x}$ последовательность векторов $A^m \vec{x}$ сходится в направлении $\vec{z}_0$, т.е.
\begin{equation} \lim_{m \to \infty} \frac{A^m \vec{x}}{||A^m \vec{x}||} = \frac{\vec{z}_0}{||\vec{z}_0||}. \end{equation}

Вопрос в том, остается ли это утверждение верно для неотрицательных неразложимых матриц, не являющихся примитивными? Будет ли и в этом случае наблюдаться сходимость степенного метода?

Допустим теперь, что матрица $A$ неотрицательна неразложима примитивна спектрального радиуса 1. Означает ли это, что для любого неотрицательного ненулевого вектора $\vec{x}$ будет наблюдаться сходимость по норме к некоторому перронову вектору $\vec{z}_\vec{x}$:
$\lim_{m \to \infty} A^m \vec{x} = \vec{z}_\vec{x}$?

[patzer2097]

wormer в сообщении #888480 писал(а):

Вопрос в том, остается ли это утверждение верно для неотрицательных неразложимых матриц, не являющихся примитивными?

Рассмотрите сначала тривиальный контрпример $A=\left(\begin{smallmatrix} 0&1\\1&0\end{smallmatrix}\right)$ и $x=\binom{0}{1}$. Есть сходимость?
А для примитивных матриц $A$ со сходимостью все обстоит так же, как и для положительных, поскольку в этом случае $A^t$ положительна при любом достаточно большом $t$

[wormer]

patzer2097 в сообщении #888566 писал(а):

wormer в сообщении #888480 писал(а):

Вопрос в том, остается ли это утверждение верно для неотрицательных неразложимых матриц, не являющихся примитивными?

Рассмотрите сначала тривиальный контрпример $A=\left(\begin{smallmatrix} 0&1\\1&0\end{smallmatrix}\right)$ и $x=\binom{0}{1}$. Есть сходимость?

Так это то, что нужно! Допустим, сходимости нет. Мне нужно понять поведение последовательности векторов $\vec{x}_m$, $\vec{x}_m = $A^m \vec{x}_0$ в этом случае (положительный вектор $\vec{x}_0$ выбирается произвольно как начальное приближение). Пусть матрица $A$ неотрицательна неразложима спектрального радиуса единица, имеет индекс импримитивности $h$, $h > 1$. Правильно ли я понимаю, что вектора $\vec{x}_m$ будут приближаться последовательно (и, с ростом $m$, всё ближе) к собственным векторам максимальных по модулю собственных чисел $A$, коими являются корни из единицы? Для них должно быть выполнено что-то вроде $\vec{x}_m = e^{\frac{2 \pi m i}{h}} \vec{z}_0 + \vec{r}_m$, где $\vec{r}_m$ стремится к нулевому вектору, а $\vec{z}_0$ - собственный вектор, отвечающий единице. То есть, для подпоследовательности векторов $\vec{x}_{m_k}$, когда $m_k$ пробегает числа сравнимые по модулю $h$, предел будет иметь место? Или же это не так и процесс будет сходится "ни туда ни сюда", а к какому-то "среднему" вектору, являющемуся комбинацией собственных векторов отвечающих наибольшим по модулю собственным числам? Мне очень важно это осознать.

P.S. Соотнесясь ещё раз с примером, я понял: гоню чушь НО, доля правды в этом имеется... Будет ли наблюдаться подобная периодичность в произвольном случае? Допустим, будут ли всегда существовать $h$ векторов, вокруг которых будут сгущаться вектора последовательности $\vec{x}_m$? Будет ли наблюдаться сходимость (пусть не к собственным векторам), когда степень $m$ пробегает числа сравнимые по модулю $h$? По-моему такое поведение выглядит вполне правдоподобно. Как бы доказать... И еще вот что: мне кажется, что начиная с положительного вектора в этом случае в последовательности $\vec{x}_m$ мы всегда будем получать положительные вектора (без нулевых координат).

[patzer2097]

wormer в сообщении #888641 писал(а):

Правильно ли я понимаю, что вектора $\vec{x}_m$ будут приближаться последовательно (и, с ростом $m$, всё ближе) к собственным векторам максимальных по модулю собственных чисел $A$, коими являются корни из единицы?

неправильно, т.к. $x_m$ вещественны, а указанные собственные векторы комплексны

wormer в сообщении #888641 писал(а):

То есть, для подпоследовательности векторов $\vec{x}_{m_k}$, когда $m_k$ пробегает числа сравнимые по модулю $h$, предел будет иметь место?

Не очень понял, что именно Вы обозначаете через $h$, но это число можно выбрать так, чтобы Ваше утверждение было верно. Например, при $h=n!$ на диагонали матрицы $A^h$ стоят положительные числа, поэтому $A^h$ примитивна, и далее сходимость следует из основной теоремы

[wormer]

patzer2097 в сообщении #888769 писал(а):

wormer в сообщении #888641 писал(а):

Правильно ли я понимаю, что вектора $\vec{x}_m$ будут приближаться последовательно (и, с ростом $m$, всё ближе) к собственным векторам максимальных по модулю собственных чисел $A$, коими являются корни из единицы?

неправильно, т.к. $x_m$ вещественны, а указанные собственные векторы комплексны

Ну уж нет, комплексных собственных векторов нам не надо Спасибо, я вроде это потихоньку осознал.

patzer2097 в сообщении #888769 писал(а):

wormer в сообщении #888641 писал(а):

То есть, для подпоследовательности векторов $\vec{x}_{m_k}$, когда $m_k$ пробегает числа сравнимые по модулю $h$, предел будет иметь место?

Не очень понял, что именно Вы обозначаете через $h$, но это число можно выбрать так, чтобы Ваше утверждение было верно. Например, при $h=n!$ на диагонали матрицы $A^h$ стоят положительные числа, поэтому $A^h$ примитивна, и далее сходимость следует из основной теоремы

Понятно. Я через $h$ обозначил индекс импримитивности матрицы $A$, или число характеристических чисел с максимальным модулем. Матрицу $A$ в этом случае перестановками рядов можно представить в виде:
\begin{equation*} A = \begin{pmatrix} 0 & A_{12} & 0 & \ldots & 0\\ 0 & 0 & A_{23} & \ldots & 0\\ \ldots & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & 0 & \ldots & A_{h-1, h}\\ A_{h 1} & 0 & 0 & \ldots & 0 \end{pmatrix}, \end{equation*}
где матрицы $A_{12}, A_{23}, \dots, A_{h-1, h}, A_{h 1}$ неотрицательны неразложимы и примитивны. Тут можно сказать даже кое-что более интересное. Книга Гантмахера по теории матриц утверждает, что если $A$ импримитивная матрица с индексом импримитивности $h$, то степень $A^h$ вполне разлагается на $h$ примитивных матриц, которые имеют одно и то же максимальное характеристическое число: $A^h = \operatorname{diag} \{ A_1, \dots, A_h \}$. Как Вы говорите, если положить $m_k = k h$, то уже будет сходимость. Мне же почему-то кажется, что сходимость будет и в случае когда $m_k = k h - r$, $1 \leqslant r < h$, то есть, другими словами, из последовательности $\vec{x}_m$ можно выделить ровно $h$ подпоследовательностей сходящихся по разным направлениям. Впрочем, может это и не так, и уж доказать это явно непросто.

Меня теперь интересует более прозаический вопрос относительно последовательности $\vec{x}_m$: помогите пожалуйста показать, что она ограничена и не стремится к нулю, какое бы начальное приближение $\vec{x}_0$, $\vec{x}_0 > 0$ мы ни выбирали. Это не должно быть сложно. Еще раз напомню, что я рассматриваю матрицу $A$ (неотрицательную, импримитивную индекса $h$ и т.д.) спектрального радиуса 1. Для случая $h = 1$ (матрица примитивна), есть доказательство сходимости на английской википедии (Power Iteration), где оно рассматривается в двух вариантах: 1) когда у матрицы есть базис из собственных векторов, и 2) когда его нет. Как бы это доказательство модифицировать для $h > 1$? Меня интересует вариант, когда базиса из собственных векторов у матрицы нет.

[patzer2097]

wormer в сообщении #888813 писал(а):

Матрицу $A$ в этом случае перестановками рядов можно представить в виде:

тут важно, что не любыми перестановками рядов, а даже перестановками вида $D^{-1}AD$, где $D$ - мономиальная матрица (иначе говоря, матрица перестановки)

wormer в сообщении #888813 писал(а):

Как Вы говорите, если положить $m_k = k h$, то уже будет сходимость. Мне же почему-то кажется, что сходимость будет и в случае когда $m_k = k h - r$, $1 \leqslant r < h$, то есть, другими словами, из последовательности $\vec{x}_m$ можно выделить ровно $h$ подпоследовательностей сходящихся по разным направлениям.

конечно, можно. Ведь $A^{kh+r}\,x=A^{kh}\,(A^rx)$

wormer в сообщении #888813 писал(а):

Меня теперь интересует более прозаический вопрос относительно последовательности $\vec{x}_m$: помогите пожалуйста показать, что она ограничена и не стремится к нулю, какое бы начальное приближение $\vec{x}_0$, $\vec{x}_0 > 0$ мы ни выбирали.

ну это же следует из написанного выше, ведь при любом фиксированном $r\in\{0...h\}$ последовательность $A^{kh+r}\,x$ сходится к ненулевому вектору пока $k\rightarrow\infty$

[wormer]

patzer2097 в сообщении #888832 писал(а):

wormer в сообщении #888813 писал(а):

Матрицу $A$ в этом случае перестановками рядов можно представить в виде:

тут важно, что не любыми перестановками рядов, а даже перестановками вида $D^{-1}AD$, где $D$ - мономиальная матрица (иначе говоря, матрица перестановки)

О, да! Спасибо за полезное замечание. Я использую терминологию из той же книги Гантмахера, где под перестановкой рядов понимается соединение перестановки строк матрицы с такой же перестановкой её столбцов.

Вот я дурак! Точно же! Спасибо большое. Все вроде просто и без косяков. Нет, ну надо же!.. И вектора $A^r \vec{x}_0$ положительны, потому что положителен $\vec{x}_0$, а в матрице $A$ нет нулевых строк.