2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Главное собственное значение огромной матрицы
Сообщение27.10.2010, 19:52 


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

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

 Профиль  
                  
 
 Re: Главное собственное значение огромной матрицы
Сообщение27.10.2010, 20:10 
Заслуженный участник
Аватара пользователя


11/03/08
10215
Москва
ewert

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

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

vajsaforutube

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

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

Zealint

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

 Профиль  
                  
 
 Re: Главное собственное значение огромной матрицы
Сообщение27.10.2010, 21:36 


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

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


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

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

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

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

 Профиль  
                  
 
 Re: Главное собственное значение огромной матрицы
Сообщение28.10.2010, 06:52 


26/01/10
959
Ales в сообщении #366962 писал(а):
Но может быть, Ваша задача имеет и другие пути решения.
Ведь у Вас не просто матрица, и не просто алгоритм вычисления ее элемента. Ведь все же Вы знаете некоторые ее свойства.

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

 Профиль  
                  
 
 Posted automatically
Сообщение04.11.2013, 01:56 
Основатель
Аватара пользователя


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

 Профиль  
                  
 
 Re: Главное собственное значение огромной матрицы
Сообщение04.11.2013, 12:21 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 36 ]  На страницу Пред.  1, 2, 3

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group