Т. Саати Принятие решений. Т. саати принятие решений метод анализа иерархий
 Скачать 4.58 Mb.
|
|
Теорема 7.7. Если A – положительная ( ) n n × -матрица, то lim k k k A ωυ λ →∞ = , где λ – положительная постоянная, υ – ненулевая вектор-строка, а ω – нену- левой вектор-столбец. Краткое доказательство. Пусть ( ) 1 1 | , , , 0, 1, , , 1, 1 n T n t i i S x x x x x i n x т е fx = = = ≥ = = = ∑ … … , где ( ) 1,1, , 1 f = … Рассмотрим отображение 1 , Tx Ax x S fAx = ∈ Это отображение положительно: так как 1 fx = , то x имеет ненулевую компоненту, и, следовательно, 0 Ax > и 0 fAx > . Далее 160 1 1 fTx fAx fAx = = , и поэтому T отображает S в S . Так как A непрерывна, по теореме Брауера о не- подвижной точке найдется точка ω , что 1 A fA ω ω ω = Поскольку левая часть положительна, ω – положительна и 0 fA λ ω = > . Следова- тельно, A ω λω = , 0 λ > , 0 ω > . Наконец, пусть D – диагональная матрица с ii i d ω = и 0 ij d = , i j ≠ . Так как 0 ω > , D имеет обратную матрицу 1 D − , также диагональ- ную, с диагональными элементами 1 i ω , т. е. De ω = и ( ) ( ) 1 1 1 1 1 D AD e D A D e λ λ ω ω − − − = = = Отсюда следует, что суммы строк матрицы ( ) 1 1 D AD λ − равны единице, т. е. эта матрица – стохастическая, и исходя из теоремы 7.6 найдётся такой вектор- строка * υ , что ( ) ( ) * 1 1 lim 1 lim 1 k k k k k e D AD D A D υ λ λ − − →∞ →∞ = = , (т. е. строки предельной матрицы все одинаковы), откуда непосредственно получа- ем ( ) * 1 * 1 lim 1 k k k A De D D λ υ ωυ ωυ − − →∞ = = = Теорема 7.8. υ и ω – собственные векторы матрицы A , соответствующие соб- ственному значению λ Доказательство. ( ) ( ) ( ) ( ) 1 1 1 1 lim 1 lim 1 k k k k k k A A A A λ ωυ λ λ λ ωυ + + →∞ →∞ = = = , откуда имеем A ωυ λωυ = и A e e ωυ λωυ = , и так как e υ постоянная, то A ω λω = Аналогично A υ λυ = Следствие. Векторы υ и ω положительны. Доказательство. Из равенства A ω λω = имеем ( ) 1 A λ ω ω = . Так как , A λ – по- ложительны, а ω – неотрицателен (с некоторыми ненулевыми компонентами), все компоненты левой части равенства положительны, и, следовательно, ω – положи- телен; аналогично для υ Теорема 7.9. Все собственные векторы, соответствующие собственному значе- нию λ , являются постоянными множителями ω и υ Доказательство. Если Au u λ = , то k k A u u λ = , а ( ) 1 k k A u u λ = для всех k . При k → ∞ имеем u u ωυ = . Аналогично для векторов-строк. Теорема 7.10. Модуль любого другого собственного значения h матрицы A удовлетворяет неравенству h λ < Доказательство. Если Au hu = , то k k A u h u = , а ( ) ( ) 1 k k k A u h u λ λ = . Переходя к пределу при k → ∞ имеем [ ] lim k k u h u ωυ λ →∞ = , 161 и предел в правой стороне должен существовать, что возможно только при h λ = или h λ < , причем в последнем случае предел равен нулю. Собственное значение λ есть главное собственное значение матрицы A , кото- рое обозначается max λ , а υ и ω – главные собственные векторы матрицы A Следствие. Главный собственный вектор-строка (столбец) — ( ) υ ω ортогонален ко всем не главным собственным векторам-столбцам (строкам) матрицы A Доказательство. Рассмотрим равенство 0 u ωυ = из доказательства предыдущей теоремы. Так как 0 ω > , имеем 0 u υ = , и, следовательно, υ ортогонален вектору- столбцу u . Аналогичный аргумент можно использовать, чтобы показать ортогональ- ность ω ко всем не главным собственным векторам-строкам матрицы A Следствие. 1 υω = Доказательство. В условиях теоремы пусть u ω = , тогда h λ = и ωυω ω = . Так как υω – число, получаем 1 υω = Замечание. υω есть след матрицы ωυ , и, следовательно, этот след всегда равен единице. Замечание. Система 1 n ij j i j a x b = = ∑ , 1, , i n = … где 0 ij a ≥ , 0 ij d > , имеет неотрицательное решение 0 j x ≥ , 1, , j n = … , если 11 12 13 11 12 11 21 22 23 21 22 31 32 33 0, 0, 0, , 0 a a a a a a a a a A a a a a a > > > > … Теорема 7.11 [182]. Если A – неотрицательная неприводимая матрица, то зна- чение max λ возрастает с увеличением любого элемента ij a Доказательство. Пусть A – неотрицательная матрица, определим ( ) B I A ρ ρ = − , где ρ – действительный параметр [110]. Пусть M – множество всех ρ , для кото- рых существует и не отрицательна обратная матрица ( ) 1 I A ρ − − . Множество M не- пусто для 0 x > и остается таким для сравнительно большого ρ , x Ax ρ > , т. е. 0 x Ax ρ − > , и это условие обеспечивает существование неотрицательного решения и эквивалентно вышеописанному условию на главные миноры. Так как M зависит от A , обозначим его ( ) M A Пусть 0 A A ′ ′′ ≥ ≥ . Тогда ( ) ( ) M A M A ′ ′′ ⊂ . В самом деле, заметим, что если ( ) M A ρ ′ ∈ , то ( ) 0 I A x ρ ′ − > для некоторого 0 x > и так как I A I A ρ ρ ′′ ′ − ≥ − , ( ) 0 I A x ρ ′′ − > для того же самого x , и, следовательно, ( ) M A ρ ′′ ∈ . Теперь макси- мальное собственное значение max λ матрицы 0 A > есть ( ) inf M A ρ ρ ∈ , для которого ( ) 1 I A ρ − − существует, т. е. это первое значение, для которого 0 I A ρ − = , ибо все другие собственные значения не превосходят max λ . Поэтому ( ) ( ) ( ) ( ) max max inf inf M A M A A A ρ ρ λ ρ ρ λ ′ ′′ ∈ ∈ ′ ′′ = ≥ = 162 Следовательно, max λ – монотонная функция A Ниже показан важный результат, который заключается в том, что собственный вектор, соответствующий max λ , представляет собой нормализованные суммы элемен- тов строк предельной матрицы в точности k -й степени k A -матрицы A (а не суммы всех степеней A ). Теорема 7.12. 1 lim k T k k A e c e A e ω →∞ = , где 0 A > , 1 ω – главный собственный вектор, соответствующий максимальному соб- ственному значению 1 λ , i j λ λ ≠ для всех i и j , i ω – правый собственный вектор, соответствующий i λ , а c – постоянная. Доказательство. 1 1 n n e a a ω ω = + + … , где , 1, , i a i n = … – постоянные. ( ) ( ) 1 1 1 1 1 1 2 2 1 2 1 k k k k k k n n n n n n A e a a a a a λ ω λ ω λ ω λ λ ω λ λ ω = + + = + + + … … , ( ) ( ) 1 1 2 2 1 1 k k T k k n n e A e b b b λ λ λ λ λ = + + + … ; T i i i b a e ω = Так как 1 0 ω > , 0 b ≠ , что и требовалось доказать. Теперь обобщим эту теорему. Определение 7.2. Неотрицательная неприводимая матрица A примитивна то- гда и только тогда, когда существует целое 1 m ≥ . такое, что 0 m A > . В противном случае матрицу называют импримитивной. Граф примитивной матрицы имеет длину пути между любыми двумя вершинами m ≥ Из работ [50, 114, 182] известно, что неотрицательная неприводимая матрица A примитивна тогда и только тогда, когда A имеет единственный характеристический корень с максимальным модулем, и этот корень имеет кратность, равную единице. Теорема 7.13. Для примитивной матрицы A lim k k k A e c A ω →∞ = , k T A e Ae ≡ , где c – постоянная, а ω – собственный вектор, соответствующий max 1 λ λ ≡ Доказательство. Допустим 0 A > . Рассмотрим жорданову каноническую форму B матрицы A . Тогда для некоторой невырожденной матрицы N 1 2 1 0 0 r B NAN B B λ − = = где , 2, , i B i r = … есть i i m m × жорданова блочная форма, которая имеет вид 163 1 0 1 1 0 1 i i i i i i B λ λ λ λ λ = где 2 , , r λ λ … – различные собственные значения с кратностями 2 , , r m m … соот- ветственно, а 2 1 r i i m n = + = ∑ – размерность матрицы A . Выбираем соответствующие базисные векторы для каждого подпространства жордановой формы 2 3 1 21 22 2 31 32 3 1 2 , , , , , , , , , r m m r r rm V V V V V V V V V V … … … и имеем 1 1 1 AV V λ = , 1 1 2 i i i i AV V V λ = + , 2 2 3 i i i i AV V V λ = + , i i im i im AV V λ = Отметим, что i i B I u λ = + , где 0 1 0 0 1 . 0 10 u = и 164 1 2 2 1 1 k k k k k i i i i k k B I u u u λ λ λ − − = + + + + … , где k u – нулевая матрица, если k n ≥ , а если k n > – диагональ единиц в u , сдвинутая вниз на каждую дополнительную степень u . Например, 2 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 u = … … … … … Теперь пусть 2 2 1 1 21 21 22 22 2 2 31 31 r r m m r m r m e a V a V a V a V a V a V = + + + + + + + … … , 1 1 1 2 1 0 r m j r k k k l ij i ij i j i k A e a V a V j l λ λ − = = = = + − ∑∑∑ , 1 1 1 2, 2 2, 1 2 2,1 2 ,1 2 k k k k k k k rk r r r A c p p p p p c λ λ λ λ λ λ − − = + + + + + + + + + … … … , где ij p – полиномы от k , а 1 c , 2 c – постоянные, не зависимые от k . Выражение k k A e A , будет иметь член 1 1 1 1 1 1 2, 2 2, 1 2 2 k k k k k k a V c p p c λ λ λ λ − − + + + + … , предел которого при k → ∞ будет ( ) 1 1 1 a c V , так как 1 λ – единственное наи- большее собственное значение. Типичный член ( ) 2 i ≥ 1 1 1 2 k il i ij k k ik i k a V j l c p c λ λ λ − − + + + + … … будет стремиться к нулю при k → ∞ (так как 1 λ превосходит все другие λ ). Пола- гая ( ) 1 1 e a c = и 1 V ω = , получаем теорему для 0 A > Замечание. Отметим, что 1 0 c = в том и только в том случае, если 1 0 a = . Можно показать, что 1 0 a ≠ , исходя из того, что все ij a в разложении e и все i V действи- тельны и положительны. Малое возмущение e оставляет 1 0 a ≠ , а результат при этом останется тем же самым. Теперь для доказательства теоремы при 0 A ≥ отметим, что из-за 0 ij a > сущест- вует такое положительное целое m , что 0 m A > (т. е. при движении по петлям в ко- нечном счете возможно получение пути любой желаемой длины между произволь- ной парой вершин соответствующего графа). Приведенное выше доказательство применимо к m A и его наибольшему собственному вектору ( ) m A ω . Действительно, так как A – ограниченный линейный оператор (и поэтому непрерывный), имеем 165 ( ) lim , 0 mk i m mk i k A c A i m A ω + + →∞ = ≤ < Легко убедиться, что ( ) m A ω есть искомый неотрицательный собственный век- тор. Это завершает доказательство. Замечание. Следующая неотрицательная матрица неприводима (ее граф – силь- но связный, так как у любой пары вершин имеется путь, связывающий их): 0 2 0 0 0 4 1 0 0 A = Эта матрица не удовлетворяет условиям теоремы, поскольку она импримитивна, имея 2 как единственное собственное значение кратности 3. Для пояснения этого отметим следующее: ( ) 2, 4,1 T Ae = ; нормализацией получаем ( ) 1 2 / 7, 4 / 7,1/ 7 T x = ; ( ) 1 8 / 7, 4 / 7, 2 / 7 T Ax = ; нормализацией получаем ( ) 2 4 / 7, 2 / 7, 1/ 7 T x = ; ( ) 2 4 / 7, 4 / 7, 4 / 7 T Ax = ; нормализацией получаем ( ) 3 1/ 3,1/ 3,1/ 3 T x = ; ( ) 3 2 / 3, 4 / 3, 1/ 3 T Ax = и нормализацией получаем ( ) 4 2 / 7, 4 / 7, 1/ 7 T x = , что то же са- мое, что и 1 x с зацикливанием вместо сходимости. 7.4. ВЫЧИСЛЕНИЕ СОБСТВЕННОГО ВЕКТОРА Вычисление главного собственного вектора основано на использовании теоре- мы 7.13. Она утверждает, что нормализованные строчные суммы степеней прими- тивной матрицы (и, следовательно, положительной матрицы) в пределе дают иско- мый собственный вектор. Поэтому краткий вычислительный способ получения дан- ного вектора – возводить матрицу в степени, каждая из которых представляет собой квадрат предыдущей. Строчные суммы вычисляются и нормализуются. Вычисления прекращаются, когда разность между этими суммами в двух последовательных вы- числениях меньше заранее заданной величины. 7.5. СОГЛАСОВАННОСТЬ Обратносимметричные неотрицательные матрицы могут иметь комплексные соб- ственные значения. Следовательно, они не допускают просто общей характеристи- ки. Однако поскольку максимальное собственное значение лежит между наиболь- шей и наименьшей из строчных сумм, согласованная матрица имеет собственное значение, равное сумме любого из ее столбцов. Как будет показано, малое возму- щение не сильно меняет максимальное собственное значение и остальные собствен- ные значения находятся в окрестности нуля, причем их сумма – действительное чис- ло. Выбор возмущения, наиболее соответствующего описанию влияния несогласо- ванности на вычисляемый собственный вектор, зависит от психологического про- цесса, имеющего место при заполнении матрицы попарных сравнений исходных 166 данных. Предположим, что все возмущения, заслуживающие внимания, могут ( быть сведены к общему виду ( ) ij i j ij a ω ω ε = . Согласованность имеет место, если 1 ij ε = Например, ( ) ( ) ( ) 1 i j ij i j j i ij a a ω ω ω ω ω ω + = + Теперь получим некоторые элементарные, однако существенные результаты для согласованных матриц. Начнем с выражения ( ) max 1 n ij j i j a λ ω ω = = ∑ , которое является i -й компонентой max A ω λ ω = , и определим ( ) 2 1 1 n i i n µ λ = = − − ∑ Тогда из 1 n i i n λ = = ∑ следует, что ( ) ( ) max 1 n n µ λ = − − ; max 1 λ λ ≡ , и так как ( ) max 1 ij j i j i a λ ω ω ≠ − = ∑ , находим, что ( ) ( ) max 1 ij j i ji i j i j n n n a a λ ω ω ω ω ≤ < ≤ − = + ∑ , поэтому ( ) ( ) ( ) max 1 1 1 1 1 1 1 ij j i ji i j i j n n n a a n n n n n λ µ ω ω ω ω ≤ < ≤ − = = − + + − − − − ∑ Подставляя ( ) , 0 ij i j ij ij a ω ω ε ε = > , приходам к уравнению ( ) ( ) 1 1 1 1 1 ij ij i j n n n µ ε ε ≤ < ≤ = − + + − ∑ Заметим, что при 1 ij ε → , т. е. при достижении согласованности, 0 µ → . Кроме того, µ выпукла по ij ε , поскольку ( ) 1 ij ij ε ε + выпукло (и имеет минимум при 1 ij ε = ) и сумма выпуклых функций выпукла. Поэтому µ мало или велико в зависимости от того, близка или далека величина ij ε от единицы соответственно (т. е. близки или далеки мы от согласованности). Наконец, если напишем 1 ij ij ε δ = + , то при 1 ij δ > − имеем ( ) 2 2 1 1 1 1 ij ij i j n ij n n δ µ δ δ ≤ < ≤ = − − + ∑ |