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

[Zealint]

Да, вполне логичное рассуждение. Но я знаю чуть больше о своей задаче, поэтому заведомо знаю, что максимальное собственное значение раза в два больше второго за ним. Поэтому метод применяю другой: умножаю $n$ раз матрицу на вектор из нулей (с одной лишь единицей в нужном месте). Получаю последовательность из $n$ чисел ($n=1..N$). То есть очередное умножение матрицы на вектор дает в нужном месте полученного вектора очередное число. Далее к этим числам применяется аппроксимация Pade. При $N=100$ точность получается очень высокой. Знаков 100, может чуть меньше.

Но я как раз интересуюсь, бывают ли более быстрые методы, в частности такие, чтобы всю матрицу не задействовать. Это сейчас она у меня порядком $10^8$, а следующая за ней в 3 раза больше. А за ней другая - еще в 3 раза больше и т. д.

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

ewert

Ну, значит, мы о разных вещах говорим. Я о том, что,согласно теореме Фробениуса-Перрона, у неразложимой матрицы естт максимальное собственное число, и оно положительно. Не по модулю, естественно.

-- Ср окт 27, 2010 21:11:30 --

vajsaforutube

Циркулянтные связаны с Фурье, и их с.з. считать хорошо...

-- Ср окт 27, 2010 21:39:24 --

Zealint

Позвольте... Но "умножение матрицы на вектор из нулей с одной единицей в нужном месте" это попросту взятие какой-либо строки?
Метод неясен. Особенно в плане работоспособности.

[Ales]

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

Да, вполне логичное рассуждение. Но я знаю чуть больше о своей задаче, поэтому заведомо знаю, что максимальное собственное значение раза в два больше второго за ним. Поэтому метод применяю другой: умножаю $n$ раз матрицу на вектор из нулей (с одной лишь единицей в нужном месте). Получаю последовательность из $n$ чисел ($n=1..N$). То есть очередное умножение матрицы на вектор дает в нужном месте полученного вектора очередное число. Далее к этим числам применяется аппроксимация Pade. При $N=100$ точность получается очень высокой. Знаков 100, может чуть меньше.

Но я как раз интересуюсь, бывают ли более быстрые методы, в частности такие, чтобы всю матрицу не задействовать. Это сейчас она у меня порядком $10^8$, а следующая за ней в 3 раза больше. А за ней другая - еще в 3 раза больше и т. д.

Если максимальное по модулю собственное значение так выделено, то число итераций степенного метода обратно пропорционально логарифму точности. И это очень хорошо.
Значит проблема только в вычислении самой матрицы. Но это, как раз, на мой взгляд, проблема P-NP.

Но может быть, Ваша задача имеет и другие пути решения.

-- Ср окт 27, 2010 21:39:06 --

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

[Zealint]

Ales в сообщении #366962 писал(а):

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

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

[cepesh]

Тема перемещена из форума «Численные и вычислительные методы, оптимизация» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.

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

А как проверено, что получено правильное значение с.з. (пусть даже не со ста знаками)?