Н.И. Яцкин - Линейная алгебра (Теоремы и алгоритмы) (1109879), страница 66

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 66)

для H.Реализация намеченного выше плана приводит нас к новой версиитеоремы Жордана [ср. с теоремой 27.2 (БТЖ)].Теорема 30.6 (теорема Жордана). Квадратная матрица приводима к ж.н.ф. тогда и только тогда, когда ее характеристическиймногочлен разлагается на линейные множители; при этом каждомуэ.д. (λ − λi )k отвечает ж.я. Jk (λi ) . ¤Кратко опишем второй (напомним, что его иногда называют "алгебраическим") алгоритм приведения матрицы к ж.н.ф.А л г о р и т м 30. 2.Приведение квадратной матрицык жордановой нормальной формеДана (n × n)-матрица A с элементами из поля P. Требуется определить ж.н.ф. J для матрицы A (если она существует), а также вычислить матрицу перехода T, такую, что J = T −1 AT.384Спектральная теория линейных эндоморфизмовГл.

31. Составляем характеристическую матрицу C(λ) = Eλ − Aи (с помощью алгоритма 30.1) приводим ее к канонической формеСмита S = S(λ); при этом также вычисляются (путем попутногопреобразования единичных матриц U0 = V0 = En ) обратимые квадратные матрицы U = U (λ) и V = V (λ), отвечающие за действия надстроками и столбцами соответственно и такие, что S = U CV. (Длянужд настоящего алгоритма достаточно точно отслеживать преобразования над столбцами, поскольку далее используется лишь матрица V.)2.

Считываем из матрицы S диагональные элементы — инвариантные многочлены: µ1 (λ), µ2 (λ), ... , µn (λ); каждый из них разлагаем на неприводимые множители. Если все они окажутся линейными,т. е. будут иметь вид λ − λi , то ж.н.ф. существует.3. Определяем список характеристических корней (спектр) дляматрицы A, выявляя — по разложению старшего и.м. µn (λ) — всевстречающиеся в (этом и предыдущих) разложениях элементы λi(i = 1, ... , s). Элементы спектра должны быть упорядочены (занумерованы), произвольным (но неизменным в дальнейшем) образом.4. Выявляем — по разложениям всех и.м.

— все элементарныеделители, т. е. примарные множители вида (λ − λi )k в разложениях и.м., и образуем из них список δ(A), руководствуясь следующимпринципом: характеристические корни идут в том порядке, которыйустановлен на предыдущем этапе; отвечающие каждому из них э.д.упорядочены по невозрастанию степеней.5. Составляем блочно-диагональную матрицу J, в которой каждому э.д. (λ − λi )k из списка δ(A) соответствует ж.я. Jk (λi ) . Порядок размещения ящиков должен быть строго согласован с порядком,в котором занумерованы э.д. Это и будет искомая ж.н.ф.

для матрицы A.6. Составляем характеристическую матрицу G(λ) = Eλ − J и(точно так же, как это делалось на этапе 1) приводим ее к канонической форме Смита, которая должна в точности совпасть с (полученой на первом этапе) матрицей S. Попутно будут вычисленыобратимые матрицы W = W (λ) и Y = Y (λ), такие, что S = W GY.(Для дальнейшего достаточно регистрировать лишь преобразованиянад столбцами и предъявить в итоге матрицу Y.)7. Из соотношения U CV = W GY выражаем матрицу G:G(λ) = P (λ)C(λ)Q(λ),(30.63)§ 30Каноническая форма Смита полиномиальной матрицы 385гдеP = W −1 U ; Q = V Y −1 .(30.64)И снова, для дальнейшего достаточно знать только матрицу Q, иопределить ее можно иначе, минуя формулы (30.64). С этой цельюнадо взять матрицу V и применить к ней элементарные преобразования над столбцами, обратные к тем, что были зарегистрированы наэтапе 6, причем — в обратном порядке (противоположном порядкурегистрации).8.

Полученную на предыдущем этапе полиномиальную матрицуQ = Q(λ) представляем как многочлен с матричными коэффициентами (разлагаем по степеням λ). Затем вычисляем правое значениеэтого матричного многочлена на матрице J:→T = Q( J ).(30.65)Матрица (30.65) будет искомой матрицей перехода.Выполнение соотношения J = T −1 AT подлежит проверке, которую проще осуществлять в форме T J = AT, но — с обязательнымконтролем необращения в нуль det(T ).Пример 30.4. Второй алгоритм приведения квадратной матрицы к ж.н.ф. является заметно более трудоемким по сравнению спервым. В основном это происходит за счет трудоемкости алгоритма Смита. Скажем, даже простейшие "гауссовы" действия приполучении нулевого окаймления требуют значительно больше усилий, поскольку должны производиться над многочленами. Крометого, этим преобразованиям должны предшествовать "евклидовы"действия: деление с остатком многочленов исходного окаймления наугловой многочлен.

Вручную вряд ли стоит браться за матрицы порядка выше пятого. Однако, если разрешено выполнение упомянутых рутинных операций с помощью компьютерных алгебраическихсистем, то можно преуспеть в решении достаточно содержательныхпримеров.Исследуем вопрос о приводимости к ж.н.ф. (6 × 6)-матрицы4 5 3A= −5−1050−10000−1−1212−1000000−1 00 −100−2−2 −3 .2 4−3386Спектральная теория линейных эндоморфизмов1. Составляем характеристическую матрицу:C0 = C = Eλ − A = λ−401002−5λ+11002−30λ−200350−1λ+10−2100−20λ+1−4−50100λ+3Гл.

3и вводим "затравочные" (единичные) матрицы: U0 = V0 = E6 .1.1. Начинаем преобразования алгоритма 30.1. Матрица C0 имеет степень 1 по λ. В северо-западный угол следует переставитьмногочлен нулевой степени, будет лучше — если единичный. Выберем с этой целью третий элемент первой строки, сделаем его угловым, а затем получим нулевое окаймление в первой строке и первомстолбце. (С единицей в углу это делать совсем просто: например,новый третий элемент обнуляется элементарным преобразованием3стб + 1стб · (−λ + 4).)Каждое действие над строками (столбцами) матрицы C0 дублируется точно таким же действием над строками матрицы U0 (столбцами матрицы V0 ). Так осуществляется первый "большой" шаг. Насамом деле, конечно, производится столько элементарных ("малых")шагов, сколько нужно для перемещения выбранного элемента в уголи последующего обнуления тех из окаймляющих элементов, которыебыли ненулевыми.

В итоге получаем матрицы:10000λ+10000−λ +6λ−11000λ+1λ+10002λ+20λ+100−λ−10000C1 = 01200000100000100001020001−10000 −1 −λ+2U1 =  10−2λ+7 ;000λ+100100001 ; V1 = 0011000−λ+40000100000011000000−2 .0 001Все элементы юго-восточного (5 × 5)-блока, дополнительного кугловому элементу, должны делиться на этот элемент.§ 30Каноническая форма Смита полиномиальной матрицы 387В данном случае это выполнено автоматически, поскольку угловой элемент равен единице.

Так что, первый "большой" шаг можносчитать завершенным. (Первый инвариантный многочлен "отщеплен" и оказался единичным.)1.2. Переходя ко второму диагональному элементу, мы можемпреждевременно обрадоваться: второе окаймление уже готово! Увы,это не так. Не все элементы юго-восточного (4 × 4)-блока, дополнительного к северо-западному диагональному (2 × 2)-блоку, делятсябез остатка на λ + 1: ненулевые элементы в третьей строке дают приделении на λ + 1 остатки −18 и 9.Далее понадобятся не только остатки, но и неполные частные.Поэтому должны быть выписаны все формулы типа:−λ2 + 6λ − 11 = (λ + 1)(−λ + 7) − 18.Из остатков следует выбрать минимальный по степени и прибавить соответствующую строку к рассматриваемой в текущий момент(в данном случае — ко второй).

У нас оба ненулевых остатка в третьей строке имеют нулевую степень.Портим окаймление: 2стр + 3стр , после чего снова попытаемся еговосстановить [уже с другим угловым элементом в позиции (2, 2)].При этом, помимо "гауссовых", уже потребуются "евклидовы" действия.

А именно, появившиеся в третьем и шестом столбцах второйстроки многочлены −λ2 + 6λ − 11 и −2λ + 7 необходимо заменить наостатки при их делении на λ + 1.Делается это по Гауссу, с использованием ранее найденных неполных частных.Например: 3стб + 2стб · (λ − 7), второй столбец перед прибавлением к третьему домножается на многочлен, противоположный ксоответствующему неполному частному.Не забудем про дублирование преобразований на следящих матрицах U и V .

Перед повторным обнулением второго окаймлениябудем иметь:1000−18000−λ +6λ−11000λ+1λ+10002λ+20λ+100−λ−10000C2 = 00λ+120−2λ+7 ;090λ+1388Спектральная теория линейных эндоморфизмов100000110000100001020001−10000 −λ+1 −λ+2U2 =  100100001 ; V2 = 001λ−6000−λ+4000010000001100000Гл. 30−2 .0 201После перестановки девятки в угловую позицию, умножения второй строки на 1/9 (с целью нормализации) и последующего обнуления второго окаймления получатся матрицы:1000C3 = 01000000002−λ +2λ+3000λ+1λ+1002λ+20λ+1λ+101−5λ−7)/9 ;002000(2λ020(−λ −2λ−1)/9000001/91/9000(2λ−7)/9(2λ+2)/900001020001(λ −10)/9(−λ−1)/9(−λ−1)/900 (−λ+1)/9 (−2λ2 +11)/9U3 = 1200100001V3 = 02λ−200−2−λ00(2λ+2)/90010000001001200(−λ−1)/9;0001(−2λ+7)/9 .Только после этого мы можем констатировать, что второй "большой" шаг завершен; второй и.м.

также оказался единичным [юговосточный (4 × 4)-блок матрицы C3 делится на единицу автоматически].1.3. Выбираем в этом блоке многочлен наименьшей степени λ + 1[например, в позиции (4,3)] и перемещаем его в позицию (3,3), после чего проводим по Гауссу — Евклиду замену элементов третьегоокаймления на остатки. Здесь нам повезет больше: все эти остатки§ 30Каноническая форма Смита полиномиальной матрицы 389окажутся нулевыми, т. е. третье окаймление сразу обнулится. Более того, все элементы юго-восточного (3 × 3)-блока будут делитьсябез остатка на третий диагональный элемент λ + 1, который, такимобразом, окажется третьим и.м.

Результаты вычислений на третьемшаге:1000000C4 = 010000λ+10000λ2 −2λ−3000−2λ−2λ+10000−λ−11000;2(2λ −5λ−7)/9 002(−λ −2λ−1)/9000001/91/900000100(2λ−7)/9(2λ+2)/9λ−30000−21(λ2 −19)/9(−λ−1)/9(−λ−1)/9−10(−λ+1)/91U4 = 2 (−2λ +9λ−16)/9;001001−10001V4 = 02λ−2−λ+20−2−λλ0(2λ+2)/900100000010012−20(−λ−1)/9(−2λ+7)/9 .1.4. Наше "везение" продолжается: обнаружив в очередном юговосточном блоке, в позиции (5,5), многочлен λ + 1, мы перемещаемего в позицию (4,4) и можем быть уверенными, в том, что сразу жеобнулится четвертое окаймление и что в следующем юго-восточномблоке (размера 3 × 3) все многочлены будут делиться без остаткана λ + 1. Результаты счета:10000000C5 = 0100000λ+100000λ+10000λ −2λ−3(2λ −5λ−7)/90000−λ−1(−λ2 −2λ−1)/90202;390Спектральная теория линейных эндоморфизмовU5 = Гл.

Характеристики

Список файлов книги