Н.И. Яцкин - Линейная алгебра (Теоремы и алгоритмы) (1109879), страница 21
Текст из файла (страница 21)
е. описания (10.11) являются экономными. (Впрочем, данный алгоритм, как и предыдущий, с небольшими модификациями, будетработать и в случае наличия в данных матрицах лишних столбцов.)Будем стремиться изменить матрицу B2 и перейти к другому заданию подпространства W2 :W2 = RB20 ,(10.12)такому, в котором (n × r2 )-матрица B20 снова имеет полный ранг постолбцам, но, кроме того, содержит B1 в качестве (начальной слева)подматрицы. Тогда столбцы B20 будут составлять искомый базис вW2 , продолжающий базис в W1 , образованный столбцами B1 , а добавочные столбцы c1 , c2 , ... , cp (где p = r2 − r1 ), дополняющие базисв W1 до базиса в W2 , составят базис некоторого прямого дополненияU к подпространству W1 в подпространстве W2 .
Матрица C, размера n × p, составленная из добавочных столбцов, будет определять(вторым способом) подпространство U.Опишем ход работы алгоритма более детально.1. Составляем матрицу-конкатенацию¯µ¶¯M= B1 ¯¯ B2(10.13)n×(r1 +r2 )n×r1 n×r2столбцы которой образуют (избыточную) порождающую с.в. для W2 .Найдем подсистему в этой с.в., являющуюся базисом в W2 и содержащую все столбцы матрицы B1 .2. С этой целью приводим матрицу (10.13), с помощью элементарных преобразований над строками, к ступенчатому виду M 0 .§ 10Алгоритмы построения базисов в подпространствах117[Как и в алгоритме 10.2, здесь не возбраняются (сопровождаемыеметками) перестановки столбцов, внутри каждой из зон по отдельности; ни в коем случае нельзя "заступать" за вертикальную черту,разделяющую зоны.
Хотя, скорее всего, какие-либо перестановкистолбцов могут потребоваться лишь при работе с неподготовленными матрицами, содержащими лишние столбцы.]В ступенчатом виде, в первой зоне (на месте блока B1 ) ступеньки будут идти подряд (в количестве r1 ); во второй зоне образуетсяp = r2 − r1 ступенек (идущих уже не обязательно подряд).3. Векторы, проходящие через ступеньки M 0 , собираем (в их исходном виде, как в матрице M ) в новую матрицу¯µ¶¯B20 = B1 ¯¯ C ,(10.14)n×r2n×r1 n×pв которой уже содержится подматрица B1 и фигурируют добавочныевекторы-столбцы матрицы C, дополняющие базис в W1 , заключенный в матрицу B1 , до базиса в W2 .4. Столбцы матрицы C составляют базис подпространстваU = RC = hc1 , c2 , ...
, cp i(10.15)в пространстве W2 , являющегося прямым дополнением к W1 , т. е.имеет место равенствоW2 = W1 ⊕ U.(10.16)Замечание 10.2. Важным частным случаем применения алгоритма 10.4 является случай, когда бо́льшее подпространство W2 совпадает со всем пространством V. В такой ситуации, в качестве базисаво втором подпространстве, естественно выбрать естественный базис, элементы которого составляют единичную матрицу: B2 = En ;дополнительные векторы будут набираться из числа единичных векторов e1 , ... , en .10.3.
Алгоритмы построения базисов в сумме и пересечении линейных подпространств. Рассмотрим два (произвольных) линейных подпространства, W1 и W2 , в линейном пространстве V = P n и, вместе с ними — их пересечение W0 = W1 ∩ W2и сумму W3 = W1 + W2 (см. диаграмму 8.1). Сохраним обозначения пункта 8.2 для размерностей рассматриваемых подпространств:di = dim(Wi ) (i = 0, 1, 2, 3).118Линейные пространства. Базисы и размерностиГл.
1Переходим к описанию пятого алгоритма, обеспечивающего построение базиса в сумме двух линейных подпространств (определение суммы см. в п. 8.1).А л г о р и т м 10. 5.Построение базиса в сумме W3 = W1 + W2двух линейных подпространств W1 , W2 6 VЛинейные подпространства W1 и W2 должны быть заданы вторымспособом, причем желательно (но не обязательно) экономное задание(10.11), с теми же предположениями относительно матриц B1 и B2 ,которые были перечислены после указанного описания.
(Если одноили оба подпространства заданы первым способом, то следует предварительно применить алгоритм 10.1.) Матрицы B1 и B2 содержатбазисы подпространств W1 и W2 . Размерности этих подпространствизвестны:di = ri = rank(Bi ); i = 1, 2.1. Так же, как и в предыдущем алгоритме, составляем матрицуконкатенацию M [см. (10.13)], столбцы которой образуют (возможно,избыточную) порождающую с.в. для суммы W3 .2. Приводим (с помощью элементарных преобразований над строками) матрицу M к ступенчатому виду M 0 . (Перестановки столбцов снова допустимы — внутри каждой из двух зон, при условиииспользования меток.) В первой зоне r1 ступенек будут идти подряд.
Подсчитаем количество ступенек p во второй зоне. Размерностьсуммы W3 данных подпространств найдется по формулеd3 = dim(W3 ) = rank(B1 |B2 ) = r1 + p.(10.17)3. Выберем из матрицы B2 добавочные векторы (образы которыхв степенчатом виде M 0 проходят через ступеньки) и составим из нихматрицуC = (c1 |c2 | ... |cp ) .(10.18)n×pМатрица B3 , содержащая базис W3 , определяется как конкатенация¯µ¶¯B3 = B1 ¯¯ C.(10.19)n×d3n×d1n×p§ 10Алгоритмы построения базисов в подпространствах119Этот базис можно охарактеризовать, как базис в W3 , продолжающий заданный базис в W1 .
ФормулаW3 = RB3(10.20)представляет собой экономное задание вторым способым для суммыW3 = W1 + W2 .4. Побочным результатом работы данного алгоритма оказываетсязначение размерности d0 для пересечения W0 = W1 ∩W2 данных подпространств. Оно находится с помощью формулы Грассмана (8.2):d0 = d1 + d2 − d3 .(10.21)Замечание 10.3. В алгоритме 10.5 подпространства W1 и W2 равноправны и конкатенацию вида (10.13) можно записывать, начинаяс матрицы B2 . Тогда, в результате работы алгоритма, будет полученбазис в W3 , продолжающий заданный базис в W2 .Переходим к заключительному алгоритму в данной серии, обеспечивающему построение базиса в пересечении двух линейных подпространств.А л г о р и т м 10.
6.Построение базиса в пересечении W0 = W1 ∩ W2двух линейных подпространств W1 , W2 6 VДля того чтобы можно было применить описываемый ниже алгоритм, линейные подпространства W1 и W2 должны быть заданыпервым способом. Желательно (но не обязательно) экономное задание:W1 = L0A1 ; W2 = L0A2 ,(10.22)где матрицы A1 и A2 имеют полные ранги по строкам и размерыr1 × n и r2 × n соответственно.(Если одно или оба данных подпространства заданы вторым способом, то следует предварительно применить алгоритм 10.3.)Вектор x ∈ V принадлежит подпространству Wi (i = 1, 2) тогда итолько тогда, когда он удовлетворяет однородной с.л.у.Airi ×n· x = 0 ; i = 1, 2.n×1ri ×1(10.23)120Линейные пространства.
Базисы и размерностиГл. 1Он будет принадлежать пересечению W0 тогда и только тогда,когда будет удовлетворять обеим системам (10.23), или, что равносильно, — одной (объединенной) с.л.у.e0A· x =(r1 +r2 )×nn×10(r1 +r2 )×1,(10.24)e0 определяется как стек (вертикальная конкатенация)где матрица Aµe0 =A¶A1A2.(10.25)Теперь все готово к описанию хода работы алгоритма.1. Составляем матрицу (10.25). Подпространство-пересечение W0можно задать первым способом:W0 = L0Ae ,0(10.26)т.
е. как подмножество решений однородной с.л.у. (10.24).Описание (10.26), вообще говоря, не является экономным, но размерность пересечения d0 уже можно вычислить:d0 = n − r0 ,(10.27)e0 ).где r0 = rank(A2. Применяя к подпространству (10.26) алгоритм 10.1, мы, прежде всего, получаем экономное задание этого подпространстваW0 = L0A0 ,(10.260 )где (r0 × n)-матрица A0 является видом Жордана — Гаусса матрицыe0 и имеет полный ранг по строкам.A3. Решая с.л.у.(10.28)A0 · x = 0 ,r0 ×nn×1r0 ×1находим фундаментальную матрицу F0 , размера n × (n − r0 ), содержащую базис в пересечении W0 . (С целью сохранения общего стиляобозначений в описаниях данного и предыдущего алгоритмов можнопереобозначить: F0 = B0 .) Получаем задание подпространства W0вторым способом:W0 = RB0 .(10.29)§ 10Алгоритмы построения базисов в подпространствах1214.
В качестве побочного результата работы алгоритма получается(по формуле Грассмана) значение размерности d3 для суммы W3данных подпространств:d3 = d1 + d2 − d0 .(10.30)Замечание 10.4. Опишем особые ситуции, которые могут возникнуть по ходу работы алгоритмов 10.1 — 10.6 и повлечь то, что можноназвать досрочным выходом из алгоритма.1. В работе алгоритма 10.1 особым можно считать случай, когда матрица A, определяющая (первым способом) линейное подпространство W = L0A 6 V = P n , имеет максимально возможный ранг:rank(A) = n.
Тогда подпространство W является нулевым, искомыйбазис — пустым.2. Аналогично, в работе алгоритма 10.2 особым будет случай,когда максимальный ранг (равный n) имеет матрица G, задающая(вторым способом) подпространство W = RG 6 V = P n . В этомслучае подпространство W совпадает со всем пространством V , иалгоритм выдаст какой-то базис в P n . Но можно этого не дожидаться и взять естественный базис En .3. О крайностях, возможных в работе алгоритма 10.3, мы ужеговорили в замечании 10.1.4. В работе алгоритма 10.4 может проявиться несколько иная особенность.
Пусть вложенные подпространства W1 и W2 (W1 6 W2 )оба заданы вторым способом (не обязательно экономно): Wi = RGi(i = 1, 2). По предположению, rank(G1 ) 6 rank(G2 ) = rank(G1 |G2 ).В ходе работы алгоритма может встретиться ситуация, когдаrank(G1 ) = rank(G1 |G2 ). Это будет свидетельствовать о совпаденииподпространств: W1 = W2 ; добавочные векторы в этом случае отсутствуют; прямое дополнение к W1 в W2 тривиально: W2 = W1 ⊕O.На самом деле ситуация еще сложнее (и интереснее). По "внешнему виду" матриц G1 , G2 никак не усматривается взаимное расположение соответствующих подпространств W1 , W2 и, в частности,наличие (или отсутствие) включения (или даже равенства) междуними.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
