Главная  Методы условной оптимизации 

[0] [1] [2] [3] [4] [5] [ 6 ] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

2.2.3.4. Собственные значения; собственные векторы. Для любой квадратной матрицы найдется хотя бы одно специальное число (возможно, комплексное) и соответствующий ему ненулевой вектор «, такие, что

Аи=Хи, (2.18)

т. е. преобразование вектора и матрицей А сводится к умножению на X. Число X называют собственным значением матрицы А, вектор и - ее собственным вектором, отвечающим собственному значению У.. Например, число Х=2 является собственным значением матрицы

поскольку

Собственный вектор и всегда определен с точностью до произвольного множителя: умножение его на любое число не нарушит равенства (2.18). Последнее можно переписать следующим образом: (А-Х1)и=0.

Отсюда видно, что если К - собственное значение матрицы А, то матрица А - 1 оказывается вырожденной. Набор всех собственных значений матрицы Л часто обозначают через {?1(1Л1}.

Полезной характеристикой является функция П (Л) - произведение всех собственных чисел матрицы Л. Эта функция обладает следующим важным свойством: для произвольных матриц Л и В выполняется равенство П(ЛВ)=П(Л)П(В).

Две матрицы называют подобными, когда их наборы собственных значений совпадают. Если W - некоторая невырожденная матрица, произведение WAW~ будет подобным матрице Л, поскольку для ее любого собственного значения К и соответствующего собственного вектора х имеем

Ах=1х, WAW-4Wx)=k{Wx).

Вещественная fiXfi-матрица и-меет п собственных значений (не обязательно различных) и максимум п линейно независимых собственных векторов. В общем случае собственные значения вещественной матрицы - комплексные числа. Нас, однако, за редким исключением, будут интересовать собственные значения симметричных матриц (матриц, удовлетворяющих равенству Л=Л), а последние обладают следующими двумя свойствами:

(1) все собственные значения симметричной матрицы вещественны;

(ii) симметричная fiXn-матрица имеет п различных линейно независимых собственных векторов.

Из собственных векторов симметричной матрицы всегда можно составить ортонормальную систему {Uj}, t=l, 2, . . ., п, т. е. выбрать их так, чтобы иТщ=0, Сфг, u\Ui = \. Иначе говоря, из них можно сформировать ортонормальный базис для iK".

Если Л - невырожденная матрица, все ее собственные значения будут ненулевыми, а обратные к ним числа будут собственными значениями обратной матрицы Л".

Максимальное и минимальное собственные числа симметричной матрицы Л удовлетворяют равенствам

.1 г лт хАк л г лп xFAx

>.„.ЛЛ] = тх. Х,„-,ЛЛ] = тт--.

Спектральным радиусом А называют число р(Л)=тпах1г[Л11

2.2.3.5. Знакоопределенность. Если все собственные значения симметричной матрицы А положительны, ее называют положительно определенной. Если А - положительно определенная матрица, для любого ненулевого вектора х обеспечено неравенство хМа>0. Отсюда, в частности, следует, что все диагональные элементы положительно определенной матрицы должны быть положительными. Аналогично положительной определенности вводится понятие отрицательная определенность. Это - свойство симметричной матрицы, состоящее в том, что все ее собственные числа отрицательны- Если собственные значения симметричной матрицы А неотрицательны, говорят, что она является положительно полуопределенной. Когда среди собственных значений симметричной матрицы А есть и положительные, и отрицательные числа, А называют знаконеопределенной.

2.2.4. ЛИНЕЙНЫЕ УРАВНЕНИЯ

2.2.4.1. Свойства линейных уравнений. Одной из фундаментальных задач вычислительной линейной алгебры является задача поиска решения системы линейных уравнений: заданы т<п-матрица А и т-мерный вектор Ь\ найти /г-мерный вектор х, такой, что

Ах=Ь. (2.19)

В этой постановке вектор b часто называют (по очевидным причинам) правой частью, ах - вектором неизвестных. Как уже говорилось выше, вектор х в (2.19) можно интерпретировать либо как список коэффициентов совпадающей с b линейной комбинации столбцов матрицы Л, либо как вектор, который преобразование Л переводит в Ь.

Для того чтобы система (2.19) имела решение, нужно, чтобы вектор b лежал в подпространстве, натянутом на столбцы Л. Если b принадлежит этому подпространству, систему называют совместной.



Например, система

совместна при любом 6, потому что столбцы А линейно независимы, и соотвегственно натянутое на них подпространство совпадает с 8!.

Система

•2 2

(2.20)

также совместна, поскольку 6 есть линейная комбинация столбцов Л, причем ее решение единственно.

Если вектор b не лежит в подпространстве, натянутом на столбцы Л, систему (2.19) называют несовместной, и в этом случае никакой вектор X равенства (2.19) не обеспечит. Так, заменив правую часть в (2.20), мы получим несовместную систему вида

О 1

(2.21)

и теперь никакая линейная комбинация столбцов А не совпадает с b

Если вектор b совместим с Л, система (2.19) будет иметь единственное решение тогда и только тогда, когда столбиь! Л линейно независимы. Если же в этой ситуации столбцы Л линейно зависимы, у системы (2.19) будет бесконечное множество решений. Чтобы понять, почему это так, вспомним, что в силу линейной зависимости найдется ненулевой вектор г, такой, что Л2=0. Соответственно, если X - некоторое решение системы (2.19), то для любого числа 6 получим

Л (х--6г)=Лх-1-6Лг=Лх=Ь,

т. е. вектор x-]-(iz тоже будет решением (2.19). К примеру, вектор х= (3, О)" есть решение совместной системы

-2\ /3\

О )(М = ( О i

(2.22)

и, так как

\1 2/\1/ \0У

ее решениями будут также векторы вида

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

(i) 11x110 для любого вектора х и lJCl=0 в том и только в том случае, если х=0;

(П) для любого вещественного числа б выполняется равенство 16а11-6х11;

(iii) для любых двух векторов х и у справедливо неравенство 11-«:+</1К1л: + 1/ (неравенство треугольника).

Целое семейство векторных норм. именуе.мых р-норлшми и обозначаемых через определяется формулой вида

l*li=(il.lJ"

При любом целом р она задает функцию, удовлетворяющую требованиям (i) - (iii).

Наиболее часто используются р-иормы с р=1, 2, оо. Квадратичную норму (р=2) иногда называют евклидовой; заметим, что 1л:=4 I-. . .+х,=хх. При р=оо получаем lxlL=niaxjlx,. Например, если х=(,\, -2. -3), то х„=3, л:=6 и Ыг= = /14.

Существует несколько полезньтх неравенств, связывающих значение скалярного произведения двух векторов с их нормами. В частности, рассматривая векторы х, у и у-х как стороны треугольника в 9i" и обозначив через G угол между Jt и , по формуле косинусов получим

lJ/ + *G = lly+llxe-2lJ/jA:l,cose.

Заменив выражение \]у-х\\1 скалярным произведением {у-х)(1)~х) и раскрыв скобки, отсюда придем к равенству

cos е =

!/Гх

а поскольку значение cos в лежит между -1 и +1, это позволяет утверждать, что

l!/x:KllJ:l,ni/ll2.

Данное соотношение называют нераоенство.ч Шварца.



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

(i) iMllO для любой матрицы А и [1Л=0 в том и только в том случае, если А - нулевая матрица; (И) 16Л1-6111Л;

(Ш) Л+В<Л + В. Поскольку матрицы можно перемножать, получая тем самым новые матрицы, целесообразно подчинить матричную норму еще одному условию, а именно потребовать, чтобы

(iv) 1ЛВ<1Л В.

Матричные нормы удобно определять через векторные. Делается это так. Задавшись какой-нибудь векторной нормой . , рассмотрим для матрицы А значения \\Ах\\ при всевозможных х, удовлетворяющих равенству 11x11 = 1. Среди них обязательно найдется максимальное. Его и возьмем в качестве нормы матрицы Л. Такую матричную норму принято называть индуцированной или подчиненней векторной. Итак, 11Л можно определять по формуле

Л1 = шах 1\Ах1 (2.23)

II j; 11=1

где справа стоят векторные нормы и максимум достигается при каком-то (или каких-то) х.

Три нормы тХп-матрицы А, подчиненные трем введенным ранее векторным нормам, таковы:

"" Il"" i5/xn (i*) ~ "зксимум суммы модулей элементов в столбце;

И2= („ах!) -квадратный корень максимального собственного значения симметричной матрицы АА;

iHL-,( Sltjl - максимум суммы модулей элементов в строке.

Квадратичную норму ЦЛЦи иногда называют еще спектральной нормой матрицы.

Помимо трех рассмотренных часто используется так называемая норма Фробениуса \\ которая не подчинена векторной. Она возникает, если интерпретировать mxn-матрицу А как вектор с тп компонентами, и представляет собой его евклидову норму:

Векторная норма . и матричная норма .Г называются согла-сованными, если для любых А и х выполняется неравенство

iHxIKlHiriUII. (2.24)

В частности, оно соблюдено (по определению) для любой пары векторной и подчиненной ей матричной норм, причем на некотором (некоторых) X достигается равенство. Евклидова векторная норма и матричная норма Фробеииуса также являются согласованными.

2.2.4.3. Теория возмущений; число обусловленности. Выше было установлено, что линейная система

Ах=Ь (2.25)

с квадратной невырожденной матрицей Л однозначно разрешима для любой правой части Ь, О том, как искать решения таких систем, речь пойдет ниже. Однако прежде, чем заняться соответствующими методами, полезно рассмотреть вопрос о влиянии на х из (2.25) малых изменений (возмущений) правой части и элементов матрицы.

Точное решение (2.25) даегся формулой х=А-Ь, Точным решением системы с возмущенной правой частью Ь+ЬЬ будет вектор х+6а-, удовлетворяющий равенству

Л (х+6х)=Ы-6Ь.

(«Приставко1» 6 здесь и в дальнейшем помечаются малые приращения векторов или матриц.) Соответственно

х+6х=Л-ЧЫ-6Ь), а так как x=A~b, отсюда ясно, что Ьх=А-т,

Для измерения Ьх воспользуемся какой-нибудь парой совместимых векторной и матричной норм. Это приведет к оценке

6х1<Л-Ч1 6Ы1, (2.26)

где при некотором 6Ь возможно равенство. Таким образом, возмущение точного решения может превосходить возмущение правой части не более, чем в \\A~\\ раз.

Для определения относительного эффекта того же самого возмущения заметим, что

1Ь1<11Л 11x11. (2.27)

С учетом этого неравенства из (2.26) легко получить такое соотношение:

(2.28)

Предположим теперь, что матрица системы (2.25) возмущается на 6Л. Тогда возмущенное решение (2.25) х+бх будет обеспечивать равенство (Л+6Л)(х+6х)=Ь, откуда следует, что

6х=-Л-6Л (х+бх)



[0] [1] [2] [3] [4] [5] [ 6 ] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

0.0016