"Максимальный" собственный вектор как мн-во приоритетов

[ozheredov]

При рассмотрении каждой упорядоченной пары ${A_i, A_j}$ из заданного набора альтернатив эксперт (или что-то еще) приписывает этой упорядоченной паре меру уверенности в том, что $A_j$ лучше $A_i$. Это порождает обратно-симметричную матрицу парных сравнений $C^i_j$, в которой (обратная симметрия) $C^j_i = \frac{1}{C^i_j}$. Благородный дон в моем лице хочет вектор приоритетов $w$, где $w^i$ обозначает меру "любви" эксперта к альтернативе $A_i$.

И я возгуглил. Чисто эстетически мне очень понравился подход, когда $w$ ищется как "максимальный" (отвечающий наибольшему СЗ) собственный вектор матрицы $C$. Но что-то я его не понимаю, совсем. И дальнейший гуглеж не особо помогает.

Мои бредовые рассуждения: допустим, есть "идеальный эксперт" (also called as "объективная реальность" ), назначивший каждой альтернативе приоритет $u_i$. Тогда матрица предпочтений эксперта это есть "искаженный шумом" образ матрицы $D^i_j = \frac{u_i}{u_j}$ (которая, BTW, является обратно-симметричной). Нам надо из этого образа вытащить некий $w$, близкий в косинусной норме к $u$ (почему косинусной? потому что суммы квадратов весов $u$ и $w$ равны единице, а почему квадратов? потому что дальше у нас аппарат собственных значений). "Максимальный" собственный вектор оптимизирует сумму

$$w'Cw = \sum \sum w_i C^i_j w_j \approx \sum \sum w_i \frac{u_i}{u_j} w_j$$

(разумеется, при условии нормированности $w$ на единицу). И что, есть какая-то теорема, что такой $w$ окажется близок к $u$, или когда? В общем, просьба наставить на путь )

[realeugene]

Приоритеты у вас складываются? По идее, нужно перемножать, то есть, складывать логарифмы. И тогда матрица у вас будет антисимметричная.

[ozheredov]

realeugene в сообщении #1612439 писал(а):

Приоритеты у вас складываются? По идее, нужно перемножать, то есть, складывать логарифмы.

О, спасибо за наводящий вопрос!! На данный момент мне кажется вот что: сложение тут как инструмент получения целевой функции, которая достигает максимума там где надо и легко оптимизируется (тут куча нюансов, которые для меня пока мрак). Что я думаю сейчас: если у нас есть вектор труЪ-приоритетов $u^i$ и полученная из него матрица парных сравнений

$$C^i_j = \frac{u^i}{u^j}$$

,
то для такой матрицы есть интересная теорема:

Если для любых индексов $i, j, k$ верно, что $C^i_j C^j_k = C^i_k$ (проверяем:

$$\frac{u^i}{u^j} \frac{u^j}{u^k} = \frac{u^i}{u^k}$$

), и она естественно состоит из положительных элементов, то ее максимальное собственное значение равно ее размеру $n$.

Вопрос: как доказать?

Так вот, если (поскольку) это верно, то

$$(Cu)^i = \sum_j {C^i_j u^j} = \sum_j {\frac{u^i}{u^j} u^j} = u^i \sum_j {1} = n u^i$$

,
то есть $Cu = nu$, и поскольку у $C$ нет собственных значений, бОльших $n$, то $u$ и есть тот самый "максимальный" СВ.

Теперь самое интересное: матрица $C$ не обязана удовлетворять условиям теоремы выше, но обязана быть обратно-симметричной. По этому поводу есть исчо одна теорема о том, что СЗ такой матрицы всегда не меньше $n$

Вопрос: а как это доказать?

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

Ну, для меня прояснение, почему собственные значения, дала процедура вычисления С.В., соответствующего максимальному С.З. методом прямых итераций. Положим, у нас есть какая-то начальная оценка "приоритетов" (хотя бы всем поровну). Можно попытаться уточнить её для j-того объекта, умножая текущую оценку i-того объекта на коэффициент, указывающий, во сколько раз j-тый лучше i-того, и все такие оценки просуммировать. Что даёт $w_{k+1}=Cw_k$. Продолжая итерации, пока вектора w не сойдутся (с учётом нормирования) - получаем максимальный собственный вектор.

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

https://scask.ru/r_book_spr.php?id=58

[ozheredov]

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

$w_{k+1}=Cw_k$

... и неподвижной точкой является $w: Cw=w$, т.е. собственный вектор, отвечающей единице. Да, любопытный подход.

Еще такой вопрос: я подумал и решыл, что обратно-симметричные матрицы зло ) Врядли алгоритму поиска eigenvectors понравится матрица, в которой на одной стороне одна миллиардная, а на другой миллиард. ИМХО, гораздо лучше предложение

realeugene в сообщении #1612439 писал(а):

нужно перемножать, то есть, складывать логарифмы. И тогда матрица.. будет антисимметричная

В этом случае "$w_{k+1}=Cw_k$" вроде как должно работать, потому как

$$(w_{k + 1})^i = \sum_j C^i_j (w_k)^j$$

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

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

https://scask.ru/r_book_spr.php?id=58

Спасибо! А там можно попасть на заданную страницу? Я пробовал декрементировать id=58 до id=57, так он сразу 10 страниц пропустил.

UPD: разобрался, надо на саму страницу кликать

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

ozheredov в сообщении #1612600 писал(а):

... и неподвижной точкой является $w: Cw=w$, т.е. собственный вектор, отвечающей единице. Да, любопытный подход.

Нет

[Утундрий]

Если $w_n$ к чему-то стремится, то таки да.

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

Стремится к собственному вектору, соответствующему максимальному собственному значению. Это очевидно, если матрицу С представить, как сумму матриц ранга 1.

[ozheredov]

Снова туплю, help please:

$$\varphi_{max} \approx w_{k + 1} = C w_k \approx C \varphi_{max} = \lambda \varphi_{max}$$

и это не особо выполняется с другими Лямбда помимо единицы. Где у меня ошибка? (первая, понятно - в ДНК, а вторая где?)

-- 06.10.2023, 00:32 --

P.S.

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

Стремится к собственному вектору, соответствующему максимальному собственному значению. Это очевидно, если матрицу С представить, как сумму матриц ранга 1.

Можете please расписать подробно? Верно ли я понимаю, что ранг 1 бывает только у диадных матриц (произведение столбца и строки)? Если да, то мы устраиваем исходной матрице нечто типа двумерного преобразования Фурье, раскладывая ее в сумму диад, так? И что далее?

[realeugene]

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

Это очевидно, если матрицу С представить, как сумму матриц ранга 1.

Но нюанс в том, что матрица у ТС не симметричная.

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

ozheredov в сообщении #1612630 писал(а):

и это не особо выполняется с другими Лямбда помимо единицы. Где у меня ошибка? (первая, понятно - в ДНК, а вторая где?)

Пропущено "с учётом нормирования". Всякий раз вектор, полученный умножением, приводится к единичной норме.