2014 dxdy logo

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

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



Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему
 
 Главный собственный вектор обратносимметричной матрицы
Сообщение16.09.2014, 20:56 
Аватара пользователя


12/01/14
1069
Рассматривается метод парных сравнений.
Матрица значений парных сравнений - положительная обратносимметричная матрица:
$$A=\left( \begin{matrix}
   1 & a_{12} & ... & a_{1n}  \\
   1/a_{12} & 1 & ... & a_{2n}  \\
   ... & ... & ... & ... &  \\
   1/a_{1n} & 1/a_{2n} & ... & 1  \\
   \end{matrix} \right)
$$
Как известно, вектор приоритетов $\omega$ – главный собственный вектор матрицы $A$:
$A \omega=\lambda_{\max}\omega$,
где $ \lambda_{\max} $ - наибольшее собственное число матрицы $A$.

Вопросы:
Каким методом находить $\omega$, если размерность матрицы $A$ больше 1000?
Можно ли в данном случае использовать стандартные матричные функции системы MATLAB?

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


11/03/08
5316
Москва
По-моему, простые итерации и при таких размерностях справляются прекрасно.

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


18/05/06
13134
с Территории
Ну а вообще есть ли какой-то толк в её обратносимметричности?

 Профиль  
                  
 
 Re: Главный собственный вектор обратносимметричной матрицы
Сообщение17.09.2014, 12:36 
Аватара пользователя


12/01/14
1069
В книге Саати Т. Принятие решений. Метод анализа иерархий. М.: Радио и связь, 1993 на стр. 24 приводится пять приближенных методов решения этой задачи:
1. Суммирование элементов каждой строки с последующим нормированием.
2. Суммирование элементов столбцов и нахождение обратных, после чего проводится нормирование.
3. Деление элементов каждого столбца на сумму его элементов, затем сложение строк полученной матрицы и деление на число элементов строки.
4. Умножение элементов каждой строки и извлечения корня степени размерности матрицы с последующей нормализацией результата.
5. Возведение матрицы в произвольную большую степень и деление суммы каждой строки на общую сумму элементов матрицы - метод позволяющий получить любую точность.

Но в данной книге рассматривается лишь размерность задачи не более 15.

Как поступать в случае гораздо большей размерности?

-- 17.09.2014, 13:38 --

Евгений Машеров в сообщении #908737 писал(а):
По-моему, простые итерации и при таких размерностях справляются прекрасно.

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

-- 17.09.2014, 13:54 --

ИСН в сообщении #908741 писал(а):
Ну а вообще есть ли какой-то толк в её обратносимметричности?

Элементы главного собственного вектора положительны, а их сумма - 1.

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


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

 Профиль  
                  
 
 Re: Главный собственный вектор обратносимметричной матрицы
Сообщение17.09.2014, 13:18 
Аватара пользователя


12/01/14
1069
ИСН в сообщении #908748 писал(а):
Начинаю подозревать, что обратносимметричность ничем не полезна, и собственные векторы этой матрицы надо искать так же, как и любой другой похожего размера.

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

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


11/03/08
5316
Москва
Собственный вектор определяется, как $Ax=\lambda x$ с точностью до постоянного множителя. Поэтому вводят некоторую нормировку, удобную для конкретного приложения. Чаще к единице приводят сумму квадратов, это всегда работает, но в данном случае неразложимая положительная матрица, все элементы первого собственного вектора положительны, и можно приводить к единичной сумме элементов вектора (в общем случае при наличии отрицательных сумма элементов может быть и 0).

-- 17 сен 2014, 13:47 --

Метод простой итерации состоит в $x_{i+1}=Ax_i$, с последующим нормированием элементов любым способом и повторении этой итерации, пока не сойдётся. Если в качестве начального приближения взять вектор из единиц, видно, что способ №1 это один шаг итерации. Второй и третий я из Вашего описания не вполне понял, но, похоже, это ещё вариант выполнения одного шага простых итераций. В четвёртом пункте неясно, что на что умножается и из чего извлекается корень (если будет время - найду эту книгу Саати, и уточню). Пятый вариант действительно позволяет вычислить не приближённо, а точно, если взять высокую степень. Но умножение матриц - кубично по числу операций (по отношению к размерности матрицы), и при большой размерности недопустимо затратно.
А умножение матрицы на вектор - квадратично.
Сходимость тут должна быть хорошая.

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


11/03/08
5316
Москва
Нашёл и прочёл.
Как я и понял вначале, №1 это один шаг простых итераций с начальным приближением в виде единичного вектора, №2 то же самое, но с транспонированной матрицей, и в качестве решения предлагаются обратные к элементам собственного вектора этой матрицы, №3 это два шага простых итераций, первый с транспонированной, а результат используется в качестве приближения для шага с исходной матрицей. В №4 перемножаются коэффициенты в строке, получая среднее геометрическое, он основан на надежде, что ранг матрицы равен единице и $a_{i,j}=w_i/w_j (что, вообще говоря, не гарантировано).
Метод №5 предполагает получение $A^n$, $n>>1$, что достаточно затратно, поскольку для матрицы 1000х1000 нужно миллиард умножений и миллиард сложений для хотя бы квадрата (n-ная степень может быть получена быстрее, чем за n умножений, за величину порядка логарифма n, скажем, для 1024-й степени понадобится лишь 10 возведений матрицы в квадрат, но и это многовато).
Но заметим, что в методе простых итераций $x_n=A^n x_0$ с точностью до нормировки, причём для указанной размерности шаг в тысячу раз дешевле.

-- 17 сен 2014, 15:16 --

Методы №№ 1-4 приближённые, причём оценить точность нельзя (в пределах самого метода, вообще же подставить и проверить, насколько $a_{i,j}$ отлично от $w_i/w_j$ не возбраняется), №5 точный и в точной арифметике даст то же, что метод простых итераций, но в силу резкого возрастания числа операций может давать большую ошибку.

 Профиль  
                  
 
 Re: Главный собственный вектор обратносимметричной матрицы
Сообщение17.09.2014, 18:47 
Аватара пользователя


12/01/14
1069
Евгений Машеров, спасибо.
Евгений Машеров в сообщении #908757 писал(а):
Метод простой итерации состоит в $x_{i+1}=Ax_i$, с последующим нормированием элементов любым способом и повторении этой итерации, пока не сойдётся.

А почему эта итерационная процедура сходится к главному собственному вектору?

 Профиль  
                  
 
 Re: Главный собственный вектор обратносимметричной матрицы
Сообщение17.09.2014, 20:36 
Аватара пользователя


12/01/14
1069
Нашел, это так называемый степенной метод (счет на установление).

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


11/03/08
5316
Москва
Сходится он в силу того, что $x_n=A^nx_0$, а представляя $A=C^{-1}\Lambda C$, получаем $x_n=C^{-1}\Lambda^nC x_0$ (старшее собственное значение простое, ни в какие ящики Жордана оно не попадает), и по мере роста n меньшие собственные значения стремятся к нулю, а старшее равно единице.

 Профиль  
                  
 
 Re: Главный собственный вектор обратносимметричной матрицы
Сообщение18.09.2014, 09:02 
Аватара пользователя


12/01/14
1069
Евгений Машеров в сообщении #908981 писал(а):
Сходится он в силу того, что $x_n=A^nx_0$, а представляя $A=C^{-1}\Lambda C$, получаем $x_n=C^{-1}\Lambda^nC x_0$ (старшее собственное значение простое, ни в какие ящики Жордана оно не попадает), и по мере роста n меньшие собственные значения стремятся к нулю, а старшее равно единице.

Маленькое уточнение, если матрица парных сравнений идеально согласована (выполняется соотношение $a_{i,j}=w_i/w_j ), старшее собственное значение $ \lambda_{\max} $ равно не 1, а размерности матрицы. Для сходимости в традиционном смысле нужно еще нормирование.

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


11/03/08
5316
Москва
Ну да, имеется в виду, что, не теряя общности, можно отнормировать к максимальному с.з., равному единице. Для вывода сходимости.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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