Т. Саати Принятие решений. Т. саати принятие решений метод анализа иерархий
 Скачать 4.58 Mb.
|
|
ЧАСТЬ III ТЕОРИЯ Обратносимметричные матрицы – Системы с обратной связью – Краткое сравнение с другими работами. Теперь вновь займемся формальной стороной предмета, определив и охаракте- ризовав иерархии и нелинейные сети. При этом исследуем свойства обратносиммет- ричной матрицы парных сравнений и устойчивость ее максимального собственного значения и соответствующего собственного вектора. Глава 7 посвящена теории Перрона-Фробениуса и свойствам согласованных и обратно-симметричных матриц. В гл. 8 излагается метод Варфильда структурирования систем, а также наша теория приоритетов, обобщенная на системы. В гл. 9 кратко обсуждаются шкалирование и теория полезности, включая работу Терстена и процедуру наименьших квадратов. 154 ГЛАВА 7 ПОЛОЖИТЕЛЬНЫЕ ОБРАТНОСИММЕТРИЧНЫЕ МАТРИЦЫ И ИХ СОБСТВЕННЫЕ ЗНАЧЕНИЯ 7.1. ВВЕДЕНИЕ В гл. 4 определены функция приоритетов и вектор приоритетов ω в иерархии H . Как известно читателю, способ нахождения приоритетов наиболее важен в на- шем методе. Для матрицы A действительных чисел, представляющих попарные сравнения важности элементов на одном уровне H по отношению к одному элемен- ту расположенного выше уровня, определяются наибольшее собственное значение max λ и решение уравнения max A ω λ ω = Поэтому наши интересы направлены на изучение квадратных матриц ( ) ij A a = , для которых 0, , 1, , ij a i j n > = … , и 1 , , 1, , ji ij a a i j n = = … , т. е. положительных, обратносимметричных. квадратных матриц. Особую важность приобретают матрицы, не только обладающие приведенными выше свойствами, но и являющиеся согласованными, что означает наличие такого важного соотношения: , , , 1, , ik ij jk a a a i j k n = = … В этой главе рассматривается та часть теории матриц, которая необходима для обоснования математических свойств нашего метода (см. определения в Приложе- нии 1). Начнем систематическое изложение с введения понятия неприводимой матрицы. Весь нужный материал по неприводимым матрицам, используемый в книге, приве- ден в следующем разделе. Затем изложим фундаментальную теорему Перрона- Фробениуса для неотрицательных неприводимых матриц, которая обеспечивает су- ществование единственного решения задачи о собственном значении. Так как рас- сматриваемые обратносимметричные матрицы положительны, сконцентрируем вни- мание на положительных матрицах, теореме Перрона и ее доказательстве. Далее доказывается, что искомый собственный вектор может быть получен как предельная сумма строк k A , где A – примитивная матрица. Затем кратко описывается способ вычисления собственного вектора на практике, после чего обсуждаются согласован- ность обратносимметричной матрицы, отклонение ее главного собственного значе- ния от n , нечувствительность этого собственного значения по отношению к малым возмущениям в A , а также изучаются свойства согласованных матриц. Далее рассматриваются характеристики обратносимметричных матриц и их пра- вых и левых собственных векторов, а также вопрос о том, что малые возмущения элементов обратносимметричной матрицы вызывают малые возмущения компонент ее главного собственного вектора. В том же разделе приводится формула, принад- лежащая Варгасу, для величины возмущения, которое получает каждая компонента собственного вектора как функция возмущения исходной матрицы. 155 7.2. НЕПРИВОДИМЫЕ МАТРИЦЫ Обратносимметричные матрицы попарного сравнения не содержат нулей, следо- вательно, они всегда неприводимы. Понятие неприводимости понадобится при рас- смотрении общем системы в гл. 8, где придется иметь дело именно с неприводимы- ми, а не просто положительными матрицами. Определение 7.1. Квадратная матрица – неприводимая (по отношению к пере- становкам), если она не может быть представлена в виде 1 2 3 0 A A A , где 1 A и 2 A – квадратные матрицы, 0 – нулевая матрица. В противном случае матрицу называют приводимой. Следующая матрица — приводима: 2 0 1 1 3 4 3 0 2 A − = Граф, соответствующий этой матрице, имеет дугу из первой в первую и третью вершины и аналогично из третьей в первую и третью вершины, но переход во вто- рую вершину невозможен. Со второй вершины можно перейти во все три вершины. Таким образом, первая и третья вершины образуют неприводимую компоненту, а вторая связана с ними. Очевидно, меняя местами второй и третий столбцы, а также вторую и третью строки, рассматриваемую матрицу можно привести к виду 1 2 3 2 0 1 0 1 3 4 3 0 2 A A A A − = = где 1 A и 3 A – квадратные, 1 A – неприводимая матрицы. Следующая теорема касается эквивалентности свойства неприводимости матри- цы и сильной связности направленного графа матрицы. Теорема 7.1. Комплексная матрица A неприводима в том и только в том слу- чае, если ее направленный граф ( ) D A — сильно связный. Доказательство этой теоремы довольно очевидно. Любая степень приводимой матрицы A также приводима и, следовательно, имеет блок нулей в правом верхнем углу. Поэтому не существует пути между вершинами, соответствующими 1 A , и вер- шинами, соответствующими 2 A и 3 A . Наоборот, если граф не сильно связный, то существует блок вершин, которые не могут быть достигнуты, и подходящими пере- становками соответствующая матрица может быть приведена к указанной выше форме. Теорема 7.2. Квадратная матрица или неприводима, или может быть приведена путем перестановок индексов к виду: 1 2 1,1 1,2 1, 1 ,1 ,2 , , 1 0 0 0 0 0 0 0 0 0 0 0 0 0 k k k k k k m m m k m k m A A A A A A A A A A A A + + + + + … … … … … … … … … … , 156 содержащему блок – диагональную матрицу с неприводимыми матрицами ( ) 1, , i A i k = … на диагонали. При этом, по крайней мере, одна из матриц с двойным индексом в каждой строке, в которой они появляются – ненулевая (см. [52, 53]). Доказательство теоремы проводится в предположении, что если матрица приво- дима и может быть представлена в виде, данном в определении приводимой матри- цы, или же ее диагональные блоки приводимы, то она вновь может быть представ- лена в такой форме. В свою очередь, если какой-либо из ее диагональных блоков приводим, он вновь представляется в соответствии со стандартной формой приво- димой матрицы. В результате после соответствующей перестановки индексов, полу- чим матрицу, все элементы которой над диагональными блоками равны нулю; все диагональные блоки неприводимы. Кроме того, соответствующей перестановкой ин- дексов все строки, диагональные блоки которых только ненулевые матрицы, могут быть расположены так, чтобы распасться на части, как уже было показано выше. Отметим, что каждый; из «изолированных» блоков 1 , , k A A … достижим в графо- теоретическом смысле, из узлов, соответствующих строкам с двумя индексами, но не наоборот. Заметим также, что все матрицы с двумя индексами в каждом столбце могут быть просто записаны в виде строки блоков 1 2 , , , k R R R … , Q , где Q , конечно, уже не является неприводимым. Приведенная выше форма является единственной с точностью до перестановок блочных индексов. Можно было бы закончить и транспонированной формой, в которой блоки 1 2 , , , k R R R … , Q образуют последний столбец нашей матрицы. Действительно, это та форма, которая будет использоваться позже, при рассмотрении «стохастических» матриц приоритетов. Процесс построения нормальной формы матрицы приоритетов – прямой. Начина- ем с любого элемента и заполняем в его столбце ненулевые приоритеты воздействий как компоненты собственного вектора всех тех элементов, которые имеют воздейст- вие на него. Каждый из этих элементов, в свою очередь, входит в примыкающие столбцы со входящими ненулевыми приоритетами воздействий всех других элемен- тов на них. Процесс продолжается до тех пор, пока еще есть новые элементы, кото- рые влияют на это множество. Следует удостовериться в том, что новых элементов больше нет. Так получаем блок для неприводимого множества. Начиная с другого элемента, процесс повторяется для следующего блока и т. д. 7.3. СУЩЕСТВОВАНИЕ И ЕДИНСТВЕННОСТЬ ГЛАВНЫХ СОБСТВЕННЫХ ВЕКТОРОВ Как указывалось ранее, сначала будет представлена общая теорема существова- ния и единственности при решении задачи о собственном значении для неотрица- тельной неприводимой матрицы (более общей, чем положительная обратносиммет- ричная матрица). Это фактически и есть теорема, доказанная Фробениусом, который обобщил результат Перрона для положительной матрицы. Затем следует обсуждение и доказательство теоремы Перрона. Доказательство теоремы Фробениуса может быть найдено в [53]. Теорема 7.3. (Перрон–Фробениус). Пусть 0 A ≥ – неприводимая матрица. То- гда: 1. A имеет действительное положительное простое (т. е. не кратное) собствен- ное значение max λ , которое по модулю не меньше любого другого собственного зна- чения матрицы A (некоторые из которых могут быть комплексными числами). 157 2. Собственный вектор A , соответствующий собственному значению max λ , имеет положительные компоненты и, по существу (с точностью до постоянного множите- ля), единственен. 3. Число max λ (иногда называемое корнем Перрона матрицы A ) удовлетворяет условию ( ) ( ) max 1 0 0 1 max min min max i i i n x x i n i i Ax Ax x x λ ≤ ≤ ≥ ≥ ≤ ≤ = = ; 0 x ≥ – произвольно. Следствие. Пусть 0 A ≥ неприводима и пусть 0 x ≥ произвольно. Тогда корень Перрона удовлетворяет условию ( ) ( ) max 1 1 min max i i i n i n i i Ax Ax x x λ ≤ ≤ ≤ ≤ ≤ ≤ , Теорема 7.4. (Перрон). В этой теореме утверждается то же, что и в предыду- щей, с той разницей, что матрица 0 A > (и, следовательно, неприводима) и модуль max λ строго превосходит модули всех других собственных значений. Краткое доказательство теоремы Перрона может быть получено как результат доказательства следующих полезных фактов о положительных ( ) n n × - матрицах [25]. Последовательность этих фактов такова: пусть A – положительная ( ) n n × -матрица, max λ – ее наибольшее собственное значение. 1. max λ ограничено сверху и снизу соответственно максимальной и минимальной строчными суммами матрицы A Следовательно, если A – стохастическая матрица, т. е. если её строчные суммы равны единице, то max 1 λ = 2. Для стохастической матрицы A lim k k A e υ →∞ = , где υ – положительный вектор-строка, ( ) 1 2 , , , n υ υ υ υ = … , 1 1 n i i υ = = ∑ и ( ) 1,1, ,1 T e = … 3. Для положительной матрицы A существует положительное число λ , ненуле- вая вектор-строка υ и ненулевой вектор-столбец ω , такие, что lim k k k A ωυ λ →∞ = 4. λ есть наибольшее собственное значение A и называется главным собствен- ным значением, а ω и υ – главные собственные векторы, единственные с точно- стью до постоянного множителя. 5. ω ортогонален всем не главным собственным векторам-столбцам, а υ – всем не главным собственным векторам-строкам. б. Если 1 λ – наибольшее собственное значение A , причем i j λ λ ≠ , i j ≠ , , 1, , i j n = … , и если i ω – правый собственный вектор, соответствующий i λ , то 1 lim k T k k A e c e A e ω →∞ = Эту важную теорему, сформулированную в таком виде, очень легко доказать. Но ее можно и обобщить. 158 7. Теорема верна и в случае, когда 0 A ≥ , 0 p A > для некоторого 0 p ≥ при тех же прочих условиях. Теорема 7.5. 1. max 1 1 max 1 1 min max ; min max n n ij ij j j i i n n ij ij i i j j a a a a λ λ = = = = ≤ ≤ ≤ ≤ ∑ ∑ ∑ ∑ Неравенство имеет место, когда суммы не одинаковы. 2. ( ) 1/ max lim k k k tr A λ →∞ = 3. 1 1 max 0 0 max min min max n n ij j ij j j j i u u i i i a u a u u u λ = = > > = = ∑ ∑ 4. 1 1 max 0 0 max min min max n n ij i ij i i i j u u j j j a u a u u u λ = = > > = = ∑ ∑ Доказательство. Компоненты вектора Ae представляют собой суммы строк мат- рицы A . Пусть наибольшая сумма строк есть M , а наименьшая – m . Тогда me Ae Me ≤ ≤ , а равенство имеет место только при m M = Из выражения max A υ λ υ = имеем max Ae e υ λ υ = , max me e Me υ λ υ υ ≤ ≤ Если теперь разделим неравенство на положительное число e υ , то получим max m M λ ≤ ≤ , причём равенство вновь будет иметь место, если m M = . Аналогично для сумм столбцов. Доказательство (2) получается либо из выражения 1/ 1/ lim 1 1 1 lim k k k k k k k tr A tr A λ λ →∞ →∞ = = , либо из 1 k k k n tr A λ λ + + = … . Пусть во втором случае 1 max λ λ = , тогда ( ) ( ) 1/ 1 2 1 1 1 k k k k n tr A λ λ λ λ λ + + + = … , при k → ∞ , 1 k tr A λ → . Остальная часть доказательства здесь не приводится. Теорема 7.6. Если A – положительная ( ) n n × -матрица, у которой сумма эле- ментов каждой строки равна единице, то существует положительная вектор-строка υ , 1 1 n i i υ = = ∑ , такая, что lim m m A e υ →∞ = , где ( ) 1,1, ,1 T e = … Доказательство. Пусть 0 y – любой n -мерный вектор-столбец. Определим 0 m m y A y = и пусть m a и m b – максимальная и минимальная компоненты m y соответ- ственно. Пусть α – минимальный элемент матрицы A . Так как 1 m m y Ay + = , любая 159 компонента вектора 1 m y + получается умножением строки A на m y , и, следователь- но, имеем следующие границы для произвольной компоненты c вектора 1 m y + : ( ) ( ) 1 1 m m m m b a c b a α α α α − + ≤ ≤ + − Это неравенство остается в силе для наибольшей и наименьшей компонент m r y + , от- куда ( ) 1 1 m m m a b a α α + ≤ + − (следовательно, m a монотонно возрастает) и ( ) 1 1 m m m b a b α α + − + ≤ (следовательно, m b монотонно убывает), или ( ) 1 1 m m m b b a α α + − ≤ − − − и ( )( ) 1 1 1 2 m m m m a b a b α + + − < − − Отсюда по индукции получаем ( ) ( ) 0 0 1 2 m m m a b a b α − ≤ − − Так как правая часть этого неравенства стремится к нулю, то m a и m b сходятся к общему пределу, и. следовательно, все компоненты m y приближаются к нему же, т. е. lim m m y Ce →∞ = при 0 0 b C a ≤ ≤ (равенство имеет место только при 0 0 a b = ). Пусть ( ) 1 2 0 0 0 0 , , , n y y y y = … , где 0 1 i y = , 0 0 j y = , j i ≠ . Тогда m y есть i -й столбец матрицы m A , и, как уже установлено, ( ) , , T T m i i y c c υ → ≡ … , причем 0 0 b = , 0 0 i c b > = . Сле- довательно, lim m m A e υ →∞ = Отметим, что поскольку каждая строчная сумма m A равна единице, то 1 1 n i i υ = = ∑ |