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

[Zealint]

Товарищи специалисты по линейной алгебре, есть такая задача, но я не специалист в этой области.

Имеется огромная матрица (порядком до $10^8$). В память она даже близко не лезет (да и на жесткий диск тоже), но зато я быстро могу построить любую её строку. Требуется отыскать максимальное по модулю собственное значение. Гарантируется, что оно либо уникальное, либо там комплексно-сопряжённая пара.

Если это поможет, матрица состоит из нулей и единиц. Даже если хранить только позиции единиц, все равно это ни в какую память не влезает. Нужен приближённый метод, решающий данную задачу за "разумное" время, скажем, за неделю. Точность решения хочется знаков 100, но пока не так важно.

Может ли кто-нибудь навести на мысль или поделиться ссылкой на решение такой задачи?

[ewert]

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

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

умножайте, умножайте, умножайте до посинения (ну в смысле до сходимости)

[Zealint]

ewert в сообщении #365398 писал(а):

умножайте, умножайте, умножайте до посинения (ну в смысле до сходимости)

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

[ИСН]

В теории сложности известна классическая подстава, когда человек пытается найти решение за меньшее время, чем необходимо, чтобы написать ответ. НИКАК.
Здесь обратная ситуация: условие такого размера, что хотя бы его прочитать - - -

[ewert]

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

Умножить матрицу такого размера...

Не матрицу умножать, а вектор на матрицу. Вы ж сами сказали, что способны просто за нефиг делать сгенерить любую её строчку. "А чего ещё нужно, чтоб спокойно встретить старость?..."

(это среди некоторых пижонов принято называть "методом прямых итераций")

[SakumaRei]

Степенной метод.

[Zealint]

ewert в сообщении #365408 писал(а):

Не матрицу умножать, а вектор на матрицу. Вы ж сами сказали, что способны просто за нефиг делать сгенерить любую её строчку. "А чего ещё нужно, чтоб спокойно встретить старость?..."

(это среди некоторых пижонов принято называть "методом прямых итераций")

Понял, то есть вектор умножаем на матрицу до посинения, смотрим что получается. Так? А ещё быстрее и проще можно?

[Pavia]

Zealint
Можно через случайные выборки. Фукунаги стр 48. вам в помощь. Если я книгу правильно понял то так. Возьмем к примеру m=8. 8 векторов случайно сгенерированных. Умножим на матрицу. Получим вектора Y. $W=(Y_1,Y_2,..,Y_m)$ найдем произведение $(1/m)W*W^T_{(m,m)}$
Дальше найдем собственные значения этой матрицы. Они будут равны искомым. Отсальные собственные значения с m+1 по n считаются нуливыми.
Преимущество в том что собственные значения вычисляются для матрицы меньшей размерности.

[Zealint]

Очень странный метод и непонятно, почему он вообще должен работать. Прочитал страницу 48, сделал как написано. В результате получается, что для более менее приличной точности надо брать половину всей матрицы, что ничуть не лучше. Кстати странно, что этим методом собственное значение получается больше, чем на самом деле.

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

Простейший метод поиска максимального собственного значения - простые итерации. Произвольный вектор умножается на матрицу, произведение нормируется, далее опять и так до сходимости. Скорость зависит от того, насколько старшее собственное значение отделено от следующего по величине. Поскольку для умножения матрицы на вектор достаточно доступа к значением её элементов - тут работать будет.
Однако, в случае пары комплексно-сопряжённых значений будут проблемы. Сходимости вектора не будет.
В этом случае, начиная с некоторой итерации, три последовательных вектора будут линейно зависимы. Найдя коэффициенты линейной комбинации их, получим алгебраическое уравнение, корнями которого будут искомые комплексно-сопряжённые значения
(Уилкинсон, "Алгебраическая проблема собственных значений", с. 501)
$v_{s+1} =Au_s $
$k_{s+1} =max(v_{s+1} )$
$u_{s+1} =v_{s+1} / k_{s+1} $

$k_{s+1}k_{s+2}u_{s+2}-pk_{s+1}u_{s+1}-qu_s =0$

$Re(\lambda_1)=p/2$

$Im(\lambda_1)=\sqrt{p^2+4q}/2$

Для нахождения коэффициентов линейной комбинации следует использовать метод наименьших квадратов.

-- Пн окт 25, 2010 15:13:36 --

Pavia

Это Вы изволили описать метод одновременных итераций. Он полезен в том случае, когда несколько наибольших с.з. равны или близки по модулю. Однако после первой итерации надеяться на сходимость не стоит. Это итеративный метод. Просто на матрицу А умножается не вектор, а матрица, одна из размерностей которой равна размерности А, а другая мала и соответствует числу одновременно отыскиваемых с.з. После умножения столбцы матрицы-произведения ортогонализуются (для чего и находятся произведение данной матрицы на транспонированную к ней и собственные вектора и числа этого произведения) и делается итерация с уже ортогонализованными столбцами
(Уилкинсон и Райнш, "Справочник алгоритмов на языке Алгол").

[ewert]

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

Однако, в случае пары комплексно-сопряжённых значений будут проблемы. Сходимости вектора не будет.

Эта проблема легко снимается применением сдвигов. Действительно проблема -- когда собственное число кратное, причём его геометрическая кратность меньше алгебраической.

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

Даже при алгебраической кратности степенной метод может затыкаться. Но автор темы вроде гарантирует (из физических соображений?) единственность?
Кстати, если матрица неразложима, то, учитывая, что её элементы $a_{i,j}$\in $ (0,1)$\geqslant 0$ $, максимальное собственное значение будет вещественным положительным.

[Zealint]

Цитата:

Даже при алгебраической кратности степенной метод может затыкаться. Но автор темы вроде гарантирует (из физических соображений?) единственность?

Да, и из физических соображений и из комбинаторных это гарантируется. Либо единственное вещественное значение, либо комплексно-сопряжённая пара.

Цитата:

Кстати, если матрица неразложима, то, учитывая, что её элементы $a_{i,j}$\in $ (0,1)$\geqslant 0$ $, максимальное собственное значение будет вещественным положительным.

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

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

[ewert]

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

Даже при алгебраической кратности степенной метод может затыкаться.

С чего бы вдруг? (если кратности максимального собственного числа совпадают, т.е. соответствующий жорданов ящик диагонален)

-- Вт окт 26, 2010 17:56:35 --

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

максимальное собственное значение будет вещественным положительным.

Ну да, щас. А как насчёт $\begin{pmatrix}0&1\\1&0\end{pmatrix}$?

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

ewert

1. С того, что одинаковым с.з. будут соответствовать разные с.в., и в натянутом на них пространстве очередные итерации будут "гулять".
Реально случается.
2. Ну, выпишем характеристический полином. Ну и?
$\lambda^2-1=0$

-- Вт окт 26, 2010 20:45:05 --

Zealint

Ну, вообще-то очевидно, что, вообще говоря, если в вычислении с.з. не участвуют все элементы матрицы, то вычисленное максимальное с.з. может быть каким угодно. Ограничение элементов матрицы значениями 0 и 1 ограничит возможный результат, но произвол останется изрядным.
Что, в сочетании с требованием "хочется знаков 100" выглядит... Странно.

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

Ну, или ищите аналитическое решение.