ewert имел в виду, что

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

x

.
Насколько я понял, Вы располагаете алгоритмом, позволяющим быстро вычислить любой конкретный элемент матрицы (0 или 1). Пусть время работы алгоритма (число шагов)

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

шагов, где

- небольшое число до 20, а

- число итераций у степенного метода, также требуется память размером

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

так и останется.
Попробуем оценить теперь

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

.
Их всего тоже около

.
Вопрос: как их модули могут быть распределены на отрезке от 0 до

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

итераций,

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

. В конкретном случае -

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