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

[prof.uskov]

Рассматривается метод парных сравнений.
Матрица значений парных сравнений - положительная обратносимметричная матрица:

$$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?

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

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

[ИСН]

Ну а вообще есть ли какой-то толк в её обратносимметричности?

[prof.uskov]

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

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

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

-- 17.09.2014, 13:38 --

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

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

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

-- 17.09.2014, 13:54 --

ИСН в сообщении #908741 писал(а):

Ну а вообще есть ли какой-то толк в её обратносимметричности?

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

[ИСН]

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

[prof.uskov]

ИСН в сообщении #908748 писал(а):

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

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

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

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

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

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

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

Нашёл и прочёл.
Как я и понял вначале, №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 точный и в точной арифметике даст то же, что метод простых итераций, но в силу резкого возрастания числа операций может давать большую ошибку.

[prof.uskov]

Евгений Машеров, спасибо.

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

Метод простой итерации состоит в $x_{i+1}=Ax_i$, с последующим нормированием элементов любым способом и повторении этой итерации, пока не сойдётся.

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

[prof.uskov]

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

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

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

[prof.uskov]

Евгений Машеров в сообщении #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, а размерности матрицы. Для сходимости в традиционном смысле нужно еще нормирование.

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

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