Главное собственное значение огромной матрицы

[ewert]

Евгений Машеров в сообщении #366510 писал(а):

С того, что одинаковым с.з. будут соответствовать разные с.в.,

это означает лишь, что все собственные векторы не в момент найдёшь (хоть и это не шибко проблемно). Но числа-то -- какие проблемы.

[Zealint]

ewert имел в виду, что $\lambda=\pm1$, то есть отрицательное получается. Но мне это не важно, лишь бы вещественное.

Цитата:

В общем, либо степенной метод (который рано или поздно результат Вам даст) - либо ничего.
Ну, или ищите аналитическое решение.

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

[ewert]

Евгений Машеров в сообщении #366510 писал(а):

1. С того, что одинаковым с.з. будут соответствовать разные с.в., и в натянутом на них пространстве очередные итерации будут "гулять".

Ничего не будет гулять. Если кратности совпадают. Тогда собственное подпространство совпадает с корневым. И та составляющая начальной итерации, которая попала в это приводящее подпространство -- так и будет воспроизводиться на всех следующих итерациях, составляющие же изо всех остальных (приводящих) корневых подпространств -- будут по мере итераций вымерзать.

[Евгений Машеров]

В реальности, увы, гуляют. Есть такой неприятный эффект от возмущения из-за ошибок округления. Если у Вас абсолютно точная арифметика - то, разумеется, вопрос принципиален, алгебраическая или геометрическая кратность. А в конечной точности - существеннее разница между последовательными с.з.

А с тем, что максимальное с.з. в Вашем примере будет положительно, Вы согласны?

[ewert]

Евгений Машеров в сообщении #366541 писал(а):

А с тем, что максимальное с.з. в Вашем примере будет положительно, Вы согласны?

нет, конечно.

Евгений Машеров в сообщении #366541 писал(а):

Есть такой неприятный эффект от возмущения из-за ошибок округления.

Возможно. Ну тут уж, знаете ли, кто кого переборет. Слон кита -- или кит слона. Погрешности округления -- или перепад модулей двух крайних с.ч.

Что же до случая, когда тот жорданов ящик нетривиален -- то тут без вариантов. Не будет сходиться тот алгоритм, хоть ты тресни. Ну т.е. формально-то будет, но -- за совершенно неразумное время.

[Евгений Машеров]

Пардон... Два собственных значения. Одно равно 1, второе -1.
И Вы полагаете, что максимальное из них не положительно?

-- Вт окт 26, 2010 22:18:03 --

Pavia
И, кстати, посмотрел я, что там у Фукунаги. Извините, там не об этом.
Там о том, что надо рассчитать с.з. и с.в. некоторой матрицы неполного ранга, полученной умножением некоей прямоугольной матрицы на себя же транспонированную. И что вместо этого можно переставить сомножители, и получить матрицу меньшего размера (порядок которой равен меньшей, а не больше размерности прямоугольной), с.з. которой совпадают с ненулевыми с.з. интересующей матрицы, а с.в. получаются простым образом.

[ewert]

Евгений Машеров в сообщении #366552 писал(а):

Пардон... Два собственных значения. Одно равно 1, второе -1.И Вы полагаете, что максимальное из них не положительно?

Конечно. В смысле -- не обязательно. Ровно из-за чего тот тупой алгоритм и проваливается, не более и не менее.

[vajsaforutube]

Здравствуйте, а можно влезть с несколько похожим вопросом. У меня тоже есть большая матрица, притом она band matrix (не знаю, как принято это переводить), то есть состоит из нескольких диагоналей (в простейшем случае, трехдиагональная, но может быть и больше), притом в каждой строке стоит одно и то же. Например:

0.3 0.5 0 0
0.2 0.3 0.5 0
0 0.2 0.3 0.5
0 0 0.2 0.3

или

0.3 0.5 0 0 0
0.2 0.3 0.5 0 0
0 0.2 0.3 0.5 0
0 0 0.2 0.3 0.5
0 0 0 0.2 0.3

Все элементы матрицы - вероятности переходов. (задача, которую мы решаем - что-то наподобие блуждания по прямой). Требуется найти главное собственное значение и главный собственный вектор, а точнее, аналитически проследить, как они меняются при увеличении размерности матрицы, как на примерах. В случае, когда диагоналей не три, а больше имеют место еще всякие эффекты, когда у первых и последних строк матрицы суммируются элементы, которые бы выехали иначе за край.

[ewert]

vajsaforutube в сообщении #366730 писал(а):

притом она band matrix (не знаю, как принято это переводить),

Буквально так и переводится -- "ленточная матрица".

[Zealint]

Возьмите какую-нибудь систему компьютерной алгебры и колдуйте в ней до тех пор, пока не увидите нужных вам закономерностей. А потом сможете навести аналитику, уже зная чего ожидать.

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

[vajsaforutube]

Zealint, ewert, спасибо! Буду знать куда копать :)

[Евгений Машеров]

ewert

Ещё раз... Вы действительно полагаете, что максимальное из двух чисел (1; -1) "не обязательно положительно"? Или это у Вас шутка юмора такая?

vajsaforutube
Это у Вас тёплицева матрица. Для близкой по структуре циркулянтной матрицы есть весьма просто выглядящие выражения для с.з. и с.в., для тёплицевых общего вида есть оценки через циркулянтные.
http://ee.stanford.edu/~gray/toeplitz.pdf

[vajsaforutube]

Спасибо за ссылку, Евгений! Матрица, правда, не совсем Тёплицева - в первой строке "выехавшие" за верхний край ненулевые элементы каждого столбца подлым образом прибавляются к первому элементу этого столбца, но авось что-нибудь с этим придумаю. :)

Забавно, что в родственной задаче у меня как раз вылезли циркулянтные матрицы - через них, например, можно представить нестандартную операцию умножения векторов:

[1, 2, 3]T x [4, 5, 6]T = [1*4, 2*5, 3*6]T

как произведение циркулянтной матрицы, на вектор в "циклическом" базисе. Пока не знаю, получится ли из этого что-то работающее, но есть надежда... спасибо!

[ewert]

Евгений Машеров в сообщении #366767 писал(а):

Вы действительно полагаете, что максимальное из двух чисел (1; -1) "не обязательно положительно"?

Конечно. Ведь максимальность-то понимается по модулю.

-- Ср окт 27, 2010 20:14:22 --

Да, и чего-то я не понял:

vajsaforutube в сообщении #366730 писал(а):

Все элементы матрицы - вероятности переходов. (задача, которую мы решаем - что-то наподобие блуждания по прямой). Требуется найти главное собственное значение

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

[Ales]

Zealint в сообщении #366522 писал(а):

ewert имел в виду, что $\lambda=\pm1$, то есть отрицательное получается. Но мне это не важно, лишь бы вещественное.

Цитата:

В общем, либо степенной метод (который рано или поздно результат Вам даст) - либо ничего.
Ну, или ищите аналитическое решение.

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

Интересная задача, предлагаю следующее рассуждение (но не очень уверен):

Пусть Ваша матрица имеет размер $10^n$x$10^n$.
Насколько я понял, Вы располагаете алгоритмом, позволяющим быстро вычислить любой конкретный элемент матрицы (0 или 1). Пусть время работы алгоритма (число шагов) $a$.
Степенной метод нахождения максимального по модулю собственного значения требует ${10^{2n}}(a+b)t $ шагов, где $b$ - небольшое число до 20, а $t$ - число итераций у степенного метода, также требуется память размером $10^n$.

Насколько можно сократить общее время вычислений?

Попытка сэкономить на вычислениях самой матрицы приводит к проблеме сходной с P-NP.
В самом деле любому алгоритму можно сопоставить матрицу, и вопрос о максимальном значении такой матрицы будет не проще, чем вопрос о том не состоит ли эта матрица вообще из одних нулей (а это co-NP полная задача).
Значит, скорее всего, не получиться избежать перебора - вычисления всех элементов матрицы.
И $10^{2n}a$ так и останется.

Попробуем оценить теперь $t$ - число итераций у степенного метода.
Все собственные значения не превосходят по модулю $10^n$.
Их всего тоже около $10^n$.
Вопрос: как их модули могут быть распределены на отрезке от 0 до $10^n$?
Возможно, что рядом с максимумом модуля есть еще тысячи относительно близких модулей,
значит чтобы, вычислить точно максимальное значение надо проделать порядка $10^n$ итераций, $t=k10^n$, ведь две почти одинаковых по модулю сопряженных пары могут существенно отличаться друг от друга.

Таким образом необходимое время порядка $k10^{3n}(a+b)$. В конкретном случае - $10^{24}$.

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