Т. Саати Принятие решений. Т. саати принятие решений метод анализа иерархий
 Скачать 4.58 Mb.
|
|
Характеристическое уравнение: собственные значения и собственные векторы Собственный вектор (характеристический вектор) матрицы A – это такой нену- левой вектор w , что Aw w λ = , или ( ) 1 A λ преобразует w в w , т. е. оставляет w инвариантным. Величины λ , соответствующие такому w , называются собственными значениями (характеристическими значениями) матрицы A . Следовательно, w бу- дет собственным вектором, если он является нетривиальным (т. е. ненулевым) ре- шением уравнения ( ) 0 A I w λ − = для некоторого числа λ . Компоненты w состав- ляют множество решений однородной линейной системы с матрицей A I λ − . Такая система фактически имеет тривиальное решение 1 0 n w w = = = … , где ( ) 1 , , n w w w = … . Но для получения нетривиального решения матрица A I λ − должна быть вырожденной, т. е. ее определитель A I λ − должен быть равен нулю. Этот оп- ределитель представляет собой полином n -й степени от λ . Он имеет вид 240 ( ) ( ) 1 1 1 det n n n a A λ λ − − + + − … и называется характеристическим полиномом матрицы A . Условие равенства определителя нулю ведёт к уравнению n -й степени, которое называется характеристическим уравнением матрицы A . Это уравнение согласно теореме Гамильтона–Кэли тождественно равно нулю, если λ заменить на A , (т. е. получая матричное уравнение). Корни i λ , л,-, 1, , i n = … , характеристического уравнения 0 A I λ − = являются искомыми собственными значениями. Основная теорема алгебры утверждает существование n -корней для полиномиального урав- нения степени n . Собственные векторы получаются в результате решения соответ- ствующей системы уравнений i i i Av v λ = . Следует обратить внимание на получение всех собственных векторов, когда имеются кратные корни. Отметим, что ( ) 1 1 n ii i a a tr A = = = ∑ , и корни характеристического уравнения, являясь корнями уравнения n -й степени, удовлетворяют ( ) 1 1 n i i a tr A λ = = = ∑ и 1 n i i A λ = = ∏ Это можно увидеть, разлагая факторизацию ( )( ) ( ) 1 2 n λ λ λ λ λ λ − − − … характери- стического полинома. Отметим, что характеристическое уравнение может иметь кратные корни, и, следовательно, общее число различных корней может быть мень- ше, чем n . Очевидно, что кратный корень i λ , кратности k появится в факторизации в виде ( ) k i λ λ − . Для простого корня 1 k = Так как λ – постоянная, из Aw w λ = и A A λ λ = имеем ( ) ( ) ( ) 2 2 A w A Aw A w Aw w w λ λ λ λ λ = = = = = Следовательно, 2 λ – собственное значение 2 A и аналогично k λ – собственное зна- чение k A , т. е. 1 k k k n trA λ λ = + + … Пример. Рассмотрим матрицу 1 2 3 4 A = , 1 0 0 1 I = , 0 0 I λ λ λ = , 1 2 3 4 A I λ λ λ − − = − , ( )( ) 2 1 4 6 5 2 0 A I λ λ λ λ λ − = − − − = − − = Так как в данном случае характеристическое уравнение квадратное, решим его, используя хорошо известную квадратичную формулу для нахождения корней такого уравнения. Для собственных значений имеем 1 5 33 2 λ + = , 2 5 33 2 λ − = , и чтобы получить собственный вектор, соответствующий 1 λ , запишем 1 Aw w λ = , т.е. 241 1 1 1 2 2 1 2 3 4 w w w w λ = , или 1 2 1 1 2 w w w λ + = , откуда 1 2 1 2 3 4 w w w λ + = Так как матрица 1 A I λ − – вырожденная, существует зависимость между её стро- ками, и поэтому второе уравнение не содержит новой информации. Собственный вектор w получается в результате присваивания произвольного значения 2 w и вы- числения 1 w согласно полученному выше соотношению. Присвоим 2 w значение 1. Тогда имеем 1 2 , 1 1 w λ = − Можно нормализовать w , приравнивая сумму коэффициентов единице. Разделим каждый коэффициент на сумму 1 2 w w + , которая равна ( )( ) 1 1 1 1 λ λ + − . Получим ре- зультирующий нормализованный вектор 1 1 1 1 2 , 1 1 λ λ λ − + + Поскольку умножение на постоянную не влияет на решение уравнения Aw w λ = , будем рассматривать собственные векторы w всегда в нормализованном виде. Ана- логично можно получить собственный вектор, соответствующий 2 λ . Собственные значения как корни любого полиномиального уравнения можно получить, используя различные стандартные численные методы. В настоящее время существуют пакеты компьютерных программ для нахождения этих корней. Для уравнения, являющегося характеристическим уравнением матрицы, существуют компьютерные программы, которые для данной матрицы находят собственные векторы. Собственные значения матрицы, будучи корнями ее характеристического урав- нения, могут быть комплексными числами и, следовательно, попарно комплексно- сопряженными. Напомним, что комплексное число имеет вид a ib + , где 1 i = − , a и b – действительные числа. Модуль такого числа обозначается a ib + и равен ( ) 1/ 2 2 2 a b + . Если элементы матрицы – действительные и она симметричная, все ее собственные значения действительны. Собственные ректоры, соответствующие раз- личным собственным значениям, ортогональны. Этим же свойством обладает эрми- това матрица. Матрицы A и T A имеют одни и те же собственные значения, но в общем случае не одни и те же собственные векторы. Следующая теорема (см. [48]) может быть применена к i ij ij j w a w ε = , если использовать непрерывное преобразование, например логарифмическую функцию. Теорема утверждает, что собственные значения матрицы непрерывно за- висят от ее коэффициентов (это то же, что непрерывная зависимость корней поли- нома от его коэффициентов). 242 Теорема. Если произвольная матрица ( ) ij A a = имеет собственные значения 1 2 , , , s λ λ λ … , где кратность j λ есть j m с 1 s j j m n = = ∑ , то при заданном, достаточно ма- лом 0 ε > существует ( ) 0 δ δ ε = > , такое, что при ij ij ij ij a a ε ε δ + − = ≤ для , 1, , i j n = … матрица ( ) ij ij B a ε = + имеет ровно j m собственных значений в окруж- ности j µ λ ε − < для каждого 1, , j s = … , 1 , , n µ µ … являются собственными значе- ниями B Доказательство. Определим ( ) ( ) , det f B I B µ µ = − Пусть 1 2 0 min 1 i j i j s ε λ λ = − ≤ < ≤ и 0 ε ε < . Окружности : j j C µ λ ε − = , 1, , j s = … – непересекающиеся. Пусть ( ) min , j r f A µ = для µ на j C . Заметим, что ( ) min , f A µ определен, так как f – непрерывная функция µ . Также 0 j r > , по- скольку корни ( ) , 0 f A µ = являются центрами окружностей. Определитель ( ) , f B µ – непрерывная функция 2 1 n + переменных и ij ij a ε + , , 1, , i j n = … , и, следовательно, для некоторых 0 δ > , ( ) , 0 f B µ ≠ , для µ на любой j C , 1, , j s = … , если ij ε δ ≤ , , 1, , i j n = … . Из теории функций комплексной пере- менной известно, что число j m корней µ уравнения ( ) , 0 f B µ = , лежащих внутри окружности j C , определяется формулой ( ) ( ) ( ) , 1 2 , j j C f B n B d i f B µ µ π µ ′ = ∫ , 1, , j s = … , которая из-за ( ) , 0 f B µ ≠ является непрерывной функцией 2 1 n + переменных в j µ λ ε − = , ij ε δ ≤ , , 1, , i j n = … . В частности, это непрерывная функция ij ij a ε + при ij ε δ ≤ Теперь для B A = по предположению имеем ( ) j j n A m = , 1, , j s = … . Так как ин- теграл непрерывен, не может быть скачка с ( ) j n A на ( ) j n B , они должны быть рав- ны и иметь общее значение j m , 1, , j s = … для всех B с ij ij ij a a ε δ + − ≤ , , 1, , i j n = … Существуют различные способы оценки max λ , здесь представлен один из хорошо известных: ( ) 1/ 2 2 max lim k k k trA λ →∞ = Например, для обратносимметричной матрицы размерности 3 3 × 4 12 23 13 13 12 23 4 4 3 19 a a a trA a a a = + + 243 Аналогичное вычисление для обратносимметричной матрицы размерности 4 4 × дает 4 12 23 13 13 34 12 24 14 14 13 12 23 14 12 24 14 13 34 4 4 4 4 4 4 4 34 a a a a a a a a a trA a a a a a a a a a = + + + + + + + 13 34 13 24 13 24 12 23 34 12 24 14 13 34 12 24 14 23 14 23 14 12 23 34 a a a a a a a a a a a a a a a a a a a a a a a a + + + + + + Отметим, что слагаемые компенсируют друг друга, так как коэффициент в числи- теле одного члена также появляется в знаменателе следующего. Поэтому возраста- ние этого коэффициента увеличивает один член и уменьшает другой. В общем слу- чае это неверно для необратносимметричных матриц. Часто встречаются функции матрицы A , такие, как степени и экспоненты. Имеет смысл рассмотреть такие функции. Существует следующая теорема из этой области, принадлежащая Сильвестру (см. [49]): ( ) ( ) ( ) ( ) ( ) 1 1 0 ! i m m k m i i i i m A I f A f Z m λ λ λ − = = − ∑ ∑ Здесь k – количество различных характеристических значений матрицы A ; i m – кратность i -го корня i λ ; ( ) ( ) m i f λ – (формальная) производная f m -го порядка, вычисленная при i λ ; ( ) i Z λ – полные ортогональные идемпотентные матрицы мат- рицы A , т. е. они обладают свойствами ( ) 1 k i i Z I λ = = ∑ ; ( ) ( ) 0 i j Z Z λ λ = , i j ≠ ; ( ) ( ) 2 i j Z Z λ λ = , где I и O – единичная и нулевая матрицы соответственно. При различных характеристических значениях для матрицы A порядка n имеем [64] ( ) ( ) ( ) 1 n i i i f A f Z λ λ = = ∑ , где ( ) ( ) ( ) i j i i i j j i I A Z λ λ λ λ ≠ ≠ − = − ∏ ∏ Для иллюстрации того, как это получается когда f является полиномом матрицы A , отметим, что из полинома n -й степени 0 I A λ − = матрица n A может быть вы- ражена через низшие степени A и, следовательно, f всегда может быть сведена к полиному степени, не превышающей 1 n − . Если написать ( ) ( ) 1 1 n i j i j j i f A A I α λ = = ≠ = − ∑ ∏ и умножить выражение справа последовательно на i v , 1, , i n = … – характери- стический вектор i λ с учетом того, что i i i Av v λ = , и, следовательно, ( ) ( ) i i i f A v f v λ = , то получим 244 ( ) ( ) i i i j j i f λ α λ λ ≠ = − ∏ , что и дает искомый результат. При ( ) ( ) exp f A At = и различных характеристических значениях A имеем спек- тральное разложение ( ) f A , заданное выражением ( ) ( ) ( ) 1 exp n i i i f A t Z λ λ = = ∑ Случай кратных характеристических корней выводится из иного варианта теоре- мы Сильвестра. Если напишем для краткости ( ) ( ) 1 k i i f A T λ = = ∑ , где k – количество различных корней, тогда ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 2 3 ! i i i i i i m i i m i m i f T f Z f Z Z z λ λ λ λ λ λ λ − − − ′′ ′ = + + +… Здесь i m относится к кратности корня i λ , а ( ) ( ) ( ) 1 ! i i i i i m m i m i m F d Z m d λ λ λ λ λ λ = = ∆ , где ( ) ( ) ( ) ( ) 1 1 ! 1 i n m m m m i i i j i F m I A I A λ λ λ − − − − ≠ = − − − ∏ есть производная F порядка m , а ( ) ( ) i m i j i λ λ λ ≠ ∆ = − ∏ Заметим, например, что ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 2 F F F d Z d λ λ λ λ λ λ λ λ λ ′ ′ ∆ − ∆ = = ∆ ∆ Рассмотрим систему x x y = + , y x y = − , или просто X AX = , x X y = , 1 1 1 1 A = − Исходя из формулы Сильвестра при 1 2 λ = , 2 2 λ = − , имеем ( ) ( ) ( ) ( ) ( ) 1 2 2 1 1 2 2 1 exp exp exp t t At A I A I λ λ λ λ λ λ λ λ = − + − − − , и применим ее для получения решения системы. Аналогично можно показать, что если 2 1 1 2 B = , то |